Not only is the Internet dead, it's starting to smell really bad.:2021年05月26日分

2021/05/26(Wed)

[オレオレN6] 続々々・bm(3)のバグのお話

新潮文庫の堀口大學訳サン=テグジュペリ「戦う操縦士」が電子書籍で格安で復刊してますね、えーっと紙は死んだ?(ニーチェ) いっとき紙の文庫は結構なプレ値してたんだよな、俺も大昔2kくらい出して買った記憶がする。みすず書房の「城砦」なんかが入ってる全集もしばらく前に復刊したけど今はもう入手困難かな。

あと久しぶりにフィルムの現像出しに行った先で、通常は4000円弱する純米吟醸酒の一升瓶が訳あり品(賞味期限5/31)で880円で売ってたので買ってみた。 普段安酒(イギリス労働者階級の不道徳な酒ことジンかロシア人のミネラルウォーターことウォッカ)ばかりで飽きてたからね、日本酒とワインはさっぱり判らんが甘くて美味しかった。

はいどうでもいい話はおいといて、前回はHume-Sunday法の4.2.4 guardを読み解いて、別にこれ文字の出現頻度テーブルなんて必要ないじゃんという結論に達し、 オレオレN6では消したところまで。

しかしですね、一晩寝てジンウォッカでなく純米吟醸酒で酔っ払った頭でもう一度このロジックについて考え直したところ

ことにはたと気づき、確率論的には勝ち目のある勝負なんだなぁと考えを改めた。いかんですねワイの脳味噌アルコールで死んでますね…まぁ賭け事クッソ弱いからしゃーない人生負け続け。

ただしこの投機的実行のアテが外れた時はループに突入するペナルティあるわけで、相殺したら大して差は無いのでは?という気がしないでもないけどなぁ。 やっぱり実際にテストデータ用意して検証しない事にはわからんくらいパラノイアな高速化なのである。

ほんとに微妙な差だと思われるので、それならfreqテーブルの国際化のコストと、実装の問題で検索パターン文字がINT_MAXより長いケースでinteger overflow起こすこと考えると、消して正解なのでは感はある。

うーんめんどくせえ、C++のboyer_moore_searcherとかboyer_moore_horspool_searcherとかどうしてんだろ。

@BM法の基本を理解する

前回Hume-Sunday法の4.3 Shift functionの解説するよと書いたけど、そもそもBM法の基本を解説しておかないとわけわかになりそうなのでそっちを先にやる。いかがでしたか?この広告をクリックするかSNSでフォローして応援してね!(広告も無いしSNSもやってない)

そいやBM法で検索して引っかかるような解説だとたいてい例題に英文を使ってるので日本人に優しくないよねあれ。 俺は何十年C書いててもfcntl.hとfctrl.hのtypoに気づかずコンパイルエラーの原因がわからず3秒くらい悩むので、英単語がマッチしてるかなんてわからないのだ。

これはBM法がマルチバイトに対応してない関係上サンプルコード書く時に困るから仕方がない面もあるのだが、ワイド文字であれば(実装の困難さはさておき)理論上問題ないので、国際化の話題を多く扱う当チラシの裏においては例題は日本語を使って解説していこうと思う。 ちなみに最初は「ぬめねわはほま」とかのゲシュタルト崩壊必至な文字のみで解説しようと思ったけど、実際に書いてる方がゲシュタルト崩壊して解説が辛くなったので断念した。

では例題としてBM法で「おまーんこくさいくうこう」から「くさい」を検索してみようと思う、くさそう。

最初に検索パターン文字列の末尾一字が一致するかをチェックする。

おま|ー|んこくさいくうこう
くさ|い|
   ↑不一致

不一致であれば移動を行う、ナイーブ法なら単純に1つ後ろにずらすだけだが、BM法では移動距離を不一致な文字がパターン中に存在するかしないかで決定する。

  • 存在する … 移動量はパターンの末尾からその文字が出現するまでの距離
  • 存在しない … 移動量はパターン長

「ー」は後者なので移動量はパターン長つまり今回は3となる、この移動距離がナイーブ法より大きくできる事が高速文字列検索のキモなのである。

それでは3移動してみよか、移動したら前回と同様に末尾一字を比較するよ。

おまーんこ|く|さいくうこう
   くさ|い|
     ↑不一致

不一致文字の「く」はパターン中に存在する文字、この場合の移動量は前述の通りパターンケツの「い」から「く」までの距離で2となる。

そんでは2移動する。

おまーんこくさ|い|くうこう
     くさ|い|
        ↑一致

末尾「い」が一致したので、そこから前方に戻ってパターンの頭までの比較を行う。

おまーんこく|さ|いくうこう
     く|さ|い
       ↑一致

おまーんこ|く|さいくうこう
     |く|さい
      ↑完全一致

はい、完全一致なのでここで検索終了。たぶんイソプロピルアルコールの情弱殺処理試験で求められるBM法の知識はこの程度でいいはず。

この末尾の不一致文字を元に移動量を計算する方法を「不一致規則(Bad Character Rule)」と呼ぶ、コードを最適化するために事前にテーブルを作成するのが一般的で、Hume-Sunday法のペーパーではこの部分やね。

#define ASIZE 256

static struct
{
	int patlen;
	unsigned char pat[1024];
	long delta[ASIZE];
	...
} pat;

void prep(unsigned char *pb, int len)
{
	register unsigned char *pe;
	register int j;
	register long *d;

	pat.patlen = len;
	assert(pat.patlen < sizeof(pat.pat)); /* true or abort */
	memcpy(pat.pat, pb, pat.patlen) ; /* store pattern */
	/* get skip delta */
	for(j = 0, d = pat.delta; j < ASIZE; j++)
		d[j] = pat.patlen;
	for(pe = pb+pat.patlen–1; pb <= pe; pb++)
		d[*pb] = pe-pb;
	...

}

@次回予告

末尾1文字は一致したけれども前方比較の最中に不一致があった場合の移動量はどうしたらいいかだ、この時どれだけ移動できるかがBM法の改良の歴史なのである。

ちたまにあふれるBM法の解説ではそのまま不一致規則を使って移動を行うものが多いのだけど、正式版のBM法では「一致サフィックス規則(Good Suffix Rule)」というものを使う。 これは結構ややこしくて計算自体がコストになったりするのでいくつかの改良法が提案されてる。それについて飽きてなければ次回説明するでしょう(飽きてる)。