United States Patent [19]
`King et al.
`
`1111111111111111111111111111111111111111111111111111111111111111111111111111 I
`
`USOO6O1 1554A
`[111 Patent Number: (cid:9)
`[45] Date of Patent: (cid:9)
`
`6,011,554
`Jan. 4, 2000
`
`[54] REDUCED KEYBOARD DISAMBIGUATING
`SYSTEM
`
`96/27947 9/1996 WIPO.
`WO 97/04580 2/1997 WIPO
`
`[75]
`
`Inventors: Martin T. King, Vashon, Wash.; Dale
`L. Grover, Lansing, Mich.; Clifford A.
`Kushler; Cheryl A. Grunbock, both of
`Vashon, Wash.
`
`[73] Assignee: Tegic Communications, Inc., Seattle,
`Wash.
`
`[21] Appl. No.: 08/686,955
`
`[22] Filed: (cid:9)
`
`Jul. 26, 1996
`
`Related U.S. Application Data
`
`[63] Continuation-in-part of application No. 08/507,756, Jul. 26,
`1995, Pat. No. 5,818,437
`[60] Provisional application No. 60/021,180, Jun. 10, 1996.
`[51] Int. Cl.7 ...................................................... G06F 15/00
`[52] U.S. Cl ............................. 345/352; 345/168; 704/10;
`707/533
`[58] (cid:9) Field of Search ..................................... 345/326, 352,
`345/353, 354, 168, 169; 704/3, 7, 9, 10;
`707/102, 530, 533, 534
`
`[56] (cid:9)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3/1972 James et al . ............................ 340/365
`3,647,973 (cid:9)
`3,967,273 6/1976 Knowlton .
`
`(List continued on next page.)
`
`FOREIGN PATENT DOCUMENTS
`
`0 213 022 3/1987 European Pat. Off.
`6/1989 European Pat. Off.
`0 319 193 A2
`0 464 726 A2 1/1992 European Pat. Off.
`5/1993 European Pat. Off.
`0 540 147 A2
`5/1995 European Pat. Off.
`0 651 315 Al
`0 689 122 Al 12/1995 European Pat. Off.
`9/1996 European Pat. Off.
`0 732 646
`8/1996 United Kingdom .
`2 298 166
`2/1982 WIPO.
`82/00442
`PCT/US89/
`05745
`W090/07149
`
`6/1990 WIPO.
`6/1990 WIPO.
`
`OTHER PUBLICATIONS
`
`Sugimoto, M. et al., "SHK: Single Hand Key Card for
`Mobile Devices," CHI 1996 (Apr. 13-18, 1996).
`
`(List continued on next page.)
`
`Primary Examiner—Ba Huynh
`Attorney, Agent, or Firm—Christensen O'Connor Johnson
`& Kindness PLLC
`
`[57] (cid:9)
`
`ABSTRACT
`
`A reduced keyboard disambiguating system (50) having a
`keyboard (54) with a reduced number of keys. A plurality of
`letters and symbols are assigned to a set of data keys (56) so
`that keystrokes entered by a user are ambiguous. Due to the
`ambiguity in each keystroke, an entered keystroke sequence
`could match a number of words with the same number of
`letters. The disambiguating system includes a memory (104)
`having a number of vocabulary modules (110). The vocabu-
`lary modules contain a library of objects that are each
`associated with a keystroke sequence. Each object is also
`associated with a frequency of use. Objects within the
`vocabulary modules that match the entered keystroke
`sequence are identified by the disambiguating system.
`Objects associated with a keystroke sequence that match the
`entered keystroke sequence are displayed to the user in a
`selection list (76). The objects are listed in the selection list
`according to their frequency of use. An unambiguous select
`key (60) is pressed by a user to delimit the end of a keystroke
`sequence. The first entry in the selection list is automatically
`selected by the disambiguating system as the default inter-
`pretation of the ambiguous keystroke sequence. The user
`accepts the selected interpretation by starting to enter
`another ambiguous keystroke sequence. Alternatively, the
`user may press the select key a number of times to select
`other entries in the selection list. For words that are not in
`the vocabulary modules, a two-stroke or multiple-stroke
`method are used to unambiguously specify each letter. The
`disambiguating system simultaneously interprets all entered
`keystroke sequences as a word, as a two-stroke sequence,
`and as a multiple-stroke sequence. The multiple interpreta-
`tions are automatically and simultaneously provided to the
`user in the selection list.
`
`49 Claims, 27 Drawing Sheets
`
`Now our mmk is
`finally
`B8
`
`66
`
`;50
`
`1
`
`Comcast, Exhibit-1208
`
`(cid:9)
`

`

`6,011,554
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`Witten, I.H., "Principles of Computer Speech," New York:
`Academic Press, (1982), pp. 246-253 1982.
`Levine, S.H., "An Adaptive Approach to Optimal Keyboard
`Design for Nonvocal Communication," IEEE, 1985.
`Minneman, S.L., "A Simplified Touch—Tone® Telecommu-
`nication Aid for Deaf and Hearing Impaired Individuals,"
`RESNA8th Annual Conference, Memphis Tennessee, 1985.
`Swiffin, A.L. et al., "PAL: An Effort Efficient Portable
`Communication Aid and Keyboard Emulator," RESNA 8th
`Annual Conference, Memphis, Tennessee, 1985.
`Levine, S.H. et al., "Adaptive Technique for Customized
`Interface Design With Application to Nonvocal Communi-
`cation," RESNA 9th Annual Conference, Minneapolis, Min-
`nesota, 1986.
`Levine, S.H. et al., "Computer Disambiguation of Multi—
`Character Key Text Entry: An Adaptive Design Approach,"
`IEEE, 1986.
`Foulds, R. et al., "Lexical Prediction Techniques Applied to
`Reduce Motor Requirements for Augmentative Communi-
`cation," RESNA 10th Annual Conference, San Jose, Cali-
`fornia, 1987.
`Foulds, R.A. et al., "Statistical Disambiguation of Multi—
`Character Keys Applied to Reduce Motor Requirements for
`Augmentative and Alternative Communication," AAC Aug-
`mentative and Alternative Communication (1987).
`Levine, S.H. et al., "Multi—Character Key Text Entry Using
`Computer Disambiguation," RESNA 10th Annual Confer-
`ence, San Jose, California, 1987.
`Swiffin, A.L. et al., "Adaptive and Predictive Techniques in
`a Communication Prosthesis,"AACAugmentative andAlter-
`native Communication (1987).
`Kamphuis, H. et al., "Katdas; A Small Number of Keys
`Direct Access System," RESNA 12th Annual Conference,
`New Orleans, Louisiana, 1989.
`Kreifeldt, J.G. et al., "Reduced Keyboard Designs Using
`Disambiguation," Proceedings of the Human Factors Soci-
`ety 33rd Annual Meeting-1989.
`Arnott, J.L. et al., "Probabilistic Character Disambiguation
`for Reduced Keyboards Using Small Text Samples," AAC
`Augmentative and Alternative Communication, vol. 8 (Sep.
`1992).
`Oommen, B.J. et al., "Correction to 'An Adaptive Learning
`Solution to the Keyboard Optimization Problem," IEEE
`Transactions on Systems, Man, and Cybernetics, 22:5 (Oct.,
`1992).
`Matias, E. et al., "Half—QWERTY: Typing With One Hand
`Using Your Two—Handed Skills," Conference Companion,
`CHI '94, (Apr. 24-28, 1994).
`King, M.T., "JustTypeTM—Efficient Communication with
`Eight Keys," Proceedings of the RESNA '95 Annual Con-
`ference, Vancouver, BC, Canada, 1995.
`
`.... 379/88
`
`................. 379/97
`
`............... 340/365
`
`................. 379/97
`
`4,191,854 3/1980 Coles .
`4,360,892 11/1982 Endfield
`4/1983 Prame .................. (cid:9)
`4,381,502 (cid:9)
`4,426,555 1/1984 Underkoffler. .
`4,427,848 1/1984 Tsakanikas
`4,442,506 4/1984 Endfield .
`4,481,508 11/1984 Kamei et al.
`4,549,279 10/1985 Lapeyre .
`3/1987 Riskin .................. (cid:9)
`4,649,563 (cid:9)
`4,661,916 4/1987 Baker et al.
`4,674,112 6/1987 Kondraske et al.
`4,677,659 6/1987 Dargan .
`4,754,474 6/1988 Feinson .
`4,791,408 12/1988 Heusinkveld .
`3/1989 Riskin .................. (cid:9)
`4,817,129 (cid:9)
`4,823,294 4/1989 Rouhani
`4,846,598 7/1989 Livits .
`4,849,732 7/1989 Dolenc .
`9/1989 Riskin .................. (cid:9)
`4,866,759 (cid:9)
`4,872,196 10/1989 Royer et al.
`4,891,777 1/1990 Lapeyre .
`5,031,206 7/1991 Riskin .
`5,035,205 (cid:9)
`7/1991 Schiller et al. ...... ................... 119/168
`5,063,376 11/1991 Chang .
`5,065,661 11/1991 Hacker .
`5,067,103 11/1991 Lapeyre .
`5,087,910 2/1992 Guyot-Sionnest .
`5,131,045 7/1992 Roth .
`5,156,475 10/1992 Zilberman .
`5,163,084 11/1992 Kim et al.
`5,200,988 4/1993 Riskin .
`5,214,689 5/1993 O'Sullivan .
`5,218,538 6/1993 Zhang .
`5,229,936 7/1993 Decker et al.
`5,255,310 10/1993 Kim et al.
`5,258,748 11/1993 Jones .
`5,281,966 1/1994 Walsh
`5,289,394 2/1994 Lapeyre .
`5,305,205 4/1994 Weber et al.
`5,317,647 5/1994 Pagallo .
`5,339,358 8/1994 Danish et al.
`5,388,061 2/1995 Hankes .
`5,392,338 2/1995 Danish et al.
`5,664,896 9/1997 Blumberg .
`5,786,776 7/1998 Kisaichi et al.
`5,847,697 12/1998 Sugimoto .
`
`OTHER PUBLICATIONS
`
`"Speed Keyboard for Data Processor," IBM Technical Dis-
`closure Bulletin, vol. 23, pp. 838-839, Jul., 1980. ©IBM
`Corp., 1993.
`
`Smith, Sidney L. et al., "Alphabetic Data Entry Via the
`Touch—Tone Pad: A Comment," Human Factors, 13(2), pp.
`189-190, 1971.
`
`2
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`so
`
`64 (cid:9)
`
`62 (cid:9)
`
`78 8O81
`done doze albe ab am a 8495 (Mlveb Lo
`
`102
`
`;50
`
`52
`
`66 176
`
`88
`
`fill dOrie
`Now our work is
`
`53 (cid:9)
`
`3
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 2 of 27
`
`6,011,554
`
`54
`
`56
`
`}[ N
`
`RPQ
`7
`
`OLX
`4
`
`Ret Tab Esc
`CYR
`Li
`
`1 ADF
`8
`! —
`E4V
`_ 5
``-
`THJ
`
`_z J
`
`n
`
`NBZ
`9
`?*
`'MG
`6
`:/
`SU
`3
`
`58
`
`SH1FT DELETE SELECT
`
`
`62
`
`64-i
`
`60
`
`4
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 3 of 27 (cid:9)
`
`6,011,554
`
`5;"
`
`1o~
`
`02
`
`;50
`
`)6
`
`,2
`f4
`
`52.
`
`5
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 4 of 27
`
`6,011,554
`
`START
`
`150
`
`FAIT FOR KEYSTROKE
`
`-IS 152
`KEYSTROKE THE
`SELECT KEY
`
`NO
`
`154
`
`ADD KEYSTROKE TO
`KEYSTROKE SEQUENCE
`
`164
`
`BOX FIRST
`ENTRY IN
`SELECTION LIST
`AND AT
`INSERTION
`POINT
`
`156
`
`IDENTIFY CORRESPONDING OBJECTS
`IN VOCABULARY MODULES
`(SEE FIGURE 5.)
`
`158
`
`RESOLVE PRIORITY BETWEEN
`OBJECT LISTS FROM DIFFERENT
`VOCABULARY MODULES ACCORDING
`TO SYSTEM MODE OF OPERATION
`
`160
`
`RESOLVE PRIORITY BETWEEN
`OBJECTS FROM THE SAME
`VOCABULARY NODULE
`
`162
`
`DISPLAY SELECTION LIST AND
`PROVISIONALLY DISPLAY AND
`HIGHLIGHT THE FIRST ENTRY IN
`THE SELECTION LIST AT THE
`INSERTION POINT IN THE TEAT REGION
`
`168
`
`PLACE A BOX AROUND THE NEXT
`ENTRY IN THE SELECTION LIST
`AND PROVISIONALLY DISPLAY
`THE ENTRY AT THE INSERTION
`POINT IN THE TEXT REGION
`
`165
`
`FAIT FOR KEYSTROKE
`
`
`166
`
`IS (cid:9)
`KEYSTROKE THE
`LECT
`
`NO
`
`170
`
`ACCEPT THE PROVISIONALLY
`DISPLAYED ENTRY AS THE
`KEYSTROKE INTERPRETATION
`IN THE TEXT REGION, AND
`CONVERT TO NORMAL TEXT
`
`172
`
`ADD A SPACE FOLLOWING
`THE INTERPRETATION
`IN THE TEXT REGION
`
`174
`
`CLEAR OLD
`KEYSTROKE SEQUENCE
`
`108
`
`AF. 3.
`
`6
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 5 of 27 (cid:9)
`
`6,011,554
`
`7
`
`

