Quale algoritmo utilizzeresti al meglio per la similarità delle stringhe?

L'algoritmo di Levenstein è basato sul numero di inserimenti, cancellazioni e sostituzioni nelle stringhe.

Purtroppo non tiene conto di un errore ortografico comune che è la trasposizione di 2 caratteri (ad esempio someawesome vs someaewsome). Quindi preferirei l'algoritmo Damerau-Levenstein più robusto .

Non penso che sia una buona idea applicare la distanza su intere stringhe perché il tempo aumenta bruscamente con la lunghezza delle stringhe confrontate. Ma ancora peggio, quando i componenti dell'indirizzo, come ZIP, vengono rimossi, indirizzi completamente diversi possono corrispondere meglio (misurati usando calcolatore Levenshtein online ):

1 someawesome street, anytown, F100 211       (reference) 
1 someawesome st.,anytown                     (difference of 15, same address)     
1 otherplaces street,anytown,F100211          (difference of 13, different ddress) 
1 sameawesome street, othertown, CA98200      (difference of 13, different ddress)
anytown, 1 someawesome street                 (28 different same address)
anytown, F100 211, 1 someawesome street       (37 different same address)

Questi effetti tendono a peggiorare per il nome della via più breve.

Quindi è meglio usare algoritmi più intelligenti. Ad esempio, Arthur Ratz ha pubblicato su CodeProject un algoritmo per il confronto tra testo intelligente . L'algoritmo non stampa una distanza (può certamente essere arricchito di conseguenza), ma identifica alcune cose difficili come lo spostamento di blocchi di testo (ad esempio lo scambio tra città e strada tra il mio primo esempio e il mio ultimo esempio).

Se un algoritmo di questo tipo è troppo generico per il tuo caso, dovresti davvero lavorare con i componenti e confrontare solo componenti comparabili. Questa non è una cosa facile se vuoi analizzare qualsiasi formato di indirizzo nel mondo. Ma se l'obiettivo è più specifico, dicono gli Stati Uniti, è certamente fattibile. Ad esempio, "street", "st.", "Place", "plazza" e le loro usuali errori ortografici potrebbero rivelare la parte di strada dell'indirizzo, la cui parte principale sarebbe in linea di massima il numero. Il codice postale potrebbe aiutare a localizzare la città, o in alternativa è probabilmente l'ultimo elemento dell'indirizzo, o se non ti piace indovinare, potresti cercare un elenco di nomi di città (ad esempio il download di un database di codice postale gratuito). È quindi possibile applicare Damerau-Levenshtein solo sui componenti rilevanti.

La distanza di Levenshtein è migliore per le parole

Se le parole sono (principalmente) scritte correttamente, guarda sacco di parole . Potrei sembrare un kill over ma TF-IDF e somiglianza del personaggio .

Oppure potresti usare Lucene gratis. Penso che facciano somiglianza con il coseno.

In primo luogo, dovresti analizzare la pagina web per gli indirizzi, RegEx è uno scritto da prendere, tuttavia può essere molto difficile analizzare gli indirizzi usando RegEx. Probabilmente finirai per dover consultare un elenco di potenziali formati di indirizzamento e una grande o più espressioni corrispondenti. Non ho molta familiarità con l'analisi degli indirizzi, ma ti consiglio di dare un'occhiata a questa domanda che segue una linea di pensiero simile: Parser di indirizzi generici per testo libero.

La distanza di Levenshtein è utile, ma solo dopo aver separato l'indirizzo nelle sue parti. Considera i seguenti indirizzi. 123 someawesome st. e 124 someawesome st. Questi indirizzi sono posizioni completamente diverse, ma la loro distanza di Levenshtein è solo 1. Questo può essere applicato anche a qualcosa come 8th st. e 9th st. I nomi di strade simili non appaiono tipicamente sulla stessa pagina web, ma non è inaudito. La pagina web di una scuola potrebbe avere l'indirizzo della biblioteca dall'altra parte della strada, per esempio, o la chiesa a pochi isolati più in basso. Ciò significa che l'unico dato che la distanza di Levenshtein è facilmente utilizzabile è la distanza tra 2 punti dati, come la distanza tra la strada e la città.

Per capire come separare i diversi campi, è piuttosto semplice una volta che otteniamo gli indirizzi da soli. Fortunatamente la maggior parte degli indirizzi ha formati molto specifici, con un po 'di magia RegEx dovrebbe essere possibile separarli in diversi campi di dati. Anche se l'indirizzo non è formattato bene, c'è ancora qualche speranza. Gli indirizzi seguono sempre (quasi) l'ordine di grandezza. Il tuo indirizzo dovrebbe trovarsi da qualche parte su una griglia lineare come questa, a seconda di quante informazioni sono fornite e di cosa si tratta:

StreetNumber < Street < City < State < Country

Succede raramente, se per niente l'indirizzo salta da un campo a uno non adiacente. Molto spesso non vedrai Street, Country o StreetNumber poi City.

Chiedete degli algoritmi di similarità delle stringhe ma le vostre stringhe sono indirizzi. Vorrei inviare gli indirizzi a un'API di ubicazione come Ricerca Google Place e utilizzare formatted_address come punto di confronto. Sembra l'approccio più preciso.

Per le stringhe di indirizzo che non possono essere localizzate tramite un'API, potresti quindi ricorrere agli algoritmi di similarità.

Un algoritmo interessante che è utile ma richiede un database preimpostato di risposte precedenti è chiamato: Line edit distance.

La distanza di modifica della linea, come funzione, può restituire "quanto diverse sono queste due parole".

Una parola come "dogma" e "cane", otterrai un valore di 3 (per 3 caratteri extra).

O "cat" e "hat", recupera un valore di 1 (per un carattere diverso).

(Fonte: link )

In effetti usare una funzione di distanza sembra un buon approccio. Ma il problema è trovare la stringa più vicina da un dato indirizzo, che è tutt'altro che banale.

Stai descrivendo un'ampia categoria di algoritmi qui. Controlla Ricerca vicino più vicino

Come menzionato in un commento, se trovi un modo per separare i componenti dell'indirizzo (nome della via, numero, ecc.), renderà il compito molto più facile.

LongestCommonSubsequence (da Apache commons-text) può essere un altro approccio per provare con gli indirizzi. Se definisci la similarità di due come rapporto tra " lunghezza / lunghezza massima comune (lunghezza degli indirizzi) ", puoi applicare la soglia di tolleranza, ad es. 0.8 che definirà la corrispondenza / nessuna corrispondenza. In questo modo ti consentirà di abbinare indirizzi come " 1 someawesome st., Anytown " e " 1 street someawesome., Anytown ".

Non è un algoritmo super veloce, quindi potresti voler applicare dei failback rapidi per minimizzare i confronti. Esempio: evitare il confronto se i codici postali non corrispondono, oppure la sequenza con le cifre estratte è diversa.