Explicit Character Filtering of Ambiguous Text Entry

• US 20100174529A1
• Filed: 03/16/2010
• Published: 07/08/2010
• Est. Priority Date: 12/03/1999
• Status: Active Grant

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: David J. Kay, Ethan Robert Bradford, Keith Charles Hullfish, Michael R. Longe, Pim Van Meurs
• Inventors: Meurs, Pim Van, Longe, Michael R., Kay, David J., Hullfish, Keith Charles, Bradford, Ethan Robert
• Granted Patent: US 8,381,137 B2
• Time in Patent Office: Days
• US Class Current: 704/10
• 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 both at least one ambiguous key input and at least one explicitly entered character input in a particular position within the sequence of key inputs;

a means for recognizing 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.

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

3. The apparatus of claim 1, wherein said characters comprise, but are not limited to letters, digits, punctuation marks, symbols from any language, Japanese kana, Korean jamos, icons, and the like;

and

wherein objects comprise, but are not limited to sequences of characters, words, part of words, word stems, icons, phone numbers, inventory records, and the like.

4. 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.

5. The apparatus of claim 4, 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.

6. The apparatus of claim 4, said long pressing further comprising, after said character sequence is displayed, either of, but not limited to:

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.

7. The apparatus of claim 1, further comprising:

means for entering an explicit character by long pressing a 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 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; and

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

8. 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.

9. The apparatus of claim 1, further comprising:

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

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

11. 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.

12. The apparatus of claim 11, 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.

13. The apparatus of claim 11, wherein said means for building an object around is actuated by pressing a next key to obtain a next set of results from multiple searches in said object database.

14. 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.

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

a full next locking mechanism, wherein a next key 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 not stored in said object database.

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

17. The apparatus of claim 15, said means for generating objects 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 said desired object using said entered first set of locked in characters and said subsequent ambiguous entry;

means for allowing selecting said desired object, responsive to said 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, responsive to said desired object not being found in said database.

18. A method for explicit character filtering of ambiguous 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, such that key inputs from said keys 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 comprises 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 both at least one ambiguous key input resulting from a one-tap key input and at least one explicitly entered intended character input in a particular position within the sequence of key inputs;

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

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

a an object database;

a means for disambiguating key input sequences;

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

a means for filtering objects from the identified objects based on the input of at least one of said 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.

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

20. The method of claim 18, 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.

21. The method of claim 18, wherein said characters comprise, but are not limited to letters, digits, punctuation marks, symbols from any language, Japanese kana, Korean jamos, icons, and the like;

and wherein objects comprise, but are not limited to sequences of characters, words, part of words, word stems, icons, phone numbers, inventory records, and the like.

22. The method of claim 20, 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.

23. The method of claim 18, 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 further comprises, after said character sequence is displayed, at least one of:

highlighting a next character in said character sequence 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; and

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

24. The method of claim 18, 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, responsive to if the addition of an input preventing the matching of at least one object in said database.

25. The method of claim 18, 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.

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

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

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

29. The method of claim 28, wherein said building around 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.

30. The method of claim 28, wherein said building around is actuated by pressing a next key to obtain a next set of results from multiple searches in said object database.

31. The method of claim 18, 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.

32. The method of claim 31, 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 not stored in said object database.

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

34. The method of claim 32, said step of generating objects 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 said desired object using said entered first set of locked in characters and a subsequent key entry;

allowing selecting said desired object, responsive to said 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, responsive to said desired object not being found in said object database.

35. 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 further comprising;

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

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.

36. The apparatus of claim 35, said explicit character filtering software further comprising:

means for 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;

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

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

means for selecting said desired object.