У меня есть список строк small_list = ['string1', 'this is string 2', ...] и больший список строк big_list = ['is string 2', 'some other string 3', 'string 1', ...]. Я хочу найти строку, ближайшую по расстоянию редактирования для всех строк в small_list в big_list.
Я нашел это который делает то же самое с числами.
Решение 1, которое я пробовал:
from difflib import get_close_matches
import datetime
a = datetime.datetime.now()
print(get_close_matches(str(small_list.iloc[0]), big_list.values.astype(str), n=3, cutoff=0.7))
b = datetime.datetime.now()
c = b - a
print(c.seconds)
Но для моего набора данных и для этой записи мне потребовалось 834 seconds. len(big_list) = 27989793 и len(small_list) = 9329931, поэтому производительность важнее всего.
Решение 2, которое я пробовал:
s = str(small_list.iloc[0])
a = datetime.datetime.now()
for i in big_list:
m = editdistance.eval(i[0], s)
if m < min:
min = m
i_s = i
b = datetime.datetime.now()
c = b - a
print(c.seconds)
Для этого я использовал пакет editdistance, который эффективно реализован на C++, и я получил время 48 секунд. .
Чтобы улучшить приведенные выше решения, я требую, чтобы я не перебирал все значения в big_list. Я ищу способы сделать то же самое.
Один из подходов, который я придумал, заключался в создании дерева (или своего рода дерева суффиксов) с конкатенированным списком строк big_list и запросом, который пытается найти совпадения. Из-за отсутствия опыта в этом я надеялся на некоторые предложения пакетов или код, с которого я мог бы начать. Другим подходом может быть изменение алгоритма KNN, который использует расстояние редактирования в качестве метрики. Любые sklearn или другие пакеты, которые делают это?
Ожидаемый результат: [3, 1, ...], которые являются позициями ближайшего совпадения в big_list.
