Language-sensitive text searching system with modified Boyer-Moore process

• US 5,485,373 A
• Filed: 03/25/1993
• Issued: 01/16/1996
• Est. Priority Date: 03/25/1993
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Taligent, Inc. (HP Inc.)
• Inventors: Davis, Mark E., Lin, Judy
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/036,785
• Time in Patent Office: 1,027 Days
• Field of Search: 364/419.07, 364/419.08, 364/419.13, 364/419.16, 395/600
• US Class Current: 715/205
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method and system for providing a language-sensitive text search that performs text comparison of any Unicode strings. For any language an ordering is defined based on features of the language. Then, an interactive compare function is performed to determine the relationship of a pair of strings. The string is examined and a compare is performed one or more characters at a time based on a predefined character precedence.

Claims

1. A method for establishing a collating order between a first text string and a second text string, the first text string and the second text string consisting of characters belonging to a language which has a predefined character precedence, the method being operable in a computer system having a processor and a memory connected to the processor and containing locations for storing information including the first text string and the second text string and comprising the steps of:

(a) defining at least one ordering value for each character based on the predefined character precedence the language;

(b) storing ordering values for all characters in the memory;

(c) retrieving from the memory pairs of characters including a first character from the first text string and a second character from the second text string;

(d) retrieving an ordering value for the first character and an ordering value for the second character;

(e) performing a comparison of the retrieved ordering values of the characters to determine a difference between the first and the second text string; and

(f) computing a minimum trailing match length value for each position in the second text string.

2. The method as recited in claim 1 wherein the computer system further has a display apparatus connected to the processor and to the memory, the display apparatus being controlled by the processor for displaying information stored in the memory including an icon graphic, and a selection apparatus controlled by a user for selecting information displayed on the display apparatus and wherein the method comprises the further step of retrieving characters in the first text string and the second text string from the memory when the icon graphic is selected with the selecting apparatus.

3. The method as recited in claim 2 wherein the selection means comprises pointing means operated by the user for generating and moving a cursor graphic on the display apparatus and button apparatus operated by the user for generating a selection command and wherein the method comprises the further step of retrieving characters in the first text string and the second the string from the memory in response to the selection command when the cursor graphic is superimposed on the icon graphic on the display apparatus.

4. The method as recited in claim 3, wherein the selection means comprises pointing means operated by the user for generating and moving a cursor graphic on the display apparatus and button apparatus operated by the user for generating a selection command and wherein the method comprises the step of retrieving characters in the first text string and the second text string from the memory in response to the selection command when the cursor graphic is superimposed on the icon graphic on the display apparatus.

5. The method as recited in claim 1 wherein step (a) comprises the steps of:

(a1) creating a table listing selected characters and their ordering values based on the predefined character precedence of the language; and

(a2) storing the table in the memory.

6. The method as recited in claim 5 wherein step (a1) comprises the step of creating a table including a selected set of characters and primary, secondary, tertiary, expanding, grouped, ignorable-secondary, ignorable-tertiary, French-secondary and French-tertiary orderings associated with the selected set of characters.

7. The method as recited in claim 1 wherein step (e) comprises the steps of:

(e1) converting each of the first and second retrieved characters into a UNICODE equivalent; and

(e2) comparing the UNICODE equivalents.

8. The method as recited in claim 7 wherein step (e1) comprises the step of converting a retrieved accented character into a UNICODE accent equivalency.

9. The method as recited in claim 1 wherein step (a) comprised the step of (a3) changing the ordering value associated with each character depending on a desired comparison result.

10. The method as recited in claim 1, wherein the first text string consists of characters belonging to a first language which has a first predefined character precedence and the second text string consists of characters belonging to a second language which has a second predefined character precedence and wherein step (a) comprises the steps of:

(a4) defining at least one first ordering value for each character based on the predefined character precedence of the first language;

(a5) defining at least one second ordering value for each character based on the predefined character precedence of the second language; and

(a6) merging the first and second ordering values.

11. The method as recited in claim 1 wherein the computer system further includes a display apparatus connected to the processor and to the memory, the display apparatus being controlled by the processor displaying information stored in the memory and wherein step (a) further comprises the step of (a7) generating a tabular display for assigning ordering values to each character.

12. The method as recited in claim 1 wherein Step (a) further comprises the steps of:

(a8) defining a primary, a second and a tertiary ordering value for each character based on the predefined character precedence of the language;

(a9) storing the primary, secondary and tertiary ordering values for all characters in the memory; and

