Local Search Optimization and the Virtual Keyboard Design Problem

Overview

Brunswick High School Two main keyboard layouts are traditionally used for text entry in English -- QWERTY and lesser-known Dvorak. Both were designed around the turn of the twentieth century and were constrained by the mechanics of the typewriter. In this paper, I investigate keyboard design in contexts in which these restraints are eliminated, such as electronic text entry devices. I evaluate the relative efficiencies of traditional layouts with regard to the speed of text entry and propose new keyboard arrangements optimized for typing speed. The speed of text entry relies on three factors: the frequencies of digraphs, or ordered pairs of keys, in a corpus of texts representative of what is being typed, the keyboard layout itself, and the facility with which the user can strike these pairs of keys consecutively. I collect data on the first and third factors, and use methods of computational mathematical optimization to determine the second. More specifically, I use three local search algorithms including simple hill climbing, steepest descent, and simulated annealing. The layout produced when optimizing for stylus input and the layout produced when optimizing for touch typing input both achieve considerable gains in speed relative to the QWERTY and the Dvorak designs. Additionally, I investigate the robustness of my results with regards to the keystroke biometrics collected experimentally.

Competition history

• JSHS 2020 Category not listed

Resources

• National JSHS abstract book ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.