はじめに

最近のコミットで最長一致探索部分を書きなおしたらシンプルになったのでメモ替わりに書いておきます。

まず、DEFLATE では chained hash table を使用することが推奨されています。 LZ77 関連では処理の高速化に関していろいろ特許があるようなので、今のところ特許問題のでていないこの方法を使用しています。

chained hash table とは、連続する 3 Byte をハッシュのキーとして辞書を持ち、 ハッシュキーの値に該当位置を記録しておくことで、高速に LZ77 の長さ距離符号の判定を行うことができます。 (なぜ 3 Byte をハッシュキーにするかというと、DEFLATE の長さ距離符号の長さの最小が 3 Byte だからだと思います。)

chained hash table を利用したとしても、わかるのは「最低でも 3 Byteは一致している」ので、 複数の候補があった場合はそこから最長のものを絞り込んでいかなければいけません。

最長一致探索

そこで、複数の「最長一致候補」から最長のものを探索する仕組みが必要になります。 以前はちょっと凝ろうとしたことをして、逆に複雑になった上にロクな出来ではなかったので、 今回以下のようなシンプルな方式に修正しました。

最長候補は常に 1 つだけ

以前は最長候補は探索処理の最後まで持っておき、最後に場合によって切り替えられるようにしていました。 ただ、あまり意味がなかったので今回は常に 1 つだけ持っておくようにしました。 この時、最長マッチ長が同じ候補が複数あった場合にどちらを選択するか決定するルールが必要なので、 「マッチ長が同じだった場合は後方(現在の位置と近い)ものを採用する」というようにしました。

なぜ後方のものを採用するかというと、長さ距離符号にした際に距離符号を短くできることがあるからです。 (extra bits はハフマン符号化の対象にならない。下記に長さによる extra bits の長さを示します。)

長さextra bits 長さextra bits
3 - 100 67-1304
11-181 131-2575
19-342 2580
35-663   

これにより無駄な配列関連の処理がばっさり減らせました。

基本は左から 1 Byte ずつ比較処理

以前はちょっと凝ろうとしたことをして複雑になってました。 すでに修正済みなので簡単にどういったことをやっていたか説明すると、例えば以下のようなマッチ候補があった時に

 "abcdefghijklmnop" ...

以下のように一定の長さに分割します。(実際に分割するわけではなく意味上の区切りですが)

  "abcdefgh" "ijklmnop" ...

そして、下記のように後方から比較していました。

  ".......h"
  "......g."
  ".....f.."
  "....e..."
  .
  .

これは何がしたかったのかというと、 chained hash table によって前 3 Byte の一致がしているのはわかっているので、 そこから絞り込む際 4 Byte 一致してるものというのは比較的多いのではないかと考えました。 ( LZ77 で圧縮可能なデータというのは偏りがあるため)

同様に 5 Byte, 6 Byte ... と見ていくよりも末尾から見ていく方が速く候補を落とせると考え、実際一定の速度向上はしました。

今回の実装では、そのへんをばっさりとやめ「基本は」左から1文字ずつ見ていくようにしました。 ただ、全ての候補を1つずつ単純に左から見ていくのも素直すぎるので、今回は以下のような仕組みを加えています。

現在までの最長マッチの長さを記録しておき、次の候補は現在の最長マッチ分右に移動し、そこから左に向かって走査していき、すべて一致していたら最長マッチ以降のデータを右に向かって調べていきます。

以下の最長マッチ候補を例に説明します。

 -. "abcdefghijklmn" // データ
 1. "abcde123456789" // マッチ候補 1
 2. "abcdefgh123456" // マッチ候補 2
 3. "abcdef12345678" // マッチ候補 3
 4. "abcdefg1234567" // マッチ候補 4
 // chained hash table の参照で 3 Byte の一致
 -. "abc..........."
 1. "abc..........."

 // 右に向かって 1 Byte ずつ一致探索した結果 5 Byte が一致
 -. "abcde........."
 1. "abcde........."
 走査方向 → 
 最長一致: 5
 最長一致マッチ: 1
 // 次の候補も chained hash table から 3 Byte の一致
 -. "abc..........."
 2. "abc..........."

 // 5 Byte 目, 4 Byte 目 と確認
 -. "abc.e.........", "abcde........."
 2. "abc.e.........", "abcde........."
 走査方向 ←

 // 最長一致までの長さは全て一致したので右に走査していく
 -. "abcdefgh........"
 2. "abcdefgh........"
 走査方向 →
 最長一致: 8
 最長一致マッチ: 2
 // 次の候補も chained hash table から 3 Byte の一致
 -. "abc..........."
 3. "abc..........."

 // 8 Byte 目を確認するが一致しないので探索終了
 -. "abc....h....."
 3. "abc....2....."
 走査方向 ←
 // 次の候補も chained hash table から 3 Byte の一致
 -. "abc..........."
 4. "abc..........."

 // 8 Byte 目を確認するが一致しないので探索終了
 -. "abc....h....."
 4. "abc....1....."
 走査方向 ←

おわりに

もっと良い方法あったら教えて下さい。