Method of identifying pattern matches in parameterized strings and square matrices

• US 5,627,748 A
• Filed: 05/14/1993
• Issued: 05/06/1997
• Est. Priority Date: 03/18/1992
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Giancarlo, Raffaele, Baker, Brenda S.
• Primary Examiner(s): Weinhardt, Robert A.
• Assistant Examiner(s): Thomas, Joseph
• Application Number:
  US08/061,782
• Time in Patent Office: 1,453 Days
• Field of Search: 364/419.1, 364/419.08, 364/419.19, 364/715.1, 364/419.13, 341/51, 341/65, 341/67, 395/600, 395/700
• US Class Current: 715/210
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data
• CPC Class Codes: G09G 5/00 Control arrangements or circuits for visual indicators common to cathode-ray tube indicators and other visual indicators image data processing or generation, in general G06T
• CPC Class Codes: Y10S 707/99936 Pattern matching access

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 alphabet 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.

Claims

1. A computer implemented method of finding maximal matches in a data string comprising the steps of:

creating a suffix tree representing the data string;

for each internal node in said suffix tree, generating a list having an entry for each suffix associated with said node, each entry indicating (i) the position of the start of its associated suffix in said data string and (ii) the left context relative to the position, each node having a pathlength indicating the number of symbols between the root of said suffix tree and said node;

recognizing matches having the length of the pathlength of said node for each pair of entries having different left context;

generating a list of said matches; and

reporting said list of matches.

2. The method of claim 1 in which said reporting step further comprises:

reporting only those matches having lengths greater than a predetermined threshold.

3. The method of claim 1 in which said data string contains symbols from at least two alphabets, further comprising the steps of:

before said creating step substituting a common symbol for all symbols from one of said alphabets;

after said recognizing step, for each match, comparing the original symbols for which said common symbol was substituted in said substituting step to determine whether said original symbols are consistent and discarding said matches in which symbols are not consistent.

4. The method of claim 1 in which said data string contains symbols from at least two alphabets, further comprising the step of:

before said creating step, substituting an integer for all symbols from one of said alphabets, each said integer for a given symbol being chosen to point to an adjacent instance of said symbol in said data string, whereby said integers form linked lists of the symbols for which said integers were substituted.

5. The method of claim 1, wherein the data string comprises a square text matrix, and wherein the step of creating a suffix tree comprises the steps of:

dividing the square text matrix into Lcharacters;

concatenating said Lcharacters to form an Lstring; and

constructing an Lsuffix tree from said Lstring.

6. A computer implemented method of locating duplications within a text, the method comprising the steps of:

dynamically encoding one or more characters of said text in a manner in which like parameters contained within a string are labelled to identify their positional relationships within the string;

creating a modified suffix tree from said encoded data;

applying said modified suffix tree to identify duplications in said text, said duplications representing identical or approximate matches of said text prior to its encoding, wherein said duplications are of at least a threshold length; and

reporting said identified duplications in said text.

7. The method of claim 6 wherein said encoded text is a square matrix which is divided into Lcharacters from which is created an Lstring.

8. The method according to claim 6 wherein said step of creating a modified suffix tree further comprises the steps of:

establishing a root for the tree,

attaching arcs to the mot for each suffix of the encoded text to the string such that suffixes having common prefixes extend from the same arc, and

defining suffix links within the tree for traversing the tree in an efficient manner.