Explicit character filtering of ambiguous text entry

• US 8,381,137 B2
• Filed: 03/16/2010
• Issued: 02/19/2013
• Est. Priority Date: 12/03/1999
• Status: Expired due to Term

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Tegic Communications, Inc. (Microsoft Corporation)
• Inventors: Bradford, Ethan Robert, Hullfish, Keith Charles, Kay, David J., Meurs, Pim Van, Longe, Michael R.
• Primary Examiner(s): YEN, ERIC L
• Application Number:
  US12/725,334
• Publication Number:
  US 20100174529A1
• Time in Patent Office: 1,071 Days
• Field of Search: 715/864, 715/200, 715/773, 341/22, 379/368, 400/485
• US Class Current: 715/864
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 3/02 Input arrangements using manually operated switches, e.g. using keyboards or dials
• CPC Class Codes: G06F 3/0233 Character input methods
• CPC Class Codes: G06F 3/0235 using chord techniques G06F3/0234 takes precedence
• CPC Class Codes: G06F 3/0236 using selection techniques to select from displayed items
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: G10L 13/08 Text analysis or generation of parameters for speech synthesis out of text, e.g. grapheme to phoneme translation, prosody generation or stress or intonation determination

Abstract

The present invention relates to a method and apparatus for explicit filtering in ambiguous text entry. The invention provides embodiments including various explicit text entry methodologies, such as 2-key and long pressing. The invention also provides means for matching words in a database using build around methodology, stem locking methodology, word completion methodology, and n-gram searches.

Claims

1. An apparatus for explicit character filtering of ambiguous key input sequences from a reduced keyboard, said apparatus comprising:

a processor, wherein said processor manages output of objects to a display operatively coupled to said processor;

a keyboard comprising a plurality of keys, said keyboard being operatively coupled to the processor through appropriate interfacing circuitry, wherein at least some of said keys are associated with at least two characters, wherein said keyboard is configured to accept a plurality of types of key inputs including;

one-tap key inputs, wherein one-tap key inputs of said keys associated with at least two characters comprise an ambiguous key input, and

at least one alternate type of key input that comprises the explicit entry of a single intended character;

wherein said processor receives at least one sequence of key inputs from said keyboard, and wherein said at least one sequence of key inputs includes any one of an ambiguous key input and an explicitly entered character input in a particular position within a sequence of key inputs, wherein said particular position is a position of any one of the at least one sequence of key inputs;

a means for distinguishing said at least one explicitly entered character input from an ambiguous key input;

a memory coupled to said processor, wherein said memory comprises;

an object database, wherein objects are associated with sequences of key inputs;

a means for disambiguating the at least one sequence of key inputs at an object level, wherein a set of candidate objects associated with said at least one sequence of key inputs is identified; and

a means for filtering the set of candidate objects, wherein objects from the set of candidate objects which do not contain said at least one explicitly entered character input in said particular position within the sequence of key inputs are filtered out of the set of candidate objects thereby forming a filtered set of candidate words, wherein only the filtered set of candidate objects are output to said display;

wherein said characters comprise letters, digits, punctuation marks, Japanese kana, Korean jamos, and icons; and

wherein objects comprise sequences of characters, words, part of words, word stems, icons, phone numbers, and inventory records.

2. The apparatus of claim 1, further comprising speech synthesis software and a speaker as a communication aid.

3. The apparatus of claim 1, further comprising means for entering an explicit character by any of or any combination of, but not limited to:

2-key explicit entry;

long pressing a key to display and cycle through a character sequence;

long pressing on a key to enter a number/digit explicitly;

changing to a numbers mode and pressing a key to enter a number/digit explicitly;

changing to a multi-tap mode and pressing a key repeatedly to enter a character explicitly;

interpreting ambiguous mode key presses as an explicit character, either by grouping each pair of key presses as a 2-key explicit entry, or by grouping repeated presses of the same key as a multi-tap entry;

using multi-switch keys, thereby permitting ambiguous entry on a simple press and an explicit character entry on a different kind of press;

