ボイヤー-ムーア文字列検索アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ボイヤー-ムーア文字列検索アルゴリズム（Boyer-Moore String Search Algorithm）は、効率的な文字列検索アルゴリズムの一種。Robert S. Boyer と J Strother Moore が 1977年に開発した。ボイヤー-ムーア法とも呼ばれる。

このアルゴリズムでは検索対象文字列（キー）の前処理を行い、検索対象テキストの前処理は行わない（他のアルゴリズムではテキストに前処理を施し、繰り返し検索を行うことで前処理のコストを償却する）。ボイヤー-ムーア法の実行時間は半線形時間である。テキスト上の全文字をチェックする必要はなく、スキップしながら処理していく。一般にキー文字列が長いほど検索が高速化される。検索文字列とテキストの間での不一致が発生するたびに、不一致であったという情報を最大限に利用して照合しなくてもいい位置を可能な限り排除することで、効率を向上させている。

目次 1 アルゴリズム 2 実装例 3 派生 3.1 ターボ・ボイヤー-ムーア法 3.2 Horspoolのアルゴリズム 4 外部リンク

[編集] アルゴリズム

ボイヤー-ムーア法に初めて接した人々が驚かされるのは、その照合時の動作である。ボイヤー-ムーア法では、逆向きに（文字列の末尾から）照合していく。"ANPANMAN" という文字列をテキストの先頭から探していく場合、テキストの先頭から 8 番目の位置が "N" であるかをまずチェックする。"N" だった場合、次に 7 番目の位置が "A" であるかをチェックし、最終的にテキストの先頭が "A" であるかをチェックする。

ボイヤー-ムーア法が何故このような逆向きの照合を行うのかは、照合に失敗した場合を考えればはっきりする。8 番目の位置が "N" ではなく "X" だったとする。"X" は "ANPANMAN" の中には出現しない文字であり、この文字を含む部分と "ANPANMAN" という文字列との照合は必ず失敗することが明らかになる。つまり、"X" の後の7文字も照合しても意味がないことがわかる（照合する範囲に "X" が含まれるため）。したがって、たった1文字をチェックしただけで次の照合位置をテキストの9番目の文字からの8文字とすることができる。

以上から、このアルゴリズムの最良実行時間はテキスト長 N をキー文字列長 M で割った N/M であることがわかる。このとき M 文字に 1 文字の割合でチェックすればよい。また、検索パターンが長ければ長いほど、このアルゴリズムの性能が良くなることがわかる。

このアルゴリズムでは 2つのテーブルを事前に作成し照合に使用する。第一のテーブルは照合に失敗した文字毎に次に照合を開始する位置まで何文字スキップすればよいかを示す。第二のテーブルは照合に失敗した文字の位置毎にそれまでに何文字照合に成功したかに基づいて同様の計算をしたものである。このふたつのテーブルを使って次にジャンプする位置を決定するため、これらを ジャンプテーブル(jump tables) と呼ぶが、一般的なジャンプテーブルと混同しないよう注意されたい。

第一のテーブルの作成は簡単である。検索文字列の最後の文字に対しては 0 とし、カウントアップしながら前方に移動していく。現在見ている文字がこれまでに出現していない文字なら、それをテーブルのエントリに加え、現在のカウントをテーブルに格納する。検索文字列内に出現しなかった文字には全て検索文字列数と同じ値を格納する。

例: 文字列 ANPANMAN に対する第一のテーブルは以下のようになる（単純化のため、各文字はテーブルに追加された順に示されている）:

文字	シフト
N	0
A	1
M	2
P	5
他のあらゆる文字	8

第二のテーブルは若干複雑である。検索文字列長未満の各値 N について、まず検索文字列の末尾 N 文字を含むパターンを求める。そのとき照合に失敗した文字もその先頭に含める。次に検索文字列とその部分文字列を並べ、検索文字列内の部分的マッチングも考慮して最低限シフトしなければならない文字数を決定する。検索文字列 ANPANMAN に関するテーブルは次のようになる:

N	パターン	シフト
0	N	1
1	AN	8
2	MAN	3
3	NMAN	6
4	ANMAN	6
5	PANMAN	6
6	NPANMAN	6
7	ANPANMAN	6

上の表の「シフト」をどう求めたのかを以下のように図示した方が分かり易いだろう。ここで、マッチしてはいけない文字は小文字で示してある。例えば "mAN" は、"AN" という文字列があって、その直前に "M" 以外の何らかの文字がある場所を探して配置してある。そのように、各部分文字列をシフトしていって条件に適合する配置を決定し、シフトした文字数をテーブルに記録するのである。

       ANPANMAN
      --------
            n  1
    aN         8
        mAN    3
    nMAN       6
   aNMAN       6
  pANMAN       6
 nPANMAN       6
