Metriche di similitudine di stringhe in Python

Question

Desidero trovare la somiglianza di stringhe tra due stringhe. La pagina This contiene esempi di alcuni di essi. Python ha un'implementazione di Levenshtein algorithm. C'è un algoritmo migliore, (e si spera una libreria python), sotto questi punti di contatto.

1. Voglio fare corrispondenze sfocate tra stringhe. ad esempio le corrispondenze ("Ciao, Tutto il popolo", "Ciao, tutto il tuo popolo") devono restituire True
2. I falsi negativi sono accettabili, i falsi positivi, tranne in casi estremamente rari, non lo sono.
3. Questo viene eseguito in un'impostazione non in tempo reale, quindi la velocità non è (molto) preoccupante.
4. [Modifica] Sto confrontando stringhe di più parole.

Qualcosa di diverso dalla distanza di Levenshtein (o dal rapporto di Levenshtein) sarebbe un algoritmo migliore per il mio caso?

Answer 1

C'è una grande risorsa per le metriche di stringa somiglianza presso l'Università di Sheffield. Ha una lista di varie metriche (oltre a Levenshtein) e ha implementazioni open-source di esse. Sembra che molti di loro dovrebbero essere facili da adattare a Python.

http://web.archive.org/web/20081224234350/http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

Ecco un po 'della lista:

• distanza di Hamming
• Levenshtein distanza
• Needleman-Wunch distanza o venditori Algoritmo
• e molti altri ...

Answer 2

E 'questo che intendi?

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy']) 
['apple', 'ape'] 
>>> import keyword 
>>> get_close_matches('wheel', keyword.kwlist) 
['while'] 
>>> get_close_matches('apple', keyword.kwlist) 
[] 
>>> get_close_matches('accept', keyword.kwlist) 
['except'] 

sguardo http://docs.python.org/library/difflib.html#difflib.get_close_matches

Answer 3

Mi rendo conto che non è la stessa cosa, ma questo è abbastanza vicino:

>>> import difflib 
>>> a = 'Hello, All you people' 
>>> b = 'hello, all You peopl' 
>>> seq=difflib.SequenceMatcher(a=a.lower(), b=b.lower()) 
>>> seq.ratio() 
0.97560975609756095 

si può fare questo in funzione

def similar(seq1, seq2): 
    return difflib.SequenceMatcher(a=seq1.lower(), b=seq2.lower()).ratio() > 0.9 

>>> similar(a, b) 
True 
>>> similar('Hello, world', 'Hi, world') 
False 

Answer 4

userei Levenshtein distanza, o il cosiddetto distanza Damerau (che prende in considerazione le trasposizioni) piuttosto che le cose difflib per due motivi (1) "abbastanza veloce" (programmazione dinamica algo) e "whoooosh" (bit-bashing) Il codice C è disponibile e (2) comportamento ben compreso ad es. Levenshtein soddisfa la disuguaglianza triangolare e quindi può essere utilizzato ad es. un albero di Burkhard-Keller.

Soglia: si dovrebbe considerare "positivo" solo quei casi in cui la distanza < (1 - X) * max (len (stringa1), len (stringa2)) e regolare X (il fattore di somiglianza) in base alle proprie esigenze. Un modo per scegliere X è ottenere un campione di partite, calcolare X per ciascuna, ignorare i casi in cui X < dice 0.8 o 0.9, quindi ordinare il resto in ordine decrescente di X e eye-ball e inserire il risultato corretto e calcolare un po ' misura del costo degli errori per vari livelli di X.

NB L'esempio di ape/mela ha la distanza 2, quindi X è 0,6 ... Io userei solo una soglia a partire da 0.75 se cercassi disperatamente qualcosa e avessi un'alta penalità falsa-negativa

Answer 5

So che questo non è lo stesso ma puoi regolare il rapporto per filtrare stringhe che non sono abbastanza simili e restituire la corrispondenza più vicina al stringa che stai cercando.

Forse sareste più interessati alle metriche di simmetria semantica.

https://www.google.com/search?client=ubuntu&channel=fs&q=semantic+similarity+string+match&ie=utf-8&oe=utf-8

mi rendo conto che hai detto la velocità non è un problema, ma se si sta elaborando un sacco di corde per il vostro algoritmo il sotto è molto utile.

def spellcheck(self, sentence): 
    #return ' '.join([difflib.get_close_matches(word, wordlist,1 , 0)[0] for word in sentence.split()]) 
    return ' '.join([ sorted({ Levenshtein.ratio(x, word):x for x in wordlist }.items(), reverse=True)[0][1] for word in sentence.split() ]) 

È circa 20 volte più veloce di difflib.

https://pypi.python.org/pypi/python-Levenshtein/

importazione Levenshtein

Answer 6

Questo frammento calcolerà il difflib, valori di similarità Levenshtein, Sørensen, e Jaccard per due stringhe. Nello snippet seguente, stavo ripetendo un tsv in cui le stringhe di interesse occupavano le colonne [3] e [4] del tsv. (pip install python-Levenshtein e pip install distance):

import codecs, difflib, Levenshtein, distance 

with codecs.open("titles.tsv","r","utf-8") as f: 
    title_list = f.read().split("\n")[:-1] 

    for row in title_list: 

     sr  = row.lower().split("\t") 

     diffl = difflib.SequenceMatcher(None, sr[3], sr[4]).ratio() 
     lev  = Levenshtein.ratio(sr[3], sr[4]) 
     sor  = 1 - distance.sorensen(sr[3], sr[4]) 
     jac  = 1 - distance.jaccard(sr[3], sr[4]) 

     print diffl, lev, sor, jac