講演抄録/キーワード |
講演名 |
2004-07-28 14:30
参照回数を考慮したLZW法によるデータ圧縮 ○芥子和宏・吉田幸二・石田 崇・平澤茂一(早大) |
抄録 |
(和) |
データ圧縮の分野において,入力列の統計的性質が未知でも入力列が長くなるにつれて漸近的に最良の圧縮が可能な手法として,LZW法が知られている.しかし,LZW法では参照された辞書番号を符号化する際に,必ずしも頻出する記号列に対して短い符号語が割り当てられているとは限らないという問題点がある.そこで本研究では,参照回数の多い順に小さい辞書番号を振ることにより,頻出する記号列に対して短い符号語を割り当てる手法を提案する.また,提案手法の実データへの適用によって,従来の符号化法に比べ小さな圧縮率を達成することを示す.さらに,比較のため,提案手法と同様に辞書の入れ替えを行い,完全に参照回数順に節点番号を割り当てた後にCBT符号による符号化を行う手法を適用した圧縮率も求め,提案手法がよい圧縮を実現できていることを示す. |
(英) |
In the field of data compression, it is known that LZW method achieves the asymptotically optimum compression even when the statistical property of input sequence is unknown. However, the LZW method has a problem, such that frequently occurring strings are not always assigned into short codes. In this paper, we propose a new algorithm that frequently occurring strings are assigned into short codes renumbering them by their occurring order, and show by simulation results that it attains lower compression rate than that of the conventional method. Furthermore, we show how proposed method can achieve higher compression rate than that of the comparative method. |
キーワード |
(和) |
情報源符号化 / LZW法 / 辞書 / 参照回数 / / / / |
(英) |
source coding / LZW method / dictionary / number of references / / / / |
文献情報 |
信学技報, vol. 104, no. 228, IT2004-10, pp. 11-16, 2004年7月. |
資料番号 |
IT2004-10 |
発行日 |
2004-07-21 (IT) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|