Sto lavorando alla creazione di un servizio di controllo ortografico per Android (nota: questa è una domanda neutra per la piattaforma e la lingua) per l'Asturiano, una lingua minoritaria romanzesca. Usiamo hunspell come base, ma sfortunatamente sui dispositivi mobili la memoria e la velocità di hunspell sono molto meno ottimali.
Ho fatto passi da gigante nel porting delle funzionalità di cui abbiamo bisogno riducendo i requisiti di memoria e la complessità dell'algoritmo, ma quando si tratta di ottimizzare la funzione dei suggerimenti, ho cercato modi per ottimizzare notevolmente le ricerche. La maggior parte delle ottimizzazioni in lingua inglese che ho trovato non possono essere applicate facilmente, perché l'asturiano richiede più livelli di stripping affix (forme 50M-ish), mentre l'inglese può memorizzare ogni singola parola in modo molto più efficiente (100k-ish possibili forme totale). In altre parole, è necessario creare una serie di ipotesi e quindi verificare se sono parole.
Il modo più semplice (leggi: stupido) è dare una parola di lunghezza n e il conteggio delle lettere l crea un elenco di cancellazioni singole ( n ), trasposizioni vicine ( n -1), sostituzioni (( n -1) ( l -1)) e aggiunte ( nl ), ma questo consente solo un singolo errore e richiede 2 nl + n - l . Permettendo due errori, finiamo con (se la mia matematica non mi tradisce) 4 n 2 l 2 + 6 n 2 l + 2 nl 2 + 2 n 2 + 2 nl indovina (approssimativamente il quadrato delle singole ipotesi). Inutile dire che anche un algoritmo molto efficiente per la determinazione inizierà a soffocare su parole più lunghe (che molto probabilmente avranno più di un singolo errore):
Word-length Single error Double error
3 183 56 610
5 329 148 370
8 584 367 040
10 694 566 840
15 1059 1 255 410
Anche se in genere le parole non si allungano troppo, in realtà è la più morfologicamente complessa (che significa anche computazionalmente complessa da verificare, perché richiedono la rimozione di più affissi) parole che sono più lunghe
Ho letto un documento sul controllo ortografico senza linguaggi utilizzando sequenze di trigrammi che potrebbero aiutare a identificare rapidamente le sequenze di problemi e iniziare a implementarle. Quindi, per esempio, data la parola achistárobmela (n = 14) lo scomporremmo nelle sue componenti del trigramma e ne controlleremo la frequenza in un corpus (questi sono i conteggi grezzi, piuttosto che una frequenza strettamente parlando ):
ach - chi - his - ist - stá - tár - áro - rob - obm - bme - mel - ela
163 192 98 739 129 46 138 214 0 0 74 421
Penso che sia ovvio che c'è un errore molto probabile nella sezione -obmel - , che in effetti è dove si trova - il b dovrebbe essere un n . Ciò potrebbe, in generale, ridurre la complessità della ricerca all'equivalente di un bruto forzato n = 5 (e se ci sono due errori in quella sequenza, non aumentando affatto la complessità e se sono chiaramente separati, solo un rougly raddoppio, piuttosto che approssimativamente una squadratura, complessità).
Tuttavia, mi chiedevo se ci fosse un modo per ottimizzare anche le ricerche del trigramma. In questo momento, sono memorizzati in un array piatto che fornisce i valori di frequenza e consente una rapida ricerca di tali informazioni (frequenze composte, poiché i trigram di esempio non sono possibili e sarebbero 0):
index: 0, 1, 2, … 44135
trigram: aaa, aaá, aab, … zzz
frequency: 1 8 14 34
Nell'esempio sopra, potremmo probabilmente restringere ulteriormente l'area di errore al segmento bm (poiché è comune a ciascuno dei trigram inesistenti). Quindi potrebbe essere meglio provare prima le sostituzioni o ** o ** e , ma idealmente solo cercando i trigrammi esistenti e eseguendoli in ordine (e fermandosi se X vengono visualizzati molti suggerimenti molto probabili).
Al momento, nel migliore dei casi, per o ** , prendo il valore di o (20) e raddoppiamo un doppio ciclo verificando i valori all'indice 20 l 2 + il + j ma un grande (75% circa) di quelli ha valori di 0 e può essere sicuro ignorato.
Esiste una struttura ottimizzata che potrebbe farmelo sapere dato un pattern di ricerca di trigramma arbitrario (a) i trigrammi di corrispondenza esistenti e / o (b) l'ordine ottimale (per frequenza nel corpus)? Ho pensato a una serie di array, ma poi i problemi di memoria hanno iniziato a ripresentarsi. Forse questo si sta avvicinando alle microottimizzazioni, ma non lo penso davvero.