萊文斯坦DFA在.NET

下午好，萊文斯坦DFA在.NET

有誰知道在.NET中的「亂用」的實施萊文斯坦的DFA（確定性有限自動機）的（或容易翻譯吧）？我有一本超過160000個不同單詞的非常大的字典，我想要給出一個原始單詞w，以有效的方式找到所有已知單詞在Levenshtein距離最多爲2的w。

當然，通過編輯距離計算給定單詞的所有可能編輯並將其應用於每個編輯的功能可以解決問題（並且以非常簡單的方式）。問題是效率 - 給定一個7個字母的單詞，這已經可能需要1秒鐘才能完成，並且我需要更多多 - 如果可能的話，就像使用Levenshtein DFA一樣，這個解決方案需要O （| w |）的步驟。

編輯：我知道我可以用一點點研究來構建我自己的解決問題的方法，但目前我買不起讀Schulz和Mihov長達60頁的文章。

非常感謝。

來源

2010-10-20 Miguel

我們爲apache lucene java實現了這個，也許你可以將它轉換爲C＃並節省你自己的時間。

主類在這裏：它只是一個使用Schulz和Mihov算法從字符串中獲得Levenshtein DFA的生成器。

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

的參數描述（預先計算表）爲LEV1和LEV2在這裏： http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Lev1ParametricDescription.java

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

你可能會注意到，這些都與計算機生成的，我們生成它們與此劇本，使用讓 - 菲利普巴雷特的偉大的莫曼實現（python） http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/createLevAutomata.py

我們將參數描述生成爲包裝long []數組，這樣它就不會使我們的jar文件太大。

只需修改toAutomaton（int n）以適應您的需求/ DFA包。在我們的例子中，我們使用了brics自動機包的修改形式，其中轉換表示爲unicode碼點範圍。

高效的單元測試對於這類事情很困難，但這裏就是我們想出的......它看起來很徹底，甚至發現了一個錯誤（作者立即修復了這個錯誤！）在莫曼實現。

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

來源

2010-10-26 15:40:12

Lucene中的Levenshtein自動機相關代碼是否可以通過Maven快照資源庫獲得？我一直無法找到它。 – 2011-02-05 19:33:08

我做了艱苦的工作，所以你不必，你可以在這裏找到移植到C＃的代碼https://github.com/mjvh80/LevenshteinDFA/（note：wip）。 – Marcus 2014-09-03 13:16:32

鏈接已死亡../ – ostati 2014-11-18 01:21:03

在這裏，你去。

/// <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-20 11:29:09

再次感謝，我不是在尋找一個距離計算算法，而是尋找一個已知詞搜索的DFA實現。 – Miguel 2010-10-20 11:32:13

感謝您的實施 – samy 2010-12-03 08:57:23

看起來像你從https://www.dotnetperls.com/levenshtein借來了這段代碼 – vladimir77 2017-01-08 08:07:06

我知道你想在大詞典中找到近乎匹配的東西。這是我做的方式。 link.

從我能弄清楚的DFA中，我看不出它在皮膚下更好，甚至實際上有什麼不同。 NFA可能會更快，但那是因爲它們不存在。也許我錯了。

來源

2010-10-20 21:44:24

-1

尼克·約翰遜有很詳細的blog post關於Python中的萊文斯坦自動機的建設，並且代碼here。這是一個很好的閱讀，我已經使用了我發現有效的代碼的稍微修改版本。

Mike Dunlavey的回答也很好。我想知道在這種情況下最有效的方法是什麼，特里搜索或Levenshtein DFA？

來源

2014-07-08 23:13:14 gui11aume

我將Robert Muir建議的相關Lucene Java代碼移植到C＃中。就問題而言，「開箱即用」：這是一項正在進行的工作，但代碼似乎可以工作，並可能進一步優化，儘管它的確表現非常好。

您可以在這裏找到它：https://github.com/mjvh80/LevenshteinDFA/。

UPDATE：看來Lucene.NET實際上並沒有死（但？），我注意到他們現在也有這個代碼的移植版本。因此，我會建議在那裏尋找（https://github.com/apache/lucenenet/blob/master/src/Lucene.Net.Core/Util/Automaton/LevenshteinAutomata.cs）。

¹代碼需要更多的測試
²，因爲它的Java移植到C＃也許因爲我寫了一些類（如位集）的天真更換。

來源

2014-09-04 06:44:39 Marcus

這應該是公認的答案！你可以添加測試嗎？ – ostati 2014-11-18 01:20:33

到目前爲止我還沒有移植測試，但我打算這麼做，但沒有太多時間來處理這個問題。請隨時通過添加測試或其他方式提供幫助。 – Marcus 2014-11-19 10:16:40

-1

我想指出的是，截至目前，Lucene和Lucene.Net中的Levenshtein Automaton實現都使用包含參數狀態表（描述自動機中具體狀態的抽象狀態表）使用Moman創建。

如果您想要一個能夠在內存中從頭構建這樣的表的解決方案，您可能需要看看LevenshteinAutomaton。它是用Java編寫的，但它結構良好，易於操作和廣泛地評論，因此與目前的Lucene實現相比，它更容易移植到C＃。它也由moi維護。

*有趣的事實：我提交LevenshteinAutomaton作爲替代，或作爲Lucene的補發一個參考，當前Levenshthein自動機的實現...... 3年前。

來源

2016-07-02 02:13:32 Kevin

萊文斯坦DFA在.NET

回答

相關問題