Statistiche di errore del mondo reale?

Question

Dove posso trovare alcune statistiche di errore relative al mondo reale?

Sto cercando di far corrispondere il testo di input della gente agli oggetti interni e le persone tendono a commettere errori di ortografia.
Ci sono 2 tipi di errori:

1. typos - "Helllo" invece di "Ciao"/"Satudray" invece di "Sabato", ecc
2. Spelling - "Shikago" invece di "Chicago"

io uso Damerau-Levenshtein distance per gli errori di battitura e Double Metaphone per l'ortografia (implementazioni Python here e here).

Voglio concentrarmi sul Damerau-Levenshtein (o semplicemente su edit-distance). Le implementazioni da manuale usano sempre '1' per il peso di cancellazioni, sostituzioni di inserzioni e trasposizioni. Anche se questo è semplice e consente algoritmi piacevoli, non corrisponde a "realtà"/"probabilità del mondo reale".

Esempi:

• sono sicuro che la probabilità di "Helllo" ("Ciao") è maggiore di "Helzlo", eppure sono entrambi 1 modifica distanza.
• "Gello" è più vicino di "Qello" a "Ciao" su una tastiera QWERTY.
• Traslitterazioni Unicode: qual è la "vera" distanza tra "München" e "Munchen"?

Quali dovrebbero essere i pesi del "mondo reale" per le eliminazioni, le inserzioni, le sostituzioni e le trasposizioni?

Anche Norvig's very cool spell corrector utilizza la distanza di modifica non ponderata.

BTW Sono sicuro che i pesi devono essere funzioni e non galleggia semplici (per quanto sopra esempi) ...

posso modificare l'algoritmo, ma dove posso "imparare" questi pesi? Non ho accesso a Google-scale data ...

Devo solo indovinarli?

EDIT - cercando di rispondere alle domande degli utenti:

• Il mio attuale algoritmo non ponderata non riesce spesso a fronte di errori di battitura per i motivi di cui sopra. "Return on Thursday": ogni "persona reale" può facilmente dire che giovedì è più probabile di martedì, tuttavia sono entrambi a 1 distanza di distanza! (Sì, registro e misura le mie prestazioni).
• Sto sviluppando un motore di ricerca viaggi NLP, quindi il mio dizionario contiene ~ 25.000 destinazioni (previsto fino a 100.000), Time Expressions ~ 200 (previsto 1K), People espressioni ~ 100 (previsto 300), Money Expressions ~ 100 (previsto 500), "glue logic words" ("from", "beautiful", "apartment") ~ 2K (previsto 10K) e così via ...
• L'utilizzo della modifica della distanza è diverso per ciascuno dei precedenti word-gruppi. Cerco di "correggere automaticamente quando è ovvio", ad es. 1 modifica la distanza dall'unica altra parola nel dizionario.Ho molte altre altre regole personalizzate, ad es. Fix doppio metaphone che non è più di 2 modifica distanza da una parola del dizionario con una lunghezza> 4 ... L'elenco delle regole continua a crescere man mano che imparo dall'input del mondo reale.
• "Quante coppie di voci del dizionario sono all'interno della soglia?": Beh, questo dipende dal "sistema di ponderazione fantasia" e dall'input del mondo reale (futuro), vero? Ad ogni modo, ho test di unità estesi in modo che ogni modifica apportata al sistema lo renda solo migliore (basato sugli input passati, ovviamente). La maggior parte delle parole con meno di 6 lettere si trovano entro 1 distanza di modifica da una parola che si trova a 1 distanza di modifica da un'altra voce del dizionario.
• Oggi quando ci sono 2 voci di dizionario alla stessa distanza dall'input, provo ad applicare varie statistiche per indovinare meglio che cosa intendesse l'utente (ad esempio, Parigi, la Francia è più probabile che compaia nella mia ricerca di Pārīz, Iran).
• Il costo della scelta di una parola sbagliata restituisce risultati semi-casuali (spesso ridicoli) all'utente finale e potenzialmente alla perdita di un cliente. Il costo di non comprensione è leggermente meno costoso: all'utente verrà chiesto di riformulare.
• Il costo della complessità ne vale la pena? Sì, sono sicuro che lo sia. Non crederesti alla quantità di errori di battitura che le persone lanciano al sistema e si aspettano che capisca, e potrei sicuramente usare la spinta in Precision and Recall.

Answer 1

La possibile fonte di statistiche di errore relative al mondo reale sarebbe nella cronologia delle modifiche complete di di Wikipedia.

http://download.wikimedia.org/

