Method of identifying pattern matches in parameterized strings a

Details Method of identifying pattern matches in parameterized strings a Method of identifying pattern matches in parameterized strings a

1993-05-14

1997-05-06

Weinhardt, Robert A.

395709, 395793, 395606, G06F 1721, G06F 1740

Patent

active

056277482

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.

REFERENCES:
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4864528 (1989-09-01), Nishiyama et al.
patent: 5058144 (1991-10-01), Fiala et al.
patent: 5151697 (1992-09-01), Bunton
patent: 5270712 (1993-12-01), Iyer et al.
patent: 5276741 (1994-01-01), Aragon
patent: 5323316 (1994-06-01), Kadashevich et al.
patent: 5355473 (1994-10-01), Au
patent: 5369577 (1994-11-01), Kadashevich et al.
patent: 5406279 (1995-04-01), Anderson et al.
patent: 5412807 (1995-05-01), Moreland
patent: 5414425 (1995-05-01), Whiting et al.
E. M. McCreight, "A Space-Economical Suffix Tree Construction Algorithm", Journal of the Association for Computing Machinery, vol. 23, No. 2, Apr. 1976, pp. 262-272.
R. Giancarlo, "The Suffix of a Square Matrix, with Applications", Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, Texas, 1993.
Aho et al., Compilers; Principles, Techniques, and Tools, Addison Wesley Publishing Co., 1986, pp. 83-88.
Blumer (Dialog Accession No. 03141370); abstract of Journal Paper Published Dec. 1987 in Journal of Algorithms, vol. 8, No. 4, pp. 451-469.

Affiliated with

Also associated with

Rating

Method of identifying pattern matches in parameterized strings a does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of identifying pattern matches in parameterized strings a, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of identifying pattern matches in parameterized strings a will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2137495