Algoritmo per rilevare se una parola è scritta correttamente

Question

Algoritmo per rilevare se una parola è scritta correttamente

#1 da (4 voti)
#2 da (1 voti)

1

Sto cercando di sviluppare un correttore ortografico JavaScript che non usi un dizionario, e posso correttamente, dato una singola parola, rilevare se una parola è scritta correttamente o meno. In questo momento, ho solo una lista di sottostringhe che non si verificano mai all'interno delle parole, e se la parola contiene una di queste stringhe, la considero come errata. Ad esempio, avrei una sottostringa "lll", e se una parola contiene "lll" sarebbe conteggiata come errata (come "I'lll").

Tuttavia, sto scoprendo che questo non funziona come previsto. La maggior parte delle parole errate sembrano implicare lettere nell'ordine sbagliato o parole che non seguono regole comuni. L'approccio sopra riportato non funziona per nessuno di questi problemi. Ad esempio, non esiste una sottostringa valida per l'ortografia "accidant".

Sto cercando un metodo più efficace per determinare se una parola è probabilmente errata o meno, idealmente qualcosa che risolve i problemi delle lettere in ordine errato e le chiavi vicino alla lettera corretta su una tastiera accidentalmente premuta (ma le soluzioni per altre cause comuni di errori di ortografia vanno bene).

Questo è solo in inglese, quindi non ha bisogno di lavorare con altre lingue. Inoltre, i falsi positivi sono per me un problema molto più grande dei falsi negativi, quindi preferirei sbagliare dicendo che le parole sono scritte correttamente quando in realtà non lo sono.

algorithms

posta firefoxuser_1 12.05.2015 - 01:19

fonte

2 risposte

Leggi altre domande sui tag algorithms

Fogli CS multipli o Javascript Quali passi pratici prendi per assicurarti di essere completo? [duplicare]

score 4 · Answer 1

Dato che sto lavorando su un problema simile, posso fornire alcune indicazioni.

Il modo più veloce che ho trovato per trovare errori (ma non necessariamente correggerli) è quello di usare le ricerche in n-grammi. È possibile memorizzarli in un array che è l'ennesima potenza della dimensione dell'alfabeto. Dato un array @words che include ogni singola parola in un corpus di testi dalla tua lingua e un trigramma (n-gram di tre elementi):

my %ngrams;
my $ngramSize = 3;
for my $word (@words) {
    next if length($word) < $ngramSize;
    $trigrams{substr($word,$_,$ngramSize)}++ for (0..length($word) -$ngramSize);
}

Probabilmente vorresti normalizzare i dati in qualche modo, e quindi puoi memorizzarli in modo più efficiente. Ad esempio, è possibile prendere il conteggio delle occorrenze mediano e impostarlo su 255, ridimensionando i valori più in alto e quindi dosando di meno. Questo ti permetterebbe di memorizzare, per esempio, un correttore ortografico in inglese con trigram in 17K, o anche solo 2K se sei disposto a scegliere un trigramma buono / cattivo in bianco e nero (e poiché la maggior parte dei trigram non esiste, puoi probabilmente eseguire anche ulteriori compressioni).

Poiché ciò si caricherebbe molto rapidamente, è possibile utilizzarlo per generare rapidamente candidati con un'accuratezza del 90% e quindi, una volta scaricato un correttore ortografico completo e corretto, usarlo, dando la priorità ai probabili errori di ortografia prima di verificare quelli corretti. Se ti aspetti che l'utente usi regolarmente il tuo sito, puoi anche salvare il dizionario nell'archivio locale per un richiamo praticamente istantaneo, piuttosto che doverli scaricare ogni volta.

Ma l'ortografia inglese, con la nostra ortografia incredibilmente irregolare e l'importazione costante di parole senza adattamento, richiede assolutamente un dizionario (anche se, poiché siamo principalmente un linguaggio analitico, possiamo effettivamente memorizzare tutto il dizionario in memoria a differenza di molto flesso o polisintetico lingue)

score 1 · Answer 2

Semplici euristiche come "nessuna tripla" e simili dovrebbero essere sicure, e potrebbero essercene altre come quelle che dovresti aggiungere, ma colgono solo alcuni degli errori possibili. Per il resto, non andrai lontano senza avere il maggior numero di parole possibile.

Il modo migliore che conosco per comprimere i dizionari senza perdita di perdite pur avendo una rapida ricerca, è un DAWG / MA-FSA, vedi link (e le introduzioni da provare su quello stesso sito) per un'introduzione amichevole. L'attrazione principale del DAWG è che puoi verificare molto rapidamente se qualcosa è sbagliato, mentre normalmente usi meno memoria di una tabella hash.

Puoi anche archiviarli su disco (o inviarli tramite la rete) usando 4 byte per margine etichettato. Prendendo solo le parole 63001 corrispondenti ^ [az] + $ dal dizionario inglese aspell / usr / share / dict / words, ottengo 49829 bordi, che dovrebbero essere possibili in ~ 194K - non molto più grandi di angular.js; Ma d'altra parte, se hai mod_deflate sul tuo server, gzip gestisce gli az in 163K (potresti trovare anche link interessante).

Leggi anche link se non l'hai già fatto.

Ma poi dici di voler sbagliare dalla parte dei falsi negativi; sarà più difficile se non vuoi includere un grande dizionario. Ovviamente puoi saltare il controllo di qualsiasi parola che corrisponda a [^ a-z] se sai che il tuo dizionario ha solo gli a-z. E puoi attaccare con errori di modifica a distanza singola (dal momento che la maggiore distanza di modifica è più probabile che si tratti di falsi positivi).

Un'altra alternativa, se vuoi andare fino in fondo su "solo-falsi-negativi", è trovare un grande elenco degli errori di ortografia più comuni , e usa semplicemente quello invece di un elenco di parole corrette. Sarà molto "dinamico", ma se lavori dalla frequenza (priorità gli errori più frequenti), potrebbe risultare un po 'utile. Puoi anche precompilare il tuo input previsto, se sai già molto su quale tipo di testo verrà scritto; per esempio. se vuoi fare lo speller per un forum in cui le persone parlano di un argomento specifico, puoi prima raschiare tutto il testo in quel forum, quindi eseguirlo tramite aspell e catturare tutti gli errori (e i suggerimenti) e archiviare solo la parte superiore N di quelli.