Alternativa alla distanza Levenshtein per prefissi/suffissi

Question

Ho un grande database di città che è stato compilato da molte fonti diverse. Sto cercando di trovare un modo per individuare facilmente i duplicati in base al nome della città. La risposta ingenua sarebbe usare la distanza di levenshtein. Tuttavia, il problema con le città è che spesso hanno prefissi e suffissi che sono comuni nel paese sono in

Ad esempio:.

Boulleville vs. Boscherville

Questi sono quasi certamente diverse città. Tuttavia, poiché entrambi terminano con "ville" (ed entrambi iniziano con "Bo") hanno una distanza Levenstein piuttosto piccola.

* Sto cercando un algoritmo a distanza stringa che tenga conto della posizione del carattere per ridurre al minimo l'effetto di prefissi e suffissi pesando le lettere nel mezzo della parola più alte delle lettere alle estremità della parola. *

Probabilmente potrei scrivere qualcosa da solo ma troverei difficile credere che nessuno abbia ancora pubblicato un algoritmo adatto.

Answer 1

Un modo piuttosto semplice per farlo sarebbe semplicemente rimuovere il prefisso e il suffisso comuni prima di eseguire il calcolo della distanza. La distanza assoluta tra le stringhe risultanti sarà la stessa delle stringhe piene, ma quando si prende in considerazione la lunghezza minore, la distanza appare molto più grande.

Inoltre, tenere presente che in generale anche gli errori ortografici più chiari ottengono la prima lettera a destra. È molto probabile, quindi, che e Bowville siano città diverse, anche se la loro distanza L. è solo 1.

Puoi rendere il tuo lavoro molto più semplice, almeno all'inizio, non facendo il calcolo della distanza se due le parole iniziano con le diverse lettere. Probabilmente saranno diversi. Concentrati prima sulla rimozione di duplicati di parole che iniziano con le stesse lettere. Se, dopo, hai ancora un gran numero di potenziali duplicati, puoi affinare la soglia della distanza per esaminare più da vicino le parole che iniziano con lettere diverse.

Answer 2

È simile a stemming nella programmazione in linguaggio naturale.

In questo campo, la radice di una parola viene trovata prima di eseguire ulteriori analisi, ad es.

run => run 
running => run 
runs => run 

(ovviamente le cose come ran non derivano da run. Per questo si può utilizzare un lemmatizer. Ma sto divagando ...). Anche se la derivazione è lungi dall'essere perfetta nella PNL, funziona molto bene.

Nel tuo caso, potrebbe funzionare bene per arginare la città usando regole specifiche per i nomi di città prima di applicare Levenstein. Non sono a conoscenza di un'implementazione incisiva per le città, ma le regole sembrano in apparenza abbastanza semplici.

È possibile iniziare con un elenco di prefissi e un elenco di suffissi (comprese eventuali varianti comuni/ortografia) e rimuovere semplicemente tale prefisso/suffisso prima di controllare la distanza di Levenstein.

Nota a margine, se si dispone di ulteriori informazioni sull'indirizzo (ad esempio un indirizzo postale o un codice postale), esiste un software di normalizzazione degli indirizzi per molti paesi che troveranno la migliore corrispondenza in base agli algoritmi specifici dell'indirizzo.