У меня есть список строк small_list = ['string1', 'this is string 2', ...] и большой список строк big_list = ['is string 2', 'some other string 3', 'string 1', ...].Я хочу найти строку, ближайшую по расстоянию редактирования для всех строк в small_list в big_list.
Я нашел this , что аналогично числам.
Решение 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.Я ищу способы сделать то же самое.
Один из подходов, которые я придумал, - это создание trie (или какого-то рода дерева суффиксов) с объединенным списком строк big_list и запросом этого trie.найти совпадения.Из-за нехватки опыта в этом, надеялся на некоторые предложения пакета или некоторый код, с которого я мог бы начать.Другой подход заключается в изменении алгоритма KNN, который использует расстояние редактирования в качестве метрики.Любой sklearn или другие пакеты, которые делают это?
Ожидаемый результат: [3, 1, ...], которые являются позициями ближайшего совпадения в big_list.