3

これらの要件を満たすために、レーベンシュタインアルゴリズムを使用しています。

N文字の単語を見つけるとき、私の辞書データベースで修正として提案する単語は次のとおりです。

見つかった単語と1文字の違いがあるN文字のすべての辞書単語。例：見つかった単語：bearn、辞書の単語：bears

見つかった単語と等しいN文字を持つN+1文字のすべての辞書単語。例：見つかった単語：クマ、辞書の単語：クマ

見つかった単語と等しいN-1文字を持つN-1文字のすべての辞書単語。例：見つかった単語：クマ、辞書の単語：クマ

このC++でのレーベンシュタインアルゴリズムの実装を使用して、単語のレーベンシュタイン数が1（3つの場合すべてのレーベンシュタイン数）であるかどうかを調べていますが、提案する単語を選択するにはどうすればよいですか？Boyer-Moore-HorspoolとKnuth-Morris-Prattについて読みましたが、どちらがどのように役立つかわかりません。

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int levenshtein(const string &s1, const string &s2)
{
   string::size_type N1 = s1.length();
   string::size_type N2 = s2.length();
   string::size_type i, j;
   vector<int> T(N2+1);

   for ( i = 0; i <= N2; i++ )
      T[i] = i;

   for ( i = 0; i < N1; i++ ) {
      T[0] = i+1;
      int corner = i;
      for ( j = 0; j < N2; j++ ) {
         int upper = T[j+1];
         if ( s1[i] == s2[j] )
            T[j+1] = corner;
         else
            T[j+1] = min(T[j], min(upper, corner)) + 1;
         corner = upper;
      }
   }
   return T[N2];
}
4

4 に答える 4

6

また、スペル修正に関するNorvigの優れた記事を読みに追加することもできます。

読んでからしばらく経ちますが、あなたの書いたものと非常によく似ていることを覚えています。

于 2009-01-27T19:30:21.647 に答える
2

別の場所で述べたように、Boyer-Moore はこれにはあまり適していません。複数のスティングを同時に検索したいので、Wu と Manber のアルゴリズムの方が好みに合うはずです。

別の質問への回答として、C++ コードの概念実証を投稿しました。そこに記載されている注意事項に注意してください。

于 2009-01-27T20:00:03.787 に答える
0

提案を 1 つの単語に限定するのはなぜですか。一連の単語を含めないのはなぜですか。1 つの単語に制限されている場合は、事前に計算された使用頻度などによって結果を並べ替えることができます。この頻度は、ユーザーが提案から選択した内容に基づいて更新できます。

また、元の単語にスペル ミスがない場合は、オートコンプリートのように、N+1 ケースを優先することもできます。とにかく、それを行う正しい方法は1つではないと思います。おそらく、要件がより具体的であれば、絞り込みやすくなります。

また、Norvig の記事で説明されているアルゴリズムを理解するために、Python の知識は必要ありません。

于 2009-01-27T19:58:03.713 に答える
0

私があなたのことを正しく理解していれば、あなたの質問に対する正しい答えはありません。レーベンシュタインを使用して、特定の単語に対して最大 3 つの提案を識別します。どれを使用し、どれを除外するかを決定するルールを考え出すのはあなた次第です。それとも、それらすべてを使用する必要がありますか?

興味深いことに、Levenshtein への Damerau の拡張機能に興味があるかもしれません。2 人のキャラクターが入れ替わった場合も、バニラの Levenshtein が返す 2 ではなく 1 のスコアを与えると見なされます。

于 2009-01-27T20:11:45.027 に答える