We propose a novel Multiple Sequence Alignment algorithm which is able to build an optimized branching graph given a set of positive matching sample strings. The algorithm is principally based on Minimum Edit Distance approach being applied incrementally. However, we essentially extended the set of edit operations. The newly added operations allow implementing an acyclic graph drawing feature. The feature yields a better visual and appropriate representation of partial alignment gaps between sample strings. For instance, it may produce an /abc|de[fg]/ regular expression from a set of "abc", "def", "deg" strings. For further optimization, we adjust edit penalties based on character class hierarchy. The algorithm may be used in Bioinformatics as well as for extracting Regular Expressions (RE, patterns) from sets of observed or prospective documents (that may be useful in Web data mining, Spam ltering, RE design advisory tools and so on). This paper also considers integration of the proposed algorithm into a full stack Regular Expression extraction ow, particularly, in conjunction to Repetition detection.
Regular expressions (RE) are used widely in various applications for the text
data processing. While in many cases the pattern a developer or analyst intends
to establish is clear and formally well de ned, there are many areas where
regular expressions used to recognize and mine a piece of text that is similar to
some sample [6]. Examples are Web data mining, Spam ltering,
Bioinformatics, State machine analysis and plenty of others. In these cases building and
testing a proper RE becomes technically challenging. Algorithms that generate
a RE that matches large number of samples are of high demand in these areas.
Also, such algorithms may provide priceless help to those application developers
who want to obtain necessary RE patterns just by supplying several matching
samples rather than by deepening into RE building details [7]. There exist a
lot of software tools aiding the regular expression building of blocks and testing
but few applications that generate a RE from samples. Examples of the latter
presented in [11],[2],[4],[3] employ genetic algorithms or Machine Learning
approaches directly to the block composition. In order to take an advantage of such
an universal approach, (
There are approaches that attempt to build an optimal automaton to satisfy a given input sequence [5]. They do produce regular expressions solely of positive samples. However, they are focused on repeated subsequence extraction while don't mind possible alignments and splitting branches for more neat representation. In this paper we propose an algorithm that performs alignment and partial join of input samples. Please note that the repetition extraction itself is generally beyond our discussion scope here, although being a part of the proposed technique. In a short word, the new algorithm performs fuzzy alignment of samples and produces branches while leaving the repetition extraction to an external method.
Our major motivation was producing regular expressions for advising programmers and users and for assisting human's work in areas where a content schema isn't much strict and clear. Following this, we pay attention to make a RE concise while adjustable both in terms of look and feel and of degrees of freedom (perplexity). 2
2.1
Hammock Graph fork
4 k [ij] 3 5 0 \d join 6 transition + bypass bypass
zero transition Non-exhaustive examples of possible/impossible new branches which might be added next time
Fig. 1. An example of regular expression graph
For the purposes of our algorithm, a regular expression is represented as a directed acyclic graph (Fig. 1). More precisely, as a "hammock graph" [14], allowing exactly one entrance and one exit to each area. A node of such a graph is referred to as a RE position , while an edge as a RE transition (there may be normal transitions that correspond to a character place as well as zero transitions shunting constructs like /(abc)?/). For the simplicity, in the current paper a graph is assumed to be sorted and having all positions enumerated with a continuous [0::N ] integer range.
We refer to a sub-graph between some entrance position and some exit position as a hammock . Thus, for example, all edges in a plain chain are hammocks. Hammocks of course may be nested. The way from a hammock's entrance position to it's exit is referred as a bypass. An entrance or exit position shared by multiple hammocks is referred as a fork or join position, respectively. 2.2
Character Selection
We represent every character place in a RE by a character selection . A character selection is both considered as a concrete character set and as a set of character classes that t it. A character set in our scope means all characters really falling to this place in some sample string(s). A character class is en entity that corresponds to some prede ned group of characters while also (optionally) restricts the maximum variety of participating characters. For example, a character class with [a z] character group and maximum allowed variety of 2 matches possible character selection of [ax] but doesn't match the [axz] due to the variety exceeding. The choice of character classes and their parameters essentially a ects the resulting regular expression look and actually represents the user preferences that cannot be deducted from a limited number of samples (like whether should we display [123] or nd for a concrete selection of digits at some RE element). Thus, character classes are considered to be user-de ned parameters in our algorithm. The only mandatory requirement is that every character should belong to at least one class. Every character class is attributed with a class cost. The class cost may be treated as an inverse metric to the prettiness of a class occurrence in a resulting expression record. The cost of a character selection is de ned as the minimum cost of a character class containing all characters selected.
sel(chars) =
min
cls2charClasses
8chcalsr:2mcahxaVrsa!recthyar2cls:chars
jjcharsjj
class(cls)
(
merge(chars; c) = sel(chars [ fcg) sel(chars) As a variant, a character class match may be additionally rewarded by substituting a zero resulting value with some negative one:
If
merge = 0 then
merge :=
match < 0
(
In order to produce a regular expression from a set of samples, we rst merge the samples into a hammock graph. The core part of our alignment algorithm generally looks like an extension of well known Minimum Edit Distance method [13]. The procedure incrementally transforms the current RE r, attempting to align it to the next sample s with the minimum penalty score. We use a dynamic programming algorithm that optimizes the total cost of regular expression modi cation choosing the best alignment between r and s positions. In order to get a nal RE, we start with some input sample as an initial RE and then merge all other samples one by one into it.
Note. The resulting expression look may depend on the order of sample string merging. Although the e ect of ordering yet needs exploration, our experiments showed that following a longer rst, shorter next order ensures an optimal alignment or a good approximation to it in vast majority of cases.
Our algorithm adds a new operation to the original operation set consisting of deletion, insertion and substitution. This new operation enables drawing a new graph branch instead of mere aligning characters between two given positions whenever it seems to yield better score. Table 1 displays the list of possible atomic editing events available at a given (i; j) combination where i is the target position in r while j is the number of processed characters of s.
We associate two cumulative costs, JL(i; j) and JS (i; j), to every possible (i; j) pair. Initially, JL(0; 0) = 0 while all other JL(i; j) and JL(i; j) are set to +1. (Subscripts L ans S near J stand for the `light' and `shadow' words, respectively). The di erence between JL and JS lays in the fact that the former immediately correspond to some position in r while the latter points to a bypass connection position inside a potential new branch coming "over" ith position in current RE. For example, if r was /ab/, s is "cd" and r will be /(ab)j(cd)/ then JS (1; 1) may refer to a connection point between a bypass "over" `a' and a bypass "over" `b'.
We ll matrices of JL and JS for all possible positions [0::M ] [0::N ] iterating positions in any convenient non-decreasing order. We use the following equations in order to take all possible edit events at (i; j) point into account. 8> JL(t:src; j 1) + insert; if j > 1 >>>> 8t 2 trans(i) JL(t:src; j) + delete JL(i; j) = min >< 8t 2 trans(i) JL(t:src; j 1) + merge(t:sel; s[j]); if j > 1 > 8b 2 bypass(r; i) : :b:f ork JS (b:src; j) >>>> 8b 2 bypass(r; i) JL(b:src; j) + branch > : 8t 2 zerotrans(i) JL(t:src; j)
>8 8b 2 bypass(r; i) : :b:join ^ :b:f ork; JS (b:src; j) JS (i; j) = min ><> J8Sb (2i;bjypa1s)s+(r; id)i:sp:;b:jiofinj >J1L(b:src; j) + branch >: JL(i; j 1) + disp + branch if j > 1
As seen from the equation, JS (i; j) cannot be used or assigned "through" a bypass that shares a fork or join, respectively. This restriction prevents projecting a hammock breaking branch, as discussed in the previous section. Once we consider a new branch creation, we apply a branch penalty. This penalty (acting merge insert 0, if the element is already marked optional; insert, otherwise disp branch, once per branch like a simpli ed Graph Edit Distance [8]) enforces the willingness to compose a laconic and uniform regular expression rather than to proliferate branches.
Having the matrix fully constructed, we traverse the lowest total penalty
path from JL(N; length(s)) back to JL(0; 0) in order to extract the least costly
sequence of editing events. To do this, we reuse the same equations (
The idea of algorithm described above may remind the A ne Gap Penalty concept known in Bioinformatics [9] ; the major di erence is the fact that we consider the gap not merely as a modi er to an element-by-element edit distance metric, but also as a reason to draw a new graph branch.
See Algorithm 1 illustrating the approach discussed.
JL(
JS(
Edit inline New branch
Fig. 3. An example: merging "rx12e" string to /ax(bejcf)/ expression A note on the complexity. The algorithm shows the same complexity as Minimum Edit Distance (per one sample), of O(M N ), which is meanly proportional to N 2, where M is the regular expression length, N is the sample string length. Still there are many known methods aimed to bound the complexity of Edit Distance minimization, and most of them are directly applicable to the proposed algorithm. Particularly, it might be bounding of maximum edit distance to some constant number [12] 4
A regular expression produced with the algorithm described above yet needs a repetition capture in order to get its nal form. We may employ any known method capable of nding and removing repetitions of adjacent substring in a plain symbol string . Let M (s) ! s0 denote such a method, where s and s0 are input and output strings, respectively. Now, we may process the RE graph recursively applying M to all edge sequences of the graph, recursively down up, representing each nested hammock by a single canonical symbol. In more detail, we use a T : ( ; Rmin; Rmax) tuple in order to represent a hammock, where is a symbol of some alphabet, Rmin and Rmax are the minimum and maximum number of 's repetition, respectively. So, we are to slightly modify the M procedure in order to t the following form.
MT (q) ! q0;
q; q0 : S;
where S denotes the sequence of T tuples. We expect that MT compares two
tuples in a sequence solely relating to the value (ignoring Rmin; Rmax). Once
has found a repetition, the procedure merges it into single tuple with proper
sums for the total Rmin and Rmax:
( ; Rmin1; Rmax1); ( ; Rmin2; Rmax2) ! ( ; Rmin1 + Rmin2; Rmax1 + Rmax2)
(
{ C(fx; []g) = (C(x): ; 0; C(x):Rmax) { C(f[x]g) = C(x) C function may expect that its arguments already represented in a canonical form.
We initially annotate each character selection cj found in our graph with a
tuple
(cHash(cj );
0; if cj marked as optional
1; otherwise
; 1) : T;
(
captureRepeat(b); b C(b); q
MT (q)
Now we have all elements annotated with their repetition bounds [Rmin ! Rmax] and thus we may deliver a RE. However, an user may want to see unbounded repetitions in it (like in /a+/ or /ab*/ ). We cannot rigorously extract an unbounded repetition from a nite number of samples, so we have to use empiric generalization rules. The simplest of them (while working well in practice) may be assigning Rmax to +1 if Rmax Rmin >= Rbound, where Rbound is some constant threshold (usually equal to 3). 5
We applied the proposed algorithm to the Spam classi cation task [10]. We used 195 series of Spam messages (i.e. 195 mimes). We extracted six sample strings from each message (four headers, a plain text and an HTML). Every series was split into the train and test sets (60% and 40% of messages, respectively). We randomly chose the sets three times per mime. As we don't know in advance which combination of sample strings (like "Subject+body" or "From+Html") better classi es a Spam mime, we have tried all 26 1 = 32 combinations and selected one per mime that yields the best F1 metric value once applied for classifying the union of the test set for this mime (Spam) and a standalone collection of non-Spam messages. We have repeated these experiments at various values of the branch cost ratio (that tells one how many avoided highest-cost character merges "worth" a new branch creation).
Fig. 4 displays F1 metric values distribution over mimes. It seems that branch cost should be at least about 3 for the best result. Further increase does not a ects the quality signi cantly.
Fig. 5 shows how the precision and the perplexity correlate to the recall. The precision in most cases equals one and behaves quite irregularly in the remaining cases that demonstrates a quite low probability of matching against some random document. A surprisingly inverse overall correlation in the (perplexity, recall) pair is due to the fact that an increase in perplexity of a generated RE is a reaction to a high content variety of training samples. A congestion near (50, 0.7) coordinate seems to be caused by the generator's attempts to satisfy the sets of altering string constants frequently occurring in Spam messages with the aim to challenge lters. The perplexity of generated regular expression still seems rather low to cover the expected variety of training set samples. Of course being a natural consequence of a synthetic approach to RE building, this fact F1 distribution over Spam mimes branch cost ratio = 1, no \d and \w classes branch cost ratio = 1 branch_cost ratio = 1.75 branch_cost ratio = 2.5 branch cost ratio = 8
Samples fraction, % indicates that further adjustments toward the perplexity boosting at "volatile" sample text regions might improve the recall values.
Spam messages provide an extremely challenging test bench because they are specially designed to foolish automated lters as possible. Thus, we didn't expect the recall to demonstrate as high values as it may be seen in "normal" content processing. A bunch of expression generated were analyzed and it was found that it's usually easy to do a manual correction (mostly meaning the removal of some parts) which results in a recall of 95..100%. Thus, the algorithm at it's today's stage may be considered as an e ective advisory solution for draft RE extraction. 6
We have found that each piece of a generated RE looks reasonable at a proper selections of major cost and limit parameters. However, the best choice of these parameters may signi cantly vary through the entire expression. At the same time, the overall alignment of samples works ne at a wide range of parameters. Thus we conclude that for the best advisory value the technique should allow recompilation of any selected part of generated RE at a di erent choice of options. Meanly, an optimal cost of branch containing 3 characters is expected to be of 0 . 1 ● ●
Precision against Recall in Spam tests
● bnroa\ndchancdos\wtrcaltaioss=e1s,
branch cost ratio = 1
branch_cost ratio = 1.75
branch_cost ratio = 2.5
branch cost ratio = 8
0.2
about 1.5..2.5 times the highest cost of single character merge (also referred to as
the Wild card cost). Table 2 displays examples of regular expressions generated
with a set of E-Mail addresses taken from a Spam distribution "From:" eld.
The table also includes manual assessment of expression quality in terms of
readability, recall, and precision. Expressions were taken under various settings of
three major parameters such as (
The algorithm has demonstrated its potential as an advisory solution for an analyst or an engineer willing to compose regular expressions in a semi-automated manner. Tuning of parameters may be really needed to get the desired look of Wild 4 4 4 2 4 7 2 2 3 4
cost
Branch Start Char 1..6 1 7 2 2 1 1 10 1 1 1 1 2 2 3 4 1 4 2 1
0 (?:Ponto Frio|(?:Sepho|Ext)ra| Ok
"?InfoJobs"?)< @mail2m\d{1,2}\.info> 0 (?:Ponto Frio|InfoJobs|"InfoJobs" | Ok but less
(?:Sepho|Ext)ra) < @mail2m\d{1,2}\.info> readable 0 .?\w{3}o?(?:ra|Jobs"?| Frio) too general,
< @mail2m\d?\d\.info> less readable 0 .?(?:[Io]n)?(?:.{2})?.{5} too general,
< @mail2m\d?\d\.info> less readable -2..0 ["P]?\wn?\wo?(?:.\w{3})?. irrelevant
< @mail2m\d?\d\.info> -2..0 (?:P|")?\wn?(?:\w{2})?(?: |\w)\w{3} too general
(?:o|")? < @mail2m\d?\d\.info> 0 (?:.{2})?(?:n[ft]o|f)?.{5} low rele
< @mail2m\d?\d\.info> vancy 0 ["P]?.n?.o?(?:.{2})?.{3} too general
< @mail2m\d?\d\.info> -2..0 .?\w{3}o?(?:ra|Jobs"?| Frio) < @mail2m\d?\d\.info> an expression produced. (And some extra logic/arithmetic in order to have an easy-to-use parameter control may be desirable in implementations).
Due to a quadratic complexity of the proposed algorithm, a preliminary alignment step should be done rst (using less consuming algorithms, for example, su x tree based ones) in case of long samples. This fact limits the maximum size of a branched RE region rather than the overall RE size and in such a way it doesn't principally prevent the usage of the proposed technique with text samples of arbitrary length.
Indeed, the proposed algorithm is expected to ll the gap between concrete substring alignment and the regularity (repetition) extraction. We mean a cascaded pipeline as follows. 1. A plain string based alignment of input samples splits a RE extraction task into a set of tasks with shorter text samples (complexity = O(K N log N ) or lower, where K is the sample count, N is a representative sample length). 2. The proposed extraction algorithm aligns characters in a fuzzy (class based) way and creates branches (complexity = O((N=N1) K N12) = O(K N N1)), where N1 is a representative length of sample substring produced by the previous phase. 3. A repetition extraction step over an aligned RE (complexity = O(N22) or lower, where N2 is a representative length of hammock chain in a graph resulting from phase 2, N2 <= N1).
Phase 2 complexity is critical in such a schema. The overall complexity depends on N1 behavior w.r.t. N . Fortunately, in real documents N1 usually seems to be bounded as thy contain some non-volatile structure that may be captured at phase 1. At such an assumption, overall complexity of the pipeline may be kept 'almost' equal to the complexity of phase 1.
An internet service demo based on the proposed algorithm is available at http://regexus.com. All interested people are welcome to test and use it. 8
We expect the following major directions of further related research. { to make parameters adjustable with Machine Learning techniques; { to explore an automated ordering of sample string as well as non-sequential merging methods; { to apply a preliminary alignment and partitioning of samples in order to reduce the overall complexity; { to explore an option to extract more 'popular' constructs of RE (say, references to previously matched substrings).
newSingle single char selection (s[current:j]) markAsOptional(newSingle) insert(r; current:i; newSingle) else if bestChoice:ancestor:j < current:j then
markAsOptional(charSelection(bestChoice:transition))) current bestChoice:ancestor if not empty(newBranch) then
addBranch(r; current; newBranch)