`

`• 42.
`
`OBJECT (NUMOBJ) (cid:9)
`
`4O8
`
`(OPT.)
`SEQUENCE TYPE
`ASCII OBJECT
`
`IDENTIFIER BITS (2) (OPT.) (cid:9)
`OBJECT
`PREVIOUS (cid:9)
`
`SYMBOL
`
`J
`
`OBJECT (2)
`
`408- (cid:9)
`
`L (cid:9)
`
`OBJECT (1) (cid:9)
`
`408- (cid:9)
`
`)
`(°~E
`OBJECT
`
`BITS (2) SEQUENCE
`SYMBOL
`
`0
`ASCII
`
`IDENTIFIER
`
`(OPT.)
`
`OBJECT PREVIOUS
`
` E
`BITS (2) SEQUENCE
`SYMBOL
`
`ASCII
`
`IDENTIFIER
`
`OBJECT
`PREVIOUS
`
`(416
`
`(414 (cid:9)
`
`c412 (cid:9)
`
`c410 (cid:9)
`
`POINTER
`
`n
`
`(NUMOBJ)
`
`BITS (9) OBJECTS POINTER POINTER
`POINTER
`
`NUMBER OF
`
`4046
`
`404 (cid:9)
`
`406 (cid:9)
`
`402 (cid:9)
`
`400-c
`
`8
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000
`
`Sheet 7 of 27
`
`6,011,554
`
`430
`
`440
`
`OLD OBJECT LIST
`
`NEW OBJECT LIST
`
`oc(1)
`OL(2)
`OL(3)
`
`OL(8)
`
`NOL(1)
`NOL(2)
`NOL(3)
`
`foe
`axe
`dow
`
`NOL(8) ri
`
`9
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000
`
`Sheet 8 of 27
`
`6,011,554
`
`START
`
`COPY NEW OBJECT LIST
`TO OLD OBJECT LIST
`
`502
`
`- -
`READ POINTER BIT (cid:9)
`S TO
`DETERMINE IF A POINTER
`EXISTS FOR THE KEYSTROKE
`
`
`504
`
`i H
`THERE A
`OP I
`NTER CORRESPONDINC
`TO THE KEYSTROKE
`
`512
`
`YES
`
`READ POINTER AND
`FOLLOW POINTER
`TO A CHILD NODE
`
`514 --
`T READ NUMBER
`NUMBER OF
`OBJECTS (X)
`ASSOCIATED WITH
`THE CHILD NODE
`
`516
`
`COUNTER = 1
`
`500
`
`508
`
`. 5.
`
`510
`
`RETURN NEW OBJECT
`LIST TO MAIN
`ROUTINE TO GENERATE
`SELECTION LIST
`
`NO
`
`J COPY OLD OBJECT LIST
`TO NEW OBJECT LIST
`
`518 (cid:9)
`
`COUNTER = X + I YES
`? (cid:9)
`
`NO
`
`RE~~r NEW OBJECT
`LIST TO MAIN
`ROUTINE TO GENERATE
`SELECTION LIST
`
`FORñiOBJECT RE1 r520
`PREVIOUS OBJECT IDENTIFIER
`FIELD AND LOAD PREVIOUS
`OBJECT FROM OLD OBJECT LIST
`
`
`
`READ SYMBOL FIELD AND APPEND I r522
`APPROPRIATE SYMBOL ASSOCIATED
`WITH THE RECEIVED KEYSTROKE
`TO END OF PREVIOUS OBJECT
`
`STORE NEW OBJECT IN V 524
`NEW OBJECT LIST AS
`ENTRY NOL(COUNTER)
`
`* _ (cid:9)
`526
`COUNTER = COUNTER + if
`
`10
`
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`U.S. Patent
`
`Jan. 4, 2000
`
`Sheet 9 of 27
`
`6,011,554
`
`Now our work is
`finally done
`802
`
`53
`
`66
`
`BEGIN
`MARK
`
`END
`MM UNDO
`
`E17T
`
`FORD
`
`CANCEL KEYS
`
`FORD
`
`REDO
`
`800
`
`;76
`
`done doze aloe ab 8495 <cancel> 1
`
`11
`
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 10 of 27 (cid:9)
`
`6,011,554
`
`53
`
`Now our work is
`finally t 4DI [0141] NBZ EIIV
`
`810
`
`j7s (cid:9)
`
`70
`
`YiF. 7.
`
`12
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 11 of 27 (cid:9)
`
`6,011,554
`
`p. 4i
`
`bl
`
`13
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 12 of 27 (cid:9)
`
`6,011,554
`
`14
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 13 of 27
`
`6,011,554
`
`Quick Help
`Select a setup option directly
`from, the keypad Press "HELP'
`for more details.
`
`53
`
`66
`NIP!
`LOAD
`UNLOAD
`E
`VOC
`B
`SAYE DEFAULT
`BIDE
`SETUP
`SETUP DISPLAY
`
`SLEEP OUTPUT
`
`HELP
`
`922
`
`9205
`
`A D F 8 <setuv> I <edit> <cancel>
`
`70
`
`906
`
`15
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 14 of 27 (cid:9)
`
`6,011,554
`
`n -_
`
`53
`
`- (cid:9)
`Quick Help
`The system vocabulary contains
`all cmnmon English words.
`
`LOAD
`
`EDIT
`
`C4RCBL
`
`INIT
`
`LIST
`
`PESET
`
`922
`
`SIT
`RESET
`PRIORITY PRIORITY
`
`92O-
`
`~76
`
`Prop.Names Abbrev. UserYocacbf UserVocab2
`
`Jr (cid:9)
`
`924
`
`.~~.B.D.
`
`16
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 15 of 27 (cid:9)
`
`6,011,554
`
`91
`
`17
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 16 of 27 (cid:9)
`
`6,011,554
`
`_DD (cid:9)
`
`crn
`
`v• v V T I VTY V'IT VTV -
`
`18
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 17 of 27 (cid:9)
`
`6,011,554
`
`nn (cid:9)
`
`to
`
`vvR. vvT vvv vvv
`
`19
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 18 of 27 (cid:9)
`
`6,011,554
`
`-r -y (cid:9)
`
`V TV (cid:9)
`
`VTV
`
`.~~. 891.
`
`20
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 19 of 27 (cid:9)
`
`6,011,554
`
`21
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 20 of 27 (cid:9)
`
`6,011,554
`
`a/ tJ L.
`
`22
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 21 of 27 (cid:9)
`
`6,011,554
`
`B
`1
`Z
`
`A
`5
`F
`
`N
`9
`U
`
`m
`
`D
`6
`X
`
`w
`
`E C
`3 4
`U
`
`H
`0
`P
`
`K
`
`T
`
`23
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000
`
`Sheet 22 of 27
`
`6,011,554
`
`Now our work Ls
`finally ne
`
`r doze albe ab 8495 <c ancel>
`
`1104
`
`mEIIo0
`
`M
`
`1102
`
`10.
`
`1106
`
`108
`1100 ~1
`
`24
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 23 of 27 (cid:9)
`
`6,011,554
`
`Now our work is
`finally, dome
`doze
`albe
`ab
`8495
`<cancel>
`
`88 (cid:9)
`
`1200
`
`[RP Q (cid:9)
`
`ADF (cid:9)
`
`NBZ
`
`[OLX[EWJ [JMGI
`
`zos
`
`CYR (cid:9)
`
`SU
`
`1204 L EEIJ
`
`T111
`
`DELETE
`
`SELECT
`
`1202
`
`25
`
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 24 of 27 (cid:9)
`
`6,011,554
`
`Now our work is
`finally >>> (cid:9)
`
`ADF OLX NB (cid:9)
`
`1300
`
`1302
`
`1306
`
`1308
`
`
`
`ne (cid:9)do
`
`L doze l
`7al —be (cid:9)
`
`ab (cid:9)
`
`8495 (cid:9)
`~<CANCEL>]
`
`1 (cid:9)
`
`2 S8 T
`
`1310
`
`1314
`
`# N
`RPQ (cid:9)
`
`ADF (cid:9)
`
`NBZ
`9
`
`7 [ 8 J
`LJL I IJ AV EIIJ
`
`0LX
`4 (cid:9)
`Ret Tab fsc (cid:9)
`C Y K (cid:9)
`1 (cid:9)
`
`5
`+ \Th r: q 7Th
`
`I
`S U
`T H J
`I
`3
`2 (cid:9)
`
`SPACE DELETE SHIFT
`
`1316 -
`1318 ' 1320 (cid:9)
`
`1322
`
`1312
`
`x .12.
`
`26
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 25 of 27 (cid:9)
`
`6,011,554
`
`1400
`
`S
`E
`L
`E
`C
`T
`
`1402
`
`'-56
`
`D
`E
`L
`E
`T
`E
`
`1404
`
`27
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 26 of 27 (cid:9)
`
`6,011,554
`
`ri-
`
`28
`
`

`

