6

こんにちは、

.NET（または簡単に翻訳可能）でのLevenshtein DFA（決定性有限オートマトン）の「すぐに使える」実装を知っている人はいますか？私は160000を超える異なる単語を含む非常に大きな辞書を持っています。そして、最初の単語wが与えられた場合、レーベンシュタイン距離で最大2つのwのすべての既知の単語を効率的な方法で見つけたいと思います。

もちろん、特定の単語の1つを編集距離ですべての可能な編集を計算し、それをこれらの各編集に再度適用する関数を使用すると、問題が解決します（非常に簡単な方法で）。問題は効率です---7文字の単語を考えると、これは完了するのにすでに1秒以上かかる可能性があり、可能であれば、レーベンシュタインDFAの場合のように、O（| w |）ステップ。

編集：私は少し勉強することで問題への独自のアプローチを構築できることを知っていますが、現時点ではシュルツとミホフの60ページの長さの記事を読む余裕はありません。

どうもありがとうございます。

4

6 に答える 6

2

これを apache lucene Java に実装しました。おそらく、これを C# に変換して時間を節約できます。

主なクラスはここにあります: シュルツとミホフのアルゴリズムを使用して、文字列からレーベンシュタイン DFA を取得する単なるビルダーです。

http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java

Lev1 とLev2のパラメータの説明 (事前計算されたテーブル) は次のとおりです。 /Lev1ParametricDescription.java

http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Lev2ParametricDescription.java

これらはコンピューターで生成されていることに気付くかもしれませんが、Jean-Phillipe Barrette の偉大な moman 実装 (python) http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/を使用して、このスクリプトで生成しました。 src/java/org/apache/lucene/util/automaton/createLevAutomata.py

jar ファイルが大きくなりすぎないように、パラメトリック記述をパックされた long[] 配列として生成します。

toAutomaton(int n) をニーズ/DFA パッケージに合わせて変更するだけです。私たちの場合、遷移が Unicode コードポイント範囲として表される、変更された形式の brics automaton パッケージを使用しています。

この種の場合、効率的な単体テストは困難ですが、ここに私たちが思いついたものがあります... それは徹底的に思われ、moman 実装でバグ (作者によってすぐに修正されました!) さえ発見されました。

http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/test/org/apache/lucene/util/automaton/TestLevenshteinAutomata.java

于 2010-10-26T15:40:12.027 に答える
1

どうぞ。

/// <summary>
/// Levenshtein Distance Calculator
/// </summary>
public static int DistanceFrom(this string s, string t)
{
    int n = s.Length;
    int m = t.Length;
    int[,] d = new int[n + 1, m + 1];

    // Step 1
    if (n == 0)
        return m;

    if (m == 0)
        return n;

    // Step 2
    for(int i = 0; i <= n; d[i, 0] = i++) ;
    for(int j = 0; j <= m; d[0, j] = j++) ;

    // Step 3
    for (int i = 1; i <= n; i++)
    {
        //Step 4
        for (int j = 1; j <= m; j++)
        {
            // Step 5
            int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

            // Step 6
            d[i, j] = Math.Min(
                Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                d[i - 1, j - 1] + cost);
        }
    }
    // Step 7
    return d[n, m];
}
于 2010-10-20T11:29:09.620 に答える
0

大きな辞書でほぼ一致するものを見つけたいと思っていることは理解しています。これが私のやり方です。リンク。

私が DFA について理解していることから、それがどのように優れているか、実際には違いがあるかさえわかりません。NFA の方が速いかもしれませんが、それは NFA が存在しないためです。たぶん私は間違っています。

于 2010-10-20T21:44:24.473 に答える
0

Nick Johnson は、Python でのレーベンシュタイン オートマトンの作成に関する非常に詳細なブログ投稿を行っています。コードはこちらにあります。読みやすく、効率的であることがわかったコードのわずかに変更されたバージョンを使用しました。

Mike Dunlavey の回答も良いです。この場合、トライ検索とレーベンシュタイン DFA のどちらが最も効率的でしょうか?

于 2014-07-08T23:13:14.893 に答える