US5577249A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for finding a reference token sequence in an original token string within a database of token strings using appended non-contiguous substrings
Assignee: International Business Machines Corp
•
Filing: 1995-08-08
•
Granted: 1996-11-19
•
Expires: 2015-08-08
Abstract
Abstract This method non sequentially compares a reference sequence of tokens to an original sequence of tokens to determine subsequences of tokens which exactly or similarly match. The method has a novel approach for creating a large number of indexes by partitioning strings of tokens into substrings, appending non contiguous substrings together to form tuples, and creating indexes from the tuples. Indexes are created in this manner for both the original and reference strings. Techniques are also provided to approximately or exactly locate the substrings which where used to create the tuples and indexes from the original sequence of tokens. Original and reference indexes are compared and matches are tracked. Higher numbers of matches result in higher scores (votes) in a table and indicate a stronger similarity between the sequences on the the original and reference strings. Using this method, the degree of similarity can also be determined. The Method is useful when comparing a reference sequence of tokens to a large database of original strings of tokens. It has applications in the biological sciences (human genome mapping or analyzing proteins) and in image, speech, and music recognition.
Inventors
- 👤 Andrea Califano
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 09:21
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; Y; Y02; Y02A; Y02A90/00; Y02A90/10; Y10; Y10S; Y10S707/00; Y10S707/964; Y10S707/966; Y10S707/967; Y10S707/968
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
307 words
A method for finding a reference string of tokens in one or more original token strings within a database comprising the steps of: creating one or more original tuples for each of the original token strings in the database by: a. partitioning each original token string into three or more original substrings of contiguous tokens; b. appending together two or more original substrings of the original token string to form one or more original tuples associated with the original token string, at least one of the original tuples being formed by appending together two or more non-contiguous original substrings of the original token string; creating a unique original index for each original tuple created from the original token string by using an index algorithm, the original index being associated with the original token string from which the original tuple was created, each original index associated with information that is used to locate the original token string in the database containing the tuple from which the original index was derived and to determine the position of the matched reference sequence in the original token string; creating one or more reference tuples from the reference string of tokens by: c. partitioning the reference string of tokens into three or more reference substrings of contiguous tokens; d. appending together two or more reference substrings to form one or more reference tuples, at least one of the reference tuples being formed by appending together two or more non-contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index; tracking the matches between the reference index and original index; selecting an original token string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 2
Independent Claim
307 words
A method for finding a reference string of tokens in one or more original token strings within a database comprising the steps of: creating one or more original tuples for each of the original token strings in the database by: a. partitioning each original token string into three or more original substrings of contiguous tokens; b. appending together two or more original substrings of the original token string to form one or more original tuples associated with the original token string, at least one of the original tuples being formed by appending together two or more non-contiguous original substrings of the original token string; creating a unique original index for each original tuple created from the original token string by using an index algorithm, the original index being associated with the original token string from which the original tuple was created, each original index associated with information that is used to locate the original token string in the database containing the tuple from which the original index was derived and to determine the position of the matched reference sequence in the original token string; creating one or more reference tuples from the reference string of tokens by: c. partitioning the reference string of tokens into three or more reference substrings of contiguous tokens; d. appending together two or more reference substrings to form one or more reference tuples, at least one of the reference tuples being formed by appending together two or more non-contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index; tracking the matches between the reference index and original index; selecting an original token string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 3
Dependent Claim
35 words
A method of finding a reference string of tokens in one or more original token strings with a database, as in claim 1, where the original substrings of tokens are all of a fixed length.
Claim 4
Dependent Claim
33 words
A method of finding a reference string of tokens in one or more original token strings within a database, as in claim 1, where the original substrings of tokens are of different lengths.
Claim 5
Dependent Claim
33 words
A method of finding a reference string of tokens in one or more original token strings within a database, as in claim 1, where the original tuples formed are of a fixed length.
Claim 6
Dependent Claim
33 words
A method of finding a reference string of tokens in one or more original token strings with a database, as in claim 1, where the original tuples formed are of a different lengths.
Claim 7
Dependent Claim
131 words
A method of finding a reference string of tokens in one or more original token strings within a database, as in claim 1, where the original tuples are formed by using the following rules: each subsequent substring forming the original tuple has a starting position in tokens further away from a beginning token of the original token string than a prior starting position of all prior substrings forming the original tuple; no substring can be used form a tuple if its starting position and length in tokens cause the tuple to exceed the length of the original token string; The starting tokens of two subsequent substrings in an original string must be between a minimum and a maximum radius of coherence of one another, the radius distances being measured in tokens.
Claim 8
Dependent Claim
33 words
A method of finding a reference string of tokens in one or more original token strings within a database, as in claim 1, where the original index and the reference index are numbers.
Claim 9
Dependent Claim
33 words
A method of finding a reference string of tokens in one or more original token strings within a database, as in claim 1, where the original index and the reference index are integers.
Claim 10
Independent Claim
350 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database comprising the steps of: creating one or more original tuples for each of the original token strings in the database by: a. partitioning each original token string into three or more original substrings of contiguous tokens; b. appending together two or more original substrings of the original token string to form one or more original tuples associated with the original token string, at least one original tuple being formed by appending two or more non-contiguous original substrings of the original token string; creating a unique original index for each original tuple created from the original token string by using an index algorithm, the original index being associated with the original token string from which the original tuple was created; using the original index to point to a cell in a first memory look-up structure and storing in the cell an information record associated with the original string, the information record containing pointing information used to locate the original token string in the database containing the tuple from which the original index was derived and displacement information used to determine the position of the matched reference sequence in the original token string; creating one or more reference tuples from the reference string of tokens by: c. partitioning the reference string of tokens into three or more reference substrings of contiguous tokens; d. appending together two or more reference substrings to form one or more reference tuples, at least one on the reference tuples being formed by appending together two or more non-contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm comparing at least one reference index to at least one original index using the memory look-up structure; tracking the matches between the reference index and original index; storing the tracking results in a second memory look-up structure; selecting an original token string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 11
Independent Claim
350 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database comprising the steps of: creating one or more original tuples for each of the original token strings in the database by: a. partitioning each original token string into three or more original substrings of contiguous tokens; b. appending together two or more original substrings of the original token string to form one or more original tuples associated with the original token string, at least one original tuple being formed by appending two or more non-contiguous original substrings of the original token string; creating a unique original index for each original tuple created from the original token string by using an index algorithm, the original index being associated with the original token string from which the original tuple was created; using the original index to point to a cell in a first memory look-up structure and storing in the cell an information record associated with the original string, the information record containing pointing information used to locate the original token string in the database containing the tuple from which the original index was derived and displacement information used to determine the position of the matched reference sequence in the original token string; creating one or more reference tuples from the reference string of tokens by: c. partitioning the reference string of tokens into three or more reference substrings of contiguous tokens; d. appending together two or more reference substrings to form one or more reference tuples, at least one on the reference tuples being formed by appending together two or more non-contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm comparing at least one reference index to at least one original index using the memory look-up structure; tracking the matches between the reference index and original index; storing the tracking results in a second memory look-up structure; selecting an original token string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 12
Dependent Claim
46 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 9, where the cell contains a list of information records where the information records contains a reference to an original token string.
Claim 13
Dependent Claim
47 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 9, where the cell contains a list of information records which include a reference to an original token string and associated displacement information.
Claim 14
Dependent Claim
56 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 9, where the displacement information is computed based on a position in tokens of at least one substring of the original token string used to form the tuple of the original index.
Claim 15
Dependent Claim
58 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 9, where the displacement information is a distance in tokens between an average of the position of each original substring used to form the tuple and a given token on the original token string.
Claim 16
Dependent Claim
41 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 9, where the match between the original token string and the reference string is an exact match.
Claim 17
Dependent Claim
41 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 9, where the match between the original token string and the reference string is a similar match.
Claim 18
Dependent Claim
50 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 9, where information in the second memory structure includes a value which indicates the degree of similarity between the original token string and the reference string.
Claim 19
Dependent Claim
44 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 9, where the first look-up structure is a data structure that includes structures like a vector, array, and hash table.
Claim 20
Dependent Claim
33 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 17, where the first look-up structure is an array.
Claim 21
Dependent Claim
45 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 9, where the second look-up structure is a static data structure that includes structures like a vector, array, and hash table.
Claim 22
Dependent Claim
45 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 9, where the second look-up structure is a dynamic data structure that includes structures like a vector, array, and hash table.
Claim 23
Dependent Claim
35 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 20, where the second look-up structure is a dynamic hash table.
Claim 24
Dependent Claim
42 words
A method for recognizing and accessing a reference string of tokens in one or more original token strings within a database, as in claim 9, where the second memory look-up structure is updated every time a reference index matches a original index.
Claim 25
Independent Claim
248 words
A method for recognizing and accessing a reference string of nucleotides in one or more original DNA strings within a database comprising the steps of: creating one or more original tuples for each of the original DNA strings in the database by: a. partitioning each original DNA string into three or more substrings of contiguous nucleotides; b. appending together two or more original DNA substrings of the original DNA string to form one or more original tuples associated with each original DNA string; creating a unique original index for each original tuple created from the original DNA string using an index algorithm, the original index being associated with the original DNA string from which the original tuple was created; creating one or more reference tuples from the reference string of tokens by: c. partitioning the reference string of nucleotides into three or more reference substrings of contiguous nucleotides: d. appending together two or more reference substrings to form one or more reference tuples, at least one of the reference tuples being formed by appending together two or more non-contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index to determine if the indexes match; tracking the matches between the reference index and original index; selecting an original DNA string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 26
Independent Claim
248 words
A method for recognizing and accessing a reference string of nucleotides in one or more original DNA strings within a database comprising the steps of: creating one or more original tuples for each of the original DNA strings in the database by: a. partitioning each original DNA string into three or more substrings of contiguous nucleotides; b. appending together two or more original DNA substrings of the original DNA string to form one or more original tuples associated with each original DNA string; creating a unique original index for each original tuple created from the original DNA string using an index algorithm, the original index being associated with the original DNA string from which the original tuple was created; creating one or more reference tuples from the reference string of tokens by: c. partitioning the reference string of nucleotides into three or more reference substrings of contiguous nucleotides: d. appending together two or more reference substrings to form one or more reference tuples, at least one of the reference tuples being formed by appending together two or more non-contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index to determine if the indexes match; tracking the matches between the reference index and original index; selecting an original DNA string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 27
Independent Claim
267 words
A method for recognizing and accessing a reference string of amino acids in one or more original protein strings within a database comprising the steps of: creating one or more original tuples for each of the original protein strings in the database by: a. partitioning each original protein string into three or more substrings of contiguous amino acids; b. forming one or more original tuples associated with each original protein string by appending together two or more original amino acid substrings of the original string, one or more of the original tuples being formed by appending together at least two non contiguous original amino acid substrings; creating a unique original index for each original tuple created from the original protein string using an index algorithm, the original index being associated with the original protein string from which the original tuple was created; creating one or more reference tuples from the reference string of tokens by: c. partitioning the reference string of amino acids into three or more contiguous reference substrings of amino acids; d. forming two or more reference tuples by appending together two or more reference substrings, one or more of the reference tuples being formed by appending two or more non contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index; tracking the matches between the reference index and original index; selecting an original protein string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 28
Independent Claim
267 words
A method for recognizing and accessing a reference string of amino acids in one or more original protein strings within a database comprising the steps of: creating one or more original tuples for each of the original protein strings in the database by: a. partitioning each original protein string into three or more substrings of contiguous amino acids; b. forming one or more original tuples associated with each original protein string by appending together two or more original amino acid substrings of the original string, one or more of the original tuples being formed by appending together at least two non contiguous original amino acid substrings; creating a unique original index for each original tuple created from the original protein string using an index algorithm, the original index being associated with the original protein string from which the original tuple was created; creating one or more reference tuples from the reference string of tokens by: c. partitioning the reference string of amino acids into three or more contiguous reference substrings of amino acids; d. forming two or more reference tuples by appending together two or more reference substrings, one or more of the reference tuples being formed by appending two or more non contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index; tracking the matches between the reference index and original index; selecting an original protein string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 29
Independent Claim
262 words
A method for recognizing and accessing a reference string of characters in one or more original character strings within a database comprising the steps of: creating one or more original tuples for each of the original character strings in the database by: a. partitioning each original character string into three or more substrings of contiguous characters; b. forming one or more original tuples associated with each original character string by appending together two or more original character substrings of the original string, one or more of the original tuples being formed by appending together two or more non contiguous original character substrings; creating a unique original index for each original tuple created from the original character string using an index algorithm, the original index being associated with the original character string from which the original tuple was created; creating one or more reference tuples from the reference string of tokens by: c. partitioning the reference string of characters into three or more non contiguous reference substrings of characters; d. forming two or more reference tuples by appending together two or more reference substrings, one or more of the reference tuples being formed by appending two or more non contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index; tracking the matches between the reference index and original index; selecting an original character string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 30
Independent Claim
262 words
A method for recognizing and accessing a reference string of characters in one or more original character strings within a database comprising the steps of: creating one or more original tuples for each of the original character strings in the database by: a. partitioning each original character string into three or more substrings of contiguous characters; b. forming one or more original tuples associated with each original character string by appending together two or more original character substrings of the original string, one or more of the original tuples being formed by appending together two or more non contiguous original character substrings; creating a unique original index for each original tuple created from the original character string using an index algorithm, the original index being associated with the original character string from which the original tuple was created; creating one or more reference tuples from the reference string of tokens by: c. partitioning the reference string of characters into three or more non contiguous reference substrings of characters; d. forming two or more reference tuples by appending together two or more reference substrings, one or more of the reference tuples being formed by appending two or more non contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index; tracking the matches between the reference index and original index; selecting an original character string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 31
Independent Claim
259 words
A method for recognizing and accessing a reference string of phonemes in one or more original phoneme strings within a database comprising the steps of: creating one or more original tuples for each of the original phoneme strings in the database by: a. partitioning each original phoneme string into three or more original substrings of contiguous phonemes; b. forming one or more original tuples associated with each original phoneme string by appending together two or more original substrings of the original string, one or more of the original tuples being formed by appending together at least two non contiguous original substrings; creating a unique original index for each original tuple created from an original phoneme string using an index algorithm, the original index being associated with the original phoneme string from which the original tuple was created; creating one or more reference tuples from the reference string of phonemes by: c. partitioning the reference string of phoneme into three or more contiguous reference substrings of phonemes; forming two or more reference tuples by appending together two or more reference substrings, one or more of the reference tuples being formed by appending two or more non contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index; tracking the matches between the reference index and original index; selecting an original phoneme string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 32
Independent Claim
259 words
A method for recognizing and accessing a reference string of phonemes in one or more original phoneme strings within a database comprising the steps of: creating one or more original tuples for each of the original phoneme strings in the database by: a. partitioning each original phoneme string into three or more original substrings of contiguous phonemes; b. forming one or more original tuples associated with each original phoneme string by appending together two or more original substrings of the original string, one or more of the original tuples being formed by appending together at least two non contiguous original substrings; creating a unique original index for each original tuple created from an original phoneme string using an index algorithm, the original index being associated with the original phoneme string from which the original tuple was created; creating one or more reference tuples from the reference string of phonemes by: c. partitioning the reference string of phoneme into three or more contiguous reference substrings of phonemes; forming two or more reference tuples by appending together two or more reference substrings, one or more of the reference tuples being formed by appending two or more non contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index; tracking the matches between the reference index and original index; selecting an original phoneme string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 33
Independent Claim
260 words
A method for recognizing and accessing a reference string of notes in one or more original note strings within a database comprising the steps of: creating one or more original tuples for each of the original note strings in the database by: a. partitioning each original note string into three or more original substrings of contiguous notes; b. forming one or more original tuples associated with each original note string by appending together two or more original substrings of the original string, one or more of the original tuples being formed by appending together at least two non contiguous original substrings; creating a unique original index for each original tuple created from the original note string using an index algorithm, the original index being associated with the original note string from which the original tuple was created; creating one or more reference tuples from the reference string of note by: c. partitioning the reference string of notes into three or more contiguous reference substrings of notes; d. forming two or more reference tuples by appending together two or more reference substrings, one or more of the reference tuples being formed by appending two or more non contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index; tracking the matches between the reference index and original index; selecting an original note string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 34
Independent Claim
260 words
A method for recognizing and accessing a reference string of notes in one or more original note strings within a database comprising the steps of: creating one or more original tuples for each of the original note strings in the database by: a. partitioning each original note string into three or more original substrings of contiguous notes; b. forming one or more original tuples associated with each original note string by appending together two or more original substrings of the original string, one or more of the original tuples being formed by appending together at least two non contiguous original substrings; creating a unique original index for each original tuple created from the original note string using an index algorithm, the original index being associated with the original note string from which the original tuple was created; creating one or more reference tuples from the reference string of note by: c. partitioning the reference string of notes into three or more contiguous reference substrings of notes; d. forming two or more reference tuples by appending together two or more reference substrings, one or more of the reference tuples being formed by appending two or more non contiguous reference substrings; creating a unique reference index for each reference tuple using the index algorithm; comparing at least one reference index to at least one original index; tracking the matches between the reference index and original index; selecting an original note string in the database based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 35
Dependent Claim
307 words
A computer system for recognizing and accessing a reference string of tokens in one or more original token strings within a database comprising: a database having a set of original token strings; a means for creating at least one original tuple for each of the original token strings in the database, the tuple formed by: a. partitioning each original token string into three or more contiguous original substrings of tokens; b. forming one or more original tuple associated with each original string by appending together two or more original substrings of the original string, one or more of the original tuples being formed by appending together at least two non contiguous original substrings; a unique original index for each original tuple created from the original string using an index algorithm, the original index being associated with the original string from which the original tuple was created; a first memory look-up structure with cells, the cells being accessed by the original index and containing information associated with the original string from which the original tuple was created; one or more reference tuples created from the reference string of tokens by: c. partitioning the reference string of tokens into three or more non contiguous reference substrings of tokens; d. forming the reference tuples by appending together at least two reference substrings, one or more of the reference tuples being formed by appending two or more non contiguous reference substrings; unique reference index for each reference tuple created using the index algorithm, the reference index compared to at least one reference index to at least one original index; a second memory look-up structure for tracking matches between the reference index and original index, an original token string in the database being selected based on the number of matches between one or more original indexes and one or more reference indexes.
Claim 36
Dependent Claim
307 words
A computer system for recognizing and accessing a reference string of tokens in one or more original token strings within a database comprising: a database having a set of original token strings; a means for creating at least one original tuple for each of the original token strings in the database, the tuple formed by: a. partitioning each original token string into three or more contiguous original substrings of tokens; b. forming one or more original tuple associated with each original string by appending together two or more original substrings of the original string, one or more of the original tuples being formed by appending together at least two non contiguous original substrings; a unique original index for each original tuple created from the original string using an index algorithm, the original index being associated with the original string from which the original tuple was created; a first memory look-up structure with cells, the cells being accessed by the original index and containing information associated with the original string from which the original tuple was created; one or more reference tuples created from the reference string of tokens by: c. partitioning the reference string of tokens into three or more non contiguous reference substrings of tokens; d. forming the reference tuples by appending together at least two reference substrings, one or more of the reference tuples being formed by appending two or more non contiguous reference substrings; unique reference index for each reference tuple created using the index algorithm, the reference index compared to at least one reference index to at least one original index; a second memory look-up structure for tracking matches between the reference index and original index, an original token string in the database being selected based on the number of matches between one or more original indexes and one or more reference indexes.
References Cited (Backward Citations)
US4753878A
Cited
US4922414A
Cited
US4670890A
Cited
US4796185A
Cited
US4760523A
Cited
US4675829A
Cited
US4899128A
Cited
US4811218A
Cited
US4853871A
Cited
US4908773A
Cited
US4930071A
Cited
US4939666A
Cited
US4876541A
Cited
US4935877A
Cited
US5008818A
Cited
US5276616A
Cited
US5051745A
Cited
US5276741A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-11-19 | 2000-05-20 | 2000-11-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-19 | 2004-05-20 | 2004-11-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-19 | 2008-05-20 | 2008-11-19 | $7700.00 | Window Closed / Lapsed |