Method and system for combining prefix and first character searching of a list

• US 5,692,173 A
• Filed: 12/13/1994
• Issued: 11/25/1997
• Est. Priority Date: 12/13/1994
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chew, Chee Heng
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US08/354,913
• Time in Patent Office: 1,078 Days
• Field of Search: 395/600, 395/148, 395/603, 395/604, 395/605, 395/607, 395/796, 395/764, 364/300, 364/419
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method and system for combining prefix and first character search methods. The present invention provides a combined search method for searching for elements in a list. The combined search method maintains a user input buffer that contains a plurality of search characters. The combined search method searches for a particular list element in a list, where each list element is a sequence of characters. That is, the combined search method searches for a list element whose prefix matches the search characters in the user input buffer. If each of the search characters in the user input buffer is the same, the combined search method also searches for a list element whose first character matches a search character in the user input buffer. If one list element is found, the combined search method selects that list element. If two list elements are found, the combined search method selects one of the two list elements based on its proximity to a predetermined list element.

Claims

1. A method in a computer system for selecting a list element in a list, each list element having a sequence of characters and having a position in the list, the computer system having a user input buffer containing a plurality of search characters, the method comprising the steps of:

searching for a list element with a prefix that matches the search characters;

determining whether each of the search characters is the same character;

when it is determined that each of the search characters is the same character, searching for a list element whose first character matches a search character;

when the searching finds only one list element that matches, selecting that list element; and

when the searching finds two distinct list elements, wherein one list element has a prefix that matches the search characters and the other list element has a first character that matches a search character, selecting from the two list elements a final list element based on its position relative to the position of a predetermined list element.

2. The method of claim 1 wherein the step of searching for a list element with a prefix that matches the search characters includes starting the searching from a search starting point that is at the position of a previously selected list element.

3. The method of claim 1 wherein the step of searching for a list element whose first character matches a search character includes starting the searching after a search starting point that is at the position of a previously selected list element.

4. The method of claim 1 wherein the step of selecting a final list element based on its position relative to the position of a predetermined list element selects the list element whose position is closest to a search starting point.

5. The method of claim 1 including the step of designating the position of the selected list element to be a search starting point.

6. The method of claim 1 including the step of outputting a feedback to indicate that the searching did not find a list element.

7. A method in a computer system for searching a list containing list elements, each list element having a sequence of characters and a position in the list, the method comprising the steps of:

receiving a plurality of search characters;

performing a prefix search of the list to find a list element whose prefix matches the received search characters;

determining whether each of the search characters is the same character;

when it is determined that each of the search characters is the same character, performing a first character search of the list to find a list element whose first character matches a search character;

when only one list element is found, selecting that found list element; and

when two different list elements are found, selecting one of the found list elements based on its position relative to the position of a predetermined list element.

8. The method of claim 7 wherein the step of performing a prefix search includes starting the prefix search from a search starting point that is the position of a previously selected list element, and wherein the step of selecting one list element based on its position relative to the position of a predetermined list element selects the list element whose position is closest to the search starting point.

9. The method of claim 7 wherein the step of performing a first character search includes the step of starting the first character search after a search starting point that is at the position of a previously selected list element, and wherein the step of selecting one list element based on its position relative to the position of a predetermined list element selects the list element whose position is closest to the search starting point.

10. The method of claim 7 including the step of outputting a feedback to indicate that neither the prefix search nor the first character search found a list element.

11. A method in a computer system for searching a list, the computer system having a user input device and a user input buffer for holding search characters, the list containing list elements, each list element having a position in the list, the method comprising repeating the following steps:

receiving user input from the user input device until a search character is received;

adding the search character to the user input buffer;

comparing the search characters in the user input buffer with the prefix of each list element until either finding a prefix search list element whose prefix is the same as the search characters in the user input buffer or detecting that no list element has a prefix which is the same as the search characters in the user input buffer;

determining whether the user input buffer contains more than one search character;

when it is determined that the user input buffer contains more than one search character,

determining whether each of the search characters in the input buffer is the same;

when it is determined that each of the search characters in the user input buffer is the same, comparing a search character in the user input buffer with the first character of each list element until finding a first character search list element whose first character is the same as a search character in the user input buffer or detecting that no list element has a first character that is the same as a search character in the user input buffer;

when both a prefix search list element and a first character search list element are found, selecting one of the found list elements based on its position relative to the position of a predetermined list element; and

when only a prefix search list element or only a first character search list element is found, selecting the found list element.

12. The method of claim 11 wherein the method comprises repeating the steps until a new search is indicated by a predetermined lapse of time during which no user input is received.

13. The method of claim 11 including the step of having a list element designated as a list element with focus and receiving user input from the user input device designating a different list element to be with focus and designating that different list element to be with focus.

