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
