Italian edit distance (Levenshtein distance)

maXim · Jan 15, 2009

Il codice che propongo è molto semplice nella sua interpretazione ed è alquanto interessante e, in alcuni casi, può essere più che utile. La funzione presente non è altro che una variante semplificata dell'algoritmo che calcola l'Edit Distance meglio conosciuta con il termine Levenshtein Distance. La distanza di Levenshtein è la "distanza" tra due stringhe, nell'esempio proposto le stringhe da elaborare sono indicate dalle variabili String1 e String2, dove per "distanza" è inteso il numero minimo di operazioni elementari (cancellazione, sostituzione o inserimento di un carattere) che occorrono per trasformare la stringa String1 nella stringa String2. In poche parole l'algoritmo di Levenshtein non fa altro che "misurare" il grado di similitudine tra due stringhe fornendo il numero di quante modifiche occorrono per trasformare una stringa in un'altra. Questo algoritmo è abbastanza conosciuto tra chi sviluppa software per l'archiviazione di dati provenienti da diverse tabelle e da diversi database, specialmente da quei db "vecchi" e "sporchi" dove, durante la loro importazione, è necessario procedere in automatico ad una "normalizzazione" dei termini contenuti in alcuni campi per "riallineare" i dati e dove, purtroppo, anche le solite query con l'operatore LIKE non riescono a risolvere il problema. Per chi vuole approfondire l'argomento sull'algoritmo che determina la distanza di Levenshtein consiglio di fare ricerche in internet e per cominciare su Wikipedia: Distanza di Levenshtein - Wikipedia (italiano) e Levenshtein distance - Wikipedia, the free encyclopedia (english).

B4X:

Sub edit_distance(String1, String2)

    Dim distance
    Dim truncateLength
    Dim xString1
    Dim xString2

    distance = 0

    If String1 <> String2 Then
        distance = Abs(StrLength(String1) - StrLength(String2))
        truncateLength = ((StrLength(String1) + StrLength(String2)) - distance) / 2
        xString1 = SubString(String1, 0, truncateLength - 1)
        xString2 = SubString(String2, 0, truncateLength - 1)
        For i = 1 To truncateLength
            If SubString(xString1, i - 1, 1) <> SubString(xString2, i - 1, 1) Then
                distance = distance + 1
            End If
        Next
    End If

    Return distance

End Sub

Deleted member 103 · Jan 16, 2009

Ciao Massimo,

grazie del per il codice che metti a disposizione.
In questo momento non ho un caso dove poterlo usare ma sono sicuro che prima o poi verrà ed è buono sapere dove trovarlo.

Ho messo solo un paio di spazzi tra End_If e If_SubString e ho aggiunto una Msgbox.

B4X:

Sub Globals
   'Declare the global variables here.

End Sub

Sub App_Start
   Msgbox(edit_distance("omissam","massimo"))  'Distance=5
End Sub

Sub edit_distance(String1, String2)
 
   Dim distance
   Dim truncateLength
   Dim xString1
   Dim xString2
 
   distance = 0
   If String1 <> String2 Then
      distance = Abs(StrLength(String1) - StrLength(String2))
      truncateLength = ((StrLength(String1) + StrLength(String2)) - distance) / 2
      xString1 = SubString(String1, 0, truncateLength - 1)
      xString2 = SubString(String2, 0, truncateLength - 1)
      For i = 1 To truncateLength
         If SubString(xString1, i - 1, 1) <> SubString(xString2, i - 1, 1) Then
            distance = distance + 1
         End If
      Next
   End If
   Return distance
 
End Sub

Ciao,
Filippo

maXim · Jan 17, 2009

Ciao Filippo,

grazie delle segnalazioni "ortografiche", comunque nell'esempio presente nel file allegato al mio post il codice è corretto mentre nel corpo del post ho voluto evidenziare il codice relativo al solo algoritmo dell'Edit Distance. L'esempio che tu proponi è proprio al limite, infatti dal risultato si evince che i due termini ("omissam" e "massimo") sono completamente diversi (solo una "s" corrisponde e cioè il carattere nella quarta posizione). Un esempio più pratico potrebbe essere il confronto tra un dato "sporco" e uno "pulito", ammettiamo quindi di dover analizzare una tabella con i nomi di alcune città italiane da verificare con i dati contenuti in una tabella di riferimento con i nomi corretti:

