US5627748A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of identifying pattern matches in parameterized strings and square matrices
Assignee: Nokia of America Corp
•
Filing: 1993-05-14
•
Granted: 1997-05-06
•
Expires: 2013-05-14
Abstract
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.
Inventors
- 👤 Brenda S. Baker
- 👤 Raffaele Giancarlo
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 07:35
CPC Classifications
G; G09; G09G; G09G5/00; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90348; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
123 words
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.
Claim 2
Dependent Claim
123 words
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.
Claim 3
Dependent Claim
23 words
The method of claim 1 in which said reporting step further comprises: reporting only those matches having lengths greater than a predetermined threshold.
Claim 4
Dependent Claim
78 words
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.
Claim 5
Dependent Claim
74 words
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.
Claim 6
Dependent Claim
49 words
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.
Claim 7
Dependent Claim
98 words
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.
Claim 8
Dependent Claim
98 words
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.
Claim 9
Dependent Claim
24 words
The method of claim 6 wherein said encoded text is a square matrix which is divided into Lcharacters from which is created an Lstring.
Claim 10
Dependent Claim
67 words
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.
References Cited (Backward Citations)
US4464650A
Cited
US4864528A
Cited
US5058144A
Cited
US5414425A
Cited
US5151697A
Cited
US5323316A
Cited
US5369577A
Cited
US5276741A
Cited
US5355473A
Cited
US5270712A
Cited
US5412807A
Cited
US5406279A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-05 | 2000-11-04 | 2001-05-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-05 | 2004-11-04 | 2005-05-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-05 | 2008-11-04 | 2009-05-06 | $7700.00 | Window Closed / Lapsed |