Teiresias algorithm

The Teiresias algorithm uses regular expressions to define the patterns. This allows the patterns reported to consist not only from the characters that appear in each position (literals) but from a specific group of characters (bracketed literals) or even from any character (wild card). The patterns created by the algorithm are <L,W> patterns that have at least k instances in the input, where L ≤ W and L, W, k positive integers. A pattern is called an <L,W> pattern if and only if any L consecutive literals or bracketed literals span at most W positions (i.e. there can be no more than W-L wild cards).

The algorithm reports only maximal patterns. Given a set of sequences S, a pattern P that appears k times in S is called maximal if and only if there exists no pattern P' which is more specific than P and also appears exactly k times in S. If there exists such a pattern P' then we say that P cannot be maximal and P is considered to be subsumed by P'. A pattern P' is said to be more specific than a pattern P if and only if P' can be obtained from P by (a) dereferencing a wild card or (b) instantiating a bracketed literal to a literal, or (c) appending a string of literals, bracketed literals or/and wild cards to the right of P, or (d) prepending a string of literals, bracketed literals or/and wild cards to the left of P.[3]

Teiresias consists of two phases, Scanning and Convolution. During the first phase the input is scanned for the patterns that satisfy the minimum requirements, the elementary patterns. The elementary patterns consist of exactly L literals and/or bracketed literals and includes at most W-L wild cards. During convolution, the elementary patterns are recursively combined and maximal patterns are created. The order in which the convolutions are performed is very important since it guarantees that all patterns will be generated and all maximal patterns are generated before all the patterns that are subsumed by them. The order is dictated by the following rules

• The priority of each pattern is defined by its contents from left to right.
• A literal has higher priority than a bracketed literal and both have higher priority than wild cards (the more specific first).
• Longer patterns have higher priority than shorter ones.
• Ties are resolved alphabetically.

Given the assurance that all maximal patterns will be created first, it is easy to check a newly created pattern against all maximal ones to ensure that it is subsumed, in which case it is discarded. If the newly created pattern is not subsumed then it is added to the list of maximal patterns. When no more patterns can be combined to form new maximal patterns then the algorithm terminates. The length of any maximal pattern is bounded from above by the length of the longest input sequence.

The algorithm is "output-sensitive." The time complexity of the TEIRESIAS algorithm is[3]

${\displaystyle O\left(W^{L}m\log m+(C^{m}+t_{H})\sum _{P_{max}}{rc(P)}\right)}$

where L and W are user-specified parameters that define the "minimum density" of a pattern (any L literals or brackets cannot span more than W positions), m is the number of characters the input includes, C ≤ 1 is the average number of patterns found in a hash entry, t_H is the time needed for locating the hash entry corresponding to any given hash value, and the summation Σ is the maximum number of patterns that will ever be placed in the stack that keeps the patterns for extension during convolution.

• A C++ based implementation of the algorithm can be found here.
• The interactive web-based user interface of Teiresias can be found here.