Newsgroup: it.comp.programmare
Titolo: Cercare la somiglianza dei nomi

Ciao a tutti!
Spero di essere nel NG giusto...
Ordunque, il mio problema e' il seguente: ho un DB con dei nomi di
persone. Quando inserisco un nuovo nome devo controllare se esso gia' non
esiste.
E fin li non ci sarebbe problema, se ogni nome potesse essere scritto
sempre nello stesso modo.
Non e' cosi'! In piu' capita ogni tanto che vengano inseriti nomi scritti
sbagliati...
Son certissimo che esiste un algoritmo che mi permette di confrontare due
nomi e dirmi la somiglianza, solo che non so qual'e'... :)
Qualcuno mi puo' aiutare?
Tanto per fare un po' di esempi:
Hans-Georg Müller potrebbe essere lo stesso di H.G. Müller o di H. Georg
Mueller o cosi' via.
Se poi aggiungiamo i nomi scritti originariamente in lingue con alfabeti
non latini, le cose diventano piu' differenti ancora...
Osama si puo' scrivere Usama, Ussama, Osama, etc.
Muhammad si puo' scrivere Mohamed, Mohammed, Muhammed, Muhammad, Mohammad,
etc. etc. etc...
Qualcuno sa suggerirmi un modo per trovare queste somiglianze e dire, con
una ragionevole sicurezza che H.G. Mueller e' probabilmente gia' inserito
come Hans-Georg Müller o che Muhammad bin Assalem bin Usama e' gia'
inserito come M. Assalem bin Osama?
Grazie mille
Luca Bertoncello
(
luca...@lucabert.de
)
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

inserito come M. Assalem bin Osama?
Questo genere di algoritmi fornisce, come è facile capire, solo le
possibili collisioni: è possibile che Mueller e Müller siano lo stesso
nome, ma potrebbero essere anche due nomi diversi.
Hanno evidentemente una loro utilità, ma non risolvono una volta per tutte
il problema.
La cosa migliore è definire un protocollo preciso per la scrittura dei
nomi: inserire i nomi sempre per esteso, seguire sempre la stessa
transilitterazione,... Su un database già costituito, forse prima è meglio
uniformare la scrittura sulla base di regole ben precise, poi cercare
eventuali duplicati.
Ciao.

 eventuali duplicati.
Purtroppo non e' possibile...
I dati non li scrivo io... son gia' li e io devo normalizzarli e segare i
duplicati...
Idee?
Grazie


Idee?
Documentazione su Soundex e Metaphone la puoi trovare in rete. Puoi anche
guardare gli algoritmi utilizzati da Aspell e Ispell per suggerire i
vocaboli.
Una ricerca su "string metric", "similarity metric algorithms" e
"approximate string-matching algorithms" può fornirti ulteriori
riferimenti. Già partendo dalla voce "string metric" di Wikipedia
(
http://en.wikipedia.org/wiki/String_metrics
) puoi trovare una lista di
algoritmi.
Puoi anche tentare qualche accrocchio artigianale, a volte anche un
approccio ingenuo può dare risultati utili. Non è difficile costruire un
qualche genere di hashing che indicizzi le stringhe, si può provare a
partire da lì.
Ciao.

 algoritmi.
Allora, ho dato un'occhiata a quella pagina di Wikipedia e, sopratutto,
alla distanza di Levenshtein.
A naso, direi che gia' trovare i nomi che abbiano una distanza di
Levenshtein piuttosto bassa e' un'idea. Poi si presentano questi nomi
all'operatore che sceglie se e' un duplicato o se e' un nome nuovo.
Il problema, ora, e' l'implementazione...
Diciamo che possiamo eliminare subito il caso in cui il nome da inserire
e' scritto esattamente uguale nel DB. Si risolve con una semplice SELECT e
non ci si pensa piu'.
Il problema si presenta quando quella SELECT non ritorna risultati.
Li devo cercare se esistono gia' nomi simili (con bassa distanza).
Pero' non posso mettermi a scansire TUTTI i record nel DB (si parla di
milioni di dati!!) ogni volta.
Hai qualche suggerimento?
Ciao


vocaboli.
Guarda anche Lucene: 
http://lucene.apache.org/java/docs
http://today.java.net/pub/a/today/2005/08/09/didyoumean.html
Ciao.

Hai qualche suggerimento?
L'argomento mi ha sempre appassionato da un punto di vista teorico, ma non
me ne sono mai occupato praticamente, quindi non sono in grado di aiutarti
nell'implementazione della cosa.
So che tutti i correttori ortografici si basano sulla costruzione di un
indice, che può essere anche piuttosto onerosa; la ricerca sull'indice è
poi molto efficiente. Sul come costruire l'indice però non sono in grado di
aiutarti: immagino che, mettendo la metrica scelta in un algoritmo per la
generazione, per esempio, di un albero binario, o di un indice hash,
qualcosa ne debba saltar fuori, ma in dettaglio non saprei come fare.
Ciao.


http://portal.acm.org/citation.cfm?id=998688.1007121
Finora non ho trovato nulla che possa essere usato immediatamente.
Ciao.

 Mueller o cosi' via.
Si suppone che un nominativo non debba contenere punti ne' lettere 
isolate o iniziali. Una query SQL con la clausola "nominativo LIKE '%.%' 
OR nominativo LIKE '% _ %' OR nominativo LIKE '_ %'" ti estrae i record 
errati, che correggerai a mano o farai correggere a chi li ha inseriti.
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila