Levenshtein DFA in .NET

Question

Buon pomeriggio,

Qualcuno sa di un'implementazione "out-of-the-box" di Levenshtein DFA (automa a stati finiti deterministico) in .NET (o facilmente traducibili ad esso) ? Ho un dizionario molto grande con più di 160000 parole diverse, e voglio, data una parola ufficiale w, trovare tutte le parole conosciute a distanza di Levenshtein al massimo 2 di w in modo efficiente.

Ovviamente, avere una funzione che calcola tutte le possibili modifiche a distanza di modifica di una determinata parola e applicarla di nuovo a ciascuna di queste modifiche risolve il problema (e in un modo abbastanza diretto). Il problema è effiency --- dato un 7 parola lettera, questo può già prendere più di 1 secondo per completare, e ho bisogno di qualcosa di molto più efficiente --- se possibile, in quanto è con Levenshtein DFA, una soluzione che prende O (| w |) passaggi.

Edit: so che posso costruire il mio approccio al problema con un po 'di studio, ma al momento non posso permettermi di leggere gli articoli di 60 pagine di Schulz e Mihov.

Grazie mille.

Answer 1

abbiamo implementato questo per apache java Lucene, forse si potrebbe convertirlo in C# e risparmiare tempo.

la classe principale è qui: il suo solo un costruttore per ottenere Levenshtein DFA da una stringa, utilizzando l'algoritmo Schulz e Mihov.

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

le descrizioni parametriche (le tabelle precalcolate) per LEV1 e Liv2 sono qui: 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

si potrebbe notare questi sono generati con un computer, li abbiamo generato con questo sceneggiatura, utilizzando la grande implementazione di mamme di Jean-Phillipe Barrette (python)

generiamo le descrizioni parametriche come [] lunghi array confezionati in modo che non farà il nostro file jar troppo grande.

è sufficiente modificare toAutomaton (int n) per soddisfare le proprie esigenze/pacchetto DFA. nel nostro caso stiamo usando una forma modificata del pacchetto di automi di brics, in cui le transizioni sono rappresentate come intervalli univoci per il punto di codice.

test di unità efficienti sono difficili per questo genere di cose, ma ecco cosa ci è venuto in mente ... sembra essere approfondito e persino trovato un bug (che è stato risolto immediatamente dall'autore!) nell'implementazione della madre.

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

Answer 2

Qui si va.

/// <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]; 
} 

Answer 3

Capisco che vogliate trovare le corrispondenze vicine in un grande dizionario. Ecco come lo faccio io. link.

Da quello che sono in grado di capire su DFA, non riesco a vedere come è meglio, o anche in realtà qualcosa di diverso, sotto la pelle. Gli NFA potrebbero essere più veloci, ma perché non esistono. Forse mi sbaglio.

Answer 4

Nick Johnson ha una molto dettagliata blog post circa la costruzione di un automa Levenshtein in Python, e il codice è here. È una buona lettura e ho usato una versione leggermente modificata del codice che ho trovato efficiente.

La risposta di Mike Dunlavey è troppo buono. Mi chiedo quale sia il più efficiente in questo caso, una ricerca trie o un DFA Levenshtein?

Answer 5

ho portato il codice Java Lucene rilevante come suggerito da Robert Muir a C#. Per quanto riguarda la domanda e "out of the box": è un work in progress ma il codice sembra funzionare1 e probabilmente può essere ulteriormente ottimizzato, sebbene funzioni molto bene.

Lo si può trovare qui: https://github.com/mjvh80/LevenshteinDFA/.

UPDATE: Sembra che Lucene.NET non sia effettivamente morto (ancora?) E ho notato che ora hanno anche una versione con port di questo codice. Vorrei quindi raccomandare di guardare lì (https://github.com/apache/lucenenet/blob/master/src/Lucene.Net.Core/Util/Automaton/LevenshteinAutomata.cs) per un'implementazione di questo.

---

¹ il codice ha bisogno di più test
² perché è Java portato su C#, forse e perché ho scritto sostituzioni ingenue di alcune classi (per esempio bitset).

Answer 6

Vorrei solo sottolineare che al momento, le implementazioni di Levenshtein Automaton in Lucene e Lucene.Net fanno uso di file contenenti tabelle di stato parametriche (tabelle di stati astratti che descrivono gli stati concreti in un automa) creato utilizzando Moman.

Se si desidera una soluzione in grado di costruire tali tabelle da zero in memoria, è possibile dare un'occhiata a LevenshteinAutomaton. È in Java, ma è ben strutturato, facile da seguire e ampiamente commentato, e come tale dovrebbe essere più facile da portare in C# rispetto all'attuale implementazione di Lucene. È inoltre gestito da moi.

* Una curiosità: ho presentato LevenshteinAutomaton come una sostituzione, o come riferimento per una sostituzione, per l'attuale implementazione Levenshthein Automaton in Lucene ... 3 anni fa.