chording by pressing more than one key simultaneously, with a primary key indicating an ambiguous set of characters and a secondary key indicating which character in the set to select; and

using a softkey as a secondary means for offering any character assigned to a key based on analysis of most likely character associated with a preceding keystroke or based on words in a current word candidate list.

4. The apparatus of claim 3, further comprising a means for entering an explicit character by 2-key explicit entry comprising use of at least one of:

a matrix display;

a label including a subset of predetermined sets of associated characters; and

a scrolling list.

5. The apparatus of claim 3, wherein long pressing a key to display and cycle through a character sequence further comprises , after a character sequence is displayed, either of,:

a next character in said character sequence is highlighted each additional time said key is pressed, ending after a sufficient time elapses between one key press and the next or when a different key is pressed;

or

a next character in said character sequence is highlighted each time a navigation key is pressed.

6. The apparatus of claim 1, further comprising:

means for entering an explicit character by long pressing a specific key to display and cycle through a character sequence, and at least one of;

means for, after said character sequence is displayed, highlighting a next character in said character sequence each time said specific key is pressed, ending after a sufficient time elapses between each press of said specific key or when a key other than said specific key is pressed; and

means for, after said character sequence is displayed, highlighting a next character in said character sequence each time a navigation key is pressed.

7. The apparatus of claim 1, said explicit character filtering software further comprising:

means for matching said objects in said database against explicitly entered characters and ambiguously entered characters as long as possible, rather than accepting a default word upon a first explicitly entered character.

8. The apparatus of claim 1, further comprising:

means for selecting a desired object from said filtered set of candidate objects.

9. The apparatus of claim 8, wherein said candidate objects are presented in a predetermined order.

10. The apparatus of claim 1, said means for explicit character filtering of the identified objects further comprises a means for building an object around at least one delimiting character.

11. The apparatus of claim 10, wherein said means for building an object around at least one delimiting character further comprises at least one means from a group consisting of:

means for interpreting by matching objects which include explicitly entered characters for a particular sequence;

means for interpreting by matching objects which include at least one object that matches ambiguous keys that precede said at least one delimiting character;

means for interpreting by matching objects which include at least one object that matches ambiguous keys that end with said at least one delimiting character;

means for interpreting by matching objects which include at least one object that begins with said at least one delimiting character; and

means for interpreting by matching objects which include at least one object that follows said at least one delimiting character.

12. The apparatus of claim 10, wherein said means for building an object around at least one delimiting character is actuated by pressing a next key to obtain a next set of results from multiple searches in said object database.

13. The apparatus of claim 1, said means for explicit character filtering of the identified objects further comprises a means for stem locking for eliminating re-interpreting at least one series of characters by marking said at least one series of characters as explicitly entered.

14. The apparatus of claim 13, said means for stem locking further comprising at least one from a group consisting of:

a full next locking mechanism, wherein a next key press locks one of said at least one series of characters;

unbounded locking by moving cursor over one of said at least one series of characters by using an arrow key;

means for using previously explicitly entered characters preceding said at least one sequence of key inputs by matching objects in said database, wherein said objects begin with said explicitly entered characters and match said ambiguously entered key sequence;

object completion capability;

means for allowing pressing a key to be assigned to a locking in function;

means for allowing pressing an appropriate arrow key to lock in a word completion being offered;

a hierarchy of locking mechanism; and

means for generating objects when a desired object is not stored in said object database.

15. The apparatus of claim 14, said full next locking mechanism further comprising means for identifying and using word boundaries.

16. The apparatus of claim 14, said means for generating objects when a desired object not stored in said object database further comprising:

means for receiving a first set of characters comprising a series of locked in entries;

means for receiving a subsequent ambiguous entry associated with a second set of characters;

means for searching said database for a first desired object using said entered first set of locked in characters;

means for allowing selecting said first desired object, responsive to said first desired object being found in said database; and

means for performing at least one subsequent search by locking in and searching on a subset of said second set of characters for a second desired object in said object database;

means for allowing selecting said second desired object, responsive to said second desired object being found in said object database;

