Я хотел бы знать, есть ли библиотека, которая расскажет мне примерно, как похожие две строки
Я не ищу ничего конкретного, но в этом случае:
a = 'alex is a buff dude'
b = 'a;exx is a buff dud'
можно сказать, что b и a примерно равны примерно 90%.
Есть ли библиотека, которая может это сделать?
import difflib
>>> a = 'alex is a buff dude'
>>> b = 'a;exx is a buff dud'
>>> difflib.SequenceMatcher(None, a, b).ratio()
0.89473684210526316
Ищите алгоритм Левенштейна для сравнения строк. Вот случайная реализация, найденная через Google: http://hetland.org/coding/python/levenshtein.py
http://en.wikipedia.org/wiki/Levenshtein_distance
Есть несколько библиотек на pypi, но имейте в виду, что это дорого, особенно для более длинных строк.
Вы также можете проверить python difflib: http://docs.python.org/library/difflib.html
Другой способ - использовать длинную общую подстроку. Здесь реализация в Daniweb с моей реализацией lcs (это также определено в difflib)
Вот простая версия с единственной версией со списком в виде структуры данных:
def longest_common_sequence(a,b):
n1=len(a)
n2=len(b)
previous=[]
for i in range(n2):
previous.append(0)
over = 0
for ch1 in a:
left = corner = 0
for ch2 in b:
over = previous.pop(0)
if ch1 == ch2:
this = corner + 1
else:
this = over if over >= left else left
previous.append(this)
left, corner = this, over
return 200.0*previous.pop()/(n1+n2)
Вот моя вторая версия, которая фактически дает общую строку с структурой данных deque (также с примером использования данных примера):
from collections import deque
a = 'alex is a buff dude'
b = 'a;exx is a buff dud'
def lcs_tuple(a,b):
n1=len(a)
n2=len(b)
previous=deque()
for i in range(n2):
previous.append((0,''))
over = (0,'')
for i in range(n1):
left = corner = (0,'')
for j in range(n2):
over = previous.popleft()
if a[i] == b[j]:
this = corner[0] + 1, corner[1]+a[i]
else:
this = max(over,left)
previous.append(this)
left, corner = this, over
return 200.0*this[0]/(n1+n2),this[1]
print lcs_tuple(a,b)
""" Output:
(89.47368421052632, 'aex is a buff dud')
"""