C++でのBKツリーの紹介

BKツリーまたはBurkhardツリーは、レーベンシュタイン距離に基づいてスペルチェックを実行するために通常使用されるデータ構造の形式です。また、文字列照合にも使用されます。オートコレクト機能を使用して、このデータ構造を作成できます。辞書にいくつかの単語があり、他のいくつかの単語のスペルミスをチェックする必要があるとします。スペルがチェックされる特定の単語に近い単語のコレクションが必要です。たとえば、「uck」という単語がある場合、正しい単語は（truck、duck、duck、suck）になります。したがって、単語を削除するか、文字を適切な文字に置き換える新しい単語を追加することで、スペルミスを修正できます。編集距離をパラメータとして使用し、辞書でスペルをチェックします。

他のすべてのツリーと同様に、BKツリーもノードとエッジで構成されます。ノードは辞書内の単語を表します。エッジには、あるノードから別のノードまでの編集距離に関する情報を提供する整数の重みが含まれています。

{本、本、ブーイング、ケーキ、ケープ}-

BKツリー

BKツリーのすべてのノートには、同じ編集距離を持つ子ノードが1つだけあります。ノードの挿入中に編集距離で衝突が発生した場合、適切な子を取得するまで挿入プロセスを伝播します。すべての挿入はルートノードから始まります。ルートノードは任意の単語にすることができます。これまで、Bkツリーとは何かを学びました。次に、正しい最も近い単語を見つける方法を見てみましょう。まず、許容値を設定する必要があります。この許容値は、スペルミスのある単語と正しい単語の間の最大編集距離にすぎません。

許容範囲内で適格な正しい単語を見つけるために、反復のプロセスを使用します。ただし、これはより複雑であるため、バイナリツリーの各ノードが親からの編集距離に基づいて構築されていることがわかっているため、BKツリーが動作します。したがって、ルートノードから許容範囲内にある特定のノードに直接移動できます。 TOLが許容限界であり、スペルミスのあるノードからの現在のノードの編集距離がdistである場合。そのため、ここでは、編集距離が範囲内にある子のみを繰り返し処理します。

[dist-TOL、dist + TOL]、これにより複雑さが大幅に軽減されます。

例

動作を説明するプログラム-

#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<<"Correct words suggestions from dictionary for : "<<word1<<endl;
   for (auto correctWords : match)
   cout<<correctWords<<endl;
   match = findCorrectSuggestions(RT,word2);
   cout<<"Correct words suggestions from dictionary for : "<<word2<<endl;
   for (auto correctWords : match)
   cout<<correctWords<<endl;
   return 0;
}

出力

Correct words suggestions from dictionary for : ok
book
boo
Correct words suggestions from dictionary for : ke
cake