wherein said desired object comprises said first desired object and said second desired object.

17. A method for explicit character filtering of key input sequences, said method comprising the steps of:

operatively coupling a processor with a display, wherein said processor manages output of objects to a display;

operatively coupling said processor with a keyboard, said keyboard comprising a plurality of keys, wherein at least some of the keys are associated with at least two characters, wherein one-tap key inputs of said keys associated with at least two characters comprise an ambiguous key input, and wherein non-one-tap key inputs of said keys associated with at least two characters comprise an explicit key input that specifies precisely one intended character,

wherein said processor receives at least one sequence of key inputs from said keyboard, and wherein said at least one sequence of key inputs includes any one of an ambiguous key input and an explicitly entered character input in a particular position within a sequence of key inputs, wherein said particular position is a position of any one of the at least one sequence of key inputs;

distinguishing a non-one-tap key input from a one-tap key input;

providing a memory coupled to said processor, wherein said memory comprises;

an object database; and

disambiguating ambiguous key inputs in said key input sequences;

identifying objects in said object database that are associated with the sequence of key inputs, forming identified words; and

filtering objects from the identified objects based on the input of at least one intended character in said particular position within the sequence of key inputs, forming filtered objects; and

causing an output to said display of said filtered objects;

wherein said characters comprise letters, digits, punctuation marks, Japanese kana, Korean jamos, and icons; and

wherein objects comprise sequences of characters, words, part of words, word stems, icons, phone numbers, and inventory records.

18. The method of claim 17, further comprising providing speech synthesis software and a speaker as a communication aid.

19. The method of claim 17, wherein the step of recognizing a non-one-tap key input from a one-tap key input is accomplished by techniques selected from among a group of precise character entry techniques consisting of:

2-key explicit entry;

long pressing a key to display and cycle through a character sequence;

long pressing on a key to enter a number/digit explicitly;

changing to a numbers mode and pressing a key to enter a number/digit explicitly;

changing to a multi-tap mode and pressing a key repeatedly to enter a character explicitly;

interpreting ambiguous mode key presses as an explicit character by grouping each pair of key presses as a 2-key explicit entry;

interpreting ambiguous mode key presses as an explicit character by grouping repeated presses of the same key as a multi-tap entry;

using multi-switch keys, thereby permitting ambiguous entry on a simple press and an explicit character entry on a different kind of press;

chording by pressing at least two keys simultaneously, with a primary key indicating an ambiguous set of characters and a secondary key indicating which character in the set to select; and

using a softkey as a secondary means for offering any character assigned to a key based on analysis of most likely character associated with a preceding keystroke based on words in a current word candidate list.

20. The method of claim 19, further comprising entering a precisely intended character by 2-key explicit entry, wherein said 2-key explicit entry further comprises use at least one of:

a matrix display;

a label including a subset of predetermined sets of associated characters; and

a scrolling list.

21. The method of claim 17, further comprising entering an intended character by long pressing a key to display and cycle through a character sequence, wherein said cycling through a character sequence further comprises, after said character sequence is displayed, at least one of:

highlighting a next character in said character sequence each time said specific key is pressed, ending after a sufficient time elapses between each press of said specific key or when a key other than said specific key is pressed; and

highlighting a next character in said character sequence each time a navigation key is pressed.

22. The method of claim 17, said means for filtering objects from the identified objects based on the at least one intended character further performing the step of:

matching said objects in said object database against said intended character; and

automatically accepting for output an object matching a first subset of the input sequence when entry of an additional input prevents the matching of at least one object in said database.

23. The method of claim 17, said explicit character filtering software further comprising:

selecting a desired character either ambiguously or explicitly, thereby actuating interpreting candidate desired objects using said ambiguously selected and explicitly selected characters by searching said object database for objects with characters associated with said ambiguously selected keys and with said explicitly selected characters, said characters in respective corresponding positions, and presenting said searched objects;

determining whether a desired object is among said presented searched objects;

if said desired object is not among said presented searched objects, repeating method from said selecting a desired key step; and

