Method of identifying parameterized matches in a string

Details Method of identifying parameterized matches in a string Method of identifying parameterized matches in a string

1994-05-13

1996-04-23

Bayerl, Raymond J.

Boots, shoes, and leggings

36441914, 36441919, G06F 300

Patent

active

055111599

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.

REFERENCES:
patent: 4887212 (1989-12-01), Zamora et al.
patent: 4916655 (1990-04-01), Ohsone et al.
patent: 5337233 (1994-08-01), Hofert et al.
patent: 5377349 (1994-12-01), Motomura
patent: 5448733 (1995-09-01), Satoh et al.
E. M. McCreight, "A Space-Economical Suffix Tree Construction Algorithm," Journal of the Association for Computing Machinery, vol. 22, No. 2, 262-272 (Apr. 1976).
D. E. Knuth et al., "Fast Pattern Matching in Strings," SIAM J. Comput., vol. 6, No. 2, 323-350 (Jun. 1977).
R. S. Boyer, "A Fast String Searching Algorithm," Communications of the ACM, vol. 20, No. 10, 762-772 (Oct. 1977).
M. Crochemore et al., "Speeding Up Two String-Matching Algorithms," 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, 589-600 (Feb. 1992).
R. Giancarlo, "The Suffix of a Square Matrix, with Applications", Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, Texas, 1993.

Affiliated with

Also associated with

Rating

Method of identifying parameterized matches in a string 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 parameterized matches in a string, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of identifying parameterized matches in a string will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2315843