可逆LZ78
辞書を成長させて文字列を圧縮、巻き戻しで完全復元
LZ78 は逐次的に辞書を構築する圧縮法。各ステップで「既出の最長一致＋次の一文字」を
(辞書ID, 文字) として出力。
可逆 LZ78 では辞書状態を共有することで、出力トークン列から元の文字列を完全に復元できる。本ゲームでは 圧縮モード で辞書を育て、展開モード でトークンから原文を再生する。
Stage
1/4
Pos
0
Dict
0
Tokens
0
Ratio
—
原文
出力トークン (id, char)
辞書 (LZ78)
辞書 0 は空文字列。各トークン (i,c) は新しい辞書エントリを追加し、その内容は
dict[i] + c となる。操作
「次のトークン」で原文を1つ消費し、辞書から最長一致を見つけて (id, char) を出力。辞書も自動的に拡張される。
展開モード: トークン列を順に読み、辞書を再構築しながら原文を復元する。完全一致でステージクリア。
目標は 圧縮率を下げつつ完全可逆。原文と展開結果が一致しなければ NG。