aNPANMAN       6

このアルゴリズムの最悪の場合の計算量は N*M となる。検索文字列が M 個の同じ文字の並びで、テキストが M-1 個の同じ文字と 1 個の別の文字が繰り返されているパターンの場合に、この最悪ケースとなる。この場合、N-M+1 個の位置で照合を行わなければならず、各位置で M 回の比較が行われる。

検索文字列がそのような特殊な繰り返しでない場合、このアルゴリズムは最悪で 3*N 回の比較をしなければならないので、（照合が成功するしないに関わらず）計算量は O(n) となる。この証明は Richard Cole の論文 Tight bounds on the complexity of the Boyer-Moore algorithm（Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1991年）に詳述されている。1977年にこのアルゴリズムが生まれたとき、最大比較回数は 6*N とされていたが、1980年には 4*N 以下であることが示されていた。

[編集] 実装例

以下に、ボイヤー-ムーア法のC言語での実装例を示す。

注: ここでの good-matchテーブル(skip[]) の生成は実装を単純化するために性能を無視したコードになっている。したがってこのコードをそのまま使って他のアルゴリズムと性能を比較してもよい結果は得られない。実用にはもっと高速な手法を使うべきである。

#include <string.h>
#include <limits.h>

/* This helper function checks, whether the last "portion" bytes
 * of "needle" (which is "nlen" bytes long) exist within the "needle"
 * at offset "offset" (counted from the end of the string),
 * and whether the character preceding "offset" is not a match.
 * Notice that the range being checked may reach beyond the
 * beginning of the string. Such range is ignored.
 */
static int boyermoore_needlematch
    (const unsigned char* needle, size_t nlen, size_t portion, size_t offset)
{
    ssize_t virtual_begin = nlen-offset-portion;
    ssize_t ignore = 0;
    if(virtual_begin < 0) { ignore = -virtual_begin; virtual_begin = 0; }
    
    if(virtual_begin > 0 && needle[virtual_begin-1] == needle[nlen-portion-1])
        return 0;

    return
        memcmp(needle + nlen - portion + ignore,
               needle + virtual_begin,
               portion - ignore) == 0;
}   

static size_t max(ssize_t a, ssize_t b) { return a>b ? a : b; }

/* Returns a pointer to the first occurrence of "needle"
 * within "haystack", or NULL if not found.
 */
const unsigned char* memmem_boyermoore
    (const unsigned char* haystack, size_t hlen,
     const unsigned char* needle,   size_t nlen)
{
    size_t skip[nlen]; /* Array of shifts with self-substring match check */
    ssize_t occ[UCHAR_MAX+1]; /* Array of last occurrence of each character */
    size_t a, hpos;
    
    if(nlen > hlen || nlen <= 0 || !haystack || !needle) return NULL;

    /* Preprocess #1: init occ[]*/
    
    /* Initialize the table to default value */
    for(a=0; a<UCHAR_MAX+1; ++a) occ[a] = -1;
    
    /* Then populate it with the analysis of the needle */
    /* But ignoring the last letter */
    for(a=0; a<nlen-1; ++a) occ[needle[a]] = a;
    
    /* Preprocess #2: init skip[] */  
    /* Note: This step could be made a lot faster.
     * A simple implementation is shown here. */
    for(a=0; a<nlen; ++a)
    {
        size_t value = 0;
        while(value < nlen && !boyermoore_needlematch(needle, nlen, a, value))
            ++value;
        skip[nlen-a-1] = value;
    }
    
    /* Search: */
    for(hpos=0; hpos <= hlen-nlen; )
    {
        size_t npos=nlen-1;
        while(needle[npos] == haystack[npos+hpos])
        {
            if(npos == 0) return haystack + hpos;
            --npos;
        }
        hpos += max(skip[npos], npos - occ[haystack[npos+hpos]]);
    }
    return NULL;
}

[編集] 派生

[編集] ターボ・ボイヤー-ムーア法

アルゴリズムが使用するメモリ領域を大きくして（固定サイズ）、比較回数を 2n 回に削減している（通常のボイヤー-ムーア法では 3n 回）。ここで n はテキストの文字数。[1]

[編集] Horspoolのアルゴリズム

ボイヤー-ムーア法を単純化したもので、クヌース-モリス-プラット法と関係がある。ボイヤー-ムーア法の第二のテーブルを使用しないバージョンである。最悪で O(MN) であるが、ランダムなテキスト上の平均では O(N) となる。

[編集] 外部リンク

• Animation of the Boyer-Moore algorithm ただしフォントの設定によっては表示がずれて見づらい（Javaアプレット）
• An explanation of the algorithm (with sample C code)
• 計算機科学 - String Matching 文字列照合 - 山本芳嗣（筑波大学）