可逆LZW
LZWの辞書成長を手動操作。展開で原文に戻せるか
LZW は LZ78 から派生し、初期辞書に全アルファベットを入れることで「次の文字」を毎回出力する必要がない。
各ステップでは「最長一致を出力」→「(最長一致 + 次の1文字) を辞書に追加」を繰り返す。
可逆 LZW は復号側が同じ辞書成長ルールに従うことで完全に原文を再構築できる。横山研
rev_lz/rev_lzw を直感的教材化。
Stage
1/4
Pos
0
Dict
0
Codes
0
Ratio
—
原文
出力コード列
サイズ比較
辞書 (LZW)
グレー = 初期辞書 (全文字)、黄 = 最新追加。新エントリは「直前出力された文字列 + 次の文字」。
操作
「次のコード」で原文中の最長一致を辞書から探し、そのIDを出力。続けて (一致 + 次の1文字) を辞書に追加。
復号モード: コード列を順に読み、辞書を再構築しながら原文を復元する。完全一致でステージクリア。
目標は 圧縮率 1/3 以下 かつ 完全可逆復元。