Python: Vergleich von zwei Strings

Question

Ich mag würde wissen, ob es eine Bibliothek, die mir etwa erzählen, wie ähnlich zwei Strings sind

ich suche nicht für etwas Bestimmtes, aber in diesem Fall:

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

können wir sagen, dass b und a zu etwa 90% ähnlich sind.

Gibt es eine Bibliothek, die das kann?

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

Suchen Sie nach Levenshtein Algorithmus zum Vergleichen von Zeichenfolgen. Hier ist eine zufällige Implementierung über google gefunden: http://hetland.org/coding/python/levenshtein.py

Answer 3

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

Es gibt ein paar Bibliotheken auf , aber bewusst sein, dass dies teuer ist, vor allem für längere Strings.

Sie können auch difflib auszuchecken Pythons wollen: http://docs.python.org/library/difflib.html

Answer 4

andere Weg ist, längste gemeinsame Teilkette zu verwenden. Hier ist eine Implementierung in Daniweb mit meiner LCS-Implementierung (dies auch in difflib definiert ist)

ist hier einfach Länge nur Version mit der Liste als Datenstruktur:

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) 

Hier ist meine zweite version which actualy gives the common string mit deque Datenstruktur (auch mit dem Anwendungsfall Beispieldaten):

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