System and Method for Identifying Words Based on a Sequence of Keyboard Events

• US 20100235780A1
• Filed: 07/17/2009
• Published: 09/16/2010
• Est. Priority Date: 03/16/2009
• Status: Abandoned Application

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Goldsmith, Deborah E., Collins, Leland D., Wilson, Drew M., Westerman, Wayne C., Kocienda, Kenneth L.
• Application Number:
  US12/505,382
• Publication Number:
  US 20100235780A1
• Time in Patent Office: Days
• US Class Current: 715/797
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/04886 by partitioning the display area of the touch-screen or the surface of the digitising tablet into independently controllable areas, e.g. virtual keyboards or menus
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A system, a computer readable storage medium including instructions, and computer-implemented method for displaying at least one word based on a sequence of keyboard events. A sequence of keyboard events representing keystrokes is received. The sequence of keyboard events is processed by: accessing and traversing nodes of a trie data structure in accordance with the sequence of keyboard events and upon arriving at a word node of the trie data structure, identifying one or more corresponding words to be displayed, and displaying at least one word of the one or more corresponding words to be displayed.

Claims

1. A computer-implemented method, comprising:

on a client system having one or more processors executing one or more programs stored on memory of the client system;

receiving a sequence of keyboard events representing keystrokes;

processing the sequence of keyboard events by;

accessing and traversing nodes of a trie data structure in accordance with the sequence of keyboard events, the trie data structure including;

intermediate nodes and word nodes, each word node of the trie data structure corresponding to one or more complete words and having a default sequence of symbols corresponding to a traversed sequence of nodes ending at the word node;

a first respective word node including a reference to a word record specifying two or more distinct words based at least in part on the sequence of keyboard events; and

a second respective word node including no reference to a word record, wherein a complete word corresponding to the second respective word node is determined based on the default sequence of symbols corresponding to the traversed sequence of nodes ending at the second respective word node;

upon arriving at a word node of the trie data structure, identifying one or more corresponding words to be displayed; and

displaying at least one word corresponding to the one or more corresponding words to be displayed.

2. The computer-implemented method of claim 1, wherein accessing and traversing nodes of the trie data structure in accordance with the sequence of keyboard events includes:

receiving a first keyboard event representing a first keystroke in the sequence of keyboard events;

determining a first character corresponding to the first keyboard event; and

locating a first node of the trie data structure that corresponds to the first character.

3. The computer-implemented method of claim 2, further comprising:

when the first node of the trie data structure corresponds only to the first character, for a respective subsequent keyboard event in the sequence of keyboard events,

determining a next character corresponding to the subsequent keyboard event; and

traversing to a next node of the trie data structure from a current node of the trie data structure, wherein the next node of the trie data structure corresponds to the next character.

4. The computer-implemented method of claim 2, further comprising:

when the first node of the trie data structure corresponds to a sequence of characters including the first character and a second character that follows the first character, for a respective subsequent keyboard event in the sequence of keyboard events,

determining a next character corresponding to the subsequent keyboard event; and

remaining at the first node when the next character is the second character.

5. The computer-implemented method of claim 1, wherein identifying one or more corresponding words to be displayed includes:

determining whether the node of the trie data structure has a corresponding word list; and

in response to determining that the node of the trie data structure has a corresponding word list, identifying one or more words from the word list to be displayed.

6. The computer-implemented method of claim 5, wherein the corresponding word list includes metadata for the one or more words.

7. The computer-implemented method of claim 6, wherein the metadata includes a frequency of occurrence of a respective word in a respective language.

8. The computer-implemented method of claim 5, wherein in response to determining that the node of the trie data structure is a word node that does not have a corresponding word list, deriving a single word to be displayed based on the traversed sequence of nodes in the trie data structure.

9. The computer-implemented method of claim 5, wherein the corresponding word list includes one or more entries, and when the corresponding word list includes two or more entries, each entry corresponds to a respective word and includes a frequency value indicating frequency of occurrence of the respective word.

10. The computer-implemented method of claim 1, wherein identifying one or more corresponding words to be displayed includes:

determining whether the node of the trie data structure has a corresponding word list; and

in response to determining that the node of the trie data structure has a corresponding word list, performing one or more transformation operations on the default sequence of symbols to produce a word to be displayed.

11. The computer-implemented method of claim 10, wherein a respective entry of the corresponding word list includes a substitution list, the substitution list including one or more transformation operations, including a transformation operation selected from the group consisting of:

a transformation operation to substitute specified characters of the default sequence of symbols;

a transformation operation to insert one or more characters at a specified position in the default sequence of symbols;

a transformation operation to insert one or more symbols at a specified position in the default sequence of symbols; and

a transformation operation to transform one or more characters of the default sequence of symbols.

12. The computer-implemented method of claim 1, wherein a respective node of the trie data structure corresponds to one or more character forms.

13. The computer-implemented method of claim 12, wherein the one or more character forms include at least one of:

a capitalized character form;

an uncapitalized character form;

an accented character form; and

an unaccented character form.

14. The computer-implemented method of claim 1, wherein displaying at least one word corresponding to the one or more corresponding words to be displayed includes displaying only a single word based on a frequency of occurrence of the one word in a respective language.

15. A client system, comprising:

one or more processors;

memory; and

one or more programs stored in the memory, the one or more programs comprising instructions to;

receive a sequence of keyboard events representing keystrokes;

process the sequence of keyboard events by;

accessing and traversing nodes of a trie data structure in accordance with the sequence of keyboard events, the trie data structure including;

intermediate nodes and word nodes, each word node of the trie data structure corresponding to one or more complete words and having a default sequence of symbols corresponding to a traversed sequence of nodes ending at the word node;

a first respective word node including a reference to a word record specifying two or more distinct words based at least in part on the sequence of keyboard events; and

a second respective word node including no reference to a word record, wherein a complete word corresponding to the second respective word node is determined based on the default sequence of symbols corresponding to the traversed sequence of nodes ending at the second respective word node;

upon arriving at a word node of the trie data structure, identifying one or more corresponding words to be displayed; and

displaying at least one word corresponding to the one or more corresponding words to be displayed.

16. The client system of claim 15, wherein the instructions to access and traverse nodes of the trie data structure in accordance with the sequence of keyboard events includes instructions to:

receive a first keyboard event representing a first keystroke in the sequence of keyboard events;

determine a first character corresponding to the first keyboard event; and

locate a first node of the trie data structure that corresponds to the first character.

17. The client system of claim 16, further comprising instructions to:

when the first node of the trie data structure corresponds only to the first character, for a respective subsequent keyboard event in the sequence of keyboard events,

determine a next character corresponding to the subsequent keyboard event; and

traverse to a next node of the trie data structure from a current node of the trie data structure, wherein the next node of the trie data structure corresponds to the next character.

18. The client system of claim 16, further comprising instructions to:

when the first node of the trie data structure corresponds to a sequence of characters including the first character and a second character that follows the first character, for a respective subsequent keyboard event in the sequence of keyboard events,

determine a next character corresponding to the subsequent keyboard event; and

remain at the first node when the next character is the second character.

19. The client system of claim 15, wherein the instructions to identify one or more corresponding words to be displayed include instructions to:

determine whether the word node of the trie data structure has a corresponding word list; and

identify one or more words from the word list to be displayed in response to determining that the node of the trie data structure has a corresponding word list.

20. The client system of claim 19, wherein the corresponding word list includes metadata for the one or more words.

21. The client system of claim 20, wherein the metadata includes a frequency of occurrence of a respective word in a respective language.

22. The client system of claim 19, further comprising instructions to derive a single word to be displayed based on the traversed sequence of nodes in the trie data structure when the node of the trie data structure is a word node that does not have a corresponding word list.

23. The client system of claim 19, wherein the corresponding word list includes one or more entries, and when the corresponding word list includes two or more entries, each entry corresponds to a respective word and includes a frequency value indicating frequency of occurrence of the respective word.

24. The client system of claim 15, wherein the instructions to identify one or more corresponding words to be displayed include instructions to:

determine whether the node of the trie data structure has a corresponding word list; and

perform one or more transformation operations on the default sequence of symbols to produce a word to be displayed in response to determining that the node of the trie data structure has a corresponding word list.

25. The client system of claim 24, wherein a respective entry of the corresponding word list includes a substitution list, the substitution list including one or more transformation operations, including a transformation operation selected from the group consisting of:

a transformation operation to substitute specified characters of the default sequence of symbols;

a transformation operation to insert one or more characters at a specified position in the default sequence of symbols;

a transformation operation to insert one or more symbols at a specified position in the default sequence of symbols; and

a transformation operation to transform one or more characters of the default sequence of symbols.

26. The client system of claim 15, wherein a respective node of the trie data structure corresponds to one or more character forms.