Inoltre, si potrebbe essere interessato al di AWB RegExTypoFix

http://en.wikipedia.org/wiki/Wikipedia:AWB/T

Answer 2

Ti consiglio di controllare lo trigram alogrithm. Secondo me funziona meglio per trovare errori di battitura e quindi modificare l'algoritmo di distanza. Dovrebbe funzionare anche più velocemente e se mantieni il dizionario nel database di Postgres puoi fare uso dell'indice.

Si possono trovare utili StackOverflow topic su google "Forse cercavi"

Answer 3

Alcune domande per voi, per aiutare a determinare se si dovrebbe chiedere il vostro "dove posso trovare i pesi del mondo reale" domanda:

Avete effettivamente misurato l'efficacia dell'attuazione uniforme della ponderazione? Come?

Quanti "oggetti interni" diversi hai - cioè qual è la dimensione del tuo dizionario?

Come stai effettivamente utilizzando la distanza di modifica, ad es. John/Joan, Marmaduke/Marmeduke, Featherstonehaugh/Featherstonhaugh: è questo "tutto 1 errore" o è una differenza del 25%/11.1%/5.9%? Quale soglia stai usando?

Quante coppie di voci del dizionario sono all'interno della soglia (ad esempio, John vs Joan, Joan vs Juan, ecc.)? Se introduci un sistema di ponderazione di fantasia, quante coppie di voci del dizionario migrerebbero (a) dall'interno della soglia all'esterno (b) viceversa?

Che cosa fai se John e Juan sono nel tuo dizionario e l'utente digita Joan?

Quali sono le penalità/i costi di (1) scegliere la parola del dizionario sbagliata (non quella che l'utente intendeva) (2) non riuscire a riconoscere l'input dell'utente?

L'introduzione di un complicato sistema di ponderazione ridurrà effettivamente le probabilità dei suddetti due tipi di errore con un margine sufficiente per rendere la complicazione e la bassa velocità utili?

BTW, come fai a sapere quale tastiera stava usando l'utente?

Aggiornamento:

"" "Il mio attuale algoritmo non ponderata non riesce spesso a fronte di errori di battitura per le ragioni di cui sopra. 'Return on Tursday': ogni 'persona reale' può facilmente dire Giovedi è più probabile rispetto Martedì , tuttavia sono entrambi a distanza 1-distanza (Sì, registro e misura le mie prestazioni). "" "

Sì, giovedì -> Giovedì omettendo una" h ", ma martedì -> Giovedì da sostituendo "r" anziché "e". E e R sono uno accanto all'altro sulle tastiere qwERty e azERty. Ogni "persona reale" può facilmente indovinare che giovedì è più probabile di martedì. Anche se le statistiche e le ipotesi indicano che giovedì è più probabile del martedì (forse omettere h avrà un costo di 0,5 ed e-> r costerà 0,75), la differenza (forse 0,25) sarà abbastanza significativa da scegliere sempre giovedì? Il tuo sistema può/può chiedere "Intendevi martedì?" o lo farà/andrà avanti con giovedì?

Answer 4

Se la ricerca è di vostro interesse, penso che continuare con quell'algoritmo, cercando di trovare pesi decenti, sarebbe fruttuoso.

Non posso aiutarti con le statistiche di errore, ma penso che dovresti giocare anche con difflib di python. In particolare, il metodo ratio() di SequenceMatcher. Utilizza un algoritmo che la rivendicazione dei documenti http://docs.python.org/library/difflib.html si adatta bene alle corrispondenze che sembrano "giuste" e può essere utile per aumentare o verificare ciò che stai facendo.

Per i programmatori Python che cercano solo errori di battitura, è un buon punto di partenza. Uno dei miei colleghi ha utilizzato sia la modifica di Levenshtein che il rapporto SequenceMatcher() e ha ottenuto risultati molto migliori da ratio().

Answer 5

Probability Scoring for Spelling Correction dalla Chiesa e Gale potrebbe aiutare. In quel documento, gli autori modellano gli errori di battitura come un canale rumoroso tra l'autore e il computer. L'appendice contiene tabelle per errori di battitura visualizzati in un corpus di pubblicazioni della Associated Press. C'è un tavolo per ciascuno dei seguenti tipi di errori di battitura:

• soppressione
• inserimento
• sostituzione
• trasposizione

Ad esempio, esaminando la tabella inserimento, possiamo vedere che l è stato inserito in modo errato dopo l 128 volte (il numero più alto in quella colonna). Usando queste tabelle, puoi generare le probabilità che stai cercando.