C++で文字列照合のためのBitapアルゴリズムを実装する方法

これは、文字列照合のためのBitapアルゴリズムを実装したC++プログラムの解説です。Bitapアルゴリズムは、指定されたテキストの中に、与えられたパターンと「ほぼ一致」する部分文字列が含まれているかどうかを判定します。ここでの「近似一致」はレーベンシュタイン距離（編集距離）に基づいて定義されており、部分文字列とパターンとの距離が許容値k以内であれば、両者は一致しているとみなされます。

このアルゴリズムは、まずパターンの各要素に対応する1ビットからなるビットマスクの集合を事前に計算します。これにより、処理の大部分を極めて高速なビット演算だけで実行できる点が大きな特徴です。Bitapアルゴリズムは「Shift-Or法」「Baeza-Yates–Gonnet法」とも呼ばれ、あいまい検索（ファジーマッチング）の分野で広く活用されています。

アルゴリズム

Begin
    テキスト文字列tとパターンpを入力として受け取る。
    関数bitmap_search()を定義する。引数はテキストtとパターンp：
    ビット配列Aを初期化する。
    パターンビットマスクp_mask[300]を初期化する。
    ビット配列を更新する。
    for i = 0 to 299
        p_mask[i] = ~0
    for i = 0 to m-1
        p_mask[p[i]] &= ~(1L << i);
    for i = 0 to t.length()-1
        A |= p_mask[t[i]];
        A <<= 1;
    if ((A & (1L << m)) == 0
        return i - m + 1
        return -1
End

サンプルコード

#include <string>
#include <map>
#include <iostream>
using namespace std;
int bitmap_search(string t, string p) {
    int m = p.length();
    long p_mask[300];
    long A = ~1;
    if (m == 0)
        return -1;
    if (m >63) {
        cout<<"Pattern is too long!";//パターンが長すぎる場合
        return -1;
    }
    for (int i = 0; i <= 299; ++i)
        p_mask[i] = ~0;
    for (int i = 0; i < m; ++i)
        p_mask[p[i]] &= ~(1L << i);
    for (int i = 0; i < t.length(); ++i) {
        A |= p_mask[t[i]];
        A <<= 1;
        if ((A & (1L << m)) == 0)
            return i - m + 1;
    }
    return -1;
}

void findPattern(string t, string p) {
    int position = bitmap_search(t, p);//bitmap_search関数の戻り値で位置を初期化
    if (position == -1)
        cout << "\nNo Match\n";
    else
        cout << "\nPattern found at position : " << position;
}

int main(int argc, char **argv) {
    cout << "Enter Text:\n";
    string t;
    cin >>t;
    cout << "Enter Pattern:\n";
    string p;
    cin >>p;
    findPattern(t, p);
}

実行結果

Enter Text:
Tutorialspoint
Enter Pattern:
point

Pattern found at position : 9

上記の実行例では、テキスト「Tutorialspoint」の中からパターン「point」を検索し、位置9（先頭を0として数えるインデックス）で発見できたことが出力されています。パターンがテキスト内に存在しない場合は「No Match」と表示されます。

なお、この実装では64ビットのlong型をビット配列として使用しているため、扱えるパターンの最大長は63文字までに制限されます。パターンが63文字を超えると「Pattern is too long!」と表示され、検索は失敗します。より長いパターンを扱いたい場合は、複数のワードに分割して処理するなどの拡張が必要になります。