C++で学ぶBKツリー：レーベンシュタイン距離によるスペルチェックの仕組みと実装

BKツリー（Burkhard-Kellerツリー）とは

BKツリーは、レーベンシュタイン距離（編集距離）に基づくスペルチェックによく使われるデータ構造です。文字列マッチングや自動修正（オートコレクト）機能の実装にも応用できます。

例えば、辞書に登録された単語の中から、チェック対象の単語に近い綴りの候補を集めたい場面を考えてみましょう。入力が「uck」だった場合、正しい単語としては「truck」「duck」「suck」などが考えられます。このように、文字の削除・追加・置き換えによって生じるスペルミスは、編集距離をパラメータとして辞書内の単語と照合することで修正できます。

木の構造

他の木構造と同様に、BKツリーもノードとエッジで構成されます。ノードは辞書内の単語を表し、エッジには整数の重み、すなわち「あるノードから別のノードへの編集距離」が格納されます。

例として、{book, books, boo, cake, cape} という単語からなる辞書を考えてみます。

ノードの挿入ルール

BKツリーの各ノードは、同じ編集距離を持つ子ノードを1つだけ持ちます。挿入時に編集距離が衝突した場合は、適切な子ノードが見つかるまで挿入処理を下位へ伝播させます。すべての挿入はルートノードから開始され、ルートには任意の単語を選ぶことができます。

許容誤差（Tolerance）を使った探索

次に、最も近い正しい単語を見つける方法を見ていきましょう。まず「許容誤差」を設定します。これは、誤入力された単語と正しい単語の間で許容できる最大編集距離のことです。

許容範囲内の候補を探すのに辞書全体を反復的に走査すると、計算量が大きくなります。ここでBKツリーが活躍します。各ノードは親ノードとの編集距離に基づいて配置されているため、ルートから許容範囲内のノードへ直接たどることができます。

許容誤差をTOL、現在のノードと誤入力単語の編集距離をdistとすると、探索すべき子ノードは編集距離が [dist − TOL, dist + TOL] の範囲に入るものだけです。これにより計算量を大幅に削減できます。

C++での実装例

以下は、BKツリーの動作を示すサンプルプログラムです。辞書 {book, cake, cart, books, boo} から木を構築し、誤入力「ok」と「ke」に対する修正候補を出力します。

#include "bits/stdc++.h"
using namespace std;
#define MAXN 100
#define TOL 2
#define LEN 10
struct Node {
    string word;
    int next[2*LEN];
    Node(string x):word(x){
        for(int i=0; i<2*LEN; i++)
        next[i] = 0;
    }
    Node() {}
};
Node RT;
Node tree[MAXN];
int ptr;
int min(int a, int b, int c) {
    return min(a, min(b, c));
}
int editDistance(string& a,string& b) {
    int m = a.length(), n = b.length();
    int dp[m+1][n+1];
    for (int i=0; i<=m; i++)
        dp[i][0] = i;
    for (int j=0; j<=n; j++)
        dp[0][j] = j;
    for (int i=1; i<=m; i++) {
        for (int j=1; j<=n; j++) {
            if (a[i-1] != b[j-1])
                dp[i][j] = min( 1 + dp[i-1][j], 1 + dp[i][j-1], 1 + dp[i-1][j-1] );
            else
                dp[i][j] = dp[i-1][j-1];
        }
    }
    return dp[m][n];
}
void insertValue(Node& root,Node& curr) {
    if (root.word == "" ){
        root = curr;
        return;
    }
    int dist = editDistance(curr.word,root.word);
    if (tree[root.next[dist]].word == ""){
        ptr++;
        tree[ptr] = curr;
        root.next[dist] = ptr;
    }
    else{
        insertValue(tree[root.next[dist]],curr);
    }
}
vector <string> findCorrectSuggestions(Node& root,string& s){
    vector <string> corrections;
    if (root.word == "")
        return corrections;
    int dist = editDistance(root.word,s);
    if (dist <= TOL) corrections.push_back(root.word);
    int start = dist - TOL;
    if (start < 0)
        start = 1;
    while (start < dist + TOL){
        vector <string> temp = findCorrectSuggestions(tree[root.next[start]],s);
        for (auto i : temp)
        corrections.push_back(i);
        start++;
    }
    return corrections;
}
int main(){
    string dictionary[] = {"book","cake","cart","books", "boo" };
    ptr = 0;
    int size = sizeof(dictionary)/sizeof(string);
    for(int i=0; i<size; i++){
        Node tmp = Node(dictionary[i]);
        insertValue(RT,tmp);
    }
    string word1 = "ok";
    string word2 = "ke";
    vector <string> match = findCorrectSuggestions(RT,word1);
    cout<<"辞書から検索した "<<word1<<" の修正候補："<<endl;
    for (auto correctWords : match)
    cout<<correctWords<<endl;
    match = findCorrectSuggestions(RT,word2);
    cout<<"辞書から検索した "<<word2<<" の修正候補："<<endl;
    for (auto correctWords : match)
    cout<<correctWords<<endl;
    return 0;
}

出力結果

辞書から検索した ok の修正候補：
book
boo
辞書から検索した ke の修正候補：
cake

このように、「ok」という誤入力に対しては編集距離が許容値2以内の「book」「boo」が、「ke」に対しては「cake」が修正候補として返されます。BKツリーを活用すれば、辞書全体を線形に走査する必要がなく、類似単語を効率的に検索できます。