Method and system for presenting alternatives for selection using adaptive learning5706450Abstract A method and system for efficiently presenting a series of alternatives for a user's selection using adaptive learning is provided. In a preferred embodiment, a software facility receives a request to select an item from an identified group of alternatives. The facility presents items from the group of alternatives identified by the request in decreasing order of their likelihood of selection. The facility subsequently receives an indication of the alternative to select, and proceeds to select that alternative. In a further preferred embodiment, the items each correspond to a set of one or more characters that cannot be generated using an available keyboard, and, when the user uses the facility to select an item, the facility inputs the corresponding set of characters. Claims We claim: Description TECHNICAL FIELD
TABLE 1
______________________________________
theme group
______________________________________
lower case letters
a, a, a, a, a, a, a, .ae butted.
upper case letters
E, E, E, E, E
currency symbols
$, c/, .English Pound., .Yen.,
grouping characters
(, ), {, }, ›, !, <<, >>
fractions /, 1/4, 1/2, 3/4
quotes ", ", ", `, `
______________________________________
Each theme is one way of associating characters that cannot be generated using the keyboard with one or more "key characters" that may be generated using the keyboard. For example, the lower case letters theme can be used to associate foreign language characters that appear to contain the a character with the key character the a character, which may be generated by the keyboard. As another example, the currency symbols theme can be used to associate foreign currency symbols that cannot be generated using the keyboard with the key character (the dollar sign) character ("$"). Besides replacing key characters that appear on the keyboard, the facility can also replace key characters that have been inserted in the document by some other method. For example, the facility is able to replace characters inserted in the document using the above-discussed prior art methods of inputting a numerical character code or using a pointing device to select a character from a display character set, as well as characters earlier entered using the facility. FIG. 3 is a high-level block diagram of the general-purpose computer system upon which the facility preferably operates. The computer system 300 contains a central processing unit (CPU) 301, a computer memory (memory) 302, and input/output devices 303. Among the input/output devices are a keyboard 304, a display device 305, such as a monitor, and storage device 306, such as a hard disk drive. By pressing one or a combination of keys, the user is able to use the keyboard 304 to generate a character that is input into the computer system. The memory contains the program for the facility 307 and other programs 308-309 for inputting, displaying, and storing characters. Character groups like those shown in Table 1 are preferably stored in memory as arrays of characters, also called strings. In some circumstances it is preferable to store each group in a separate string. In some other circumstances, however, it is more convenient to store all the groups in the same string. In either case, each group is preferably stored by first storing the key character, then storing the characters of the group in decreasing anticipated likelihood of selection. The key character is also preferably stored at the end of the group, so that the user may select the key character if the user does not wish to select any of the other characters in the group. Storing the key character at the end of the group also has the advantage that the user may loop through the group repeatedly if desired. All of the programs preferably execute on the CPU. In an alternate preferred embodiment, the computer system shown in FIG. 3 is part of a distributed processing system, in which multiple computer systems that are connected by communication links work together to execute programs, executing each of a number of different parts of a single program on the CPUs of different computer systems. FIG. 4 is a flow diagram showing the steps required to use the facility to input a target character. While the steps shown in the other flow diagram figures are preferably executed by the facility, these steps shown in FIG. 4 are preferably carried out by a human user. In step 401, the user determines the key character that corresponds to the target character. In most cases, this involves identifying the theme most likely to encompass the target character, then determine the key character for the correct group having that theme. As an example, suppose the target character was the a-accent-aigu character. Because the a-accent-aigu character looks something like the a character, it is likely to be in a group having the theme lowercase letters and for which the key character is the a character. In step 402, the user types the key character, in this case the a character. FIG. 5 is a screen image showing the user carrying out step 402. The screen image shows a program window 500 generated by a program for inputting, displaying, and storing characters. The program window 500 containing text 501. As part of the text 501, the user has already entered the a character 502. In step 403, the user invokes the Replace function. Briefly, the Replace function replaces the key character with the next character in the key group. The user preferably invokes the Replace function by typing a command key combination on the keyboard that is received by a program that is able to execute the facility. The Replace function is described in more detail below. FIG. 6 is a screen image showing the replacement of the key character with the first character in the key character's group. The screen image shows a program window 600 containing text 601. The Replace function has replaced the last letter of the text 601 with an a-umlaut character ("a") 602. In step 404, if the replace function replaced the key character with the target character, then these steps conclude, else the user continues its step 403 to invoke the replace function again. Since the key character a was replaced with an a-umlaut character and not the target character a-accent-aigu, the user continues at step 403. In step 403, the user invokes the replace function again. FIG. 7 is a screen image showing the replacement of the key character with the second character following the key character in the key character's group. The screen image shows a program window 700 containing text 701. The Replace function has replaced the last character of the text 701 with the next character in the group, the a-accent-aigu character 702. In step 404, because the key character has been replaced with the target character, these steps conclude. After the user has used the facility to input the a-accent-aigu character, the facility updates the order of the group that contains the a-accent-aigu character. This involves determining whether the selection of the a-accent-aigu character changes the order of anticipated likelihood of selection of the characters within the group for the future, and, if so, reorders the group to reflect the new order of anticipated likelihood of selection of the characters in the group. The facility uses several different update approaches, described below, to determine whether a selection changes the order of anticipated likelihood of selection of the characters in a group. Under several of these approaches, after the user uses the facility to input the a-accent-aigu character, the a-accent-aigu character is considered to be the most likely character to be selected the next time a character is selected from its group. The facility therefore reorders the group, moving the a-accent-aigu character to the position immediately after the a character. The next time the user uses the facility to input an a-accent-aigu character, the a-accent-aigu character, and not the a-umlaut character, will be the first character in the group after the a character. The user will therefore only have to invoke the Replace function once to replace the a character with the target character, the a-accent-aigu character. This reflects the adaptive learning nature of the facility. FIG. 8 is a flow diagram showing the steps required for the replace function in step 403. These steps are carried out by the facility. The Replace function receives a designated character and, if the designated character is in a group, replaces the designated character with a character that follows the designated character in the group. In step 801, if the user has made a selection since the last invocation of the replace function, the facility continues at step 802, else the facility continues its step 803. In a preferred embodiment, the determination made in step 801 involves checking whether the position of the cursor has moved since the last invocation of the Replace function. The facility preferably stores the position of the cursor during each invocation of the replace function. The facility then compares the current location of the cursor to the stored location of the cursor from the last invocation of the Replace function. If the two cursor locations are different, then the user is deemed to have made a selection since the last invocation of the replace function and the facility continues its step 802. In an alternate preferred embodiment, the facility makes the determination in step 801 by storing the designated character during each invocation of the replace function and comparing the present designated character to the designated character stored during the last invocation of the replace function. If the designated characters are different, then the facility continues at step 802. In step 802, the facility updates the order of likelihood of selection of the characters in the group from which the selection was made. Step 802 is discussed in more detail below. After step 802, the facility continues at step 803. In step 803, if the designated character is in a group, then the facility continues its step 805, else the facility continues at step 804. In step 804, the facility provides the user with an indication that the replace function failed, such as an audible beep. These steps then conclude. In step 805, the facility presents the character that follows the designated character in the group that contains the designated character. Step 805 involves identifying the character to be presented by reading the group that contains the designated character, then inputting the character to be presented, causing its display on the display device. The facility identifies the character to be presented by locating the designated character in the group and identifying the character that follows the identified character in the group. In order to make the group circular, i.e., to permit the user to traverse the entire list multiple times, if desired, if the designated character is the last character of the group, then the facility identifies the first character of the group. In a preferred embodiment, this is accomplished by appending the first character of the group to the end of the group. This way, the first character in the group follows the second-to-last character in the group, completing the circularity of the group. The facility then returns success and these steps conclude. Step 802 for updating the order of the group in which the last selection was made reorders the group if the last selection changes the order of anticipated likelihood of selection in the future. The facility provides three different approaches for performing step 802. The facility may order the group based upon the recency of the selection of each character in the group, the frequency of selection of each of the characters in the group, or so that if the selected character is the first member of a character pair (pair), then the second member of the same character pair becomes the first character in the group. Each of the approaches is described in detail below. FIG. 9 is a flow diagram showing the steps required for the update group step 802 under the recency of selection approach. Under the recency of selection approach, the last character selected from its group is considered to be the most likely character to be selected the next time a character is selected from its group. For example, if the a-accent-aigu character is the last character that was selected from its group, then the a-accent-aigu character is considered to be the most likely character to be selected the next time a character is selected from its group. In step 901, the facility moves the selected character from its present location in the group that contains it to the position immediately following the key character, shifting each of the other characters back one position. These steps then conclude. FIG. 10 is a flow diagram that shows the steps required for the update group step 802 under the frequency of selection approach. Under the frequency of selection approach, the character most frequently selected from the group is considered most likely to be selected the next time a character is selected from the group. In step 1001, the facility increments the counter for the selected character. In step 1002, the facility sorts the group containing the selected character. For example, if the a-accent-aigu character has been selected more frequently than any of the other characters in its group, then the a-accent-aigu character is considered to be the most likely character to be selected the next time a character is selected from its group. Under this approach, the facility maintains a counter for each character in each group. The counters are preferably stored in arrays, each array corresponding to a group. If any counter grows to a value approaching the largest value that may be stored in the memory space allocated to a counter, the facility preferably reduces all the counter values for the group so that the counter values bear the same relationship to one another, but the largest one does not threaten the capacity of the space allocated for it. FIG. 11 is a flow diagram that shows the steps required for step 1002. In step 1101, a current character variable for maintaining position within the group while traversing it is set equal to the position of the select character in the group. For example, if the selected character is the fourth character in its group, the current character variable is set equal to four. In step 1102, if the current character is greater than one, then the facility continues at step 1103, else these steps conclude. In step 1103, if the counter value for the character in the position current character minus one is less than the counter value for the character in the position current character, then the facility continues its step 1104, else these steps conclude. In step 1104, the facility exchanges the counter value for the character in position current character minus one with the counter value for the character in position current character. Correspondingly, in step 1105, the facility exchanges the character and position current character minus one with the character and position current character. In step 1106, the facility decrements the value of the current character variable. The facility then continues at step 1102 to compare the next pair of counter values. Those skilled in the art will recognize that there are many other ways that the steps required for step 1002 could be implemented. FIG. 12 is a flow diagram showing the steps required for the update group step 802 under the character pairs approach. Under the character pairs approach, if the selected characters the first member of a pair of characters, then the second member of the same pair of characters is considered to be the most likely character to be selected the next time a character is selected from that group. For example, when the left brace character ("{") is selected, the right brace character ("}") is considered to be the most likely character to be selected the next time a character is selected from that group. In step 1201, if the selected character is the first member of a pair of characters, then the facility continues its step 1202, else these steps conclude. The determination of step 1201 requires the facility maintain a separate data structure for storing character pairs, such as a linked list of character pair structures, each containing a first member character and a second member character. For example, one character pair structure would have a left brace character as its first member and the right brace character as its second member. The facility determines whether the selected character is the first member of a pair by traversing the linked list in comparing the selected character to the first member of each character pair structure. In step 1202, the facility moves the second member of the character pair whose first member is the selected character to the beginning of the group containing the selected character. These steps then conclude. All of the data structures associated with the facility are preferably maintained in a persistent manner, so that the optimized order of each group is not lost. The facility preferably stores these data structures on the storage device and retrieves them when they are needed by the facility. The data structures are preferably stored in a form in which they may be readily edited by the user, such as plain text. This permits the user to reorder or add characters to a group and add or delete a group. The user may also preferably elect among the approaches for updating a group. The user may preferably elect a single approach, or may elect to combine the character pairs approach with the frequency or recency approach. Also, in a preferred embodiment, the facility maintains a separate copy of its data structures for each user of the facility. While this invention has been shown and described with reference to preferred embodiments, it will be understood by those skilled in the art that various changes or modifications in form and detail may be made without departing from the scope of the invention. Besides conventional characters, the facility may also be used to input other kinds of symbols or pictures that can somehow be related to key characters on the keyboard. Also, instead of a single character, each selection corresponds to a series of one or more characters. The facility may further be used to present menu items in decreasing order of likelihood of selection. The facility may also be used by non-human users, such as computer programs requesting services from an operating system.
|
Same subclass Same class Consider this |
||||||||||