Perl の Boyer-Moore 文字列探索の実装

Perl正規表現と index 関数は、 Boyer-Moore 文字列探索アルゴリズムを使って文字列探索をしています。どのように実装してあるのか、Perl 5.16.1 のコードを覗いてみました。

Perl が使っているアルゴリズムは、パターン文字列のずらし数を一致しなかったオクテットから求めるだけの、Boyer-Moore 文字列探索アルゴリズムの中で最も単純なものです。Boyer-Moore では、さらに、パターン文字列が一致しなかった場合に一致した文字数からスキップ数を求めるテーブルを使うのが一般的ですけど、Perl はこちらのテーブルを使わない単純版を採用しています。

Perl では文字単位ではなく、オクテット単位で探索をおこなっています。スキップ数の表は 256 要素の配列にしてあり、パターン文字列スカラー構造体 (SV) のマジック (MAGIC_bm) に探索の前にあらかじめテーブルを作ってメモライズしています。この処理をしている Perl_fbm_compile でテーブルを生成してスカラー(SV)のマジック(MAGIC_bm)にセットします。

perl-5.16.1/util.c

void
Perl_fbm_compile(pTHX_ SV *sv, U32 flags)
{
    /* 省略 */

    Newx(table, 256, U8);
    memset((void*)table, mlen, 256);
    mg->mg_ptr = (char *)table;
    mg->mg_len = 256;

    s += len - 1; /* last char */
    i = 0;
    while (s >= sb) {
        if (table[*s] == mlen)
            table[*s] = (U8)i;
        s--, i++;
    }

    /* 省略 */
}

このテーブルでは、パターン文字列の最後のオクテットに対するスキップ数をゼロにしています。ポピュラーな実装の多くでパターン文字列の長さ (上ではオクテットサイズで mlen) になっているのとは異なっています。

テーブルを使った探索ルーチンは Perl_fbm_instr の末尾にあります。 s が被探索文字列のオクテット列を指差すポインタです。little はパターン文字列のオクテットを指差すポインタです。スキップ配列からオクテットに対するスキップ数を調べ、ゼロでないときは、その分、s を進めます。一方、オクテットに対するスキップ数がゼロのときは、文字列の逆方向に一致するかどうか確かめていって、一致しないときは、当初の s の指差すオクテットの次の位置のオクテットへ s を指差し直して、探索を繰り返します。

perl-5.16.1/util.c

char *
Perl_fbm_instr(pTHX_ unsigned char *big, register unsigned char *bigend, SV *littlestr, U32 flags)
{
        /* 省略 */
        const MAGIC *const mg = mg_find(littlestr, PERL_MAGIC_bm);
        const unsigned char * const table = (const unsigned char *) mg->mg_ptr;
        register const unsigned char *oldlittle;

        --littlelen;			/* Last char found by table lookup */

        s = big + littlelen;
        little += littlelen;		/* last char */
        oldlittle = little;
        if (s < bigend) {
            register I32 tmp;

          top2:
            if ((tmp = table[*s])) {
                if ((s += tmp) < bigend)
                    goto top2;
                goto check_end;
            }
            else {		/* less expensive than calling strncmp() */
                register unsigned char * const olds = s;

                tmp = littlelen;

                while (tmp--) {
                    if (*--s == *--little)
	                    continue;
                    s = olds + 1;	/* here we pay the price for failure */
                    little = oldlittle;
                    if (s < bigend)	/* fake up continue to outer loop */
	                    goto top2;
                    goto check_end;
                }
                return (char *)s;
            }
        }
      check_end:
        if ( s == bigend
             && SvTAIL(littlestr)
             && memEQ((char *)(bigend - littlelen),
                  (char *)(oldlittle - littlelen), littlelen) )
            return (char*)bigend - littlelen;
        return NULL;
}

パターン文字列とちょっとでも一致すると、探索開始位置のスキップ数を 1 にするので、効率が良くなさそうなのが気になるところです。