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

1. 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

1. 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

1. 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

1. 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

1. 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.

1. Distanza di Levenshtein in Wikipedia, l'enciclopedia libera.
   http://it.wikipedia.org/wiki/
2. 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