講演抄録/キーワード |
講演名 |
2010-07-22 10:15
期待符号語長を最小にするSuffix tree上の最適文脈に基づくデータ圧縮法 ○友國恵太・山本博資(東大) IT2010-12 |
抄録 |
(和) |
本稿では,suffix treeと算術符号を用いてバイト単位で符号化するデータ圧縮法を取り扱う.suffix treeを用いたPPM*や動的な反辞書法と同様に,符号化が終了した系列から作成されたsuffix treeを用いて,次の文字を算術符号化する.符号化に用いる文脈の決定に閾値を用いる方法と,符号語長の期待値が最小となる文脈を選択する方法の2つの符号化法を提案する.Calgary Corpusに対する圧縮性能を比較することにより,提案符号化法が大きいファイルサイズの文書データについてPPM*を上回る圧縮性能を達成できることを示す. |
(英) |
In this paper, we consider a data compression method, which encodes each byte of data by using
a suffix tree. In the same way as PPM* and a dynamic anti-dictionary method based on a suffix tree, each byte is encoded by an arithmetic code using a suffix tree, which is constructed dynamically from the past data that has already been encoded. Two methods, threshold method and minimum-expected-codeword-length method, are proposed to select a context (or a suffix node) for encoding in a suffix tree.The performance of the proposed methods are compared with other methods for the Calgary Corpus, and it is shown that the minimum-expected-codeword-length method can achieve better compression rate than PPM* in the case of text files with large size. |
キーワード |
(和) |
suffix tree / 算術符号 / データ圧縮 / PPM / / / / |
(英) |
suffix tree / arithmetic coding / data compression / PPM / / / / |
文献情報 |
信学技報, vol. 110, no. 137, IT2010-12, pp. 7-12, 2010年7月. |
資料番号 |
IT2010-12 |
発行日 |
2010-07-15 (IT) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2010-12 |