27. The client system of claim 26, wherein the one or more character forms include at least one of:

a capitalized character form;

an uncapitalized character form;

an accented character form; and

an unaccented character form.

28. The client system of claim 15, wherein the instructions to display at least one word corresponding to the one or more corresponding words to be displayed include instructions to display only a single word based on a frequency of occurrence of the one word in a respective language.

29. A computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions to:

receive a sequence of keyboard events representing keystrokes;

process the sequence of keyboard events by;

accessing and traversing nodes of a trie data structure in accordance with the sequence of keyboard events, the trie data structure including;

intermediate nodes and word nodes, each word node of the trie data structure corresponding to one or more complete words and having a default sequence of symbols corresponding to s traversed sequence of nodes ending at the word node;

a first respective word node including a reference to a word record specifying two or more distinct words based at least in part on the sequence of keyboard events; and

a second respective word node including no reference to a word record, wherein a complete word corresponding to the second respective word node is determined based on the default sequence of symbols corresponding to the traversed sequence of nodes ending at the second respective word node;

upon arriving at a word node of the trie data structure, identifying one or more corresponding words to be displayed; and

displaying at least one word corresponding to the one or more corresponding words to be displayed.

30. The computer readable storage medium of claim 29, wherein the instructions to access and traverse nodes of the trie data structure in accordance with the sequence of keyboard events includes instructions to:

receive a first keyboard event representing a first keystroke in the sequence of keyboard events;

determine a first character corresponding to the first keyboard event; and

locate a first node of the trie data structure that corresponds to the first character.

31. The computer readable storage medium of claim 30, further comprising instructions to:

when the first node of the trie data structure corresponds only to the first character, for a respective subsequent keyboard event in the sequence of keyboard events,

determine a next character corresponding to the subsequent keyboard event; and

traverse to a next node of the trie data structure from a current node of the trie data structure, wherein the next node of the trie data structure corresponds to the next character.

32. The computer readable storage medium of claim 30, further comprising instructions to:

when the first node of the trie data structure corresponds to a sequence of characters including the first character and a second character that follows the first character, for a respective subsequent keyboard event in the sequence of keyboard events,

determine a next character corresponding to the subsequent keyboard event; and

remain at the first node when the next character is the second character.

33. The computer readable storage medium of claim 29, wherein the instructions to identify one or more corresponding words to be displayed include instructions to:

determine whether the node of the trie data structure has a corresponding word list; and

identify one or more words from the word list to be displayed in response to determining that the node of the trie data structure has a corresponding word list.

34. The computer readable storage medium of claim 33, wherein the corresponding word list includes metadata for the one or more words.

35. The computer readable storage medium of claim 34, wherein the metadata includes a frequency of occurrence of a respective word in a respective language.

36. The computer readable storage medium of claim 33, further comprising instructions to derive a single word to be displayed based on the traversed sequence of nodes in the trie data structure when the node of the trie data structure does not have a corresponding word list.

37. The computer readable storage medium of claim 33, wherein the corresponding word list includes one or more entries, and when the corresponding word list includes two or more entries, each entry corresponds to a respective word and includes a frequency value indicating frequency of occurrence of the respective word.

38. The computer readable storage medium of claim 29, wherein the instructions to identify one or more corresponding words to be displayed include instructions to:

determine whether the node of the trie data structure has a corresponding word list; and

perform one or more transformation operations on the default sequence of symbols to produce a word to be displayed in response to determining that the node of the trie data structure has a corresponding word list.

39. The computer readable storage medium of claim 38, wherein a respective entry of the corresponding word list includes a substitution list, the substitution list including one or more transformation operations, including a transformation operation selected from the group consisting of:

a transformation operation to substitute specified characters of the default sequence of symbols;

a transformation operation to insert one or more characters at a specified position in the default sequence of symbols;

a transformation operation to insert one or more symbols at a specified position in the default sequence of symbols; and

a transformation operation to transform one or more characters of the default sequence of symbols.

40. The computer readable storage medium of claim 29, wherein a respective node of the trie data structure corresponds to one or more character forms.

41. The computer readable storage medium of claim 40, wherein the one or more character forms include at least one of:

a capitalized character form;

an uncapitalized character form;

an accented character form; and

an unaccented character form.

42. The computer readable storage medium of claim 29, wherein the instructions to display at least one word corresponding to the one or more corresponding words to be displayed include instructions to display only a single word based on a frequency of occurrence of the one word in a respective language.