2024-03-29T16:14:13Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000700132024-03-29T05:26:34Z01164:01165:06144:06145
VF符号と算術符号の組合せ手法による圧縮性能の向上についてA Combination of VF Coding with Arithmetic Coding for Efficient Compressionjpn大規模データの効率的アクセスhttp://id.nii.ac.jp/1001/00070013/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=70013&item_no=1&attribute_id=1&file_no=1Copyright (c) 2010 by the Information Processing Society of Japan北海道大学大学院情報科学研究科北海道大学大学院情報科学研究科吉田, 諭史喜田, 拓也本稿では,VF 符号に算術符号を組み合わせることで,検索の効率と圧縮率とを保つ方法について議論する.ここで議論する VF 符号とは,分節木と呼ばれる圧縮のための辞書木を用いて元のテキストを可変長のブロックに分割し,各ブロックに固定長の符号語を割り当てることでデータ圧縮を達成する情報源符号化方法である.VF 符号は,近年,パターン照合を高速化することのできるデータ圧縮法として見直されている.VF 符号は,符号語長が固定であるという制限から,分節木が小さいときには圧縮性能が低い.圧縮率を向上させるには分節木を大きくすればよいが,逆にパターン照合時の前処理に時間がかかり全体の検索の速度を低下させてしまう.そこで,VF 符号の出力を,展開が早い他の符号化方法で符号化することで,圧縮率と検索速度の両方を保つ方法が考えられる.本稿では,代表的な VF 符号である Tunstall 符号および VF 符号の中では優れた圧縮性能を持つ STVF 符号に Range Coder を組み合わせた圧縮方法について,その圧縮性能を実験的に評価した.その結果,符号語長が短い場合において,それぞれおよそ 18 ~ 20%,7 ~ 15% の圧縮率改善が見られた.In this paper, we discuss about a method to preserve both search efficiency and compression ratio by combining VF coding with arithmetic coding. A VF code, we discuss here, is a source coding scheme that parses an input text into variable-length blocks with a dictionary tree, called parse tree, and then encodes them by fixed-length codewords. It is reevaluated recently since it can accelerate pattern matching on the text. As the codewords are fixed length, a VF code usually has low compression ratios when its parse tree is small. Although we can obtain higher compression ratios when we make the parse tree large enough, pattern matching speed will decline since we take much more time to preprocess such large tree for compressed pattern matching. One of the natural trade-off solutions is to encode outputs of a VF code with the other compression method whose decompression speed is fast. We would be able to do fast pattern matching on such compressed text by decoding it to a sequence of VF codewords once and then searching on the sequence without decoding the codewords. In this paper, we investigated a combination of Tunstall codes or STVF codes with Range coder. The experimental results show that those combinations can improve the compression ratios about 18 ~ 20% and 7 ~ 15%, respectively, when the codeword length is short.AN10112482研究報告データベースシステム(DBS)2010-DBS-15010182010-07-282010-07-22