SYSTEM AND METHOD FOR DETERMINING COMMON SUBSEQUENCES

摘要

A computer-implemented method and system of generating a list of substrings that are common to at least two strings in a plurality of strings is disclosed. Each of the plurality of strings comprises a sequence of terms, and each of the substrings comprises a sequence of one or more of these terms. The method includes forming a reverse index of the terms in the plurality of strings. The reverse index identifies, for each of the terms, the one or more strings containing that term and position therein. The method includes arranging the plurality of strings in an order; and for each one of the strings in the order determining, using the reverse index, substrings common to that one of the strings and subsequent ones of the strings in the order; and for each one of those common substrings, saving an indication associating that common substring with the one of the strings and the subsequent ones of the strings in which that substring is found.

主权项

1. A computer-implemented method of generating a list of substrings that are common to at least two strings in a plurality of strings, wherein each of said plurality of strings comprises a sequence of terms, and wherein each of said substrings comprises a sequence of one or more of said terms, said method comprising:
forming a reverse index of said terms in said plurality of strings, said reverse index identifying, for each of said terms, the one or more strings containing that term and position therein; arranging said plurality of strings in an order; and for each one of said strings in said order:
determining, using said reverse index, substrings common to said one of said strings and subsequent ones of said strings in said order; andfor each one of those common substrings, saving an indication associating that common substring with said one of said strings and the subsequent ones of said strings in which that substring is found.