+-----------+-----------+----------+
| STRINGA 1 | STRINGA 2 | DISTANZA |
+-----------+-----------+----------+
| Aosta ... | Aosta ... | .. 0 ... |
| Fiòenze . | Firenze . | .. 1 ... |
| MilaNo .. | Milano .. | .. 1 ... |
| Npaloi .. | Napoli .. | .. 4 (!) |
| Rieri ... | Rieti ... | .. 1 (?) |
+-----------+-----------+----------+

Se il processo di analisi dei dati sopra indicati è affidato ad una procedura software, un'automatismo potrebbe portare ad accettare tutti i nomi delle città la cui "distanza" è uguale a 0 e a modificarli con tutti quelli dove la "distanza" risulta molto minima (prossima a 1), occorre però fare molta attenzione all'effettiva lunghezza delle due stringhe da confrontare e al numero dei caratteri identici (anche se in posizioni diverse) come nel caso di Napoli ma il confronto con Rieri rappresenta un classico errore di digitalizzazione alquanto "diabolico", infatti potrebbe indicare Riesi e non Rieti! Di solito, in questi casi, le procedure che si occupano di questi processi si limitano ad evindeziare il termine lasciando la scelta della possibile modifica ad un'intervento manuale. Si potrebbe pensare, visto il layout della tastiera, che si tratta effettivamente di un errore di battitura, infatti il tasto 'r' si trova adiacente alla lettera 't' e quindi si può presumere che chi ha immesso i dati voleva digitare proprio Rieti. Integrando un controllo sulla lunghezza delle due stringhe, la quantità dei caratteri aventi lo stesso codice ASCII e la loro sequenza nella direzione di scrittura verificata su una "mappa" che identifica il layout della tastiera, si arriverebbe, con un buon margine di certezza, all'individuazione e alla successiva assegnazione del nome corretto. Comunque per chi vuole cimentarsi in algoritmi più sofisticati la discussione è aperta!

moster67 · Jan 21, 2009

ciao,

questo algoritmo è molto utile in vari scenari, p.esempio con i spelling-checkers. Nella mia libreria "PhoneticAlgorithms Library" (v. http://www.b4x.com/forum/additional-libraries/2999-phoneticalgorithms-library-ex-stringcomparison-library.html#post16781 ) questo algoritmo è già presente. E' stato usato anche nel mio piccolo progetto Spell-checker (v. http://www.b4x.com/forum/open-source-projects/2980-spell-checker.html#post16711). Devo ancora finire questo progetto - ci sono già dizionari per inglese e svedese - manca solo quello italiano.

saluti
moster67

maXim · Jan 21, 2009

Ciao moster67,

avevo già notato a suo tempo la tua libreria ma anche tu utilizzi l'algoritmo in una "forma" semplificata, comunque la mia intenzione (se trovo dei "compagni" di viaggio) è quella di dare il "via" ad un progetto sicuramente più complicato e interessante come quello proposto tra le ultime righe del mio ultimo post. Mi auguro che qualcuno accetti la sfida...

moster67 · Jan 22, 2009

Ciao Maxim,

Ho capito - forse ho già qualcosa che ti potrebbe tornare utile che ho già implementato nel mio spell-checker (non ho ancora pubblicato il source-code dove questo codice è presente). Questa tecnica si chiama "Near-Miss" ed è basata su 4-5 funzioni ed una "mappa". Stasera quando torno a casa metterò a disposizione questi funzioni qui in questo thread e spiegherò come funzionano. Forse devono essere modificati un po' per italiano ma secondo me possono essere un buon inizio o una spunta/idea per fare quello che vuoi ottenere.

maXim said:
Ciao moster67,
Mi auguro che qualcuno accetti la sfida...

maXim · Jan 22, 2009

Ciao moster67,

grazie per aver accettato la sfida!

Sono curioso di "vedere" come hai affrontato queste problematiche anche perché conosco le tecniche di near-miss (i check e alcuni dei metodi risolutivi su i così detti "quasi errori"). Professionalmente affronto questi temi quasi quotidianamente perché (nell'ambito dell'automazione industriale e di altri processi aziendali) mi occupo anche di risk management, incident-reporting, ecc. per creare modelli che, nell'ottica del miglioramento continuo, intercettino a monte tutte quelle cause non desiderate in modo da ridurre al minimo i controlli sui singoli processi e sulle attività con l'intenzione di annullare qualsiasi intervento di "rimedio" agli effetti derivanti dalle cause non desiderate impegnando così tutte le risorse a mantenere la qualità standard di produzione (domanda: la qualità deve essere controllata o prodotta?). Ho fatto questa premessa per segnalarti che non sono "digiuno" in questa materia e spesso realizzo del software anche come strumento di supporto alle decisioni. Per esperienza so che ogni strumento efficiente alla soluzione di qualsiasi problema può perdere la sua efficacia perché condizionato da comportamenti umani non conformi e quindi diventare inutile se non addirittura più dannoso del problema per il quale era stato progetto come risolutore. Anche la "sfida" che ho proposto in questo thread "attraversa" le problematiche sopra descritte, infatti l'immissione manuale dei dati è altamente soggetta all'errore (interpretazioni errate, errori di battitura dei tasti, vizi comportamentali, ecc.) e ancora oggi, anche se è stata "scomodata" l'A.I., non è stata trovata una soluzione veramente efficace che risolva il problema in una maniera elegante e poco costosa. Comunque l'intento della "sfida" non deve essere quello di realizzare il prodotto risolutore (alri ci stanno lavorando e probabilmente con più risorse di quelle che noi possiamo disporre, di me sicuramente!) ma di unire le nostre esperienze per creare una discussione aperta su un tema interessante utile anche dal punto di vista didattico.

moster67 · Jan 22, 2009

Maxim,

ora mi metti in difficoltà. Io non sono un mago per niente per quanto riguarda la programmazione (lo faccio per hobby) ma se faccio un progetto (come per esempio lo spelling-checker) vado a documentarmi un bel po' e poi vado a implementare quello che trovo (in una maniera o'altro) anche se non capisco tutto quello che sto facendo - basta che funziona.

