10
votes

Python: comparer deux cordes

J'aimerais savoir s'il y a une bibliothèque qui me dira approximativement à quel point deux cordes similaires sont

Je ne cherche rien de spécifique, mais dans ce cas: P>

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

string python

1 commentaires

Dupliqué possible de Algorithme de différence de texte

4 Réponses :

6
votes

Rechercher Levenshtein algorithme pour comparer des chaînes. Voici une implémentation aléatoire trouvée via Google: http://hetland.org/coding/python/levenshtein. py

0 commentaires

7
votes

http://fr.wikipedia.org/wiki/levenshtein_distance

Il y a quelques bibliothèques sur PYPI , mais soyez conscient que cela est cher, surtout pour des chaînes plus longues.

Vous voudrez peut-être également consulter le difffffib de Python: http://docs.python.org/ Bibliothèque / DIFFLIH.HTML

2 commentaires

cher? DIFFLIB est un monstre par rapport aux implémentations de Levenshtein semi-décentes.

Mon intention n'a pas eu l'intention de suggérer que DIFFLIH est moins chère - cela fait une chose similaire, bien que peu différente.

21
votes

import difflib

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

0.89473684210526316

0 commentaires

1
votes

Autre moyen est d'utiliser la plus longue sous-chaîne commune. Ici, une implémentation dans DaniWeb avec ma mise en œuvre de la LCS (ceci est également définie dans DIFFLIB)

Voici une seule ligne de longueur uniquement avec la liste comme structure de données: p>

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

0 commentaires