RESNA 28th Annual Conference - Atlanta, Georgia
Gregory W. Lesher, PhD & Bryan J. Moulton, MS
DynaVox Technologies
Pittsburgh, PA 15203
Abbreviation expansion is a well-established means to reduce keystrokes in augmentative communication. However, there have been no studies to determine the theoretical performance limit of this technique. As a first step in that direction, we present a computational method for determining such a bound on keystroke savings. Although the theoretical savings we found for a sample text would not be realistically achievable, it represents a quantitative starting point from which we can refine our model of real-word abbreviation expansion in future studies.
Abbreviation expansion, keystroke savings, AAC
The automatic expansion of pre-defined abbreviations was one of the earliest techniques for enhancing the communication rate and reducing the motor load of persons utilizing voice output communication aids. First used in text-based AAC devices more than 25 years ago [1, 2], abbreviation expansion has become a cornerstone method for keystroke savings – a decrease in the number of distinct user actions required to produce text or speech. It is now difficult to find a voice output system that doesn’t include at least a rudimentary abbreviation expansion system.
Abbreviation expansion has the advantage of being both simple and effective – it’s easy to explain, trivial to implement, and straight-forward to use. Like other encoding schemes (e.g., Morse code or semantic compaction), once the abbreviations are memorized, their use quickly becomes automatic. This automaticity contrasts sharply with many alternative methods of keystroke reduction (e.g., word prediction) that introduce significant cognitive loads and search times. Of course, the memorization requirement represents a non-trivial impediment to the effective use of abbreviation expansion. Furthermore, there have been few attempts to define a comprehensive set of abbreviations for general purpose use. The combination of two factors has tended to limit the use of this technique to relatively small sets of abbreviations highly tailored for specific individuals.
Our research team set out to derive a comprehensive set of consistent abbreviations that would maximize keystroke savings while concomitantly considering how easy it would be to memorize each entry. As the first step in this process, we investigated the theoretical limits of single-word abbreviation expansion without considering a person’s ability to actually memorize the abbreviations. This is an admittedly unrealistic scenario. In the real world, people use various mnemonic techniques such as truncation or vowel deletion to define abbreviations. Furthermore, they often use abbreviations for multiple word sequences. And, of course, there’s a limit to the number of abbreviations that can be memorized. However, we felt that it was important to determine the upper limits on one tightly constrained aspect of abbreviation expansion before attempting to address less easily quantified factors.
To determine the relative frequency of words in English, we turned to the British National Corpus – a disciplined 100 million word collection of text samples from diverse sources. From this corpus, we generated a list of the frequency of each of the most frequent 57,000 unique component words. By multiplying the length of a word plus one (indicating a terminating space or punctuation) by the number of times it occurred in the text, we established how many characters each component word accounted for.
To maximize keystroke savings, the total number of characters required to produce a message must be minimized. In the context of the current study, this implies that the decision of which abbreviations to pair with each word should be driven by the number of characters that will be saved by such a pairing. Since we were focusing only on theoretical limitations, we did not concern ourselves with assigning memorable abbreviation pairs. Our pairing decisions were based solely on maximizing keystroke reductions.
In determining how to assign abbreviations, we cannot just consider the relative frequency of a word – we need to also look at how many characters each word accounts for. For example, the 2,681,858 occurrences of the word “of” accounted for 8,045,574 individual characters in the corpus. By counting the total number of words and characters in the corpus, we can compute that “of” represented 3.39% of all words, but only 1.79% of all characters. Because it’s a much shorter-than-average word, “of” doesn’t contribute as high a percentage of characters as it does words. If we instead look at a slightly longer-than-average word, like “which”, we see that the inverse is true – it contributes a higher percentage of characters (0.45%) than it does words (0.43%).
The number of characters saved by defining a particular abbreviation-word pair is equal to the difference in the lengths of the abbreviation and the word, multiplied by the number of times the word appears. For example, by using the abbreviation “wc” for “which” we’d save 3 characters for each of the 337,779 occurrences of “which” in the source corpus, for a total of 1,013,337 saved characters. This single abbreviation would provide an overall keystroke savings of roughly 0.23%.
If all of our abbreviations were of the same length, determining the theoretical keystroke savings limit would be trivial. We’d simply perform the savings calculation for each word and sum the results. We’d find that if we had an unlimited number of unique two-character abbreviations (recognizing that we couldn’t have a shorter abbreviation due to the need for a terminating character), our keystroke savings would be nearly 65%. Of course, we only have a limited set of characters from which to define abbreviations, so we could never have this many short abbreviations. In practice, we’d have abbreviations of all different lengths. Using only letters, we’d have 26 abbreviations with one letter (plus a space terminator), 676 (26 x 26) with two letters, 17,576 (26 x 26 x 26) with three letters, and so on. Of course, we’d have to eliminate some of these permutations of letters because they would be actual words rather than abbreviations. For example, because “I” and “a” are single-letter words, we’d only have 24 single-letter abbreviations available. Similarly, there are between 30 and 50 two-letter words (depending on what you think constitutes a word), reducing our availability of two-letter abbreviations.
Because we have abbreviations of varying lengths, the task of determining the optimal pairings between abbreviations and words becomes quite difficult. Of course, the general idea is to pair the shortest abbreviations with the longest, most frequent words. But what if a word is frequent, but not that long? It turns out that there is no simple answer. To determine the best pairings, we therefore adapted a computationally intensive optimization technique that our group had earlier applied to the task of arranging letters on an ambiguous telephone-like keypad [3]. In the first step of a two-step process, we used a “greedy” algorithm to assign abbreviations so as to maximize the individual character savings for each word. In the second step, we iteratively swapped abbreviations of different lengths between words to maximize the overall keystroke savings.
In our first test, we restricted abbreviations to combinations of letters only, with a space terminator. By optimizing the abbreviation-word pairings across all 57,000 unique words, we established an upper bound on keystroke savings of 47.1%. If we allow the abbreviations to contain both letters and numerals (using the numerals as additional terminators), we have more unique permutations from which to generate shorter abbreviations. This, in turn, bumps the keystroke savings to an impressive 56.7%.
As a first attempt to determine more achievable keystroke savings using abbreviation expansion, we also applied our optimization techniques to a system in which we restricted the number of abbreviations. Using 250 abbreviations – a number that a typical person might reasonably be expected to memorize over the period of several weeks – we recorded a keystroke savings of 18.6% when using only letters in the abbreviations, and 22.2% when using both letters and numerals.
We have deliberately ignored many practical limitations of abbreviation expansion in an attempt to establish theoretical upper bounds on keystroke savings. Our next step will be to adjust the system constraints to establish a realistic set of abbreviations for use within AAC. Further limiting the number of abbreviations and ensuring that abbreviations are mnemonically appropriate (at the expense of efficiency) will tend to reduce keystroke savings. On the other hand, allowing multi-word abbreviation expansions will push the savings higher. Ultimately, we expect that a comprehensive abbreviation expansion framework will prove an attractive augmentative component for a wide range of candidates.
This study was supported in part by a National Center for Research Resources (NCRR) SBIR grant (1 R43 RR13220-01).
Dr. Gregory W. Lesher
DynaVox Technologies,
2 High Rock Lane,
South Hamilton, MA 01982
412-222-7944
greg.lesher@dynavoxtech.com