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.

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.

Web Bug ToDo List: il database

Ho buttato giù abbastanza velocemente la struttura del data base, sicuramente subirà delle modifiche, probabilmente quache tabella non rispetta qualcuna delle forme normali convenzionalmente utilizzare (mi riferisco alle prime 3) quindi potrebbero variare in futuro, sono inoltre in via di realizzazione ulteriori tabelle di grant per la gestione dei privilegi a livello utente, intanto allego il dump del database appena posso lo commenterò e apporterò le eventuali modifiche.

structure.pdf

p.s: sfortunatamente non sono riuscito a linkare il file .sql, non conosco bene wordpress, mi diceva che è un formato non linkabile per problemi di sicurezza, vedremo cosa si può fare

Il primo è andato…

Siamo quasi alla fine di quello che per mercatodellibro.com doveva essere un periodo di fuoco. Così è stato, entrato in funzione nell’attuale versione il 22 Agosto da quel giorno ha gestito l’ecommerce della libreria, tanti utenti hanno deciso di acquistare i testi scolastici in rete, si sono verificati un paio di bug come è normale che accada e prontamente sono stati corretti, alla fine penso abbia superato l’esame.
Adesso mi sono state anticipate delle nuove richieste per l’aggiunta di nuovi servizi da implementare per il prossimo anno scolastico e di una nuovo store interno che dovrà essere pronto per il periodo natalizio, non anticipo altro spero di farcela e ti tirare nuove somme positive.

Ringrazio veramente tanto la mia guida (se mai leggerà capirà che mi riferisco a lui), mi ha insegnato, suggerito e stimolato (a fare sempre meglio per non sfigurare al suo fianco) tanto, un grande ringraziamento va anche all’amico esaurito (anche in questo caso se mai leggerà si riconoscerà) che ha curato una parte della grafica, tante grazie anche a te contumace che non sei altro 🙂

Nicola Masella

Web Bug e ToDo List: l’idea

L’idea di fondo è quella di uno strumento utile per segnalare, gestire, monitorare i bug di un progetto (bug in senso lato, sarebbe meglio pensare a loro come qualunque problema si presenti), di un lavoro ecc.

Avevo dunque pensato che questa applicazione non dovrà essere indirizzata solo ai progetti software come un normale bug tracker ma anche ad altri lavori (nel mio caso ne ho sentito la mancanza anche durante una migrazione a linux, quindi un lavoro più di tipo sistemico che di realizzazione software). Per fare questo i dati necessari per la realizzazione di un bug tracker diventeranno o più ‘generici’ oppure alla creazione del progetto l’utilizzatore dovrà scegliere la tipologia dello stesso, deciderò più in la.
Da una prima analisi ho pensato che l’applicazione potrà essere multi progetto, quindi creare, modificare ed eliminare più progetti, sarà inoltre possibile dividere il rpogetto in più sezioni. Si potrà organizzare gli utenti in team così da gestire meglio i bug ed associare ad uno o più team una o più sezione del progetto.

Per i bug come per i progetti sarà possibile creare, modificare, eliminare e in più segnalare gli stessi, mostrare il loro stato, assegnare loro una sigla mnemonica e d affidare la loro sorte ad un team.

Per quanto riguarda poi la ToDo List sarà possibile anche in questo caso, inserire, modificare, cancellare i propri ‘todo’ ed organizzarli in una o più sezioni.

Nel prossimo post penso di buttare giù qualche idea per la struttura dell’applicazione, giusto qualche linea guida e per la grafica.

Alla prossima

Web Bug e ToDo List: presentazione

Nell’ultimo periodo dopo aver seguito alcuni lavori contemporaneamente mi sono accorto che mi sarebbe di grande utilità un bug tracker con funzioni anche di ToDo List visto che la mia memoria fa veramente pena.

Sono sicurissimo che ce ne sono già tanti, BugZilla ad esempio sembra essere il migliore per la gestione dei bug, avevo però pensato di realizzarne uno nel tempo libero (quindi aspettatelo finito per il prossimo secolo, se ci sarò ancore…) sfruttando l’occasione per imparare e/o approfondire qualcosa di nuovo. Con quest’ottica vi presento il progetto, sarà un’applicazione Web Based, realizzata usando come linguaggio lato server il Php e come Data Base PostgreSQL (approfitto per approfondirlo un pò potrebbe servirmi per lavoro ad oggi l’ho solo sfiorato); cercherò anche di rendere l’applicazione il più possibile WEB 2.0 quindi con XHTML e spero anche AJAX.

Il progetto sarà rilasciato sotto licenza GPL, stavo poi pensando di non collaborare con nessuno fino alla realizzazione della prima versione alfa, il motivo è che preferisco utilizzare i pochi ritagli di tempo per avviare e strutturare per bene il progetto piuttosto che contattare e coordinare chi vorrà sviluppare. Quando sarà disponibile una base chiunque vorrà contribuire al progetto sarà il benvenuto, così come saranno benvenuti tutti coloro che seguiranno il progetto dall’inizio partecipando inserendo i loro commenti nel blog.

Tempo permettendo posterò man mano le funzioni che ho intenzione di implementare e tutta la progettazione.

Alla prossima