LZ77の一致探索・トークン列

有限のバイト列から最長一致を探索し、トークン列と復元結果を照合する。

offsetは現在位置から参照元までの距離(byte)です。lengthはコピーするbyte数です。同長の一致では近い参照元を選びます。

最終参照で次バイトがない場合だけnextByteを「終端」とします。これは本ページの終端規約であり、gzip等のファイル形式ではありません。

入力すると自動で計算します。Enterで次の項目へ進めます。次の入力欄を選んで進めます。

必要な入力・選択は4項目です。

空欄は空のバイト列として扱います。最大1000バイト。空白文字もデータです。16進形式は2桁単位(連続または空白・カンマ区切り)で入力してください。

現在位置より前の何バイトを検索するか。1~1000の整数。

一度の参照でコピーできる最大バイト数。1~1000の整数。

この長さ未満の一致は1バイトのリテラルトークンにします。


計算結果

必要な値を入力すると自動で計算します。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

現在位置pに対し、offset=1からmin(窓長,p)までを調べます。各候補の一致長を最大一致長と残りバイト数まで比較し、最長を採用します。同長ならoffsetが最小の参照を採用。一致長が最小一致長以上なら(offset,length,nextByte)を出力し、次バイトがあればlength+1、終端ならlengthだけ進みます。未満なら(0,0,現在の1byte)を出力。復元は既出力をoffsetだけ遡って1byteずつlength回追加するため、参照元と書込先の重複にも対応します。最後の参照に限り次バイトを省略して「終端」とします。

参照オフセット・一致長・次バイトの順序付き表、トークン数、復元後バイト列。

計算例(架空の数値)

ASCII「aaaaa」、窓長4・最大一致長4・最小一致長2の場合、(0,0,61)の後に(1,4,終端)が続き、復元は61 61 61 61 61です。61は16進数で文字aを表します。

適用対象と限界

ブラウザ上で直接入力した最大1000バイトのデータ。DEFLATE・gzip等の実ファイル形式、ビット符号化、圧縮率、外部ファイル読込、最適パース、Unicode文字単位の一致探索は行いません。。

方法と出典

方法:本ページのLZ77三つ組規約 v1.0(終端はnextByte=null)。データ記録日:2026-11-14。