LZHUFアルゴリズム - かそくそうち

LHAがLZSSとハフマン符号化を使っていることは有名ですが、自分は今までこの２つをどう繋ぐのか知りませんでした。
ようやく理解できたのでまとめておきます。

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	余りビット

あとはコーディングするだけです。