I am working on creating a spell-checking service for Android (note: this is a platform- and language-neutral question) for Asturian, a minority Romance language. We're using hunspell as the base but unfortunately on mobile devices the memory and speed of hunspell is far less than optimal.
I've made some great strides in porting the features that we need while reducing the memory requirements and algorithm complexity, but when it comes to optimizing the suggestions feature, I've been looking for ways to greatly optimize the look ups. Most of the English-language optimizations I've found can't be easily applied, because Asturian requires multiple levels of affix stripping (50M-ish forms), whereas English can store every single possible word much more efficiently (100k-ish possible forms total). In other words, you need to effectively create a set of guesses, and then check to see if they are words.
The most basic (read: dumb) way is to given a word of length n and letter count l create a list of single deletions (n), neighboring transpositions (n-1), replacements ((n-1)(l-1)), and additions (nl), but this only allows for a single error and requires 2nl + n - l guesses. Allowing two mistakes, we end up with (if my math doesn't fail me) 4n2l2 + 6n2l + 2nl2 + 2n2 + 2nl guesses (roughly the square of single guesses). Needless to say, even a very efficient algorithm for determing will start to choke on longer words (which will more likely have more than a single mistake):
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
Although generally words don't get too much longer than that, it is actually the most morphologically complex (which also means computationally complex to verify, because they require stripping multiple affixes) words that are longer
I read a paper on language-neutral spell checking using trigram sequences that could help to quickly identify problem sequences and began implementing it. So for example, given the word achistárobmela (n=14) we'd break it up into its trigram components and check their frequency in a corpus (these are the raw counts, rather than a frequency strictly speaking):
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
I think it becomes obvious here that there is a very likely mistake in the -obmel- section, which is in fact where it is — the b should be an n. This could, in general, reduce search complexity to the equivalent of a brute forced n=5 (and if there are two mistakes in that sequence, not increasing complexity at all, and if they are clearly separated, only rougly doubling, rather than roughly squaring, complexity).
However, I was wondering if there is any way to optimize even the trigram searches. Right now, they are stored in a flat array which gives the frequency values and allows for a very fast look up of that information (frequencies made up, as the example trigrams are not possible and would be 0):
index: 0, 1, 2, … 44135 trigram: aaa, aaá, aab, … zzz frequency: 1 8 14 34
In the above example, we could probably narrow the mistake area even further to the bm segment (as it's common to each of the non-existent trigrams). So it might be best to try o** or **e replacements first, but ideally only searching for trigrams that exist, and doing them in order (and stopping if X numbers of highly likely suggestions appear).
Right now, at best, for o**, I take the value of o (20) and double a double loop checking the values at index 20l2 + il + j but a large (75% or so) of those have values of 0 and can be safely ignored.
Is there any optimized structure that could let me know given an arbitrary trigram search pattern (a) the extant matching trigrams and/or (b) the optimal order (by frequency in the corpus)? I thought about an array of arrays but then memory concerns start to pop in again. Maybe this is approaching microoptimizations, but I don't really think so.