Modifier la distance en Python

Question

Je programme un programme de vérification orthographique en Python. J'ai une liste de mots valides (le dictionnaire) et j'ai besoin de sortir une liste de mots de ce dictionnaire qui ont une distance d'édition de 2 à partir d'un mot invalide donné.

Je sais que je dois commencer par générer une liste avec une distance d'édition de un du mot invalide (et ensuite exécuter à nouveau sur tous les mots générés). J'ai trois méthodes, insertions (...), suppressions (...) et changements (...) qui devraient produire une liste de mots avec une distance d'édition de 1, où les insertions sortent tous les mots valides avec une lettre de plus que le mot donné, les suppressions sortent tous les mots valides avec une lettre de moins, et les changements produisent tous les mots valides avec une lettre différente.

J'ai vérifié un tas d'endroits, mais je n'arrive pas à trouver un algorithme décrivant ce processus. Toutes les idées que j'ai imaginées impliquent de parcourir plusieurs fois la liste des dictionnaires, ce qui prendrait énormément de temps. Si quelqu'un pouvait donner un aperçu, je serais extrêmement reconnaissant.

Answer 1

L'algorithme spécifique que vous décrivez s'appelle Levenshtein distance. Un rapide Google lève plusieurs bibliothèques et recettes Python pour le calculer.

Answer 2

#this calculates edit distance not levenstein edit distance 
word1="rice" 

word2="ice" 

len_1=len(word1) 

len_2=len(word2) 

x =[[0]*(len_2+1) for _ in range(len_1+1)]#the matrix whose last element ->edit distance 

for i in range(0,len_1+1): #initialization of base case values 

    x[i][0]=i 
for j in range(0,len_2+1): 

    x[0][j]=j 
for i in range (1,len_1+1): 

    for j in range(1,len_2+1): 

     if word1[i-1]==word2[j-1]: 
      x[i][j] = x[i-1][j-1] 

     else : 
      x[i][j]= min(x[i][j-1],x[i-1][j],x[i-1][j-1])+1 

print x[i][j] 

Answer 3

Voici ma version pour la distance Levenshtein

 
def edit_distance(s1, s2): 
    m=len(s1)+1 
    n=len(s2)+1 

    tbl = {} 
    for i in range(m): tbl[i,0]=i 
    for j in range(n): tbl[0,j]=j 
    for i in range(1, m): 
     for j in range(1, n): 
      cost = 0 if s1[i-1] == s2[j-1] else 1 
      tbl[i,j] = min(tbl[i, j-1]+1, tbl[i-1, j]+1, tbl[i-1, j-1]+cost) 

    return tbl[i,j] 

print(edit_distance("Helloworld", "HalloWorld")) 

Answer 4

La chose que vous êtes à la recherche est appelée une distance d'édition et voici un nice explanation on wiki. Il y a beaucoup de façons de définir une distance entre les deux mots et celle que vous voulez s'appelle distance Levenshtein et voici une implémentation de DP en python.

def levenshteinDistance(s1, s2): 
    if len(s1) > len(s2): 
     s1, s2 = s2, s1 

    distances = range(len(s1) + 1) 
    for i2, c2 in enumerate(s2): 
     distances_ = [i2+1] 
     for i1, c1 in enumerate(s1): 
      if c1 == c2: 
       distances_.append(distances[i1]) 
      else: 
       distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1]))) 
     distances = distances_ 
    return distances[-1] 

Et couple of more implementations are here.

Answer 5

Au lieu d'aller avec la distance algo Levenshtein utilisation arbre BK ou TRIE, car ces algorithmes ont moins de complexité, puis de distance d'édition. Une bonne navigation sur ces sujets donnera une description détaillée.

Cette link vous aidera à mieux vérifier l'orthographe.