14. The method of claim 13 including the step of receiving user input from the user input device for a space character ("") when the user input buffer contains no search characters and selecting and highlighting the list element with focus.

15. The method of claim 13 including the step of, after designating a different list element to be with focus, setting a search starting point to be the list element with focus.

16. The method of claim 11 including the step of comparing the search characters in the user input buffer with the prefix of each list element starting with a predetermined search starting point when the user input buffer contains more than one search character and starting with a list element after the predetermined search starting point when the user input buffer contains only one search character.

17. The method of claim 11 including the step of comparing a search character in the user input buffer with the first character of each list element starting with the list element after a predetermined search starting point.

18. The method of claim 11 including the step of outputting a feedback to indicate that neither a prefix search list element nor a first character search list element was identified.

19. A method in a computer system for detecting whether to execute a prefix search or a first character search, the computer system having a list containing list elements with one list element designated as a search starting point, the method comprising the steps of:

determining whether a prefix search would find a list element and a first character search would find a different list element;

when the prefix search and first character search would find different list elements, determining whether the prefix search or the first character search would find a list element closer to the search starting point;

when the prefix search would find a list element closer to the search starting point, performing the prefix search; and

when the first character search would find a list element closer to the search starting point, performing the first character search.

20. A computer system with an input device, an output device, a list containing list elements, an input buffer, and a combined search engine, the system comprising:

means for receiving a plurality of search characters from the input device;

means for storing the received search characters in the input buffer;

means for performing a prefix search based on the search characters in the input buffer using the combined search engine;

means for determining whether each of the search characters in the input buffer is the same;

means for performing a first character search when it is determined that each of the search characters in the input buffer is the same;

means for selecting a found list element when at least the prefix search or the first character search finds a list element; and

means for displaying the selected list element on the output device.

21. The system of claim 20, further comprising means for outputting a feedback to indicate the searching did not find a list element.

22. A method in a computer system for selecting a list element in a list, each list element having a sequence of characters and a position in the list, the computer system having a plurality of search characters and a combined search system for performing searches, the method comprising:

performing a prefix search of the list using the combined search system to find a list element with a prefix that matches the search characters starting from a predetermined position in the list;

determining whether each of the search characters is the same;

when it is determined that each of the search characters is not the same and the prefix search found a match, selecting the result of the prefix search; and

when it is determined that each of the search characters is the same,

performing a first character search of the list using the combined search system to find a list element whose first character matches a search character starting from the position following the predetermined position in the list;

when only the first character search found a list element, selecting the found list element;

when the prefix search and the first character search both found the same list element, selecting that list element; and

when the prefix search and the first character search each found a different list element, selecting the result of whichever search found a list element whose position is closer to the predetermined position in the list.

23. The method of claim 22, further comprising outputting a feedback to indicate the searching did not find a list element.

24. The method of claim 22, further comprising designating the selected list element to be a search starting point.

25. A method in a computer system for selecting a list element in a list, each list element having a sequence of characters and having a position in the list, the computer system having a user input buffer containing a plurality of search characters, the method comprising:

searching for a list element with a prefix that matches the search characters in the user input buffer;

determining whether each of the search characters is the same character;

when it is determined that each of the search characters is the same character, searching for a list element whose first character matches a search character;

when the searching finds either a list element with a prefix that matches the search characters or a list element with a first character that matches a search character, selecting the found list element; and

when the searching finds a list element with a prefix that matches the search characters and a different list element with a first character that matches a search character, then selecting one of these found list elements based on its position relative to the position of a predetermined list element in the list.

26. The method of claim 25, further comprising outputting a feedback to indicate the searching did not find a list element.

27. A computer-readable storage medium containing computer instructions that cause a computer system to:

receive a plurality of search characters;

perform a prefix search of a list to find a list element starting at a search starting point, the list containing list elements, each list element having a sequence of characters and a position in the list;

determine whether each of the search characters is the same;

when it is determined that each of the search characters is the same, perform a first character search of the list to find a list element starting at the position of the list element following the search starting point;

when only one list element is found, select the found list element; and

when two list elements are found, select one of the found list elements based on its position proximate to the search starting point.

28. The computer-readable storage medium of claim 27 wherein the computer instructions cause the computer to output a feedback indicating that no list element was found.

29. A computer-storage medium containing computer instructions that cause a computer system to:

determine a first position of a list element in a list that would be found using a prefix search, the list having a plurality of list elements, each list element having a position in the list;

determine a second position of a list element in the list that would be found using a first character search; and

select the list element whose determined position is closer to the position of a predetermined list element.

30. The computer-storage medium of claim 29 wherein the computer instructions that determine a first position of a list element using the prefix search compare a search character sequence with the prefix of each list element starting with the predetermined list element.

31. The computer-storage medium of claim 29 wherein the computer instructions that determine a second position of the list element using the first character search compare a search character with the first character of each list element starting with the list element after the predetermined list element.