Ecco l'approccio generale:
-
Leggi un file di dizionario e organizza tutte le parole in una trie struttura dati. Molti sistemi Unix hanno tali file nella directory /usr/share/dict/ .
-
Trova possibili corrispondenze di un prefisso del tuo input nel trie. Questo di solito produce più corrispondenze, ad esempio theologyisabout inizia con theology e the .
-
Se rimuoviamo i prefissi corrispondenti, otteniamo una serie di possibili continuazioni, su cui ripetiamo il passaggio 2.
Finiremo quindi con un vasto albero di possibili interpretazioni.
Ci sono due problemi con questo:
- ci sarà una quantità esponenziale di interpretazioni
- potremmo perdere le interpretazioni a causa di una parola sconosciuta o di qualche forma grammaticale sconosciuta
Siamo in grado di risolvere entrambi questi problemi grazie alla corrispondenza fuzzy. Quando cerchiamo prefissi nel trie, permettiamo che le lettere siano mancanti, inserite o modificate. Tuttavia, ciascuna di queste aberrazioni aumenta la distanza di Levenshtein. Se un'interpretazione ha una distanza di Levenshtein troppo alta, possiamo potare quella interpretazione e concentrarci su altri rami. Puoi anche tenere i rami in una coda di priorità e investigare sempre i rami con la distanza di modifica corrente più bassa, che è più probabile che sia un'interpretazione ragionevole - non diversamente da Algoritmo di ricerca del percorso di Dijkstra .
Si noti che sequenze multiple di prefissi con diverse distanze di modifica potrebbero portare alla stessa stringa rimanente. Puoi quindi mantenere i tuoi progressi in una struttura dati che consente di condividere parti. Questa memorizzazione nella cache sarà probabilmente utile per le prestazioni. Se in effetti cerchi di implementare una variante dell'algoritmo di Dijkstra, una coda nota corrisponderebbe a un nodo visitato nel grafico.
La parte difficile è come eseguire effettivamente la corrispondenza fuzzy. Per esempio. puoi decidere su una densità di modifica massima di x modifiche per carattere ( 0 < = x < = 1 ), e interrompere un'interpretazione se è garantito che questa interpretazione avrà una densità più alta. Per una determinata stringa con lunghezza l possiamo quindi determinare un budget di modifica b = x · l . Questo budget è meno importante quando si abbinano i prefissi nel trie, ma questo trie è utile solo se ci sono meno modifiche rispetto ai caratteri nel prefisso. Un budget di modifica come b = floor (c / 2) con un prefisso di lunghezza c potrebbe essere ragionevole. Quante modifiche permetti non è solo una metrica per quanto i testi confusi permettano al tuo sistema di "capire", ma anche un'impostazione prestazionale: budget più piccoli vengono eseguiti più velocemente, poiché è necessario esaminare meno alternative.