Per cui mi sa che tu sai molto di più di me in questa materia ma se posso dare una mano valida lo faccio volentieri - però può darsi che sto dicendo un sacco di fesserie. Per quanta riguarda lo "spell-checking" è giusto che questi funzioni "near-miss" insieme con altri algoritmi creano delle parole da suggerire in modo che l'utente finale possa selezionare la parola giusta mentre nel tuo caso è diverso visto che vuoi che sia il computer a prendere la decisione.

a dopo
moster67

maXim · Jan 22, 2009

... l'intento della "sfida" non deve essere quello di realizzare il prodotto risolutore [... omissis ...] ma di unire le nostre esperienze per creare una discussione aperta su un tema interessante utile anche dal punto di vista didattico.

... niente di più!

moster67 · Jan 25, 2009

Near Miss

Questo è un esempio di come funzionano in linea di massima i più famosi spelling-checkers open-source tipo ISpell, PSpell, MySpell, ASPell e HunSpell (usato da OpenOffice) ed altri.

Forse può sembrare che questo messaggio non ha niente da fare con il discorso/la sfida di Maxim ma invece secondo me può essere interessante e soprattutto riesco a spiegare a meglio l’uso di “Near Miss” da me menzionato in un messaggio precedente.

Lo spelling-checker ha vari files a disposizione come supporto ma i più importanti sono:

1) il dizionario nella lingua che ci interessa. Il dizionario può essere strutturato/codificato in vari modi ma in questo caso per semplicità diciamo che è una lista di parole di cui siamo sicuri siano corrette per quanto riguarda lo spelling. Naturalmente più parole sono presenti nel dizionario, meno controlli sono necessari.

2) un file che contiene le lettere più usate (in ordine di frequenza di uso) nella lingua che ci interessa. Io chiamo questo file "TryMe" e serve per il controllo “Near Miss”.

