LZHUFアルゴリズム
LHAがLZSSとハフマン符号化を使っていることは有名ですが、自分は今までこの2つをどう繋ぐのか知りませんでした。
ようやく理解できたのでまとめておきます。
LZSSの出力は、
- (0、不一致記号)
- (1、一致位置、一致長)
のいずれかですが、LHAのLZHUFアルゴリズムでは頭の0/1を省くため、不一致記号と一致長(3〜256)を一つの記号にまとめて、0〜255を不一致記号、それ以降(256〜509)を一致長に割り当てています。(以下、単に記号と表記します)
そしてこの記号列に対してハフマン符号化を施します。
また、残った一致位置の情報はこれとは別にハフマン符号化します。
実際にはLZSSの出力を16KBほど貯めて、それに対してハフマン符号化を行います。
出力は次のような形式です。
+------------------------------------+ | LZSS出力の個数 | +------------------------------------+ | 記号用のハフマン表 | +------------------------------------+ | 一致位置用ハフマン表 | +------------------------------------+ |LZSSの出力(をハフマン符号化したもの)| +------------------------------------+
「LZSS出力の個数」と「LZSSの出力」は名前の通りですが、ハフマン表の出力はかなり変わっています。
ハフマン表は、
符号 | 文字 |
---|---|
00 | A |
01 | B |
10 | C |
110 | D |
111 | E |
のように符号と文字の対応表ですが、符号の振り方を決めておけば、符号長から符号は導き出すことができます。(実際にやってみると分かります)
符号長 | 文字 |
---|---|
2 | A |
2 | B |
2 | C |
3 | D |
3 | E |
記号用のハフマン表の場合はこれでも巨大なので、0の出現が多いことを利用して0のランレングス圧縮をした上で、さらにハフマン符号化を行います。
符号長 | 新しい符号 |
0 | 0のハフマン符号 |
0×2 | (0のハフマン符号) (0のハフマン符号) |
0×3〜18 | (1のハフマン符号) (0の繰り返し回数-3、4ビット) |
0×19 | (0のハフマン符号) (1のハフマン符号) 1111 |
0×20〜531 | (2のハフマン符号) (0の繰り返し回数-20、9ビット) |
1〜16 | ((符号長+2)のハフマン符号) |
これを次の形で出力します。
+----------------------------------------------------+ | 記号用のハフマン表の符号長のハフマン表 | +----------------------------------------------------+ | 記号用のハフマン表の符号長の個数 | +----------------------------------------------------+ |記号用のハフマン表の符号長(をハフマン符号化したもの)| +----------------------------------------------------+
さらに「記号用のハフマン表の符号長のハフマン表」や「一致位置用ハフマン表」も圧縮されていますが、省略します。
フォーマットが理解できたので、手作業でデコードしてみました。
元データは
aaaaaaaaaaa
(aを11個)で、LHMeltingで圧縮したデータは16進で
00032004307136484008
となりました。
解析結果は次の通り、
符号 | 意味 |
0000000000000011 | LZSSの出力数=3 |
00100 | 記号用のハフマン表の符号長のハフマン表の符号長の数=4 |
000 | 0 |
000 | 0 |
001 | 1 |
00 | 0の連続=なし |
001 | 1 |
100000111 | 記号用のハフマン表の符号長の数=263 |
0 001001101 | 0×97 |
1 | 1、'a'の符号長は1 |
0 010010000 | 0×164 |
1 | 1、一致長9の符号長は1 |
0000 | 一致位置用ハフマン表の符号長の数=0 |
0000 | 一致位置=0 |
0 | 'a' |
0 | 'a' |
1 | 一致位置=0、一致長=9 |
000 | 余りビット |
あとはコーディングするだけです。