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

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

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

Answer 3

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

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

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

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) 

Вот мой второй version which actualy gives the common string со структурой 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') 
"""