Modifier l'algorithme de distance

Question

J'ai un dictionnaire de 'n' mots donnés et il y a des requêtes 'm' auxquelles répondre. Je veux sortir le nombre de mots dans le dictionnaire qui sont la distance de modifier 1 ou 2. Je veux optimiser le jeu de résultats étant donné que n et m sont à peu près 3000.

Modifier ajouté de réponse ci-dessous:

Je vais essayer de le dire différemment.

Initialement, il y a 'n' mots donnés comme un ensemble de mots du dictionnaire. Les mots 'm' suivants sont donnés qui sont des mots de requête et pour chaque mot de requête, je dois trouver si le mot existe déjà dans Dictionary (Edit Distance '0') ou le nombre total de mots dans le dictionnaire qui sont à la distance d'édition 1 ou 2 à partir des mots du dictionnaire.

J'espère que la question est maintenant claire. Eh bien, il arrive à expiration si la complexité du temps est (m * n) n. L'utilisation naïve de l'algorithme DP Distance Distance expire. Même en calculant les éléments diagonaux de 2k + 1 fois où k est le seuil ici k = 3 dans le cas ci-dessus.

Answer 1

Vous voulez utiliser le Levenshtein distance entre deux mots, mais je suppose que vous le savez puisque c'est ce que disent les balises de la question.

Vous devez parcourir votre liste (hypothèse) et comparer chaque mot de la liste avec la requête en cours que vous exécutez. Vous pouvez construire un BK-tree pour limiter votre espace de recherche, mais cela ressemble à une surcharge si vous avez seulement ~ 3000 mots.

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

Ajouté après modification de la question initiale

Trouver les cas où la distance = 0 serait facile Contient-requêtes si vous avez un cas dictionnaire insensible. Dans les cas où la distance < = 2 nécessiterait un balayage complet de l'espace de recherche, 3000 comparaisons par mot de requête. En supposant qu'une quantité égale de mots de requête aboutirait à 9 millions de comparaisons.

Vous indiquez que cela expire, donc je suppose que vous avez configuré un délai d'expiration? Votre vitesse pourrait-elle être due à une implémentation faible ou lente du calcul de Levenshtein?

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 graphique ci-dessus est volé de CLiki: bk-tree

Comme on le voit, en utilisant bk-arbre avec une distance d'édition < = 2 serait seulement visiter environ 1% de l'espace de recherche, mais cela suppose que vous avez un très grand données d'entrée, dans leur cas jusqu'à un demi-million de mots. J'assumerais des nombres semblables dans votre cas, mais une quantité si faible d'entrées ne causerait pas beaucoup de problèmes même si elles sont stockées dans une liste/dictionnaire.

Answer 2

Je vais essayer de le dire différemment.

Initialement, il y a 'n' mots donnés comme un ensemble de mots du dictionnaire. Les mots 'm' suivants sont donnés qui sont des mots de requête et pour chaque mot de requête, je dois trouver si le mot existe déjà dans Dictionary (Edit Distance '0') ou le nombre total de mots dans le dictionnaire qui sont à la distance d'édition 1 ou 2 à partir des mots du dictionnaire.

J'espère que la question est maintenant claire.Eh bien, il arrive à expiration si la complexité temporelle est (m * n) * n. L'utilisation naïve de l'algorithme DP Distance Distance expire. Même en calculant les éléments diagonaux de 2 * k + 1 fois où k est le seuil ici k = 3 dans le cas ci-dessus.

PS: BK Arbre devrait suffire à l'objectif. Tous les liens sur l'implémentation en 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()]; 
    } 
}