`U.S. Patent (cid:9)
`
`Jan. 4, 2000 (cid:9)
`
`Sheet 27 of 27 (cid:9)
`
`6,011,554
`
`1500
`
`1522
`
`15C. (cid:9)
`
`1518
`
`15B.
`
`1506 -
`
`f5f0-
`
`X 1502
`
`1520
`
`508
`
`~-1518
`1514
`
`154.
`
`1504 (cid:9)
`1512 (cid:9)
`
`f g
`
`15C•
`
`1506
`
`1506
`
`f518
`
`1516
`
`15► o
`
`.156.
`
`29
`
`

`

`6,011,554
`
`REDUCED KEYBOARD DISAMBIGUATING
`SYSTEM
`
`RELATIONSHIP OF OTHER APPLICATIONS
`
`This application is a continuation-in-part of U.S. patent
`application Ser. No. 08/507,756, filed Jul. 26, 1995, which
`issued on Oct. 6, 1998 as U.S. Pat. No. 5,818,437 and U.S.
`provisional application Ser. No. 60/021,180, filed Jun. 10,
`1996 pending, the benefit of the filing of which is hereby
`claimed under 35 U.S.C. §120.
`
`FIELD OF THE INVENTION
`
`The invention relates generally to reduced keyboard
`systems, and more specifically to reduced keyboard systems
`using disambiguation to resolve ambiguous keystrokes.
`
`BACKGROUND OF THE INVENTION
`
`For many years, portable computers have been getting
`smaller and smaller. The principal size-limiting component
`in the effort to produce a smaller portable computer has been
`the keyboard. If standard typewriter-size keys are used, the
`portable computer must be at least as large as the keyboard.
`Miniature keyboards have been used on portable computers,
`but the miniature keyboard keys have been found to be too
`small to be easily or quickly manipulated by a user.
`Incorporating a full-size keyboard in a portable computer
`also hinders true portable use of the computer. Most portable
`computers cannot be operated without placing the computer
`on a flat work surface to allow the user to type with both
`hands. A user cannot easily use a portable computer while
`standing or moving. In the latest generation of small portable
`computers, called Personal Digital Assistants (PDAs), com-
`panies have attempted to address this problem by incorpo-
`rating handwriting recognition software in the PDA. A user
`may directly enter text by writing on a touch-sensitive panel
`or screen. Unfortunately, the accuracy and speed of the
`handwriting recognition software has to date been less than
`satisfactory.
`It would therefore be advantageous to develop a keyboard
`for entry of text into a computer that is both small and
`operable with one hand while the user is holding the
`computer with the other hand. Prior development work has
`considered use of a keyboard that has a reduced number of
`keys. As suggested by the keypad layout of a Touch-Tone
`telephone, many of the reduced keyboards have used a
`3-by-4 array of keys. Each key in the array of keys contains
`multiple characters. As a user enters a sequence of keys,
`there is therefore ambiguity in the resulting output since
`each keystroke may indicate one of several letters. Several
`approaches have been suggested for resolving the ambiguity
`of the keystroke sequence.
`One suggested approach for unambiguously specifying
`characters entered on a reduced keyboard requires the user
`to enter two or more keystrokes to specify each letter. The
`keystrokes may be entered either simultaneously (chording)
`or in sequence (two-stroke specification). Neither chording
`nor two-stroke specification has produced a keyboard having
`adequate simplicity and efficiency of use. Two-stroke speci-
`fication is inefficient, and chording is complicated to learn
`and use.
`Other suggested approaches for determining the correct
`character sequence that corresponds to an ambiguous key-
`stroke sequence are summarized in the article "Probabilistic
`Character Disambiguation for Reduced Keyboards Using
`Small Text Samples," published in the Journal of the Inter-
`
`2
`national Society for Augmentative and Alternative Commu-
`nication by John L. Arnott and Muhammad Y. Javad
`(hereinafter the "Arnott article"). The Arnott article notes
`that the majority of disambiguation approaches employ
`5 known statistics of character sequences in the relevant
`language to resolve character ambiguity in a given context.
`That is, existing disambiguating systems statistically ana-
`lyze ambiguous keystroke groupings as they are being
`entered by a user to determine the appropriate interpretation
`to of the keystrokes. The Arnott article also notes that several
`disambiguating systems have attempted to use word level
`disambiguation to decode text from a reduced keyboard.
`Word level disambiguation disambiguates entire words by
`comparing the sequence of received keystrokes with pos-
`15 sible matches in a dictionary after the receipt of an unam-
`biguous character signifying the end of the word. The Arnott
`article discusses many of the disadvantages of word-level
`disambiguation. For example, word level disambiguation
`oftentimes fails to decode a word correctly, because of the
`20 limitations in identifying unusual words and the inability to
`decode words that are not contained in the dictionary.
`Because of the decoding limitations, word level disambigu-
`ation does not give error-free decoding of unconstrained
`English text with an efficiency of one keystroke per char-
`25 acter. The Arnott article therefore concentrates on character
`level disambiguation rather than word level disambiguation,
`and indicates that character level disambiguation appears to
`be the most promising disambiguation technique.
`Still another suggested approach is disclosed in a textbook
`30 entitled Principles of Computer Speech, authored by I. H.
`Witten, and published by Academic Press in 1982
`(hereinafter the "Witten approach"). Witten discusses a
`system for reducing ambiguity from text entered using a
`telephone touch pad. Witten recognizes that for approxi-
`35 mately 92% of the words in a 24,500 word dictionary, no
`ambiguity will arise when comparing the keystroke
`sequence with the dictionary. When ambiguities do arise,
`however, Witten notes that they must be resolved interac-
`tively by the system presenting the ambiguity to the user and
`40 asking the user to make a selection between the number of
`ambiguous entries. A user must therefore respond to the
`system's prediction at the end of each word. Such a response
`slows the efficiency of the system and increases the number
`of keystrokes required to enter a given segment of text.
`Disambiguating an ambiguous keystroke sequence con-
`tinues to be a challenging problem. As noted in the publi-
`cations discussed above, satisfactory solutions that minimize
`the number of keystrokes required to enter a segment of text
`have failed to achieve the necessary efficiencies to be
`50 acceptable for use in a portable computer. Moreover, the
`publications have taught away from using word level dis-
`ambiguation and have focused on character level disambigu-
`ating techniques. It would therefore be desirable to develop
`a disambiguating system that minimizes the ambiguity of
`55 entered keystrokes and thereby maximizes the efficiency of
`text entry.
`
`45 (cid:9)
`
`SUMMARY OF THE INVENTION
`The present invention provides a reduced keyboard using
`60 word level disambiguation to resolve ambiguities in key-
`strokes. The keyboard is constructed with full-size keys,
`preferably twelve keys arrayed in three columns and four
`rows or three rows and four columns. A plurality of letters
`and symbols are assigned to at least several of the keys, so
`65 that keystrokes by a user are ambiguous. A user enters a
`keystroke sequence wherein each keystroke corresponds to
`the entry of one letter of a word. Because individual key-
`
`30
`
`

`

