Как я могу найти вариации строк в словаре на расстоянии 1? - PullRequest
Новая
       26

Как я могу найти вариации строк в словаре на расстоянии 1?

0 голосов
/ 11 февраля 2019

Скажем, вы отсканировали документ с именами на нем.Из-за ошибок в процессе сканирования, вы хотите посмотреть имена в словаре.Следовательно, вам нужна функция, которая принимает возможное имя и выводит список со всеми возможными строковыми вариантами ввода в пределах расстояния Левенштейна, равного 1.

Я изменил реализацию (https://rosettacode.org/wiki/Levenshtein_distance#Python), нопока что не получил правильный результат. Поскольку реализации Левенштейна обычно берут две строки и сравнивают их, чтобы выдать int для L-Distance, мне интересно, как изменить это, чтобы получить варианты одной строки? 

def levenshteinVariation(n_possible):


m = n_possible
n = n_correct

d = []           

for i in range(len(m)+1):
    d.append([i])        
del d[0][0]    

for j in range(len(n)+1):
    d[0].append(j)       

for j in range(1,len(n)+1):

    for i in range(1,len(m)+1):

        if m[i-1] == n[j-1]:
            d[i].insert(j,d[i-1][j-1])           

        else:
            minimum = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+2)         
            d[i].insert(j, minimum)

return d

Ожидаемый результат будет совпадением в словаре со всеми вариациями в пределах L-расстояния 1. 

for n_correct, n_possible in [('Marcus','Maacus'), ('David','Davide'), ('Steve', 'Steven')]:
print(f"{n_correct} found: {n_correct in levenshteinVariation(n_possible)}")

Но я получил: 

Marcus found: False
David found: False
Steve found: False

1 Ответ

0 голосов
/ 11 февраля 2019

Благодаря Дэну Д. я смог решить это сам: 

def Variations1(name):

letters    = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

splits     = [(name[:i], name[i:])    for i in range(len(name) + 1)]
deletes    = [L + R[1:]               for L, R in splits if R]
transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R) > 1]
replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]
inserts    = [L + c + R               for L, R in splits for c in letters]

return set(deletes + transposes + replaces + inserts)
...