US 5,511,159 AGranted

Method of identifying parameterized matches in a string

AssigneeAT&T Corp.

InventorsBrenda S. Baker, Raffaele Giancarlo

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods are disclosed for finding maximal matches in data strings and for finding matches in parameterized strings, that is, strings containing symbols from more than one alphabet in which the symbols from one of the alphabets are treated as parameters. In general, such maximal matches are found by creating a suffix tree representing the data string, generating lists for each node in the tree indicating the left contexts of all suffixes associated with that node and reporting matches for pairs of suffixes having different left contexts. One method of finding parameterized matches is to substitute a common symbol for the symbols of the alphabet representing the parameters before creating the suffix tree and then discarding matches found for which the actual parameters are not consistent. Another, preferred, method of finding parameterized matches is to substitute integers for the symbols of the alphabet representing the parameters, such symbols being chosen to create a linked list in the data string for each different symbol in such alphabet. Matches found by the suffix tree are then consistent and no matches need be discarded. Other methods of finding matches are disclosed in which suffix trees are used in conjunction with square matrices to analyze the data strings.

Claims6

Dependent claims

A method of matching a pattern data string with a text data string, said pattern data string and text data string being comprised of parameter characters and constant characters, said pattern data string containing fewer numbers of characters than said text string, the method comprising the steps of:

a) substituting the parameter characters within the pattern data string with a numerical character, each numerical character being chosen to point to a proximate instance of said parameter character in said pattern data string, said substitution occurring in a right to left direction;
b) aligning the pattern data string with a portion of the text data string;
c) substituting the parameter characters within at least the aligned portion of the text data string with a numerical character, each numerical character being chosen to point to a proximate instance of said parameter character in said text data string, said substitution occurring in a right to left direction;
d) comparing said aligned portion of said pattern data string with said text data string in a right to left direction;
e) identifying a first occurrence of a mismatch between the pattern data string and the text data string;
f) identifying a match between said pattern string and said aligned portion of said text string if no mismatch occurs;
g) determining the number of positions required to shift the pattern data string relative to the text data string so that the mismatched character in the text data string is aligned with a proximate occurrence of a like character in the pattern data string, said determination considering the relationship between characters adjacent to the mismatched character;
and
h) repeating steps b)-g) and identifying every occurrence where a portion of the text string matches the pattern data string.

6 more elements

A method of matching at least a portion of a pattern data string with a text data string, said pattern data string and text data string being comprised of parameter characters and constant characters, the method comprising the steps of:

a) substituting the parameter characters within the pattern data string with a numerical character, each numerical character being chosen to point to a proximate instance of said parameter character in said pattern data string, said substitution occurring in a right to left direction;
b) creating at least one table, said table being based on known pattern string information and which represents relationships between symbols in said substituted pattern string, said relationships establishing a lower bound which determines the number of consecutive positions to shift a pointer with respect to the text string;
c) aligning the pattern data string with a portion of the text data string;
d) substituting the parameter characters within at least the aligned portion of the text data string with a numerical character, each numerical character being chosen to point to a proximate instance of said parameter character in said text data string, said substitution occurring in a right to left direction;
e) comparing said aligned portion of said pattern data string with said text data string in a right to left direction;
f) identifying a first occurrence of a mismatch between the pattern data string and the text data string;
g) identifying a match between said pattern string and said aligned portion of said text string if no mismatch occurs;
h) determining the number of positions to shift the pointer based on information obtained from the at least one table, said information being a function of the mismatched character identified in the text string, said determination considering the relationship between characters adjacent to the mismatched character;
and
i) repeating steps b)-h) and identifying every occurrence where a portion of the text string matches the pattern data string.

7 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/242,385Filed 13 May 1994 · continuation in part
Priority: 18 Mar 1992
Granted: 23 Apr 1996
Term ends: Not estimatedThe source records don’t support an estimate.

Classification9 codes

G09G 5/00
Control arrangements or circuits for visual indicators common to cathode-ray tube indicators
C07K 1/00
General methods for the preparation of peptides , i.e. processes for the
C12N 15/11
Recombinant DNA-technology: dNA or RNA fragments; Modified forms thereof ; Non-coding nucleic acids having a biological activity
G06F 16/90344
Query processing: by using string matching techniques