Soundex, Metaphone: come funzionano

Ho più volte parlato di queste due funzioni, oramai sappiamo che sono dei codifici fonetici che permettono di indicizzare le stringhe in base alloro suono. Un pò per curiosità, un pò perchè voglio avere sempre tutto sotto controllo mi sono chiesto come realizzano l’hash sonoro di una stringa, anche per capire se e come sono vincolati da una lingua, così dopo un pò di ricerche in rete ho capito le cose che vado a scrivere di seguito.

Iniziamo con il soundex, sappiamo che produce un codice formato da una lettere (la prima della paroloa) e da 3 cifre, ogni cifra rappresenta uno dei sei codici consonantici. La procedura per ottenere il soundex è la seguente:

  • prendiamo la prima lettera, essa come detto rappresenta la prima posizione del soundex
  • quando incontriamo uno dei seguenti caratteri los ostituiamo con il rispettivo valore

B, F, P, V => 1

C, G, J, K, Q, S, X, Z => 2

D, T => 3

L => 4

M, N => 5

R => 6

  • Eliminiamo le lettere adiacenti con lo stesso codice
  • Eliminiamo le lettere A, E, I, O, U, Y, W e H se non sono iniziali
  • Prendiamo i primi 3 numeri ottenuti riempendo eventualmente le posizioni rimanenti con degli zeri

i pro dell’utilizzo del soundex li ho già evidenziati negli altri post, vorreim sottolineare i contro. Il primo inconveniente è che il soundex è stato sviluppato per la lingua inglese (in particolare il contesto è quello statunitense), nella quale il rapporto di corrispondenza tra i suoni ed i simboli scritti è piutosto libero e la fonetica ricopre un ruolo molto importante (lo vedremo con il metaphone). Possiamo però dire che per sua natura o meglio, per la procedura che utilizzare per ottenere l’hash è l’agoritmo che meglio si presta nell’utilizzo con le lingue latine. Il secondo inconveniente è rappresentato dal rapporto stringa estesa caratteri del sounex, ipotizziamo di trattare un indirizzo, per sua natura sarà sicuramente composto da un prefisso (via, viale, piazza ecc), dal nome della via e spesso dal civico (ipotizziamo di non voler separare quest’ultimo dalla stringa). Se decidiamo di non dare peso al prefisso perchè il contenuto informativo più importante è rappresentato dal nome, potremmo trovarci in un caso del tipo

via alessandro volta 3

via volta 3

nel primo caso la parola alesandro ci permette di ottenere un soundex e di conseguenza di non avere traccia della parola volta nello stesso. Nel secondo caso il soundex si forma proprio sulla parola volta, in questo modo il match non avverrà e non potrebbe avvenire neanche utilizzando il metaphone.

Con il metaphone abbiamo 16 suoni consonantici:

B, X (rappresenta il suono Sh), S, K, J, T, F, H, L, M, N, P, R, 0 (inteso come zero e rappresenta il suono Th), W, Y

e segue le seguenti regole:

  • Eliminiamo le doppie cancellando una delle due lettere in tutti i casi tranne che con la C
  • Eliminiamo la prima lettere delle parole che iniziano per KN, GN, PN, AE e WR
  • Eliminiamo la B alla fine della parola dopo la M.
  • Cambiamo le lettere C => X in CIA o CH; C => S in CI, CE o CY; C => K neglia ltri casi
  • Cambiamo le lettere D => J in DGE, DGY o DGI; D => T negli altri casi
  • Eliminiamo la G in GH e se non si trova alla fine della parola o prima di una vocale in GN o GNED; G => J prima di I o E o Y se non doppia GG; G → K negli altri casi
  • Eliminiamo H dopo una vocale e se non seguita da una vocale
  • Eliminiamo K dopo C
  • Cambiamo:

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 eliminiamo H; eliminiamo W se non èseguita da una vocale
  • Se la parola comincia con X, X => S; X => KS negli altri casi
  • Eliminiamo Y se non è seguita da una vocale
  • Z => S
  • Le vocali restano solo quando si trovano nella prima posizione

come possiamo notare è estremamente legato alla fonetica della lingua inglese e ciò rende meno duttile. Risulta inoltre sensibile al problema evidenziato per il soundex (“eccesso” di caratteri…) nel suo caso a causa del numero variabile di caratteri che formano l’hash.

Annunci

Fonetica nel pattern matching con php #2: ridondanza e distanza di Levenshtein

Tempo fa vi ho parlato delle funzioni soundex e metaphone per utilzzare una verifica vocale nel matching tra stringhe di testo. Personalmente dopo alcuni test avevo riscontrato una buona affidabilità di soundex, sono però poi stato smentito, mi è capitato il caso:

via ennio quirino visconti

via m. carucci

soundex mi forniva lo stesso hash mentre sono palesemente differenti, come fare dunque? Dopo alcune prove in cui provavo a capire cosa potesse influenzare il calcolo di soundex ho deciso di provare metaphone.

Metaphone produce un hash variabile (prima differenza con soundex) generato conoscendo le regole di pronuncia della lingua inglese inglese (seconda differenza); le parole utilizzate non sono solo inglesi quindi l’hash potrebbe essere non completamente corretto anche perchè la lingua inglese ha molti termini con una pronuncia simile se non uguale però se serve un hash che non varia per cambiamenti minimi della parola, potrete come sto provando io, provare a concatenare gli effetti di soundex e metaphone per avere un unico hash sicuramente più affidabile del solo soundex.

Per controlli più accurati si può utilizzare la distanza di Levenshtein ovvero il numero minimo (distanza di caratteri) di operazioni (rimozione, aggiunta, spostamento ed eliminazione) che servono per uguagliare due stringhe. In PHP vi è l’omonima funzione:

int levenshtein ( string str1, string str2 [, int cost_ins [, int cost_rep, int cost_del]] )

questa funzione è molto utile e versatile, penso che con un controllo incrociato tra gli hash prodotti dalle funzioni soundex-metaphone e dalla distanza di Levenshtein si può ottenere un buon risultato.

Fonetica nel pattern matching con php

In questo periodo per lavoro mi sto scontrando con problemi che riguardano il matrching tra stringhe. Gli strumenti per la manipolazione delle stringhe che il php mette a disposizione sono diversi, tutti molto efficaci a seconda dei casi.

Ci sono casi in cui le normali operazioni di confronto e sostituzione tra stringhe e caratteri non bastano, così ci viene in aiuto la fonetica. Le funzioni che il php ci mette a disposizione sono metaphone e soundex. Entrambe calcolano una chiave per ogni suono uguale, ovvero fornisce un impronta derivata dalla pronuncia della parola. Metaphone fornisce una chiave secondo la pronuncia inglese della parola ed ha una lunghezza variabile, essa è formata dalla prima lettera della parola e da un numero con diverse cifre. Soundex fornisce una chiave dello stesso tipo di metaphone ma di 4 caratteri, il primo carattere è la prima lettera della parola, poi ci sono 3 cifre che rappresentano il risultato dell’operazione.

Per meglio comprendere l’utilità di queste funzioni vediamo alcuni esempi:

<?
echo "\n".soundex("Viale Marconi")." ". soundex("V.le marconi");
?>

con un normale confronto le due stringhe risulterebbero differenti sfalsando dunque qualche vostro controllo, soundex invece ci fornirà due chiavi del tipo V… e V… dove al posto dei … ci sono dei numeri, uguali perchè foneticamente le due parole sono molto vicine.