Изменить расстояние в Python

Я программирую программу проверки орфографии в Python. У меня есть список допустимых слов (словарь), и мне нужно вывести список слов из этого словаря, у которых есть расстояние редактирования 2 от данного недопустимого слова.

Я знаю, что мне нужно начать с создания списка с расстоянием редактирования от недопустимого слова (а затем снова запустить его для всех сгенерированных слов). У меня есть три метода: inserts (...), delete (...) и изменения (...), которые должны выводить список слов с расстоянием редактирования 1, где inserts выводит все действительные слова с еще одной буквой, данное слово, удаления выводит все действительные слова с одной буквой и изменяет вывод всех допустимых слов с помощью одной другой буквы.

Я проверил множество мест, но я не могу найти алгоритм, описывающий этот процесс. Все идеи, которые я придумал, включают в себя цикл через список словарей несколько раз, что было бы чрезвычайно трудоемким. Если бы кто-нибудь мог предложить некоторое понимание, я был бы чрезвычайно благодарен.

Ответ 1

То, что вы смотрите, называется расстоянием редактирования, и вот хорошее объяснение в вики. Существует множество способов определить расстояние между двумя словами и тем, что вы хотите, называется расстоянием Левенштейна, и здесь реализована реализация DP в 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]

И пара дополнительных реализаций находится здесь.

Ответ 2

Вот моя версия для расстояния Левенштейна

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"))

Ответ 3

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

Ответ 4

Определенный вами алгоритм называется расстоянием Левенштейна. Быстрый Google выдает несколько библиотек и рецептов Python для его расчета.

Ответ 5

Вам нужно Минимальное расстояние редактирования для этой задачи.

Ниже приводится моя версия MED ака 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(1,len1):
        char1=str1[i]
        for j in range(1,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

Ответ 6

difflib в стандартной библиотеке есть различные утилиты для сопоставления последовательностей, включая метод get_close_matches который вы можете использовать. Он использует алгоритм, адаптированный из Ratcliff и Obershelp.

Из документов

from difflib import get_close_matches

# Yields ['apple', 'ape']
get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])

Ответ 7

Вместо того, чтобы идти с Levenshtein distance algo, используйте BK tree или TRIE, так как эти алгоритмы имеют меньшую сложность, а затем редактируют расстояние. Хороший обзор по этой теме даст подробное описание.

Эта ссылка поможет вам подробнее про проверку орфографии.