Prototype: auto-correct & word suggestions for the LP3 keyboard

[CryptoRodeo]

Hey! I always wondered how auto-correct and suggestions would work on the LP3 keyboard and after the light-keyboard repo went live I created a small prototype:

lp3-auto-correct-and-suggestions.mp4

The keyboard suggests words as you type, showing the top 3 guesses in a bar above the keys with the most likely one in bold, so you can tap to pick one or just keep typing.

It fixes obvious typos inline by using key positions to figure out what you meant, and you can always hit backspace to undo, though it never changes words it already recognizes as real.

It also auto-completes, predicts your next word between words and learns names or slang you use a lot, all locally on the phone.

The prototype isn't really the point though, I'm curious what the Light team thinks of something like this UX-wise, and whether there's anything already in the works (that you can share) 🙂

[dupontgu]

This is so cooool!!! Can I ask what you're using as the prediction engine?

• we're closing in on swipe though we haven't really figured out the "show list of probable words in case the top choice is wrong" UX, which is similar to prediction. My current favorite idea is just replacing the speech button with a "next word 🔁 " button after completing a swipe that just cycles through the best matches. Haven't really run that by the team yet though
• we've got existing spell check in LightOS which I would like to pull out into the keyboard repo at some point.

BUT I haven't personally been around for any conversations around prediction, thought I know it's a highly requested feature. I imagine the problem is just real vertical real estate on the LP3.

Gonna tag @JoeHollier

[CryptoRodeo]

TLDR: It's just a smart dictionary and some clever lookups.

Prefix trees for fast completions, fuzzy matching (Damerau-Levenshtein) for typos, and a couple of curated lookup tables for next-word predictions.

If there's interest I can submit a PR and we'll go from there 🙂

Here's the technical stuff:

The two word lists

The engine uses two raw text files, and the split is how the trick works:

• autocorrect_words.txt: About ~9,880 words ordered from common to rare. This contains the words the engine will suggest and correct to.
• valid_words.txt: A big "yes, that's a real word" list (~36K). It's used to recognize words so they're left alone. It never suggests anything.

