複数辞書を用いたデータ圧縮法とその誤り回復  [in Japanese] Data Compression Method by Using Multiple Dictionaries and Its Error Recovery Method  [in Japanese]

現在一般に用いられている圧縮ソフトやアーカイバは,その多くがZiv-Lempel符号等の辞書を利用した圧縮方式を採用している.Ziv-Lempel符号は辞書の保持方法によってLZ77符号とLZ78符号に大別され,それぞれに特有の利点と欠点を有している.また一般に,圧縮されたデータに誤りが発生すると,復号したとき広範囲に誤りが伝播しデータの大部分が失われてしまう.そのため,様々なデータ圧縮法に対して誤り回復手法が提案されている.本稿では,LZ77符号とLZ78符号が持つ欠点を指摘し,両者の辞書を併用することでその欠点を解消する圧縮アルゴリズムを提案する.さらに提案した圧縮手法に対して,誤りの伝播を抑制する誤り回復手法を提案する.計算機シミュレーションの結果,圧縮性能では従来のZiv-Lempel符号と比べ優れた圧縮率を得ること,回復性能では数%の圧縮率悪化で一定の長さ以下のバースト誤りに対して復号データのほとんどが正しく復号できることが分かった.

Most of the generally-used compression software and archiver are based on dictionary-based compression such as Ziv-Lempel coding. Ziv-Lempel coding is classified into LZ77 coding and LZ78 coding according to the type of dictionary, and they have a peculiar advantage and a drawback. Moreover, if the error occurs in the compressed data, it spreads widely to the decompressed data and most of data are lost in general. In this paper, we point out drawbacks of LZ77 coding and LZ78 coding, and propose the compression algorithm that removes the drawbacks by using two types of dictionaries. In addition, we propose error recovery method for the proposed compression method. Computer simulation says that the proposed method achieves good compression ratio in comparison with conventional Ziv-Lempel coding, and that this method can recover most of the data from burst error with less than supposed length by several percent aggravation.