DICTIONARY COMPILATIONS

• US 20100011016A1
• Filed: 07/11/2008
• Published: 01/14/2010
• Est. Priority Date: 07/11/2008
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Greene, Andrew Marc
• Granted Patent: US 8,645,350 B2
• Time in Patent Office: Days
• US Class Current: N/A
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06F 40/151 Transformation
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/242 Dictionaries

Abstract

Apparatus, systems, and methods operate to obtain data from a first array constructed from a directed acyclic graph formed as a prefix tree having key strings associated with a plurality of interconnected nodes, including branch nodes coupled via branches to sibling nodes and child nodes. Reference numbers are assigned to nodes in a monotonic progression as the prefix tree is traversed along the plurality of nodes. Sibling nodes are assigned reference numbers before child nodes, and child nodes are assigned reference numbers according to the order of appearance of key string characters. The first array comprises the key strings ordered according to the reference numbers. A second array can be formed as a linear searchable index derived from data in the first array, with elements of the second array comprising the reference numbers. Additional apparatus, systems, and methods are disclosed.

Claims

1. A computer implemented method, comprising:

constructing a dictionary as a prefix tree having key strings associated with a plurality of nodes interconnected via branches, the plurality of nodes including at least one branch node coupled via some of the branches to sibling nodes of the branch node and child nodes of the branch node; and

assigning reference numbers to the plurality of nodes in a monotonic progression as the prefix tree is traversed along the plurality of nodes, wherein the sibling nodes are assigned the reference numbers before assigning the reference numbers to the child nodes, and wherein the child nodes are assigned the reference numbers according to order of appearance of characters in the key strings.

2. The method of claim 1, wherein constructing the dictionary comprises:

constructing the prefix tree as a directed acyclic graph with at least one of the child nodes comprising a redirect node that is associated with one of the key strings including a redirect indicator character and one of the references numbers assigned to an assigned node of the plurality of nodes so that searches may be redirected from the redirect node to the assigned node.

3. The method of claim 2, wherein the dictionary comprises words selected from a non-English language.

4. The method of claim 1, wherein constructing the dictionary comprises:

constructing the prefix tree as a directed acyclic graph with at least one of the child nodes comprising a chain node associated with one of the key strings including a plurality of alphabetic characters and coupled to either one or zero additional child nodes by the branches.

5. The method of claim 1, wherein alphabetic characters within a first group of the key strings are ordered according to a first letter frequency, and wherein alphabetic characters within a second group of the key strings are ordered according to a second letter frequency.

6. The method of claim 1, comprising:

at least one of displaying an error message to a user when a word in a document cannot be constructed by traversing the prefix tree along a path defined by some of the plurality of nodes and the branches, or displaying a suggested automatic completion of the word.

7. A computer implemented method, comprising:

retrieving data from a first array constructed from a directed acyclic graph formed as a prefix tree having key strings associated with a plurality of nodes interconnected via branches, the plurality of nodes including at least one branch node coupled via some of the branches to sibling nodes of the branch node and child nodes of the branch node, wherein reference numbers are assigned to the plurality of nodes in a monotonic progression as the prefix tree is traversed along the plurality of nodes, wherein the sibling nodes are assigned the reference numbers before assigning the reference numbers to the child nodes, wherein the child nodes are assigned the reference numbers according to order of appearance of characters in the key strings, and wherein the first array comprises the key strings ordered according to the reference numbers; and

forming a second array as a linear searchable index derived from the data, with each element of the second array comprising one of the reference numbers.

8. The method of claim 7, comprising:

adding, to the first array, an element comprising a non-repeating list of the characters.

9. The method of claim 8, comprising:

searching for a word formed by concatenating the characters included in the key strings along a path defined by some of the plurality of nodes and the branches; and

upon failing to find the word, displaying a list of suggested words according to the non-repeating list of the characters by inserting possible missing characters and replacing possible mistaken characters with possible intended substitute characters, the possible missing characters and the possible intended substitute characters included in the non-repeating list of the characters.

10. The method of claim 7, comprising:

designating some nodes of the plurality of nodes as a chain node by including a chain node indicator in the key string associated with the chain node.

11. The method of claim 10, comprising:

using a termination character in the key string associated with the chain node.

12. The method of claim 7, wherein forming the second array comprises:

forming the second array each time execution of a word processing application program is initiated, or language within the word processing application program is changed.

13. The method of claim 12, wherein at least one of the child nodes comprises:

a redirect node that is associated with one of the key strings including a redirect indicator character and one of the references numbers assigned to an assigned node of the plurality of nodes so that searches may be redirected from the redirect node to the assigned node.

14. The method of claim 7, comprising:

converting the reference numbers to a string representation having a radix of 10 to 40.

15. A system, comprising:

a display;

an index construction module to form a second array as a linear searchable index derived from a first array constructed from a directed acyclic graph formed as a prefix tree having key strings associated with a plurality of nodes interconnected via branches, the plurality of nodes including at least one branch node coupled via some of the branches to sibling nodes of the branch node and child nodes of the branch node, wherein reference numbers are assigned to the plurality of nodes in a monotonic progression as the prefix tree is traversed along the plurality of nodes, wherein the sibling nodes are assigned the reference numbers before assigning the reference numbers to the child nodes, wherein the child nodes are assigned the reference numbers according to order of appearance of characters in the key strings, wherein the first array comprises the key strings ordered according to the reference numbers, and wherein each element of the second array comprises one of the reference numbers; and

a rendering module to display words on the display after the words have been checked for spelling against a concatenation of alphabetic characters included in the key strings in the first array.

16. The system of claim 15, comprising:

a user input device;

a processor coupled to the display; and

a storage device to store a word processing application program which, when executed by the processor, is used to receive the words via the user input device.

17. The system of claim 15, comprising:

a server to store at least one of the first array or the second array; and

a client coupled to the server via a network, the client to receive the words via a user input device coupled to the client.

18. The system of claim 15, comprising:

a server to construct the first array; and

a client to form the second array, the client capable of being coupled to the server via a network, the client to receive the words via a user input device coupled to the client.

19. The medium of claim 18, the method comprising:

sorting the characters in the key strings according to a frequency of occurrence.

20. The medium of claim 18, the method comprising:

storing the second array in memory after initiating execution of an application program; and

deleting the second array from the memory about the same time as the execution is terminated.

21. The medium of claim 18, the method comprising:

designating some of the plurality of nodes as redirect nodes pointing to other nodes in the plurality of nodes, the reference numbers corresponding to line numbers of the first array, the redirect nodes associated with the key strings including the reference numbers assigned to the other nodes.

18-1. A computer-readable medium having instructions stored therein for causing a computer to implement a method, comprising:

retrieving data from a first array constructed from a directed acyclic graph formed as a prefix tree having key strings associated with a plurality of nodes interconnected via branches, the plurality of nodes including at least one branch node coupled via some of the branches to sibling nodes of the branch node and child nodes of the branch node, wherein reference numbers are assigned to the plurality of nodes in a monotonic progression as the prefix tree is traversed along the plurality of nodes, wherein the sibling nodes are assigned the reference numbers before assigning the reference numbers to the child nodes, wherein the child nodes are assigned the reference numbers according to order of appearance of characters in the key strings, and wherein the first array comprises the key strings ordered according to the reference numbers; and

forming a second array as a linear searchable index derived from the data, with each element of the second array comprising one of the reference numbers.