pitón: comparar dos cadenas

Question

me gustaría saber si hay una biblioteca que me diga aproximadamente la similitud de dos cadenas son

No estoy buscando algo específico, pero en este caso:

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

podríamos decir que b y a son aproximadamente 90% similares.

¿Hay alguna biblioteca que pueda hacer esto?

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

Busque el algoritmo Levenshtein para comparar cadenas. He aquí una aplicación aleatoria encontrado a través de Google: http://hetland.org/coding/python/levenshtein.py

Answer 3

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

Hay algunas bibliotecas en , pero tenga en cuenta que esto es caro, especialmente para las cadenas más largas.

También es posible que desee comprobar hacia fuera difflib de pitón: http://docs.python.org/library/difflib.html

Answer 4

Otra forma es utilizar subcadena más larga común. Aquí una implementación en Daniweb con mi aplicación LCS (esto también se define en difflib)

aquí es simple longitud única versión con la lista como estructura de datos:

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) 

aquí es mi segundo version which actualy gives the common string con estructura de datos deque (también con el caso de uso de datos de ejemplo):

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