Efficient context-sensitive word completion for mobile devices

Word completion is a basic technology for reducing the effort involved in text entry on mobile devices and in augmentative communication devices, where efficiency and ease of use are needed, but where a low memory footprint is also required. Standard solutions compress a lexicon into a suffix tree with a small memory footprint and high retrieval speed. Keystroke savings, a measurable correlate of text entry effort gain, typically improve when the algorithm would also take into account the previous word; however, this comes at the cost of a large footprint. We develop two word completion algorithms that encode the previous word in the input. The first algorithm utilizes a character buffer that includes a fixed number of recent keystrokes, including those belonging to previous words. The second algorithm includes the complete previous word as an extra input feature. In simulation studies, the first algorithm yields marked improvements in keystroke savings, but has a large memory footprint. The second algorithm can be tuned by frequency thresholding to have a small footprint, and be less than one order of magnitude slower than the baseline system, while its keystroke savings improve over the baseline.