Mi sono guardato intorno e un metodo semplice è la somiglianza Jaro .
Ecco la mia implementazione approssimativa in Python 3:
import math
def match(s1, s2):
set_of_matches = set.intersection(set(s1), set(s2))
return set_of_matches
def technical_match(s1, s2):
matches = match(s1, s2)
max_distance = math.floor(max(len(s1), len(s2)/2)) - 1
true_list = []
for i in matches:
distance = abs(s1.index(i) - s2.index(i))
if distance <= max_distance:
true_list.append(i)
return true_list
def diff_letters(a,b):
#note - this function comes from an SO answer and is not mine
return sum(a[i] != b[i] for i in range(len(a)))
def transpositions(s1, s2):
t = list(technical_match(s1, s2))
s1_list = []
s2_list = []
for i in s1:
if i in t:
s1_list.append(i)
for i in s2:
if i in t:
s2_list.append(i)
s1 = ''.join(s1_list)
s2 = ''.join(s2_list)
return diff_letters(s1, s2)
def jaro_similarity(s1, s2):
matches = technical_match(s1, s2)
if matches == 0:
return 0
else:
return 1/3*(matches/len(s1) + matches/len(s2) + (matches + transpositions(s1, s2))/matches)
Per riepilogare, match() trasforma le due stringhe in serie e trova la loro intersezione per un elenco di corrispondenze. technical_match() segue quindi la definizione nell'articolo - esamina ogni elemento nell'elenco di corrispondenze e controlla la distanza tra i loro indici in ciascuna stringa e controlla se tale distanza è inferiore alla distanza massima, sempre come definito dall'articolo. Quindi restituisco la lunghezza dell'elenco delle corrispondenze true.
Quindi definiamo il numero di trasposizioni, sempre come nell'articolo. Ciò è leggermente confuso, ma la mia comprensione è stata migliorata dalla discussione sulla pagina di discussione dell'articolo.
Quindi calcolo la somiglianza Jaro con la formula semplice fornita nell'articolo. Da lì, possiamo scorrere un file di mock e usarlo per confrontare le stringhe (nota: non è proprio quello che stai cercando, invece di trovare gruppi corrisponde a un modello, ma lavorerò su quello più in seguito):
match_text = open('foobar.txt', 'r').read().splitlines()
pattern = 'hat'
constant = .5
results = []
for i in match_text:
if jaro_similarity(i, pattern) > constant:
results.append(i)
print(results)
Sto ancora controllando i bug, ma finora sembra buono. Due stringhe che sono esattamente le stesse restituiscono una somiglianza jaro di 1.
Puoi pasticciare con il codice qui . Ho fatto una domanda di revisione del codice su questo che può essere trovato qui che ha una risposta favolosa migliorando il mio codice.
Sembra che ci sia effettivamente un pacchetto python che fa esattamente quello che stai cercando.
Vedi fuzzywuzzy ; grazie a Mathias Ettinger su Code Review per averlo indicato! Sembra anche avere porte per alcuni altri linguaggi come Java, Ruby e C.