Python: сравнение двух строк

Question

Я хотел бы знать, есть ли библиотека, которая приблизительно скажет мне, насколько похожи две строки

Я не ищу ничего конкретного, но в этом случае:

a = 'alex is a buff dude'
b = 'a;exx is a buff dud'

можно сказать, что b и a примерно на 90% похожи.

Есть ли библиотека, которая может это сделать?

Answer 1

import difflib

>>> a = 'alex is a buff dude'
>>> b = 'a;exx is a buff dud'
>>> difflib.SequenceMatcher(None, a, b).ratio()

0.89473684210526316

Answer 2

http://en.wikipedia.org/wiki/Levenshtein_distance

На pypi есть несколько библиотек, но имейте в виду, что это дорого, особенно для более длинных строк.

Вы также можете захотетьпроверить difflib Python: http://docs.python.org/library/difflib.html

Answer 3

Ищите Левенштейн алгоритм сравнения строк.Вот случайная реализация, найденная через Google: http://hetland.org/coding/python/levenshtein.py

Answer 4

Другой способ - использовать самую длинную общую подстроку. Здесь реализация в 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')
"""