Informatica
Algoritmi di confronto approssimativo delle stringhe di testo, parte 2
Parte 1, Parte 2
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
Rimandiamo anche alla vasta bibliografia web in inglese.
- Distanza di Levenshtein in Wikipedia, l'enciclopedia libera.
http://it.wikipedia.org/wiki/ - Descrizione di funzioni PHP per manipolare le stringhe: levenshtein, soundex, similar_text e metaphone.
http://www.php.net/manual/it/ref.strings.php
Algoritmi di confronto approssimativo delle stringhe di testo
Parte 1, Parte 2