DEFLATE
RFC 1951 DEFLATE Compressed Data Format Specification version 1.3
doi:10.17487/rfc1951
urn:ietf:rfc:1951
https://www.asahi-net.or.jp/~wr9k-oohs/Pages/Nigel's/Nigel58/deflate.html
LZ77とハフマン符号を組み合わせた圧縮アルゴリズムのひとつ
圧縮アルゴリズムとしては特許を回避したものだが特許も切れているので他の方法も有効かもしれない
利用例
RFC 1950 zlib
RFC 1952 gzip
PNG
RFC 1951 適当訳
DEFLATE 圧縮データフォーマット仕様 バージョン 1.3
本メモのステータス
本メモはインターネットコミュニティ向けの情報を提供します。本メモは、いかなる種類のインターネット標準も規定するものではありません。本メモの配布は無制限です。
IESG 注記：
IESG は、本文書に含まれる知的財産権に関する記述の有効性について、いかなる立場も表明しません。
通知
著作権 (c) 1996 L. Peter Deutsch
本文書は、著作権表示および本表示が保持され、原本からの重要な変更または削除が明確に示されている限り、いかなる目的においても無償で複製および配布することができます。これには、他言語への翻訳および編集物への組み込みも含まれます。
本文書および関連文書の最新版（HTML形式）は、URL <ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html> で参照できます。
概要
本仕様は、LZ77アルゴリズムとハフマン符号化を組み合わせてデータを圧縮するロスレス圧縮データ形式を定義します。この圧縮効率は、現在利用可能な最高の汎用圧縮方式に匹敵します。このデータは、任意の長さの順次入力データストリームであっても、事前に制限された量の中間記憶のみを使用して生成または利用できます。このフォーマットは、特許で保護されない方法で容易に実装できます。
1. はじめに
1.1. 目的
本仕様の目的は、以下の要件を満たすロスレス圧縮データ形式を定義することです。
CPUの種類、オペレーティングシステム、ファイルシステム、および文字セットに依存しないため、データ交換に使用できます。
任意の長さの連続入力データストリームであっても、事前に制限された量の中間ストレージのみを使用して生成または使用できます。したがって、データ通信やUnixフィルタなどの類似の構造で使用できます。
現在利用可能な最高の汎用圧縮方式に匹敵する効率でデータを圧縮します。特に、「compress」プログラムよりも大幅に優れています。
特許で保護されない方法で容易に実装できるため、自由に実施できます。
現在広く使用されているgzipユーティリティによって生成されるファイル形式と互換性があり、準拠した解凍プログラムは既存のgzip圧縮プログラムによって生成されたデータを読み取ることができます。
この仕様で定義されるデータ形式は、以下のことを目的としていません。
圧縮データへのランダムアクセスを許可すること。
特殊なデータ（例：ラスターグラフィック）を、現在利用可能な最良の特殊アルゴリズムと同様に圧縮すること。
単純な数え上げの議論から、ロスレス圧縮アルゴリズムではあらゆる入力データセットを圧縮できないことがわかります。ここで定義される形式では、最悪のケースで32KBブロックあたり5バイトの拡張となり、大規模なデータセットではサイズが0.015%増加します。
英語のテキストは通常​​2.5～3倍に圧縮されます。実行ファイルは通常、圧縮率はやや低くなりますが、ラスターイメージなどのグラフィックデータははるかに高い圧縮率になる可能性があります。
1.2. 対象読者
本仕様は、データを「deflate」形式に圧縮したり、「deflate」形式からデータを解凍したりするソフトウェアの実装者を対象としています。
本仕様は、ビットレベルおよびその他の基本的なデータ表現におけるプログラミングの基本的な知識を前提としています。ハフマン符号化の技術に関する知識があれば役立ちますが、必須ではありません。
1.3. 適用範囲
本仕様は、バイト列を（通常はより短い）ビット列として表現する方法と、後者のビット列をバイトにパックする方法を規定します。
1.4. 準拠性
以下で特に明記しない限り、準拠する解凍器(decompressor)は、ここで提示されるすべての仕様に準拠するデータセットを受け入れ、解凍できなければなりません。また、準拠する圧縮器(compressor)は、ここで提示されるすべての仕様に準拠するデータセットを生成しなければなりません。
1.5. 用語の定義と表記規則
バイト: 8ビットを1単位として保存または転送する単位（オクテットと同じ）。
本仕様では、1バイトは8ビットとします。これは、文字を8ビット以外のビット数で保存するマシンでも同様です。バイト内のビットの番号付けについては、後述します。
文字列: 任意のバイトのシーケンス。
1.6. 以前のバージョンからの変更点
本仕様のバージョン1.1以降、deflate形式には技術的な変更はありません。バージョン1.2では、一部の用語が変更されました。バージョン1.3では、仕様をRFCスタイルに変換しています。
2. 圧縮表現の概要
圧縮データセットは、入力データの連続ブロックに対応する一連のブロックで構成されます。ブロックサイズは任意ですが、圧縮不可ブロックは65,535バイトに制限されます。
各ブロックは、LZ77アルゴリズムとハフマン符号化の組み合わせを使用して圧縮されます。各ブロックのハフマン木は、前後のブロックのハフマン木とは独立しています。LZ77アルゴリズムは、最大32Kバイト前の入力ブロックに出現する重複文字列への参照を使用できます。
各ブロックは、圧縮データ部分の表現を記述するハフマン符号木のペアと、圧縮データ部分の2つの部分で構成されます。（ハフマン木自体はハフマン符号化を使用して圧縮されます。）圧縮データは、2種類の要素の連続で構成されます。1つはリテラルバイト（前の32Kバイトの入力バイト内で重複が検出されなかった文字列）で、もう1つは重複文字列へのポインタです。ポインタは<長さ、後方距離>のペアで表されます。 「deflate」形式で使用される表現では、距離は32Kバイト、長さは258バイトに制限されますが、ブロックのサイズには制限がありません。ただし、圧縮できないブロックは上記のように制限されます。
圧縮データ内の各値（リテラル、距離、長さ）はハフマン符号で表現され、リテラルと長さには1つのコードツリー、距離には別のコードツリーが使用されます。
各ブロックのコードツリーは、そのブロックの圧縮データの直前にコンパクトな形式で表示されます。
3. 詳細仕様
3.1. 全体的な表記規則 以下の図では、次のようなボックスは1バイトを表します。
+---+
| | <-- 縦線が抜けている可能性があります。
+---+
は1バイトを表します。また、次のようなボックスは可変長バイトを表します。
+================+
| |
+================+
は可変長バイトを表します。
コンピュータに格納されるバイトには「ビット順序」はありません。これは、バイトが常に1つの単位として扱われるためです。ただし、0から255までの整数として扱われるバイトには最上位ビットと最下位ビットがあり、数値は最上位桁を左側に記述するため、バイトも最上位ビットを左側に記述します。以下の図では、バイトのビットをビット 0 が最下位ビットとなるように番号付けしています。つまり、ビットは次のように番号付けされています。
+--------+
|76543210|
+--------+
コンピュータ内では、数値が複数のバイトを占める場合があります。ここで説明する形式のマルチバイト数値はすべて、最下位バイトから（メモリの下位アドレスに）格納されます。
例えば、10進数 520 は次のように格納されます。
0 1
+--------+--------+
|00001000|00000010|
+--------+--------+
^ ^
| |
| + 上位バイト = 2 x 256
+ 下位バイト = 8
3.1.1.バイトへのパッキング
本文書では、ビットシーケンシャルメディア上でバイトのビットが伝送される順序については扱いません。これは、ここで説明する最終的なデータ形式がビット指向ではなくバイト指向であるためです。ただし、以下で説明する圧縮ブロック形式は、バイトのシーケンスではなく、様々なビット長のデータ要素のシーケンスとして記述します。したがって、これらのデータ要素をバイトにパッキングして最終的な圧縮バイトシーケンスを形成する方法を指定する必要があります。
データ要素は、バイト内のビット番号の昇順、つまりバイトの最下位ビットから順にバイトにパッキングされます。
ハフマンコード以外のデータ要素は、データ要素の最下位ビットからパッキングされます。
ハフマンコードは、コードの最上位ビットからパッキングされます。
言い換えれば、圧縮されたデータを、最初のバイトを 右 マージンから始めて 左 へ進み、各バイトの最上位ビットを通常どおり左側にして、結果を右から左へ解析することができ、固定幅の要素は正しい MSB から LSB の順序で、ハフマン コードはビット反転順序 (つまり、コードの最初のビットが相対的な LSB 位置にある) になります。
3.2. 圧縮ブロック形式
3.2.1. プレフィックス符号化とハフマン符号化の概要
プレフィックス符号化は、事前に既知のアルファベットの記号を、各記号につき1つのコードを持つビット列（コード）で表します。この方法では、異なる記号は異なる長さのビット列で表されますが、パーサーは常にエンコードされた文字列を記号ごとに明確に解析できます。
プレフィックスコードは、各非葉ノードから伸びる2つの辺に0と1のラベルが付けられ、葉ノードはアルファベットの記号と1対1で対応します（ラベルが付けられます）。この場合、記号のコードは、根からその記号でラベル付けされた葉に至る辺上の0と1のシーケンスとなります。例えば：
code:example
/\ Symbol Code
0 1 ------ ----
/ \ A 00
/\ B B 1
0 1 C 011
/ \ D 010
A /\
0 1
/ \
D C
パーサーは、ルートからツリーを辿り、各ステップで次の入力ビットに対応するエッジを選択することで、エンコードされた入力ストリームから次のシンボルをデコードできます。
シンボル頻度が既知のアルファベットが与えられた場合、ハフマンアルゴリズムは最適なプレフィックスコード（そのアルファベットの可能なプレフィックスコードの中で最小のビット数で、それらのシンボル頻度を持つ文字列を表すコード）を構築できます。このようなコードはハフマンコードと呼ばれます。（ハフマンコードに関する詳細は、第5章の参考文献 1 を参照してください。）
「deflate」形式では、様々なアルファベットのハフマンコードは、特定の最大コード長を超えてはならないことに注意してください。
この制約により、シンボル頻度からコード長を計算するアルゴリズムが複雑になります。詳細については、第 5 章の参考文献を参照してください。
3.2.2. 「deflate」形式でのハフマン符号化の使用
「deflate」形式で各アルファベットに使用されるハフマン符号には、さらに2つの規則があります。
特定のビット長のすべてのコードは、それが表す記号と同じ順序で、辞書式に連続した値を持ちます。
短いコードは、辞書式に長いコードより前にあります。
上記の例をこの規則に従って書き換えると、アルファベットの順序がABCDであると仮定すると、以下のように記述できます。
table:規則
記号 コード
A 10
B 0
C 110
D 111
つまり、0は10の前にあり、10は11xの前にあり、110と111は辞書式に連続しています。
この規則に従うと、アルファベットの各記号のコードのビット長を順番に与えるだけで、アルファベットのハフマン符号を定義できます。これで実際のコードを特定できます。この例では、コードはビット長のシーケンス (2, 1, 3, 3) によって完全に定義されます。以下のアルゴリズムは、最上位ビットから最下位ビットへと読み取られる整数としてコードを生成します。コード長は最初に tree[I].Len に格納され、コードは tree[I].Code に生成されます。
1. 各コード長のコードの数を数えます。長さ N (N >= 1) のコードの数を bl_countN とします。
2. 各コード長の最小コードの数値を求めます。
code:length
code = 0;
bl_count0 = 0;
for (bits = 1; bits <= MAX_BITS; bits++) {
code = (code + bl_countbits-1) << 1;
next_codebits = code;
}
3) すべてのコードに数値を割り当てます。ステップ2で決定した基数と同じ長さのコードすべてに連続した値を使用します。使用されないコード（ビット長が0）には値を割り当ててはなりません。
code:num
for (n = 0; n <= max_code; n++) {
len = treen.Len;
if (len != 0) {
treen.Code = next_codelen;
next_codelen++;
}
}
例:
ビット長が(3, 3, 3, 3, 3, 3, 2, 4, 4)であるアルファベットABCDEFGHを考えてみましょう。ステップ1の後、以下のようになります。
table:N
N bl_count[N]
- -----------
2 1
3 5
4 2
ステップ 2 では、次の next_code 値が計算されます。
table:N
N next_code[N]
- ------------
1 0
2 0
3 2
4 14
ステップ 3 では次のコード値が生成されます。
table:Code
Symbol Length Code
------ ------ ----
A 3 010
B 3 011
C 3 100
D 3 101
E 3 110
F 2 00
G 4 1110
H 4 1111
3.2.3. ブロック形式の詳細
圧縮データの各ブロックは、以下のデータを含む3ビットのヘッダーで始まります。
最初のビット BFINAL
次の2ビット BTYPE
ブロックは必ずしも整数バイト数を占めるとは限らないため、ヘッダービットは必ずしもバイト境界から始まるとは限りません。
BFINALは、これがデータセットの最後のブロックである場合にのみ設定されます。
BTYPEは、データの圧縮方法を以下のように指定します。
00 - 圧縮なし
01 - 固定ハフマンコードで圧縮
10 - 動的ハフマンコードで圧縮
11 - 予約済み（エラー）
2つの圧縮ケースの唯一の違いは、リテラル/長さと距離を表すアルファベットのハフマンコードの定義方法です。
いずれの場合も、実際のデータのデコードアルゴリズムは以下のとおりです。
code:decode
do
read block header from input stream. 入力ストリームからブロックヘッダーを読み取ります。
if stored with no compression 圧縮なしで格納されている場合
skip any remaining bits in current partially 現在部分的に処理されたバイトの残りのビットをスキップします
processed byte
read LEN and NLEN (see next section) LENとNLENを読み取ります（次のセクションを参照）
copy LEN bytes of data to output LENバイトのデータを出力にコピーします
otherwise それ以外の場合
if compressed with dynamic Huffman codes 動的ハフマン符号で圧縮されている場合
read representation of code trees (see コードツリーの表現を読み取ります（以下のサブセクションを参照）
subsection below)
loop (until end of block code recognized) ループします（ブロックコードの終わりが認識されるまで）
decode literal/length value from input stream 入力ストリームからリテラル/長さの値をデコードします
if value < 256 値 < 256の場合
copy value (literal byte) to output stream 値（リテラルバイト）を出力ストリームにコピーします
otherwise それ以外の場合
if value = end of block (256) 値がブロックの末尾（256）の場合
break from loop ループを終了します
otherwise (value = 257..285) それ以外の場合（値 = 257..285）
decode distance from input stream 入力ストリームから距離をデコードします
move backwards distance bytes in the output 出力ストリーム内で距離バイト後方に移動し、
stream, and copy length bytes from this この位置から長さバイトを出力ストリームにコピーします
position to the output stream.
end loop ループを終了します
while not last block 最後のブロックではない場合
重複した文字列参照は、前のブロック内の文字列を参照する可能性があることに注意してください。つまり、後方への距離は1つ以上のブロック境界を越える可能性があります。ただし、距離は出力ストリームの先頭を超えて参照することはできません。（プリセット辞書を使用するアプリケーションは出力ストリームの一部を破棄する可能性がありますが、距離は出力ストリームのその部分を参照できます。）また、参照先の文字列が現在の位置と重複する可能性があることにも注意してください。例えば、デコードされた最後の2バイトの値がXとYの場合、<長さ = 5、距離 = 2>の文字列参照は、X、Y、X、Y、Xを出力ストリームに追加します。
次に、各圧縮方式を順番に指定します。
3.2.4. 非圧縮ブロック (BTYPE=00)
次のバイト境界までの入力ビットは無視されます。
ブロックの残りの部分は以下の情報で構成されます。
code:block
0 1 2 3 4...
+---+---+---+---+==============================+
| LEN | NLEN |... LENバイトのリテラルデータ...|
+---+---+---+---+==============================+
LENはブロック内のデータバイト数です。NLENはLENの1の補数です。
3.2.5.圧縮ブロック（長さと距離のコード）
前述の通り、「deflate」形式でエンコードされたデータブロックは、概念的に異なる3つのアルファベットから抽出されたシンボルのシーケンスで構成されます。これらのアルファベットは、バイト値のアルファベット（0..255）から抽出されたリテラルバイト、または長さ（3..258）、距離（1..32,768）から抽出された<長さ、後方距離>のペアのいずれかです。実際には、リテラルと長さのアルファベットは1つのアルファベット（0..285）に統合されており、値0..255はリテラルバイト、値256はブロックの終端、値257..285は長さコード（シンボルコードの後に​​続く追加ビットと組み合わせられる場合もあります）を表します。
code:extra
Extra Extra Extra
Code Bits Length(s) Code Bits Lengths Code Bits Length(s)
---- ---- ------ ---- ---- ------- ---- ---- -------
257 0 3 267 1 15,16 277 4 67-82
258 0 4 268 1 17,18 278 4 83-98
259 0 5 269 2 19-22 279 4 99-114
260 0 6 270 2 23-26 280 4 115-130
261 0 7 271 2 27-30 281 5 131-162
262 0 8 272 2 31-34 282 5 163-194
263 0 9 273 3 35-42 283 5 195-226
264 0 10 274 3 43-50 284 5 227-257
265 1 11,12 275 3 51-58 285 0 258
266 1 13,14 276 3 59-66
追加ビットは、最上位ビットを先頭に格納されたマシン整数として解釈する必要があります。たとえば、ビット1110は値14を表します。
code:extra
Extra Extra Extra
Code Bits Dist Code Bits Dist Code Bits Distance
---- ---- ---- ---- ---- ------ ---- ---- --------
0 0 1 10 4 33-48 20 9 1025-1536
1 0 2 11 4 49-64 21 9 1537-2048
2 0 3 12 5 65-96 22 10 2049-3072
3 0 4 13 5 97-128 23 10 3073-4096
4 1 5,6 14 6 129-192 24 11 4097-6144
5 1 7,8 15 6 193-256 25 11 6145-8192
6 2 9-12 16 7 257-384 26 12 8193-12288
7 2 13-16 17 7 385-512 27 12 12289-16384
8 3 17-24 18 8 513-768 28 13 16385-24576
9 3 25-32 19 8 769-1024 29 13 24577-32768
3.2.6. 固定ハフマンコードによる圧縮 (BTYPE=01)
2つのアルファベットのハフマンコードは固定であり、データ内には明示的に表現されません。リテラル/長さアルファベットのハフマンコード長は以下のとおりです。
code:literal
リテラル値 ビット コード
--------- ---- -----
0 - 143 8 00110000 ～
10111111
144 - 255 9 110010000 ～
111111111
256 - 279 7 0000000 ～
0010111
280 - 287 8 11000000 ～
11000111
上記のように、これらのコード長は実際のコードを生成するのに十分な長さです。分かりやすさを増すために、表にコードを示します。リテラル値/長さ値286～287は、圧縮データには実際には出現しませんが、コード構築には使用されます。
距離コード0～31は（固定長）5ビットコードで表され、上記のパラグラフ3.2.5の表に示されているように、追加ビットが含まれる場合があります。距離コード30～31は、圧縮データには実際には出現しないことに注意してください。
3.2.7. 動的ハフマン符号による圧縮 (BTYPE=10)
2つのアルファベットに対応するハフマン符号は、ブロック内のヘッダービットの直後、実際の圧縮データの前に配置されます。最初にリテラル/長さコード、次に距離コードが続きます。各コードは、前述の3.2.2項で説明したように、コード長のシーケンスによって定義されます。さらに圧縮率を高めるために、コード長シーケンス自体もハフマン符号を用いて圧縮されます。コード長に対応するアルファベットは次のとおりです。
code:length
0 - 15: 0 - 15のコード長を表します。
16: 前のコード長を3 - 6回コピーします。
次の2ビットは繰り返しの長さを示します。
(0 = 3、…、3 = 6)
例：コード8、16（+2ビット 11）、
16（+2ビット 10）は、
12ビットのコード長 8 ( 1 + 6 + 5）に拡張されます。
17：コード長0を3～10回繰り返します。
(長さ3ビット)
18：コード長0を11～138回繰り返します。
(長さ7ビット)
コード長0は、リテラル/長さまたは距離アルファベット内の対応するシンボルがブロック内に出現せず、前述のハフマン符号構築アルゴリズムに使用されないことを示します。距離コードが1つだけ使用される場合、それは0ビットではなく1ビットを使用してエンコードされます。この場合、コード長1のコードが1つ存在し、未使用のコードが1つあります。ゼロビットの距離コードが1つある場合、距離コードがまったく使用されていないことを意味します（データはすべてリテラルです）。
ブロックのフォーマットを定義できます。
5ビット: HLIT、リテラル/長さコードの数 - 257 (257 - 286)
5ビット: HDIST、距離コードの数 - 1 (1 - 32)
4ビット: HCLEN、コード長コードの数 - 4 (4 - 19)
(HCLEN + 4) × 3ビット: 上記のコード長アルファベットのコード長。順序は、16、17、18、0、8、7、9、6、10、5、11、4、12、3、13、2、14、1、15です。
これらのコード長は3ビットの整数(0 - 7)として解釈されます。前述のように、コード長が0の場合、対応するシンボル(リテラル/長さまたは距離コード長)は使用されません。
リテラル/長さアルファベットのHLIT + 257のコード長。
コード長ハフマンコードを使用してエンコードされます。
距離アルファベットのHDIST + 1のコード長。
コード長ハフマンコードを使用してエンコードされます。
ブロックの実際の圧縮データ。
リテラル/長さハフマンコードと距離ハフマンコードを使用してエンコードされます。
リテラル/長さシンボル256（データ終了）は、
リテラル/長さハフマンコードを使用してエンコードされます。
コード長繰り返しコードは、HLIT + 257からHDIST + 1のコード長までの範囲で使用できます。つまり、すべてのコード長は、HLIT + HDIST + 258の値の単一のシーケンスを形成します。
3.3. 準拠
圧縮器は、前のセクションで規定された値の範囲をさらに制限しても準拠を維持することができます。例えば、後方ポインタの範囲を32K未満の値に制限することができます。同様に、圧縮器は、圧縮可能なブロックがメモリに収まるようにブロックのサイズを制限することができます。
準拠する解凍器は、前のセクションで定義された可能な値の範囲全体を受け入れなければならず、また、任意のサイズのブロックを受け入れなければなりません。
4. 圧縮アルゴリズムの詳細
本文書は、特定の圧縮アルゴリズムに言及することなく「deflate」圧縮データ形式を定義することを目的としていますが、この形式はLZ77 (Lempel-Ziv 1977、下記参考文献2参照) によって生成される圧縮形式と関連しています。
LZ77には多くのバリエーションがあり特許取得済みであるため、圧縮器の実装者は、ここで示す一般的なアルゴリズムに従うことを強く推奨します。このアルゴリズム自体は特許取得済みではないことが分かっています。
本セクションの内容は、仕様の定義そのものの一部ではなく、圧縮器が準拠するためにこのアルゴリズムに従う必要はありません。
圧縮器は、新しいブロックを新しいツリーで開始することが有益であると判断した場合、またはブロックサイズが圧縮器のブロックバッファをいっぱいにした場合、ブロックを終了します。
圧縮器は、3バイトシーケンスを処理するハッシュ関数を用いて、連鎖ハッシュテーブルを使用して重複文字列を検索します。圧縮中の任意の時点で、XYZ を次に検査する入力 3 バイトとします（もちろん、すべてが異なる必要はありません）。まず、圧縮プログラムはハッシュチェーンで XYZ を調べます。チェーンが空の場合、圧縮プログラムは X をリテラルバイトとして書き出し、入力を 1 バイト進めます。ハッシュチェーンが空でない場合、つまりシーケンス XYZ（または、運が悪ければ、同じハッシュ関数値を持つ他の 3 バイト）が最近発生したことを示している場合、圧縮プログラムは XYZ ハッシュチェーン上のすべての文字列を、現在の時点から始まる実際の入力データシーケンスと比較し、最も長い一致を選択します。
圧縮プログラムは、ハッシュチェーンを最新の文字列から検索します。これは、距離が短いことを優先し、ハフマン符号化の利点を活かすためです。ハッシュチェーンは単独でリンクされています。ハッシュチェーンからの削除は行われず、アルゴリズムは古すぎる一致を単に破棄します。最悪の事態を回避するため、非常に長いハッシュチェーンは、実行時パラメータによって決定される特定の長さで任意に切り詰められます。
全体的な圧縮率を向上させるため、圧縮機は一致の選択を任意に延期します（「遅延マッチング」）。長さNの一致が見つかった後、圧縮機は次の入力バイトからより長い一致を検索します。より長い一致が見つかった場合、前の一致を長さ1に切り詰め（単一のリテラルバイトを生成）、より長い一致を出力します。そうでない場合は、元の一致を出力し、前述のようにNバイト進めてから処理を続行します。
実行時パラメータは、この「遅延マッチング」の手順も制御します。圧縮率が最も重要な場合、圧縮機は最初の一致の長さに関係なく、完全な2回目の検索を試みます。
通常の場合、現在の一致が「十分に長い」場合、圧縮機はより長い一致の検索を短縮し、処理を高速化します。速度を最優先する場合、圧縮プログラムは一致する文字列が見つからなかったとき、または一致する文字列が「長すぎる」と判断されない場合にのみ、ハッシュテーブルに新しい文字列を挿入します。これにより圧縮率は低下しますが、挿入回数と検索回数が減るため、処理時間は短縮されます。