`6,011,554
`
`40
`
`60 (cid:9)
`
`strokes are ambiguous, the keystroke sequence could poten-
`tially match more than one word with the same number of
`letters. The keystroke sequence is processed by comparing
`the keystroke sequence with stored vocabulary modules to
`match the sequence with corresponding stored words or
`other interpretations. Words that match the sequence of
`keystrokes are simultaneously and automatically presented
`to the user in a list on a display as each keystroke is received
`(hereinafter referred to as "the selection list"). The other
`interpretations of the keystroke sequence are also provided
`to the user in the selection list. The words and other
`interpretations are presented in order of decreasing fre-
`quency of use, with the most commonly used word pre-
`sented first.
`In accordance with one aspect of the invention, the user
`presses an unambiguous select key to delimit an entered
`keystroke sequence. After receiving the select key, the
`disambiguating system automatically selects the most com-
`monly used word and adds the word to the sentence being
`constructed if the user continues to enter additional text.
`In accordance with another aspect of the invention, the
`select key that is pressed by the user to delimit the end of a
`word is also used to select less commonly used words from
`the selection list presented to the user. If the most commonly
`used word presented to the user at the top of the selection list
`is not the desired word, the user presses the select key again
`to advance from the most frequently used word to the second
`most frequently used word, and again to advance to the third
`most frequently used word, and so on. By repetitively
`pressing the select key, the user may therefore select the
`desired word from the selection list. Upon reaching the end
`of the displayed selection list, additional less commonly
`used words scroll into the selection list with continued
`presses of the select key. The reduced keyboard disambigu-
`ating system automatically inserts the appropriate spacing
`between the words.
`In accordance with yet another aspect of the invention,
`multiple interpretations of the keystroke sequence are pro-
`vided to the user in the selection list. The keystroke sequence
`is interpreted as forming a word, and the corresponding
`word is displayed in the selection list. Simultaneously, the
`keystroke sequence is interpreted as a number, as a word
`entered using a two-stroke or multiple-stroke specification
`method, as a stem of an uncompleted word, or as a system
`command. The multiple interpretations are simultaneously
`presented to the user for each keystroke of a keystroke
`sequence entered by the user. The user may select from the
`alternate interpretations by pressing the select key a number
`of times.
`In accordance with still another aspect of the invention, a
`method to enter words that are not contained in the vocabu-
`lary is provided. To enter unusual words, such as proper
`names, a two-stroke specification method is used. A first
`keystroke indicates the key containing the letter, and a
`second keystroke disambiguates the first keystroke.
`Preferably, the system simultaneously interprets each
`sequence of keystrokes as both an ambiguous sequence of
`one stroke per letter and as a fully specified sequence of two
`strokes per letter.
`In accordance with still another aspect of the invention, a
`second method to enter unusual words that are not contained
`in the vocabulary is provided, using a multiple-stroke speci-
`fication method. In this method, a sequence of keystrokes is
`interpreted as unambiguously specifying a specific string of
`alphabetic characters by requiring from one to three key-
`presses per letter. Preferably, each key contains up to three
`
`n
`letters that are arranged in a row on the top of each key. The
`letters are ordered from left to right on each keytop in order
`of decreasing frequency, so that the most frequently occur-
`ring letter is in the leftmost position. Each letter of a word
`5 may be unambiguously spelled by pressing the key on which
`the letter appears a number of times corresponding to the
`position of the desired letter in the row. Thus, the leftmost
`letter is specified by a single keypress, the center letter by
`two keypresses, and the rightmost letter by three keypresses.
`to The system simultaneously interprets each sequence of
`keystrokes as both an ambiguous sequence of one stroke per
`letter and as a fully specified sequence using the multiple-
`stroke specification method.
`At the user's option, either or both of the two-stroke and
`15 multiple-stroke interpretations are displayed in the selection
`list of possible words. The user therefore does not have to
`change modes to enter words using either of these specifi-
`cation methods. Instead, when the user wants to enter a word
`that is not in the vocabulary, the user simply uses the
`20 preferred specification method, and then presses the select
`key to move down the selection list and select the desired
`interpretation of the keystroke sequence. In the vast majority
`of cases, these interpretations will be the only valid choices
`left in the selection list, so that only one or two presses of
`25 the select key will be required.
`In accordance with yet another aspect of the invention,
`words that are entered by the user using the two-stroke or
`multiple-stroke specification methods that are not in a
`vocabulary module are automatically added to a vocabulary
`30 module. The added words can subsequently be displayed
`upon entry of one stroke per letter.
`In accordance with still another aspect of the invention,
`words are stored in a vocabulary module using a tree data
`structure. Words corresponding to a particular keystroke
`sequence are constructed using the set of words associated
`with an immediately preceding keystroke sequence (i.e., the
`particular keystroke sequence without the last keystroke).
`Constructing words in this manner greatly reduces the
`storage space of the vocabulary module.
`In accordance with yet another aspect of the invention,
`letters are assigned to the keys in a non-sequential order.
`Rather than assigning the letters from "a" to "z," the letters
`are grouped onto the keys in a manner that reduces the
`45 frequency of ambiguities during word entry. In particular,
`the letters are assigned on the keys to take into account the
`frequency of use of each word in the disambiguating sys-
`tem's vocabulary modules. That is, the letters are grouped to
`reduce the ambiguities between the most commonly entered
`so words. The grouping of the letters on the keys is therefore
`optimized with respect to one or more preferred vocabulary
`modules that include information regarding the frequency of
`common usage.
`In accordance with still another aspect of the invention,
`ss the keyboard of the reduced keyboard disambiguating sys-
`tem may be replaced with an input device movable to
`multiple states. Each state is associated with a keystroke,
`allowing a user to input text by appropriate movement of the
`input device.
`The combined effects of the non-sequential and optimized
`assignment of letters to keys, the delimiting of words using
`a select key, the presentation of the most commonly occur-
`ring word as the first word in the selection list, the inclusion
`of multiple interpretations in the selection list, the automatic
`65 addition of a selected word to a sentence by the first
`keystroke of the following word, and the automatic addition
`of spaces produces a surprising result: for over 99% of
`
`35
`
`31
`
`

`

`6,011,554
`
`5
`entered words, the same number of keystrokes is required to
`enter a word with the reduced key disambiguating system as
`for word entry with a conventional keyboard. Because
`ambiguities are reduced and the words are presented in
`frequency of use order, the desired word is most often the
`first word presented and is frequently the only word pre-
`sented. The user simply proceeds to enter the next word with
`no more than the usual number of keystrokes. High speed
`entry of text is therefore achieved using a keyboard having
`a small number of full-size keys.
`Moreover, the reduced keyboard disambiguation system
`disclosed herein also minimizes the size of the computer or
`other device that incorporates the system. The reduced
`number of keys allows a device to be constructed that may
`be held by the user in one hand, while being operated with
`the other hand. The disclosed system is therefore particularly
`advantageous for use with PDAs, two-way pagers, or other
`small electronic devices that would benefit from accurate
`and high-speed text entry.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The foregoing aspects and many of the attendant advan-
`tages of this invention will become more readily appreciated
`as the same becomes better understood by reference to the
`following detailed description, when taken in conjunction
`with the accompanying drawings, wherein:
`FIGS. 1A and IB are perspective views of a preferred
`embodiment of a portable computer incorporating a reduced
`keyboard disambiguating system of the present invention,
`the disambiguating system including a reduced keyboard
`and a display for displaying text and a selection list;
`FIG. 2 is a hardware block diagram of the reduced
`keyboard disambiguating system of FIG. 1;
`FIG. 3 is a flow chart of disambiguating software for the
`reduced keyboard disambiguating system of FIG. 1;
`FIGS. 4A-4C are diagrams depicting the construction of
`a preferred vocabulary module and associated object lists for
`the