5

「n」個の単語の辞書があり、応答する「m」個のクエリがあります。編集距離が 1 または 2 である辞書内の単語数を出力したい。n と m がおよそ 3000 であることを考慮して、結果セットを最適化したい。

以下の回答から追加された編集：

私はそれを別の言葉で表現しようとします。

最初に、一連の Dictionary 単語として指定された 'n' 個の単語があります。次の 'm' 個の単語がクエリ単語として与えられ、クエリ単語ごとに、その単語が辞書に既に存在するか (編集距離 '0')、または編集距離 1 にある辞書内の単語の総数を見つける必要があります。 2 辞書の言葉から。

質問が明確になったことを願っています。

そうですね、時間計算量が (m*n)n の場合はタイムアウトになります。単純に DP Edit Distance Algorithm を使用するとタイムアウトになります。2k+1 の対角要素を計算しても、上記の場合は k=3 のしきい値である場合にタイムアウトになります。

4

3 に答える 3

7

2つの単語の間のレーベンシュタイン距離を使用したいのですが、それが質問のタグが言っていることなので、あなたはそれを知っていると思います。

リストを繰り返し処理し（仮定）、リスト内のすべての単語を実行中の現在のクエリと比較する必要があります。BKツリーを構築して検索スペースを制限することもできますが、単語数が3000語以下の場合、それはやり過ぎのように聞こえます。

var upperLimit = 2;
var allWords = GetAllWords();
var matchingWords = allWords
        .Where(word => Levenshtein(query, word) <= upperLimit)
        .ToList();

元の質問の編集後に追加

大文字と小文字を区別しない辞書がある場合は、distance=0のケースを簡単に見つけることができます。距離<=2の場合、検索スペースの完全なスキャン、クエリワードごとに3000回の比較が必要になります。同量のクエリワードを想定すると、900万回の比較になります。

タイムアウトするとおっしゃっていたので、タイムアウトが設定されていると思いますか？あなたの速度は、レーベンシュタイン計算の実装が不十分または遅いことが原因でしょうか？

入力量が異なるbkツリーを使用して訪問した検索スペースを示すグラフ
（出典：itu.edu.tr）
上のグラフはCLikiから盗まれたものです：bk-tree

ご覧のとおり、編集距離が2未満のbk-treeを使用すると、検索スペースの約1％しかアクセスできませんが、入力データが非常に大きく、その場合は最大50万語であると想定しています。あなたの場合も同様の数字を想定しますが、リスト/辞書に保存されていても、入力量が少ないと問題は発生しません。

于 2009-10-14T05:40:21.057 に答える
1

別の言い方をします。

最初は、辞書の単語のセットとして与えられた「n」の単語があります。次に、クエリ単語である「m」単語が与えられ、クエリ単語ごとに、その単語が辞書にすでに存在するかどうか（編集距離「0」）、または編集距離1にある辞書内の単語の総数を見つける必要があります。辞書の単語から2。

質問が明確になったことを願っています。

時間計算量が（m * n）* nの場合、タイムアウトになります。DPEditDistanceAlgorithmの単純な使用はタイムアウトになります。2 * k + 1の対角要素を計算することでさえ、上記の場合、ここでk=3のしきい値であるkがタイムアウトになります。

PS：BKツリーで十分です。C++での実装に関するリンク。

于 2009-10-14T05:54:23.977 に答える
1 
public class Solution   {
    public int minDistance(String word1, String word2) {
        int[][] table = new int[word1.length()+1][word2.length()+1];
        for(int i = 0; i < table.length; ++i) {
            for(int j = 0; j < table[i].length; ++j) {
                if(i == 0)
                    table[i][j] = j;
                else if(j == 0)
                    table[i][j] = i;
                else {
                    if(word1.charAt(i-1) == word2.charAt(j-1))
                        table[i][j] = table[i-1][j-1];
                    else
                        table[i][j] = 1 + Math.min(Math.min(table[i-1][j-1], 
                            table[i-1][j]), table[i][j-1]);
                }
            }
        }
        return table[word1.length()][word2.length()];
    }
}
于 2012-12-20T19:24:26.927 に答える