Why two? So the keyboard can know that axolotl is a real word (don't touch it) without ever suggesting axolotl when you fat-finger something. So recognizing does not equal recommending.

Trie (prefix tree) for auto-completion:

autocorrect_words.txt is loaded into a trie, where shared beginnings share a branch:

        c
        └─ a
           ├─ t         -> "cat"
           ├─ r ─ e     -> "care"
           └─ n         -> "can"

(valid_words.txt doesn't get loaded into the trie, it's just a big lookup set for the "is this a real word?" check.)

This is nice because completions are basically free. Type ca and it just read everything hanging below that branch (cat, care, can, ...) instead of scanning all the words in autocorrect_words.txt.

This also makes fuzzy matching fast because branches get skipped the instance they're too far off, rather than comparing your typo against every word.

Fuzzy matching for typos

For fuzzy-matching I used Damerau-Levenshtein, which helps answer "how close are these two words?"

A typo isn't in the dictionary, so instead of an exact lookup, the keyboard finds the real words that are only a small number of edits away.

How this works

TLDR: It swaps at most two characters when auto-correcting a word.

The classic way to measure closeness between words is edit distance, the number of single character edits that turn one word to another. With this algorithm we get three kinds of edits:

insert a letter     ca  -> cat     (add 't')
delete a letter     cart -> car    (remove 't')
substitute a letter cot -> cat     (change 'o' to 'a')

Each edit counts as 1, and the distance is the smallest number of edits that gets you there. So cat and cart are 1 (on insert); cat and dog are 3.

Then there's transposition (swap two adjacent letters) and count it as a single edit:

transpose two letters   teh -> the    (swap 'e' and 'h')

Swapping two adjacent letters is one of the most common human typos.

The keyboard computes this distance by walking the trie and only keeping candidate words within a small edit budget (at most 2). Anything further away is ignored. They're most likely not typos, just different words.

The cool thing about this fuzzy matching algorithm is that it learns! Type a word it doesn't know twice (slang, a name) and it becomes trusted. It stops correcting it and starts suggesting it.

[CryptoRodeo]

I just realized I answered how the inline auto-correct and word completion works but not how the next-word prediction engine works 🥀 (which is what I think you were asking for?)

Next-word prediction is a way simpler mechanism. It's just a hand-written lookup table. It uses the word you just finished as the key:

you                 ->  are | can | have
thank               ->  you
good                ->  morning | luck | night
(start of sentence) ->  I | the | you

The whole thing is a curated map of ~40 common contexts. It's dead simple:

1. Take the previous word, lowercase it, strip any apostrophes.
2. Look it up in the table.
3. Show those (up to 3) in the strip, with the middle one emphasized.
4. If the word isn't in the table, fall back to a generic the | to | a so the strip is never blank.

Here's a snippet:

fun predictNext(prevWord: String): WordSuggestions {
    val key = prevWord.lowercase().trim('\'')
    val words = (nextWordMap[key] ?: GENERIC_NEXT).take(3)
    if (words.isEmpty()) return WordSuggestions.None
    // No auto-apply target between words, but emphasize the centre.
    return WordSuggestions(words, primaryIndex = words.size / 2)
}

// Generic fallback so the strip is never blank.
private val GENERIC_NEXT = listOf("the", "to", "a")

// Curated next-word predictions. The empty key is the sentence start.
val nextWordMap: Map<String, List<String>> = mapOf(
    "" to listOf("I", "the", "you"),
    "i" to listOf("am", "have", "think"),
    "you" to listOf("are", "can", "have"),
    "thank" to listOf("you"),
    "good" to listOf("morning", "luck", "night"),
    // ...~40 entries in total
)

It's a super basic implementation of a next-word predictor but hey, it works 🤷

[CryptoRodeo]

On another note, the FUTO keyboard page gave me an idea for the talk to text button 🎙️ :

Maybe it can get added to the right of the right text suggestion button? 🤔

[CryptoRodeo]

Here's the LP3 keyboard with the moved mic idea I mentioned (inspired by the FUTO keyboard):

spacing could be improved here (give the mic element more padding?). On toggle (suggestion bar gone) it just goes back to its previous position.

And here it is again but this time all the character keys have a key separators 🙂 :

[CryptoRodeo]

I updated my device VM to better match the LP3 and I get the concerns on vertical real estate. I tried out the following:

Minimized suggestion strip:

suggestion-strip-minimized.mp4

This can probably be minimized even more, right now it's 28dp.

Here it is at 24dp:

And 14dp (spacing needs some work):

Toggle suggestion strip:
I added the ability to toggle this section. All the other functionality still works.

suggestion-strip-toggled-off.mp4

[zacksimpson]

Fantastic stuff. This is my dream for how this would be implemented. The only other step, in my view, is a dotted underline on an autocorrected word to indicate the change has been made. (Similar to the solid underline for a typo right now.)

Predictive text is great and I think that should be included as well! The vertical screen real estate issue solves itself completely with an implementation like this, though, so it would be a win for everyone and would largely solve keyboard complaints. I hope they consider baking this in! Bravo!

[CryptoRodeo]

Thank you for the feedback, yeah a way to tell a word was auto-corrected would improve the UX a lot. What I think I'll do is submit a PR (with no expectation it ever gets merged) so the ⅃ight dev team can rip the code apart and maybe it'll ignite some ideas for the keyboard 🙂

[CryptoRodeo]

I found this great keyboard for the LP3 that I've been using recently: https://github.com/KEZO555/Type
It basically solves what I was trying to do here. To prevent duplicate efforts I recommend checking that out and seeing if some of its features can be ported to the official LP keyboard.

Great work @KEZO555!

I'll close this out now.