動的ハフマン符号を同期させた動的辞書法による1パスデータ圧縮

Abstract

This paper proposes a new data compression algorithm. In the dynamic dictionary method, when building the dictionary from an original file, a large number of single characters appear. Each character is usually put into a file with fixed-length bits. The performance of compression ratio can be improved by using the dynamic Huffman codes which is assigned to a part of this output procedure. The features of our algorithm are that it is a one-pass data compression and that it is reversible coding. It is necessary that both dictionary tree and dynamic Huffman tree must be synchronously updated, when encoding a sequential of characters from input file to output one. The algorithm utilizes LRU (Least Recently Used) queue for deleting a dictionary item when the dictionary is full.