# Optimizing trigram look ups with wildcards

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.

• Could you store the trigram info in a trie? It's going to be fairly sparse after the first edge. So when you've found f(obm)=0, you want to try say f(o..), then you just have to follow first the o-edge, then the only possible edges to follow are the ones that actually existed in the corpus, you simply don't store any 0-count edges. – unhammer Jun 1 '15 at 7:55
• You might also find github.com/voikko/droidvoikko/wiki interesting – unhammer Jun 1 '15 at 7:56
• @unhammer I'm storing a lot of things already in tries, but I'm not sure it would help much here. Right now, to look up a trigram ijk (given alphabet length l) I can go directly to index ill + jl + k. There may not be a way to optimize much more than for loops and checking if the value stored at the index is 0, but I can't help thinking for the ordering there ought to be. – guifa Jun 1 '15 at 8:10
• But then you still have to look up all 900 entries of o[a-zá][a-zá], whereas there might only be, say 30 possibilities of f>0. By only following existing edges in a trie you might save an order of magnitude lookups, although at the cost of a more complicated data structure. Hard to know if it's worth it without trying though ;) – unhammer Jun 1 '15 at 8:54