python: so sánh hai chuỗi

Question

Tôi muốn biết nếu có một thư viện mà sẽ cho tôi biết khoảng cách tương tự như hai chuỗi là

Tôi không tìm kiếm bất cứ điều gì cụ thể, nhưng trong trường hợp này:

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

chúng tôi có thể nói rằng b và a tương đương khoảng 90%.

Có thư viện nào có thể thực hiện việc này không?

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

Tìm kiếm thuật toán Levenshtein để so sánh chuỗi. Dưới đây là một việc thực hiện ngẫu nhiên tìm thấy qua google: http://hetland.org/coding/python/levenshtein.py

Answer 3

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

Có một vài thư viện trên , nhưng lưu ý rằng đây là tốn kém, đặc biệt là cho các chuỗi dài hơn.

Bạn cũng có thể muốn kiểm tra difflib python của: http://docs.python.org/library/difflib.html

Answer 4

cách khác là sử dụng chuỗi con chung dài nhất. Dưới đây là một thực hiện trong Daniweb với thực hiện LCS của tôi (điều này cũng được định nghĩa trong difflib)

Đây là đơn giản chỉ chiều dài phiên bản với danh sách như cấu trúc dữ liệu:

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) 

Đây là của tôi thứ hai version which actualy gives the common string với cấu trúc dữ liệu deque (còn với các trường hợp sử dụng dữ liệu chẳng hạn):

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') 
"""