講演抄録/キーワード |
講演名 |
2006-07-27 15:00
多値アルファベットに対する反辞書を用いたデータ圧縮 ○太田隆博(長野県工科短大)・森田啓義(電通大) |
抄録 |
(和) |
反辞書とは,入力系列に現れない系列の集合であり,これを2値系列に対して用いた無歪みデータ圧縮手法がCrochemoreらにより,Data Compression using Antidictionaries(DCA)法として提案されている.しかし,DCA法が扱える系列は,アルファベットが2値の場合に限られており,多値アルファベット上の一般的な系列を直接扱えない問題点がある.ここでは,反辞書を多値アルファベットに拡張し,多値アルファベット上の系列を直接に扱える符号化・復号化手法および線形計算量での反辞書構築手法を提案する.また,反辞書構築の提案手法について計算機実験を行い,線形計算量で十分高速に動作することが確認できた. |
(英) |
An antidictionary is a set of words of minimal length that never appear in this string. And it is known that the antidictionary is useful for source coding. The original coding scheme given by Crochemore et al. aimed to compress strings over only binary alphabets. However, it can not compress directly strings over any finite alphatbet.
In this paper, we are concerned with an extension of antidicitonary coding to any strings over a finite alphabet. A construction of an antidictionary for finite alphabets with linear complexity is proposed and its effectiveness is demonstrated by simulation results. |
キーワード |
(和) |
反辞書 / 有限アルファベット / 無ひずみ圧縮 / 接尾辞木 / 反辞書木 / 情報源符号化 / / |
(英) |
Antidictionary / Finite alphabets / Lossless coding / Suffix tree / Antidictionary tree / Source coding / / |
文献情報 |
信学技報, vol. 106, no. 184, IT2006-31, pp. 37-42, 2006年7月. |
資料番号 |
IT2006-31 |
発行日 |
2006-07-20 (IT) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|