levenshtein - Editar distancia en Python

levenshtein distance python

Question

Estoy programando un programa de corrección ortográfica en Python. Tengo una lista de palabras válidas (el diccionario) y necesito dar salida a una lista de palabras de este diccionario que tienen una distancia de edición de 2 de una palabra no válida dada.

Sé que debo comenzar generando una lista con una distancia de edición de una de la palabra no válida (y luego volver a ejecutarla en todas las palabras generadas). Tengo tres métodos, inserciones (...), eliminaciones (...) y cambios (...) que deberían generar una lista de palabras con una distancia de edición de 1, donde las inserciones generan 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 las salidas 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 se me han ocurrido implican recorrer la lista del diccionario varias veces, lo que llevaría mucho tiempo. Si alguien pudiera ofrecer alguna idea, estaría extremadamente agradecido.

Answer 1

Aquí está mi versión para Levenshtein distancia

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 2

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

Answer 3

En lugar de ir con Levenshtein distance, use BK tree o TRIE , ya que estos algoritmos tienen menos complejidad que la distancia de edición. Un buen vistazo a este tema le dará una descripción detallada.

Este link te ayudará más sobre el corrector ortográfico.

Answer 4

Lo que estás viendo se llama distancia de edición y aquí hay una buena explicación en wiki . Hay muchas maneras de definir una distancia entre las dos palabras y la que desea que se llame distancia de Levenshtein y aquí hay una implementación 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]

Y un par de implementaciones más están aquí .

Answer 5

Necesita la Distancia de edición mínima para esta tarea.

La siguiente es mi versión de MED aka Levenshtein Distance.

def MED_character(str1,str2):
    cost=0
    len1=len(str1)
    len2=len(str2)

    #output the length of other string in case the length of any of the string is zero
    if len1==0:
        return len2
    if len2==0:
        return len1

    accumulator = [[0 for x in range(len2)] for y in range(len1)] #initializing a zero matrix

    # initializing the base cases
    for i in range(0,len1):
        accumulator[i][0] = i;
    for i in range(0,len2):
        accumulator[0][i] = i;

    # we take the accumulator and iterate through it row by row. 
    for i in range(0,len1):
        char1=str1[i]
        for j in range(0,len2):
            char2=str2[j]
            cost1=0
            if char1!=char2:
                cost1=2 #cost for substitution
            accumulator[i][j]=min(accumulator[i-1][j]+1, accumulator[i][j-1]+1, accumulator[i-1][j-1] + cost1 )

    cost=accumulator[len1-1][len2-1]
    return cost

Answer 6

#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]