not have all the nodes between the marked leaf and the root node marked as well. An incomplete path is a path that has a non-leaf node marked, but may not have all intervening nodes between the marked non-leaf node and the root node marked as well.
FIG. 4 shows a simplified representation of an array (40) of data elements (4-1 through 4-12) that is a keyword dictionary. The array (40) is a one-dimensional associative array, each word of which (4-1:4-12) is itself an index into the linked lists (60). The array (40) could be stored in random access memory, magnetic tape or disk, or other memory.
FIG. 4 also shows the relationships of the data elements (40) of the keyword dictionary and the node(s) shown in FIG. 3 representing the relationships between the pre-defined keywords. FIG. 4 also shows linked lists (4-14 through 4-36).
Each data element (4-16:4-12) in the array of data elements (40) includes a pointer, not shown, which is effectively the starting address of an associated linked list (4-14; 4-1; 4-18; 4-20; 4-22; 4-24; 4-26; 4-28; 4-30; 4-32; 4-34; 4-36) stored in the computer. The linked lists of FIG. 4 (4-14; 4-16; 4-18; 4-20; 4-22; 4-24; 4-26; 4-28; 4-30; 4-32; 4-34; 4-36) are represented in the tree graph (70) of FIG. 3 by the line segments pointing to the nodes on the tree graph that are enumerated 0 through 20.
The array of recognizable keywords (4-1:4-12), which comprises a dictionary of recognizable keywords, the associated pointers (not shown) and the structure and organization of the linked lists ((4-14; 4-16; 4-18; 4-20; 4-22; 4-24; 4-26; 4-28; 4-30; 4-32; 4-34; 4-36)) are represented by the tree graph of FIG. 3 and effectively define both the recognizable keywords of the language and the relationships between the keywords.
FIG. 5 shows three data arrays (5-2; 5-3; 5-4) that effectively comprise the relationships between the various nodes of the tree graph (70) shown in FIG. 3. For the arrays shown in FIG. 5 (5-2, 5-3, 5-4) the index of the arrays (5-1) corresponds to the node number. The value of the array element in array 5-2 is the node number of the parent node. The second array (5-3) identifies the level or tier of the node in the tree graph. Knowing the level of a node in the tree graph expedites the process of path selection. The third array (5-4) identifies nodes that are leaves by “T” or “true” and nodes that are not leaves as “false”.
Each of the recognizable keywords (4-1:4-12) is defined by the language to have possible syntactical relationships with other keywords. Stated alternatively, each keyword (4-1:4-12) could be used with the other keywords, albeit in a limited number of possible combinations. The possible combinations that the keywords (4-1:4-12) that can be used with other keywords is specified and these relationships are representable by the links between the nodes in the tree graph (70) depicted in FIG. 3.
Each keyword (4-1:4-12) can be mapped to one or more nodes of the tree graph (70). Keywords that might be synonyms will be mapped to more than one node.
FIGS. 6, 7 and 8 show a graphical representation of the steps of the preferred method of practicing the invention.
FIG. 6 shows that user input is first requested (6-2). An empty set, Node_Set, (6-3) is created, which in FIGS. 9A, 9B, and 9C is implemented as an associative array. User input is obtained (6-4) and is then processed (6-5) as set forth in FIG. 7 to determine all complete paths through the tree graph of FIG. 3 that can be built from the user input obtained (6-4).
After the user input (6-4) has been processed (6-5) as set forth in FIG. 7, the procedure shown in FIG. 7 returns to the procedure shown in FIG. 6 a list of leaves that each correspond to a complete path. The entries in this list are in descending order according to their probability of being the correct path.
Another quantity returned by the procedure shown in FIG. 7 is the number of paths through the tree graph. This number is denoted in FIG. 6 as Npaths.
The variable I, is a loop counter, initially set to zero (6-6). If Npaths is equal to zero (6-8) no c