TEXT MATCHING ALGORITHM

• US 3,568,156 A
• Filed: 08/09/1967
• Issued: 03/02/1971
• Est. Priority Date: 08/09/1967
• Status: Expired due to Term

• Current Assignee: Kenneth Thompson
• Original Assignee: Kenneth Thompson
• Inventors: Thompson, Kenneth L.
• Application Number:
  US04/659,389
• Time in Patent Office: 1,301 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A general purpose computer program and special purpose apparatus for matching strings of alphanumeric characters are disclosed. The algorithm involved makes use of a current-character search list (augmented for all alternative characters) and a nextcharacter search list (augmented for all successful character matches). These characters are portions of the test text to which the string to be matched is compared. Each character of the string to be matched is tested by the current character list, during which time the next character list is compiled. Then a new character is obtained, the next character list substituted for the current character list, and the process continues. The process terminates successfully when test text characters are exhausted, and terminates unsuccessfully when the searched text to be matched is exhausted.

Claims

1. Apparatus for detecting matches between strings of information-representing signals comprising:

means for comparing each subunit of a first string to the first subunit of a second string;

means for recording the identification of that subunit of the second string which subunit follows each matched subunit of the first string;

means for comparing each identified subunit of the second string to the next succeeding subunit of the first string;

means for indicating a successful match when all subunits of the second string are compared; and

means for indicating an unsuccessful match when all subunits of the first string are compared.

2. compiling a first list of all possible next characters of said second expression in response to successful matches to the currently compared character of said first expression, said possible next characters becoming said currently possible matching characters for the next character of said first expression;

and

3. comparing each identified subunit of the second string to the next succeeding subunit of the first string;

4. Apparatus according to claim 3 further comprising:

means for compiling a second list of all currently possible matching characters in response to disjunctive operators in said first expression;

said obtaining means including means for substituting said first list for said second list.

5. The method of detecting matches between two alphanumeric expressions represented by electronically coDed characters comprising the steps of:

6. The method according to claim 5 further comprising the steps of:

7. Signal matching apparatus comprising:

storage means for a first sequence of signals having identified subsequences;

storage means for a second sequence of signals having correspondingly-sized subsequences, said subsequences being made available one at a time;

means for comparing identified ones of the subsequences of said first sequence to a currently available subsequence of said second sequence;

first means for storing subsequence identifications for said first sequence corresponding to the next succeeding subsequence following each matched subsequence of said first sequence;

second means for storing subsequence identifications for said first sequence, means for transferring subsequence identifications from said first storage means to said second storage means; and

means responsive to identifications stored in said second storage means for selectively enabling said comparing means.

8. A method for a data processing system for matching strings of electronically coded characters comprising the steps of: