Informatica

Algoritmi di confronto approssimativo delle stringhe di testo, parte 1

Parte 1, Parte 2

Sommario

• Introduzione
• Codificazione fonetica
  • Soundex
  • Daitch-Mokotoff Soundex
  • Sistema di identificazione e delle informazioni dello stato di New York
  • Metaphone
  • Doppio metaphone
  • Caverphone
• Metrica di somiglianza
  • Distanza di Hamming
  • Distanza di modifiche
  • Trigrammi
  • Riconoscimento delle forme di Ratcliff/Obershelp
  • Jaro-Winkler
  • Errori di dattilografia
• Confronto degli algoritmi
• Risorse

Introduzione

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 che è possibile inviare al seguente indirizzo e-mail: alexandre.rodichevski@chiappani.it.

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

1. Prendere la prima lettera.
2. 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
3. Scartare le lettere adiacenti che hanno lo stesso codice.
4. Scartare A, E, I, O, U, Y, W e H non iniziali.
5. Prendere i primi quattro caratteri riempendo a destra con gli zeri.

Esempi

1. ALEXANDRE → A4E2A536E → A4E2A536E → A42536 → A425.
2. 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

1. Tradurre i primi caratteri del nome:
   MAC → MCC
   PH → FF
   KN → NN
   PF → FF
   K → C
   SCH → SSS
2. Tradurre gli ultimi caratteri del nome:
   EE → Y
   IE → Y
   DT, RT, RD, NT, ND → D
3. 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
4. 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
5. Eliminare la seconda lettera delle lettere doppie.
6. Prendere i primi sei caratteri.

Esempi

1. ALEXANDRE → ALAXANDRA → ALAXANDR → ALAXANDR → ALAXAN
2. 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

1. Eliminare la seconda lettera delle lettere doppie, tranne la C.
2. Se la parola comincia con KN, GN, PN, AE, WR, eliminare la prima lettera.
3. Eliminare la B alla fine della parola dopo la M.
4. C → X in CIA o CH; C → S in CI, CE o CY; C → K altrimenti.
5. D → J in DGE, DGY o DGI; D → T altrimenti.
6. 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.
7. Eliminare H dopo una vocale e se non seguita da una vocale.
8. Eliminare K dopo C.
9. P → F in PH.
10. Q → K.
11. S → X in SH o SIO o SIA.
12. T → X in TIA o TIO; T → 0 in TH; T viene eliminata in TCH.
13. V → F.
14. Se la parola comincia con WH, eliminare H; eliminare W se non èseguita da una vocale.
15. Se la parola comincia con X, allora X → S; X → KS altrimenti.
16. Eliminare Y se non è seguita da una vocale.
17. Z → S.
18. Le vocali sono mantenute soltanto quando sono la prima lettera.
19. In tutti gli altri casi le lettere non cambiano.

Esempi

1. ALEXANDRE → ALEKSANTRE → ALKSNTR
2. 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.

Algoritmi di confronto approssimativo delle stringhe di testo
Parte 1, Parte 2