python вычислить близость строк

Question

Я хочу сравнить строковые представления 3 или 4-значных целых чисел. Я хочу сгруппировать их в пары «близости». То есть, pc_dud[3] должен сочетаться с dud[0].

dud = ['3433', '3467', '3551', '345', '345', '3613'] 
pc_dud = ['3401', '3402', '3430', '0342', '3584'] 

Кто-нибудь знает о хорошем инструменте для этого (я думал, что-то вроде медузы)? Другим решением, конечно же, было бы использование арифметической разницы в качестве индикатора «близости». Есть предположения?

Answer 1

Вы можете использовать difflib модуль:

Пример:

>>> import difflib 
>>> dud = ['3433', '3467', '3551', '345', '345', '3613'] 
>>> pc_dud = ['3401', '3402', '3430', '0342', '3584'] 
>>> difflib.get_close_matches(dud[0], pc_dud) 
['3430'] 

Answer 2

Один подход может принять это вычислить Levenshtein Distance между каждой целочисленной строки в рвань по сравнению с каждой целочисленной строки в pc_dud. Этот алгоритм даст вам расстояние редактирования между каждой последовательностью чисел. Номер расстояния редактирования указывает минимальное количество шагов, которое потребуется для преобразования данной последовательности в другую последовательность. Он рассматривает вставку, удаление и замену.

Вам понадобится структура данных для хранения результатов редактирования расстояния по сравнению с последовательностью, которую она сравнивала. Затем вы можете исследовать, какое расстояние редактирования является наименьшим, а затем группировать их как пару.

Вот наглядный пример того, как будут выглядеть две последовательности чисел из ваших массивов по сравнению с levenshtein. Я использовал этот инструмент для создания скриншота. http://www.let.rug.nl/kleiweg/lev/

http://imgur.com/OTJia7W

Число в нижнем правом углу это минимальное расстояние редактирования.

Answer 3

Если вы идете на маршрут Левенштейна, как рекомендовал Пол, взгляните на Apache's PyLucene - Я считаю, что FuzzyQuery на Lucene основан на этом.

Answer 4

Если вы ищете арифметическую близость, то pc_dud [3] не будет соответствовать dud [0].

Если вы хотите только сохранить уникальные пары используют это: модуль

dud_ = dud[:] 
pc_dud_ = pc_dud[:] 

while dud_: 
    d1, d2 = min(itertools.product(dud, pc_dud), key=lambda d1,d2: abs(int(d1) - int(d2))) 
    dud_.remove(d1) 
    pc_dud_.remove(d2) 
    print d1, d2