Forward and reverse Boyer-Moore string searching of multilingual text having a defined collation order

• US 5,440,482 A
• Filed: 03/25/1993
• Issued: 08/08/1995
• 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.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lintz, Paul R.
• Application Number:
  US08/036,749
• Time in Patent Office: 866 Days
• Field of Search: 395/600, 395/800, 364/419.13, 364/419.16
• US Class Current: 715/226
• 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/917 Text
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and system for providing a language-sensitive text compare. An innovative system and method for performing the compare is presented 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 character at a time based on a predefined character precedence.

Claims

1. A computer system for searching 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 and a second index table comprising minimum shift values for shifting the second text string relative to the first text string in order to obtain a match;

(f) means responsive to values in the second index table for shifting the second text string relative to the first text string in either of a first direction or a second direction opposite to the first direction by an mount indicated by the second index table;

(g) 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.

2. A computer system as recited in claim 1 wherein the preprocessing means comprises means controlled by the program for constructing a first index table having a predetermined maximum value and hashing means responsive to an ordering value greater than the predetermined maximum value for generating a hashed ordering value which is less than the predetermined maximum value and means responsive to the hashed ordering value for storing the hashed ordering value in the first index table.

3. A method for searching 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 method operating in a computer system having a processor, a memory connected to the processor and containing locations for storing information including the first text string and the second text string and 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 and comprising the steps of:

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

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

(c) preprocessing the first text string to generate a first index table comprising ordering values for each character in the first text string and a second index table comprising minimum shift values for shifting the second text string relative to the first text string in order to obtain a match;

(d) shifting the second text string relative to the first text string in either of a first direction or a second direction opposite to the first direction by an amount indicated by the second index table; and

(e) 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.

4. A method as recited in claim 3 wherein step (c) comprises the steps of:

(c1) constructing a first index table having a predetermined maximum value;

(c2) comparing each ordering value to the predetermined maximum value;

(c3) generating a hashed ordering value which is less than the predetermined maximum value when an ordering value is greater than the predetermined maximum value as determined by the comparison in step (c2); and

(c4) storing the hashed ordering value in the first index table.