(a10) determining a strength of comparison between primary, secondary and tertiary ordering values.

13. A computer system for searching a first text string for an occurrence of a second text string, the first text string and the second text string consisting of characters belonging to a language which has a predefined character precedence, the computer system comprising:

(a) a processor;

(b) a memory connected to the processor and containing locations for storing information including the first text string and the second text string;

(c) a program stored in the memory and controlling the processor to retrieve information stored in the memory, to manipulate the retrieved information and to store the manipulated information in the memory;

(d) means controlled by the program for defining at least one ordering value for each character based on the predefined character precedence of the language and for storing ordering values for all characters in the memory;

(e) means controlled by the program for preprocessing the first text string to generate a first index table comprising ordering values for each character in the first text string;

(f) means controlled by the program for computing a minimum trailing match length for each position in the first text string, wherein the minimum trailing match length value corresponds to a minimum length of the second text string when the second text string matches trailing elements at the end of the first text string;

(d) means responsive to the minimum trailing match length values for shifting the second text string relative to the first text string in a first direction by an amount indicated by the minimum trailing match length values; and

(h) means for performing a comparison of the ordering values of the characters in the second string to the ordering values in the first index table to determine whether the second text string occurs in the first text string.

14. The system as recited in claim 13, further including a display apparatus connected to the processor and to the memory, the display apparatus being controlled by the processor for displaying information stored in the memory including an icon graphic, a selection apparatus controller by a user for selecting information displayed on the display apparatus and means responsive to selection of the icon graphic with the selecting apparatus for instructing the program to retrieve characters in the first text string and the second text string from the memory.

15. The computer system as recited in claim 14 wherein the selection means comprises pointing means operated by the user for generating and moving a cursor graphic on the display apparatus and button apparatus operated by the user for generating a selection command and wherein the selecting apparatus instructs the program to retrieve characters in the first text string and the second text string from the memory in response to the selection command when the cursor graphic is superimposed on the icon graphic on the display apparatus,

16. The computer system as recited in claim 14, wherein the selection means comprises pointing means operated by the user for moving the icon graphic on the display apparatus and means for generating a compare graphic on the display apparatus and wherein the selecting apparatus instructs the program to retrieve characters in the first text string and the second text string from the memory when the icon graphic is moved and superimposed on the compare graphic on the display apparatus.

17. The computer system as recited in claim 14 wherein the ordering values defining means comprises means for creating a table listing selected characters and their associated ordering values based on other predefined character precedence of the language and means for storing the table in the memory.

18. The computer system as recited in claim 17 wherein the table creating means comprises means for creating a table including a selected set of characters and primary, secondary, tertiary, expanding, grouped, ignorable-secondary, ignorable-tertiary, French-secondary and French-tertiary orderings associated with the selected set of characters.

19. The computer system as recited in claim 18, further including a display apparatus connected to the processor an to the memory, the display apparatus being controlled by the processor for displaying information stored in the memory and wherein the defining means comprises means controlled by the program for generating a tabular display for assigning ordering values to each character.

20. The computer system as recited in claim 13 wherein the means for performing a comparison of the retrieved ordering values comprises means responsive to the first and second retrieved characters for converting each of the first and second retrieved characters into a UNICODE equivalent and means for comparing the UNICODE equivalents.

21. The computer system as recited in claim 20 wherein the means for converting each of the retrieved first and second characters into a UNICODE equivalent comprises means responsive to a retrieved accented character for convening the retrieved accented character into a UNICODE accent equivalency.

22. The computer system as recited in claim 20 wherein the means for defining at least one ordering value for each character comprises means controlled by the user for changing the ordering value associated with each character depending on a desired comparison result.

23. The computer system as recited in claim 13 wherein the first text string consists of characters belonging to a first language which has a first predefined character precedence and the second text string consists of characters belonging to a second language which has a second predefined character precedence and wherein the defining means comprises:

means for defining at least one first ordering value for each character based on the predefined character precedence of the first language;

means for defining at least one second ordering value for each character based on the predefined character precedence of the second language; and

means for merging the first and second ordering values.

24. The computer system as recited in claim 13 wherein the defining means further comprises means controlled by the program for defining a primary, a secondary and a tertiary ordering value for each character based on the predefined character precedence of the language;

means for storing the primary, secondary and tertiary ordering values for all characters in the memory; and

means controlled by the program for determining a strength of matches between primary, secondary and tertiary ordering values.