LZHUF - 通信用語の基礎知識

概要

LHAの開発者である吉崎栄泰により考案されたアルゴリズムで、LZSSにハフマン符号を組み合わせたもの。

これより以前、奥村晴彦によりLZSSに算術圧縮を組み合わせたLZARIが考案されたが、これを見た吉崎栄泰は算術圧縮の部分をハフマン符号に置き換えればより効率的なアルゴリズムになるはずだと考え、LZHUFの開発に至ったと言われる。

利用例は以下の通り。

実際にはLZHUFではないが、概念的に近いもの。

開発当初はハフマン符号に適応型ハフマン符号(動的ハフマン)法を採用していたが、速度が遅かったなどの理由で、後に静的ハフマン符号に変更された。

ソフトウェアLHAは、スライド辞書法で使うスライド窓の大きさや、LZSSのビット長などで様々なものがある。

-lh0- (無圧縮)
-lh1- (窓サイズ4Kiバイト・最大60、適応型ハフマン符号、固定符号位置)
-lh2- (窓サイズ8Kiバイト・最大256、適応型ハフマン符号)
-lh3- (窓サイズ8Kiバイト・最大256、静的ハフマン符号)
-lh4- (窓サイズ4Kiバイト・最大256、静的ハフマン符号、ツリー符号化改善)
-lh5- (窓サイズ8Kiバイト・最大256、静的ハフマン符号、ツリー符号化改善)
-lh6- (窓サイズ32Kiバイト・最大256、静的ハフマン符号、ツリー符号化改善)
-lh7- (窓サイズ64Kiバイト・最大256、静的ハフマン符号)

例えば、LHAで一般的な-lh5-では、ハッシュと二分木を用いた13ビットLZSSである。

その後開発された-lh6-ではハッシュと線形リストを使った15ビットLZSSを初段に用い、後段は共通でハフマン符号を組み合わせている。