Method of discovering patterns in symbol sequences

A method of discovering one or more patterns in a set of k+1 sequences of symbols, called a (k+1)-tuple, where k is greater than or equal to two, within an overall set of w sequences having sequence numbers 1, 2, . . . , w , the symbols being members of an alphabet, each sequence of symbols having respective lengths L1, L2, . . . , Lw by first forming a k-tuple table and then forming a (k+1)-tuple table by combining the k-tuple table with an additional sequence of symbols, the formation of the k-tuple table comprising the steps of:

• a) translating the sequences of symbols into a table of ordered (symbol, position index) pairs, where the position index refers to the location of the symbol in a sequence;
• b) for each of the w sequences, grouping the (symbol, position index) pairs by symbol to form a respective master offset table, thus creating w master offset tables;
• c) using the position indices in the w master offset tables to determine the difference-in-position value between each occurrence of a symbol in one of the sequences and each occurrence of that same symbol in the other sequence in each master offset table, forming a k-tuple table associated with the k-tuple, the table comprising k columns, one of the k columns being a primary column and the remaining (k−1) columns being suffix columns, each column corresponding to one of the k sequences;
• i) the primary column comprising the (symbol, position index) pairs of a primary sequence,
• ii) the (k−1) suffix columns comprising (symbol, difference-in-position value) pairs, where the difference-in-position values are the position differences between all same symbols of each remaining sequence of the tuple and the primary sequence of the tuple,
• iii) the rows in the k-tuple table resulting from forming all combinations of same symbols from each sequence;
• d) creating a sorted k-tuple table by performing a multi-key sort on the k-tuple table, the sort keys being selected respectively from the difference-in-position values of the last suffix column (kth column) through the difference-in-position value of the first suffix column;
• the formation of the (k+1)-tuple table comprising the steps of:
• e) translating the additional sequence of symbols into a table of ordered (symbol, position index) pairs, where the position index refers to the location of the symbol in the additional sequence of symbols;
• f) grouping the (symbol, position index) pairs by symbol to form a master offset table;
• g) creating the (k+1)-tuple table of k+1 columns, one of the k+1 columns being a primary column and the remaining k columns being suffix columns, by:
• i) forming all combinations of same symbols between the primary column of the k-tuple table and the master offset table,
• ii) for each such combination, duplicating the corresponding row of the k-tuple table, and appending a (symbol, difference-in-position value) pair corresponding to the difference between the position index of the master offset table and the position index of the primary column;
• h) creating a sorted (k+1)-tuple table by performing a multi-key sort on the (k+1)-tuple table, the sort keys being selected respectively from the difference-in-position values of the last suffix column [(k+1)th column] through the difference-in-position value of the first suffix column;
• i) identifying one or more patterns by collecting adjacent rows of the sorted (k+1)-tuple table whose suffix columns contain identical difference-in-position values, the relative positions of the symbols in each pattern being determined by the primary column position indices, the one or more patterns being common to the k+1 sequences;
• and
• j) reading out the identified one or more patterns to a user.

A method of discovering one or more patterns in a set of k sequences of symbols, called a k-tuple, comprising the steps of:

• a) for a first pair of sequences of the k-tuple
• i) translating each sequence of symbols into a table of ordered (symbol, position index) pairs, where the position index of each (symbol, position index) pair refers to the location of the symbol in the sequence;
• ii) for each of the paired sequences, grouping the (symbol, position index) pairs by symbol to respectively form a first master offset table and a second master offset table;
• iii) forming a Pattern Map comprising an array having (L1+L2−1) rows by:
• A) subtracting the position index of the first master offset table from the position index of the second master offset table for every combination of (symbol, position index) pair having same symbols, the difference-in-position value resulting from each subtraction defining a row index;
• B) storing each (symbol, position index) pair from the first master offset table in a row of the Pattern Map, the row being defined by the row index, until all (symbol, position index) pairs have been stored in the Pattern Map;
• iv) identifying a parent pattern by collecting symbols having the identical difference-in-position value from each row of the Pattern Map and populating an output array with the collected symbols, the symbols being placed at relative locations in the parent pattern indicated by the position index of the (symbol, position index) pair;
• and
• v) repeating step iv) for each row of the Pattern Map;
• b) storing the identified patterns as arrays of (symbol, position index) pairs;
• c) for each subsequent pair of sequences of the k-tuple, replacing the (symbol, position index) pairs of the first sequence of the pair of sequences by the (symbol, position index) pairs of the stored patterns;
• d) repeating steps (a) through (c) for each subsequent pair of sequences until the k-th sequence of the k-tuple is reached;
• and
• e) reading out the identified one or more patterns to a user.

A computer-readable medium containing a plurality of data structures useful in controlling a computer system to discover one or more patterns in k sequences of symbols within an overall set of w sequences, the plurality of data structures comprising:

• a number w of master offset table data structures each grouping,
• for each value of a difference in position between each occurrence of a symbol in one of the sequences and each occurrence of that same symbol in each other sequence,
• the position (position index) in the first sequence of each symbol therein that appears in each of the other sequences at that difference-in-position value;
• a k-tuple table data structure comprising columns and rows, the columns comprising (symbol, position index) pairs and (symbol, difference-in-position value) pairs;
• and
• a sorted k-tuple table data structure comprising a row-sorted representation of the (symbol, position index) pairs and (symbol, difference-in-position value) pairs contained in the k-tuple table data structure,
• wherein adjacent rows of the sorted k-tuple table data structure whose suffix columns contain identical difference-in-position values define one or more patterns of symbols, the relative positions of symbols in each pattern being determined by the primary column position indices in the sorted k-tuple table data structure.

A computer-readable medium containing instructions for controlling a computer system to discover one or more patterns in a set of k sequences of symbols, called a k-tuple, where k is greater than or equal to two, within an overall set of w sequences having sequence numbers 1, 2, . . . , w , the symbols being members of an alphabet, each sequence of symbols having respective lengths L1, L2, . . . , Lw, by executing a method comprising the steps of:

• a) translating the sequences of symbols into a table of ordered (symbol, position index) pairs, where the position index refers to the location of the symbol in a sequence;
• b) for each of the w sequences, grouping the (symbol, position index) pairs by symbol to form a respective master offset table, thus creating w master offset tables;
• c) using the position indices in the w master offset tables to determine the difference-in-position value between each occurrence of a symbol in one of the sequences and each occurrence of that same symbol in the other sequence in each master offset table, forming a k-tuple table associated with the k-tuple, the table comprising k columns, one of the k columns being a primary column and the remaining (k−1) columns being suffix columns, each column corresponding to one of the k sequences;
• i) the primary column comprising the (symbol, position index) pairs of a primary sequence,
• ii) the (k−1) suffix columns comprising (symbol, difference-in-position value) pairs, where the difference-in-position values are the position differences between all same symbols of each remaining sequence of the tuple and the primary sequence of the tuple,
• iii) the rows in the k-tuple table resulting from forming all combinations of same symbols from each sequence;
• d) creating a sorted k-tuple table by performing a multi-key sort on the k-tuple table, the sort keys being selected respectively from the difference-in-position values of the last suffix column (kth column) through the difference-in-position value of the first suffix column;
• e) identifying a one or more patterns by collecting adjacent rows of the sorted k-tuple table whose suffix columns contain identical difference-in-position values, the relative positions of the symbols in each pattern being determined by the primary column position indices, the one or more patterns being common to the k sequences;
• and
• f) reading out the identified one or more patterns to a user