3) un file con lettere che spesso vengono scambiati tra i loro (perché l'utente si confonde o sbaglia nella battitura). Un esempio in italiano sono le lettere è e é (v. perchè e perché). Io chiamo questo file "Errors" e serve per il controllo “Near Miss”.

Controllo parola:

Se la parola esiste in un dizionario allora lo spelling è giusto e si prosegue con la verifica della prossima parola.

Se la parola invece non è presente nel dizionario allora lo spelling non è corretto e si iniziano le varie procedure per trovare una parola da suggerire, sempre presente nel dizionario, che probabilmente corrisponde a quella che l'utente voleva.

La prima strategia NON presume che la parola sbagliata è dovuta ad un errore ortografico (cioè l'utente non sa come si scrive la parola) ma piuttosto è dovuto ad un errore nella battitura/input della parola. In questo caso si usa la strategia "Near Miss”.

Bad Character routine (with TryMe)
Omitting extra-character routine (ExtraChar)
Inserting a TryMe-character before each letter (ForgotChar)
swapping adjacent chars one by one (SwapChar)
Replace-routine (with Errors)
TwoWords (missing space between two valid words)

(Non sto qui a tradurre quello che ho scritto sopra in inglese – invece allego un progetto, che non è eseguibile e serve solo per vedere meglio il mio codice per queste funzioni. Ho semplicemente copiato il mio codice esistente ma penso che il codice sia abbastanza "parlante")

Tramite questi controlli "Near Miss" si ottengono delle parole, presente nel dizionario, che sono simili a quella sbagliata e che poi vengono aggiunte in un array di parole da suggerire all'utente.

Ora si procede con la seconda fase di controlli tramite vari algoritmi fonetici tipo “Soundex” (più adatto per la lingua inglese) e “DoubleMetaphone” (anche per l'italiano anche se non è il massimo). Tramite questi algoritmi si ottengono altre parole, presenti nel dizionario, che somigliano a quella sbagliata. Va fatto un controllo per stabilire che queste parole da suggerire non esistano già nell'array (trovate tramite la procedura "Near Miss") altrimenti vengono aggiunte all'array di parole da suggerire all'utente.

A questo punto si usa l'algoritmo "Levenshtein Distance" (Edit Distance) per diminuire le parole da suggerire - cioè si verifica la distanza tra la parola sbagliata e quelle presente nell'array di parole da suggerire. Se la distanza generata tramite l'algoritmo "Levenshtein Distance" da un risultato di 1 o 2, allora questa parola va segnalata come una parola da suggerire all'utente altrimenti viene scartata.

In alternativa all’uso di algoritmi fonetici, si potrebbe usare semplicemente l’algoritmo “Levenshtein Distance". Questo funziona bene quando si accetta una distanza di 3 o di più perché altrimenti le parole suggerite saranno troppe soprattutto se la parola sbagliata è composta di appena due o tre lettere.

Ho già un thread aperto per uno spelling-checker. Tra poco spero di postare il codice sorgente finale. In questo momento ci sono dizionari per l’inglese e lo svedese. Sto lavorando su un dizionario in italiano ma manca ancora un po’ di lavoro prima che posso postarlo. Se qualcuno vuol dare una mano per completare il dizionario in italiano, fammi sapere.

La differenza tra questo progetto è quello che Maxim vuole fare sta nel fatto che lo spelling-checker deve suggerire soluzioni per l’utente da prendere mentre quello che Maxim vuole ottenere è che il computer prende la decisione. La sfida di Maxim è molto interessante ma secondo me è molto più difficile da ottenere ma in fondo dipende anche molto dal file di riferimento che nel mio esempio con lo spelling-checker è il dizionario. Se invece il file di riferimento, come nel caso di Maxim con poche città, non è molto vasto allora probabilmente l’uso di “Levenshtein Distance" e con distanza uguale = 1 può funzionare, magari aggiungendo anche un controllo “Near Miss” che si basa per esempio sulla mappatura della tastiera. Per esempio, l'utente scrive Leccr ma in realità voleva scrivere Lecce, allora il controllo Edit Distance indica un errore cioè una distanza = 1. La riposta corretta può essere Lecce ma anche Lecco. Se il controllo Near Miss in qualche maniera teneva in conto il layout della tastiera, come suggerito da Maxim, allora il programma potrebbe cambiare l'errore in Lecce in modo automatico visto che la lettera "r" è situata più vicino a "e" che a "o".

Come già detto - è un topic molto interessante. Portiamolo avanti e vediamo se riusciamo fare qualcosa. A Voi la parola.

saluti,
moster67

moster67 · Jan 26, 2009

Altre due cose che si potrebbe fare:

1) Ora non ho il modo di controllare il codice di Maxim per cui non so come si comporta ma in genere l'algoritmo “Levenshtein Distance" distingue anche tra lettere maiuscole e minuscoli. Questo vuol dire che genera una distanza = 1 se si confronta le parole computer e computeR. Si potrebbe modificare l'algoritmo di non tener conto della differenza tra maiuscolo e minuscolo.

2) Secondo statistiche che ho letto, spesso la prima lettera in una parola scritta in un modo errata è quasi sempre giusta. Per cui quando si va a controllare la lista di riferimento potrebbe bastare controllare le parole che iniziano con la stessa lettera di quella sbagliata.

saluti,
moster67

maXim · Jan 26, 2009

Ciao moster67,

quanto hai esposto rappresenta proprio la problematica che desideravo affrontare in apertura di questo thread.

Sono più che felice della tua partecipazione e mi auguro che anche il tuo invito venga accettato da altri in modo da allargare questa discussione che, precisiamolo, non è una "sfida" tra i partecipanti ma un confronto di idee il cui unico scopo è quello di analizzare questo tipo di problema cercando poi di sviluppare delle possibili soluzioni informatiche con Basic4PPC e, chissà, il tutto potrebbe diventare anche un bel progetto open source valido anche per altri ambienti di sviluppo.

Se sei d'accordo, prima di "mettere mano" al codice, proporrei di analizzare la questione "partendo" dall'origine e cioè dal data entry cercando di elencare le possibili cause che portano agli errori di trascrizione. In teoria operando bene a "monte", nel tentativo di dare una soluzione al problema con gli adeguati automatismi, potrebbero diventare più semplici (se non addirittura inutili, e questa non è pura utopia) i tools necessari alle correzioni o interpretazioni dei dati apparentemente non validi.

Cosa ne pensi?

Massimo

P.S. La "sfida" potrebbe diventare più impegnativa: fin quando si tratta di stringhe alfanumeriche si può pensare che una soluzione ottimale sia possibile ma quando si tratta di date o, peggio, di numeri e per giunta a virgola mobile, la questione si complica e non di poco... Ma questa è un'altra storia...

moster67 · Jan 26, 2009

Maxim,

sono d'accordo con te - si deve partire a monte cioè dal Data Entry.

La mia prima domanda viene in modo spontaneo: Device e/o Desktop ?

Per quanto riguardano i device, gli "input" in genere sono tastiere fisici o tastiere "software" presenti sul schermo del device. Volendo c'è anche software "vocale/speech" che possa generare l'input. Si potrebbe anche aggiungere OCR....

Poi, c'è la questione del layout delle tastiere. In genere sono QWERTY ma non sempre - dipende dalla lingua in uso. Si potrebbe iniziare con italiano per poi includere anche tastiere di altre lingue/layout.

cosa ne pensi?

saluti,
moster67

maXim · Jan 26, 2009

Ciao moster67,

per il momento, sempre se sei d'accordo, limitiamoci a teorizzare un modello adatto ad applicazioni desktop con input da tastiera. Successivamente, una volta che il modello teorizzato è stato messo in pratica e risultasse affidabile, si può cominciare a studiare tutte quelle cause derivanti da altri dispositivi predisposti all'immissione dei dati a prescindere da input manuali o automatizzati sia in parte che totalmente. Pertanto, in questa prima fase, soffermiamoci a definire le cause dovute a certi errori tipo quelli che abbiamo già evidenziato come ad esempio gli errori di trascrizione e/o di battitura. Tutto questo non vieta di realizzare procedure di esempio, anzi sono necessarie per dar "sfogo" alle nostre teorie, per questo ti informo che anche io sto lavorando ad una procedura che opera con diversi algoritmi e appena sarà a punto la pubblicherò in modo da mantenere "calda" la discussione, peccato che il tempo da dedicare non sia molto ma per fortuna ci sono i fine settimana! Si, insomma, ognuno si diverte come può!

Deleted member 103 · Feb 6, 2009

Ciao Massimo,

ho trovato una procedura scritta in Visual Basic 6 e l' ho tradotta in Basic4ppc.
Penso che potrebbe essere utile in questo progetto, che ne pensi tu?

Ciao,
Filippo

Italian edit distance (Levenshtein distance)

maXim

Active Member

Attachments

Deleted member 103

Guest

maXim

Active Member

moster67

Expert

maXim

Active Member

moster67

Expert

maXim

Active Member

moster67

Expert

maXim

Active Member

moster67

Expert

Attachments

moster67

Expert

maXim

Active Member

moster67

Expert

maXim

Active Member

Deleted member 103

Guest

Attachments

Italian edit distance (Levenshtein distance)

Active Member

Attachments

Deleted member 103

Guest

Active Member

Expert

Active Member

Expert

Active Member

Expert

Active Member

Expert

Attachments

Expert

Active Member

Expert

Active Member

Deleted member 103

Guest

Attachments

Privacy & Transparency

Privacy & Transparency