Editar Distancia en Python

Question

Estoy programando un programa de revisión ortográfica en Python. Tengo una lista de palabras válidas (el diccionario) y necesito generar una lista de palabras de este diccionario que tengan una distancia de edición de 2 desde una palabra inválida dada.

Sé que necesito comenzar por generar una lista con una distancia de edición de uno de la palabra no válida (y luego ejecutar eso de nuevo en todas las palabras generadas). Tengo tres métodos, inserts (...), eliminaciones (...) y cambios (...) que deberían generar una lista de palabras con una distancia de edición de 1, donde inserts genera todas las palabras válidas con una letra más que la palabra dada, eliminaciones genera todas las palabras válidas con una letra menos, y cambia todas las palabras válidas con una letra diferente.

He revisado un montón de lugares pero parece que no puedo encontrar un algoritmo que describa este proceso. Todas las ideas que he propuesto implican recorrer varias veces la lista del diccionario, lo que llevaría mucho tiempo. Si alguien pudiera ofrecer alguna idea, estaría extremadamente agradecido.

Answer 1

El algoritmo específico que describes se llama distancia Levenshtein. Un Google rápido arroja varias bibliotecas y recetas de Python para calcularlo.

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

Aquí es mi versión de la distancia 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

Lo que busca en una edición que se llama distancia y aquí hay una nice explanation on wiki. Hay muchas maneras de definir una distancia entre las dos palabras y la que usted quiere se llama distancia Levenshtein y aquí hay una implementación 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] 

Y un couple of more implementations are here.

Answer 5

En vez de ir con la distancia Levenshtein algo utilización árbol BK o TRIE, ya que estos algoritmos tienen una menor complejidad a continuación, distancia de edición. Una buena navegación sobre estos temas dará una descripción detallada.

Este link le ayudará a obtener más información sobre la corrección ortográfica.