Dialing for documents: an experiment in information theory

ABSTRACT

Standard telephone keypads are labeled with letters of the alphabet, enabling users to enter textual data for a variety of possible applications. However, the overloading of three letters on a single key creates a potential ambiguity as to which character was intended, which must be resolved for unambiguous text entry. Existing systems all use pairs of keypresses to spell out single key letters, but are extremely cumbersome and frustrating to use.Instead, we propose single-stroke text entry on telephone keypads, with the ambiguity resolved by exploiting information-theoretic constraints. We develop algorithms capable of correctly identifying up to 99% of the characters in typical English text, sufficient for such applications as telephones for the hearing impaired, E-mail without a terminal, and advanced voice-response systems.

REFERENCES

• 1: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 2: J. Dargan. Telephonic data access and transmission system. US Patent 4,677,659, June 30, 1987.
• 3: J. R. Davis. Let your fingers do the spelling: Disambiguating words spelled with the telephone keypad. A VIO$ Journal, 9:57-66, March 1991.
• 4: R. L. Deininger. Human factors engineering studies of the design and use of pushbutton telephone sets. Bell System Tech. journal, 39:995-1012, 1960.
• 5: M. C. Detweiler, R. M. Schumacher, and N. L. Gattuso. Alphabetic input on a telephone keypad. In Proc. 3$th Annual Meeting Human Factors $ociely, 1990.
• 6: R. Feinson. Interpretive tone telecommunication method and apparatus. US Patent 4,754,474, June 28, 1988.
• 7: J. Flanagan, J. Kronmeyer, and R. Nelson. Communications system for alphanumeric information employing audio tone signalling. US Patent 3,675,513, July 11, 1972.
• 8: W. N. Francis. Frequency analysis of English usage: lexicon and grammar. Houghton Mifflin, Boston, 1982.
• 9: K. Hashimoto. Push button phone capable of sending to the telephone line alphabetical characters. US Patent 4,918,721, April 17, 1990.
• 10: J. J. Hull and S. N. Srihari. Experiments in text recognition with binary n-gram and viterbi algorithms. IEEE Trans. Pattern Analysis and Ma. chine Intelligence, PAMI-4:520-530, 1982.
• 11: L. James. Processor-assisted communication system using tone-generating telephones. US Patent 4,650,927, March 17, 1987.
• 12: J. J. Kramer. Human factors problems in the use of pushbutton telephones for data entry. In International Symposium On Human Factors In Telephony, Berlin, 1970. VDE-Verlag GmbH.
• 13: M. A. Marics. How do you enter "d'anzi~quist" using a telephone keypad? In Proc. 3$th Annual Meeting Human Factors Society, 1990.
• 14: M. D. McIlroy. Development of a spelling list. IEEE Trans. Communications, COM-30:91-99, 1982.
• 15: B. Riskin. Method and apparatus for identifying words entered on DTMF pushbuttons. US Patent 5,031,206, July 9, 1991.
• 16: C. E. Shannon. Prediction and entropy of printed english. Bell System Technical Journal, 30:50-64, 1951.
• 17: Sargur N. Srihari , Jonathan J. Hull , Ramesh Choudhari, Integrating diverse knowledge sources in text recognition, ACM Transactions on Information Systems (TOIS), v.1 n.1, p.68-87, Jan. 1983 [doi>10.1145/357423.357428]
• 18: P. Tsakanikas. Telephonic alphanumeric data transmission system. US Patent 4,427,848, January 24, 1994.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Input devices and strategies (e.g., mouse, touchscreen)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Dictionaries
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Theory and methods

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING

General Terms:
Algorithms, Experimentation, Languages, Theory

Keywords:
Viterbi algorithm, information theory, telephone keypads, telephones for the hearing-impaired