Минимальное расстояние Левенштейна

Question

как найти минимальное расстояние левенштейна в наборе строк.

на вход подается 25 строк, надо определить у какой паре мин расстояние и указать это расстояние

что я делаю:

N = 25
file = open('input.txt')
bio = []
for i in range(N):
    a = file.readline().strip()
    bio.append(a)
distance = 0
min_d = 0
dop_l_1 = []
dop_l_2 = []
for i in bio:
    list_d = []
    for j in range(len(bio)):
        distance = distance_1(i, bio[j])
        list_d.append(distance)
    res = nsmallest(2, list_d)[1]
    ind = list_d.index(res)
    dop_l_1.append((i, bio[ind]))
    dop_l_2.append(res)
    if min(dop_l_2) == 1:
        break
mini = min(dop_l_2)
m = dop_l_2.index(mini)
m_2 = dop_l_1[m]
fout = open('output.txt', 'w')
print(bio.index(m_2[0]) + 1, bio.index(m_2[1]) + 1, mini, file=fout)

считываю данные, беру строку и пробегаюсь по всему массиву строк, нахожу с мин расстоянием и так по кругу. есть ли способ сделать это быстрее ?

Answer 1

Если вес вставки и удаления равен 1, а вес замены равен 2, то вам нужна метрика наибольшей общей подпоследовательности. Ведь замену с весом 2 можно эквивалентно заменить на удаление и вставку. То есть можно просто выкинуть.

Библиотека strsimpy всё это реализует. Можно воспользоваться конкретной метрикой:

from strsimpy.longest_common_subsequence import LongestCommonSubsequence
lcs = LongestCommonSubsequence()
print(lcs.distance('AGCAT', 'GAC'))  # 4
print(lcs.distance('AGCAT', 'AGCT'))  # 1

Или использовать более общей метод взвешенного расстояния Левенштейна:

from strsimpy.weighted_levenshtein import WeightedLevenshtein

def insertion_cost(char):
    return 1.0


def deletion_cost(char):
    return 1.0


def substitution_cost(char_a, char_b):
    return 2.0

weighted_levenshtein = WeightedLevenshtein(
    substitution_cost_fn=substitution_cost,
    insertion_cost_fn=insertion_cost,
    deletion_cost_fn=deletion_cost)
print(weighted_levenshtein.distance('AGCAT', 'GAC'))

БЛОГ НА HUSL

Минимальное расстояние Левенштейна

Ответы (1 шт):