【プログラムトピック(一般)】


【BM法と線形検索】

文字列検索のルーチンでBM法(Boyer-Moore法)と力ずくでやる線形検索がある。
(ここでは、一つの配列を使用する、簡易BM法の事を記します。)
BM法は、検索する文字列の末尾から比較するのが特徴で、一致しないパターン分だけ後ろに移動できるので、比較の回数が少なくてすむ。
しかし、検索する文字列に同じ文字がある場合の処理のため、最初に配列を作る。
となると、どういった状況下でBM法を使うべきなのか悩む。
そこで、特殊な条件下だが、調べてみた。(*1)

何バイト目か検索する文字数BM法の検索タイム線形検索のタイム
48,159バイト目2文字4msec4msec
48,159バイト目4文字2msec3msec
48,159バイト目5文字2msec3msec
48,159バイト目10文字1msec3msec
254,048バイト目2文字22msec20msec
254,048バイト目4文字18msec17msec
254,048バイト目5文字11msec17msec
254,048バイト目10文字7msec17msec
537,660バイト目2文字48msec40msec
537,660バイト目4文字29msec37msec
537,660バイト目5文字25msec37msec
537,660バイト目10文字17msec37msec

この表の限りだと、4文字目か5文字目が境目だ。
10文字くらいになると、スキップできる文字数が長くなるので、BM法の方が早いことが多い。
検索する文字数をstrlenでしらべて、5文字以上くらいならBM方を使った方が一般的には良さそうだ。
しかし、線形検索では、特に検索する文字数は必要ないので、若干のオーバーヘッドが付いてしまうが、
そもそも5文字以下のstrlenならばそれほど気にすることはないだろう。

(*1)
538,196byteのc言語のソースを使って、純粋に検索スピードをチェックした。
timeはtimeGetTime()で収得したものでmsec単位。
40回の繰り返しを1セットとし、100回計測し、最低と最高を除いた98回の平均。

【圧縮】

LZSには要素が4つある。
1)圧縮が掛かっているか否かのフラグビット1bit。
2)圧縮が掛かっていないときのキャラクターコード8bit。
3)辞書の位置。
4)圧縮長。最後の二つは色々ある。

展開スピードを考えると、
1)フラグビットを8個まとめる。
2)辞書の位置を12bit、圧縮長を4bitにして、計16bitにする。
以上のことを行うと、バイト単位の読み込みだけになるので展開は早い。

フラグビットを1だと圧縮、0だと非圧縮とすると、以下のようになる。

例)
00byte目:フラグビットを8個まとめた物:00111001b
01byte目:辞書位置12bit+圧縮長4bit
03byte目:圧縮されなかったキャラクターコード8bit
04byte目:圧縮されなかったキャラクターコード8bit
05byte目:辞書位置12bit+圧縮長4bit
07byte目:辞書位置12bit+圧縮長4bit
09byte目:辞書位置12bit+圧縮長4bit
0bbyte目:圧縮されなかったキャラクターコード8bit
0cbyte目:圧縮されなかったキャラクターコード8bit
0dbyte目:フラグビットを8個まとめた物:00000111b
0ebyte目:辞書位置12bit+圧縮長4bit
        ・
        ・
        ・
辞書のサイズは4096なので問題ない。
圧縮長は4bitだが、圧縮するかどうかのしきい値を3にして、3なら0x00、18なら0x0fとすれば、結構長く一致長を調べられる。
これより圧縮率を高くするためにハフマン符号を導入するとすると、(これがレンジコーダでも同じ)
静的ハフマンを使うとハフマン木が大きくなり、LZSの4つの要素のうちキャラクターコードしか圧縮できない。
ハフマン木は、枝節は0、葉は1の後にキャラクターコードを出力したとする。

ハフマン木
| +----------0---------+ | | 1(Z) 1(B) 出力データ
01[Z] 2+8bit 1[B] 1+8bit ハフマン木
| +----------0---------+ | | +---0---+ +----0-----+ | | | | 1(A) +-0---+ +-0---+ 1(G) | | | | 1(Z) 1(V) 1(D) 1(T) 出力データ
001[A] 3+8bit 01[Z] 2+8bit 1[V] 1+8bit 001[D] 1+8bit 1[T] 1+8bit 1[G] 1+8bit
ハフマン木が大きくなると言う事以外にも、1つの要素を1ビット以下に割り当てられないのも大きな原因だ。
そこでレンジコーダを導入する。
その際には、(圧縮が掛かっているか否かの)フラグを圧縮長か位置とまとめると良いかもしれない。
それと、レンジコーダは適応型にすると頻度表もいらなくなる。
4つの要素(まとめた場合には3つの要素)を全て適応型レンジコーダにすると、圧縮率はなかなか良いし、適応型でもハフマンと比べると実装が楽なんでなかなか良い。


戻る