Edit Distanzalgorithmus

Question

Ich habe ein Wörterbuch von 'n' Worten gegeben und es gibt 'm' Abfragen zu reagieren. Ich möchte die Anzahl der Wörter im Wörterbuch zu Ausgabe, die zu bearbeiten sind Abstand 1 oder 2. Ich möchte gegeben, um die Ergebnismenge optimieren, dass n und m etwa 3000.

Bearbeiten Antwort hinzugefügt unter:

Ich werde versuchen, es anders zu formulieren.

Anfangs gibt es 'n' Wörter, die als Dictionary-Wörter definiert sind. Als nächstes werden 'm'-Wörter angegeben, die Abfragewörter sind, und für jedes Abfragewort muss ich herausfinden, ob das Wort bereits in Dictionary (Edit Distance' 0 ') oder der Gesamtzahl von Wörtern im Dictionary existiert, die sich bei Editierdistanz 1 oder befinden 2 aus den Wörterbuchwörtern.

Ich hoffe, die Frage ist jetzt klar.

Nun, es Time-Out, wenn die Zeit Komplexität ist (m * n) n. Die naive Verwendung von DP Edit Distance Algorithm abläuft. Sogar Berechnen der diagonalen Elemente von 2k + 1 mal aus, wobei k der Schwellenwert hier ist, k = 3 im obigen Fall.

Answer 1

Sie möchten die Levenshtein distance zwischen zwei Wörtern verwenden, aber ich nehme an, dass Sie wissen, dass das, was die Tags der Frage sagen.

Sie müssten durch Ihre Liste (Annahme) iterieren und jedes Wort in der Liste mit der aktuellen Abfrage vergleichen, die Sie ausführen. Du könntest einen BK-tree bauen, um deinen Suchraum zu begrenzen, aber das klingt wie ein Overkill, wenn du nur ~ 3000 Wörter hast.

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

Hinzugefügt nach Bearbeiten der ursprünglichen Frage

Fälle zu finden, bei denen der Abstand = 0 wäre leicht Enthält-Abfragen, wenn Sie einen Fall unempfindlich Wörterbuch haben. Die Fälle, in denen die Entfernung < = 2 einen vollständigen Scan des Suchbereichs erfordert, 3000 Vergleiche pro Abfragewort. Unter der Annahme, dass eine gleiche Anzahl von Abfragewörtern 9 Millionen Vergleiche ergeben würde.

Sie erwähnen, dass es Zeitüberschreitung, so vermute ich, dass Sie ein Timeout konfiguriert haben? Könnte Ihre Geschwindigkeit auf eine schlechte oder langsame Implementierung der Levenshtein-Berechnung zurückzuführen sein?

Graph showing visited search space using a bk-tree with different amount of input http://www.students.itu.edu.tr/~yazicivo/bk-tree-report.png Above Graph ist gestohlen von CLiki: bk-tree

Wie zu sehen ist, bk-Baum mit einer Edit-Distanz mit < = 2 nur etwa 1% des Suchraumes würde besuchen, aber das ist vorausgesetzt, dass Sie ein sehr großes haben Eingabedaten, in ihrem Fall bis zu einer halben Million Wörter. Ich würde ähnliche Zahlen in Ihrem Fall annehmen, aber solch eine geringe Menge von Eingaben würde nicht viel Mühe verursachen, selbst wenn sie in einer Liste/einem Wörterbuch gespeichert werden.

Answer 2

Ich werde versuchen, es anders zu formulieren.

Anfangs gibt es 'n' Wörter, die als Dictionary-Wörter definiert sind. Als nächstes werden 'm'-Wörter angegeben, die Query-Wörter sind und für jedes Query-Wort muss ich herausfinden, ob das Wort bereits im Dictionary (Edit Distance' 0 ') oder der Gesamtzahl der Wörter im Dictionary bei Editierdistanz 1 existiert oder 2 aus den Wörterbuchwörtern.

Ich hoffe, die Frage ist jetzt klar.

Nun, es Timeout, wenn die Zeitkomplexität ist (m * n) * n. Die naive Verwendung von DP Edit Distance Algorithm abläuft. Sogar Berechnen der diagonalen Elemente von 2 * k + 1 mal aus, wobei k der Schwellenwert ist, k = 3 im obigen Fall.

PS: BK-Tree sollte den Zweck erfüllen.Jeder Links über die Implementierung in C++.

Answer 3

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()]; 
    } 
}