selecting said desired object.

24. The method of claim 17, wherein said filtered objects are displayed in a predetermined order.

25. The method of claim 17, wherein said filtered objects are displayed in a prioritized order.

26. The method of claim 17, said means for filtering objects from the identified objects based on the at least one intended character further performing the step of building an object around at least one intended character.

27. The method of claim 26, wherein said building an object around at least one intended character further comprises at least one step from a group of steps consisting of:

interpreting by matching objects which include said at least one intended character at a particular position in said sequence of key inputs;

interpreting by matching objects which include at least one object that matches ambiguous keys that precede said at least one intended character;

interpreting by matching objects which include at least one object that matches ambiguous keys that end with said at least one intended character;

interpreting by matching objects which include at least one object that begins with said at least one intended character; and

interpreting by matching objects which include at least one object that follows said at least one intended character.

28. The method of claim 26, wherein said building an object around at least one intended character is actuated by pressing a next key to obtain a next set of results from multiple searches in said object database.

29. The method of claim 17, said means for filtering objects from the identified objects based on the at least one explicit input further performing the step of stem locking for eliminating re-interpreting at least one series of characters by marking said series of characters as explicitly entered.

30. The method of claim 29, said stem locking further comprising performing at least one step from a group of steps consisting of:

providing a full next locking mechanism, wherein a next key locks one of said at least one series of characters;

providing unbounded locking by moving cursor over one of said at least one of said series of characters by using an arrow key;

using previously explicitly entered characters preceding a current sequence of key inputs by matching objects in said object database, wherein said objects begin with said intended characters and match said sequence of key inputs;

providing object completion capability;

allowing pressing a key to be assigned to a locking in function;

allowing pressing an appropriate arrow key to lock in a word completion being offered;

providing a hierarchy of locking mechanism; and

generating objects when a desired object is not stored in said object database.

31. The method of claim 30, said full next locking mechanism further performing the step of identifying and using word boundaries.

32. The method of claim 30, said step of generating objects when a desired object is not stored in said object database further comprising the steps of:

receiving a first set of characters comprising a series of locked in entries;

receiving a subsequent sequence of key inputs entry associated with a second set of characters;

searching said object database for a first desired object using said entered first set of locked in characters;

allowing selecting said first desired object, responsive to said first desired object being found in said object database; and

performing at least one subsequent search by locking in and searching on a subset of said second set of characters for a second desired object in said object database;

allowing selecting said second desired object, responsive to said second desired obiect being found in said object database;

wherein said desired object comprises said first desired object and said second desired obiect.

33. An apparatus for explicit character filtering of ambiguous text entry, said apparatus comprising:

a keyboard and a display each coupled to a processor through appropriate interfacing circuitry, wherein said processor receives input characters from said keyboard and manages output objects to said display;

a memory coupled to said processor, wherein said memory comprises;

an operating system;

disambiguating software;

explicit character filtering in ambiguous text entry software; and

an object database,

wherein said explicit character filtering software, when executed by said processor;

when one or more characters in a sequence of characters are explicitly entered, retrieves only stored objects from said object database having said explicitly entered characters in corresponding positions; and

matches said objects in said database against explicitly entered characters and ambiguously entered characters as long as possible, rather than accepting a default word upon a first explicitly entered character;

wherein said characters comprise letters, digits, punctuation marks, Japanese kana, Korean jamos, and icons; and

wherein objects comprise sequences of characters, words, part of words, word stems, icons, phone numbers, and inventory records.

34. The apparatus of claim 33, said explicit character filtering software, when executed by said processor:

selects a desired character either ambiguously or explicitly, thereby actuating interpreting candidate desired objects using said ambiguously selected and explicitly selected characters by searching said object database for objects with characters associated with said ambiguously selected keys and with said explicitly selected characters, said characters in respective corresponding positions, and presents said searched objects;

determines whether a desired object is among said presented searched objects;

if said desired object is not among said presented searched objects, continues execution from said selection of a desired character; and

selects said desired object.