Oggigiorno i computer conservano una quantità enorme di dati. Tuttavia il recupero delle informazioni testuali è difficile quando è errata o non nota l’ortografia. Questo articolo è dedicato agli algoritmi per il confronto approssimativo delle stringhe di testo e fornisce una descrizione semplice ma chiara degli algoritmi, corredandola con alcuni esempi.
In primo luogo spiegheremo le procedure che costruiscono i codici fonetici per il testo cercato che suona in modo identico, ma è scritto diversamente. Quindi spiegheremo le procedure che forniscono diversi tipi di metrica testuale di somiglianza usate in una ricerca che tollera gli errori. In conclusione, verranno confrontate le procedure affinché il lettore possa scegliere quella più adatta. In fondo all’articolo si trovano le risorse.
Sono graditi commenti e domande.
Codificazione fonetica
Le procedure qui presentate vengono utilizzate per semplificare le ricerche nei database nei casi in cui si sa come il testo viene pronunciato ma non come viene scritto. A questo scopo vengono costruiti i codici fonetici per il testo cercato, mentre il database viene preventivamente indicizzato usando tali codici. I cognomi che hanno la stessa pronuncia ma diversa scrittura, come SMITH e SMYTH, hanno lo stesso codice e possono essere archiviati insieme. L’uso dei codici fonetici riduce i problemi di abbinamento quando il testo è scritto con gli errori o in modo differente.
I codici fonetici sono molto utili per abbinare le liste dei nomi personali o delle denominazioni delle imprese. Inoltre sono usati per il riconoscimento vocale e nei motori di ricerca dei database come quelli dell’antiterrorismo.
Soundex
Soundex costruisce codici fonetici per i nomi personali. Il codice è costituito di una lettera e di tre cifre, ogni cifra corrispondente ad uno di sei suoni consonantici. La procedura è stata applicata per la prima volta nel censimento degli Stati Uniti del 1880.
Procedura
- Prendere la prima lettera.
- Tradurre i restanti caratteri:
B, F, P, V → 1
C, G, J, K, Q, S, X, Z → 2
D, T → 3
L → 4
M, N → 5
R → 6 - Scartare le lettere adiacenti che hanno lo stesso codice.
- Scartare A, E, I, O, U, Y, W e H non iniziali.
- Prendere i primi quattro caratteri riempendo a destra con gli zeri.
Esempi
- ALEXANDRE → A4E2A536E → A4E2A536E → A42536 → A425.
- ALEKSANDER → A4E22A53E6 → A4E2A53E6 → A42536 → A425.
Daitch-Mokotoff Soundex
Nel 1985 la nuova procedura Daitch-Mokotoff Soundex è stata applicata per codificazione fonetica dei cognomi slavici o yiddish con simile pronuncia ma differente scrittura. I miglioramenti più importanti sono i seguenti: il codice si compone di sei caratteri; ci sono due codici differenti quando un nome ha due pronunce possibili; il codice si compone di dieci cifre da 0 a 9.
Sistema di identificazione e delle informazioni dello stato di New York
L’algoritmo del Sistema di identificazione e delle informazioni dello stato di New York (NYSIIS – New York State Identification and Intelligence System) è stato sviluppato nel 1970 attraverso una rigorosa analisi empirica. In questo algoritmo viene costruito un codice fonetico fino a 6 lettere.
Procedura
- Tradurre i primi caratteri del nome:
MAC → MCC
PH → FF
KN → NN
PF → FF
K → C
SCH → SSS - Tradurre gli ultimi caratteri del nome:
EE → Y
IE → Y
DT, RT, RD, NT, ND → D - Tradurre i restanti caratteri utilizzando le seguenti regole, avanzando ogni volta di un carattere:
EV → AF; altri E, I, O, U → A
Q → G
Z → S
M → N
KN → N; altri K → C
SCH → SSS
PH → FF
H → il carattere precedente, se il precedente o il successivo non sono una vocale
W → il carattere precedente, se il precedente è una vocale - Controllare l’ultimo carattere:
se l’ultimo carattere è S, rimuoverlo
se gli ultimi caratteri sono AY, sostituirli con Y
se l’ultimo carattere è A, rimuoverlo - Eliminare la seconda lettera delle lettere doppie.
- Prendere i primi sei caratteri.
Esempi
- ALEXANDRE → ALAXANDRA → ALAXANDR → ALAXANDR → ALAXAN
- ALEKSANDER → ALACSANDAR → ALACSANDAR → ALACSANDAR → ALACSA
Metaphone
L’algoritmo codifica foneticamente le parole riducendole a 16 suoni consonantici: B, X, S, K, J, T, F, H, L, M, N, P, R, 0, W, Y. Zero rappresenta il suono “Th”; X sta per “Sh”.
Procedura
- Eliminare la seconda lettera delle lettere doppie, tranne la C.
- Se la parola comincia con KN, GN, PN, AE, WR, eliminare la prima lettera.
- Eliminare la B alla fine della parola dopo la M.
- C → X in CIA o CH; C → S in CI, CE o CY; C → K altrimenti.
- D → J in DGE, DGY o DGI; D → T altrimenti.
- Eliminare G in GH e se non alla fine o prima di una vocale in GN o GNED; G → J prima di I o E o Y se non doppia GG; G → K altrimenti.
- Eliminare H dopo una vocale e se non seguita da una vocale.
- Eliminare K dopo C.
- P → F in PH.
- Q → K.
- S → X in SH o SIO o SIA.
- T → X in TIA o TIO; T → 0 in TH; T viene eliminata in TCH.
- V → F.
- Se la parola comincia con WH, eliminare H; eliminare W se non èseguita da una vocale.
- Se la parola comincia con X, allora X → S; X → KS altrimenti.
- Eliminare Y se non è seguita da una vocale.
- Z → S.
- Le vocali sono mantenute soltanto quando sono la prima lettera.
- In tutti gli altri casi le lettere non cambiano.
Esempi
- ALEXANDRE → ALEKSANTRE → ALKSNTR
- ALEKSANDER → ALEKSANTER → ALKSNTR
Doppio metaphone
Doppio metaphone (Double metaphone) è la versione migliorata di Metaphone. Questo algoritmo codifica foneticamente le parole riducendole a 12 suoni consonanti. Restituisce due chiavi se una parola ha due pronunce possibili.
Caverphone
La procedura di confronto fonetico Caverphone è stata creata nel progetto Caversham all’università di Otago nella Nuova Zelanda in 2002. La procedura ammette gli accenti presenti nella zona studiata (parte del sud della città di Dunedin in Nuova Zelanda).
Una nuova versione, Caverphone 2.0, è stata sviluppata come un algoritmo fonetico di applicazione più vasta.
Metrica di somiglianza
Le altre procedure presentate qui usano diversi tipi di metrica testuale di somiglianza. Possono essere usate in una ricerca che tollera gli errori.
La maggior parte di quelle procedure calcola la somiglianza di due stringhe come numero fra 0 e 1. Il valore 0 significa che le stringhe sono completamente differenti. Il valore 1 significa la perfetta corrispondenza delle stringhe. I valori intermedi indicano una corrispondenza parziale.
Gli algoritmi che usano metrica testuale di somiglianza sono utili per il controllo ortografico, il riconoscimento vocale, l’analisi del DNA, la rilevazione di plagio, il ritrovamento della differenza fra file e il problema dell’aggiornamento a distanza dello schermo.
Distanza di Hamming
Per due stringhe aventi la stessa lunghezza, la distanza di Hamming (Hamming distance) è il numero di posti in cui le due stringhe hanno caratteri differenti.
Esempi
- Distanza di Hamming da ALEXANDRE a ALEKSANDR è 6 (coincidono solo ALE, gli altri 6 caratteri sono differenti).
Distanza di modifiche
La distanza di modifiche (edit distance) di due stringhe è definita come il numero minimo di inserimenti, di cancellazioni e di sostituzioni richiesti per trasformare la prima stringa nella seconda. La distanza 0 significa che le stringhe sono identiche.
La procedura è stata inventata in 1965 dallo scienziato sovietico Vladimir Levenshtein. Per questo viene chiamata anche distanza Levenshtein.
Ci sono versioni moderne di distanza di modifiche che assegnano pesi differenti agli inserimenti, alle cancellazioni ed alle sostituzioni.
Esempi
- La distanza di modifiche da ALEXANDRE a ALEKSANDER è 4 (sostituire X con K, inserire S dopo K, inserire E dopo D, cancellare E alla fine).
Trigrammi
La somiglianza fra due stringhe è determinata dal numero di triplette di caratteri in comune in entrambe le stringhe. La procedura può essere generalizzata ai n-grammi, dove n=1, 2, …
Le stringhe string1 e string2 sono riempite a sinistra ed a destra da uno spazio. Poi le stringhe si dividono nelle triplette di caratteri (trigrammi). Quindi la somiglianza è calcolata come:
s = 2*m/(a + b).
Qui:
m è il numero di trigrammi in comune
a è il numero di trigrammi nella string1
b è il numero di trigrammi nella string2
Esempi
- La somiglianza di ALEXANDRE e di ALEKSANDER è 2*3 / (9+10) = 0.32 (trigrammi in comune: _AL, ALE, AND).
Riconoscimento delle forme di Ratcliff/Obershelp
L’algoritmo di Ratcliff/Obershelp (Ratcliff/Obershelp pattern recognition) calcola la somiglianza di due stringhe come il numero doppio di caratteri corrispondenti diviso il numero totale di caratteri nelle due stringhe. I caratteri corrispondenti sono quelli nella sottostringa comune più lunga più, ricorsivamente, i caratteri corrispondenti nella restante parte da qualsiasi lato della sottostringa comune.
Esempi
- La somiglianza di ALEXANDRE e di ALEKSANDER è 2 * (3+3+1+1) / (9+10) = 0.84 (corrispondono ALE, AND, E, R).
Jaro-Winkler
La procedura Jaro-Winkler è stata sviluppata nei censimenti degli Stati Uniti ed è stata usata nell’analisi di post-enumerazione.
Date le stringhe string1 e string2, la loro somiglianza è:
s = m/3a + m/3b + (m-t)/3m.
Qui:
m è il numero del caratteri abbinati
a è la lunghezza di string1
b è la lunghezza di string2
t è il numero delle trasposizioni
Due caratteri sono considerati abbinati soltanto se si trovano non più lontano di (max(a, b)/2 – 1). Il primo carattere abbinato di string1 è confrontato con il primo carattere abbinato di string2; il secondo carattere abbinato di string1 è confrontato con il secondo carattere abbinato di string2, ecc. Il numero di caratteri abbinati ma diversi è diviso per due e dà il numero di trasposizioni.
Il metodo migliorato di Jaro-Winkler usa pesi diversi da 1/3. Inoltre penalizza meno alcuni tipi di errori: errori della visualizzazione e dattilografici, errori alla fine delle stringhe.
Esempi
- La somiglianza di ALEXANDRE ed ALEKSANDER è (8/9 + 8/10 + (8-1)/8)/3 = 0.85 (abbinando A, L, E, A, N, D, R, E; 1 trasposizione).
Errori di dattilografia
Ci sono alcuni algoritmi che considerano gli errori derivati dalla digitazione dei tasti errati sulla tastiera: V anziché la B, 6 anziché Y ecc.
Confronto degli algoritmi
La scelta di uno dei seguenti algoritmi di comparazione delle stringhe dipende principalmente dalla natura dell’errore che influenza il testo.
| Algoritmo | Tipo | Quado usare |
|---|---|---|
| Soundex | fonetico | errori ortografici nelle parole inglesi |
| Daitch-Mokotoff | fonetico | cognomi europei scritti diversamente |
| NYSIIS | fonetico | errori ortografici nelle parole inglesi ed alcune straniere |
| Metaphone, Doppio metaphone | fonetico | errori ortografici nelle parole inglesi |
| Caverphone 2.0 | fonetico | errori ortografici nelle parole inglesi |
| Hamming, Distanza di modifiche | somiglianza | errori ortografici localizzati |
| Trigram, n-gram | somiglianza | errori ortografici, testo modificato |
| Ratcliff/Obershelp | somiglianza | errori ortografici, testo modificato |
| Jaro-Winkler | somiglianza | errori ortografici e dattilografici |
Risorse
Segue la bibliografia web in italiano e in inglese:
Risorse in italiano
- Distanza di Levenshtein in Wikipedia, l’enciclopedia libera.
http://it.wikipedia.org/wiki/Distanza_di_Levenshtein - Descrizione di funzioni PHP per manipolare le stringhe: levenshtein, soundex, similar_text e metaphone.
http://www.php.net/manual/it/ref.strings.php
Handbooks, lectures
- The dictionary of algorithms and data structures.
http://www.nist.gov/dads/ - Handbook of algorithms and data structures by Gaston H. Gonnet and Ricardo Baeza-Yates.
http://www.dcc.uchile.cl/~rbaeza/handbook/ - Exact string matching algorithms: lectures of Laboratoire d’Informatique de Rouen, France.
http://www-igm.univ-mlv.fr/~lecroq/string/index.html
Papers
- Soundex reference.
http://www.archives.gov/ - Usage of Soundex and NYSIIS in NameSearch system.
http://www.qas.com/ - Introduction to Daitch-Mokotoff soundex system by Gary Mokotoff.
http://www.avotaynu.com/soundex.html - Description of Caverphone 2.0.
http://caversham.otago.ac.nz/ - Metaphone reference.
http://aspell.sourceforge.net/ - Article by Reinhard Rapp on Trigram method.
http://heise.de/ - Article by Bruce L. Lambert on usage of N-gram and Edit distance in drug naming.
http://www.hc-sc.gc.ca/ - Paper by William E. Winkler and Yves Thibaudeau on Jaro-Winkler string comparator.
http://www.census.gov/srd/papers/pdf/rr91-9.pdf - Articles on Fuzzy string searching, Phonetic algorithm, Soundex, NYSIIS, Metaphone, Daitch-Mokotoff Soundex, Levenshtein distance and Trigram search in Wikipedia, the free encyclopedia.
http://en.wikipedia.org/ - Article on SQL Server 2005 Fuzzy Lookup and Grouping technology on MSDN Magazine.
http://msdn.microsoft.com/
Implementations
- Implementation of Soundex in C.
http://physics.nist.gov/cuu/Reference/soundex.html - Implementation of Metaphone and Double metaphone in Basic, C, Perl, and C++.
http://aspell.sourceforge.net/metaphone/ - Dynamic programming algorithm for Edit distance.
http://www.csse.monash.edu.au/ - Description of PHP string functions levenshtein, soundex, similar_text and metaphone.
http://www.php.net/manual/en/ref.strings.php - Fuzzy Matching & Deduplication SourceGorge project.
http://sourceforge.net/projects/dedupe/