Maxime Crochemore

Costas S Iliopoulos

Hiafeng Yu

Algorithms for Computing Evolutionary Chains in Molecular and Musical Sequences

Keywords: String algorithms, approximate string matching, dynamic programming, molecular sequences, music analysis

The problem of nding evolutionary chains is de ned as follows: given a string t (\the text") and a pattern p ( the \motif"), nd whether there exists a sequence u1 = p; u2 ; : : : ; u l occurring in the text t such that ui+1 occurs to the right of ui in t and ui and ui+1 are \similar" (i.e. the di er by a certain number of symbols). Here we consider several variants of the evolutionary chain problem and we present e cient algorithms for solving them.

Introduction

This paper is focused on a set of string pattern-matching problems which arise in music analysis, musical information retrieval and molecular sequence analysis. A musical score can be viewed as a string: at a very rudimentary level, the alphabet could simply be the set of notes in the chromatic or diatonic notation, or at a more complex level, we could use the GPIR representation of Cambouropoulos 3,[START_REF] Cambouropoulos | A formal theory for the discovery of local boundaries in a melodic surface[END_REF] as the basis of an alphabet. Approximate repetitions in musical entities play a crucial role in nding musical similarities amongst di erent musical entities, as well as playing a part in de ning the \characteristic signature" (see 7]). Such algorithms can be used for melody identi cation and music retrieval e.g. audio applications on Internet systems.

Furthermore, e cient algorithms for computing the approximate repetitions are also directly applicable to molecular biology (see [START_REF] Fischetti | Identifying periodic occurences of a template with applications to protein structure[END_REF][START_REF] Karlin | E cients algorithms for molecular sequences analysis[END_REF][START_REF] Landau | An algorithm for approximate tandem repeats[END_REF] and in particular in DNA sequencing by hybridization [START_REF] Pevzner | Gray Code Masks for DNA Sequencing by Hybridization[END_REF]), reconstruction of DNA sequences from known DNA fragments (see [START_REF] Schmidt | All shortest paths in weighted grid graphs and its application to nding all approximate repeats in strings[END_REF][START_REF] Skiena | Reconstructing strings from substrings[END_REF]), in human organ and bone marrow transplantation as well as the determination of evolutionary trees among distinct species [START_REF] Schmidt | All shortest paths in weighted grid graphs and its application to nding all approximate repeats in strings[END_REF]).

Exact repetitions have been studied extensively. The repetitions can be either concatenated with the original substring or they may overlap or they may not. Algorithms for nding non-overlapping repetitions in a given string can be found in [START_REF] Apostolico | The myriad virtues of the Su x Trees[END_REF][START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF][START_REF] Iliopoulos | A linear algorithm for computing the squares of a Fibonacci string[END_REF][START_REF] Main | An O(n log n) algorithm for nding all repetitions in a string[END_REF][START_REF] Landau | An algorithm for approximate tandem repeats[END_REF][START_REF] Myers | An algorithm for locating non-overlapping regions of maximum alignment score[END_REF] and algorithms for computing overlapping repetitions can be found in 2, [START_REF] Iliopoulos | Fast local covers[END_REF][START_REF] Iliopoulos | Covering a string[END_REF][START_REF] Moore | Computing the covers of a string in linear time[END_REF]. A natural extension of the repetitions problem is to allow the presence of errors; that is, the identi cation of substrings that are duplicated to within a certain tolerance k (usually edit distance or Hamming distance). Moreover, the repeated substring may be subject to other constraints: it may be required to be of at least a certain length, and certain positions in it may be required to be invariant.

The problem of nding evolutionary chains is de ned as follows: given a string t (\the text") and a pattern p ( the \motif"), nd whether there exists a sequence u 1 = p; u 2 ; : : : ; u l occurring in the text t such that u i+1 occurs to the right of u i in t and u i and u i+1 are \similar" (i.e. the di er by a certain number of symbols).

a) Original d) replacement (= deletion + insertion) c) deletion b) insertion [ ] [ ] Figure 1
Local approximations in search pattern, trace gradual change (`evolution') in a motif.

See Music Example in Appendix

There is no speci c algorithm for the evolutionary chain problem in the literature. Landau and Vishkin 16,[START_REF] Landau | Fast string matching with k di erences[END_REF] gave an algorithm (LV Algorithm) for the string searching with k-di erences problem: given a text of length n, and an integer k and a pattern of length m, nd all occurrences of the pattern in the text with at most k-di erences; the LV algorithm requires O(n(log m + log j j)) time, where is the alphabet used. A naive way to solve this problem is to repeatedly apply the LV algorithm to the text using u i as the pattern, for i = 1; 2; :::, giving a worst-case O(n 2 (log m+log j j)) running time. Here we present a straightforward O(nm) algorithm for computing non-overlapping evolutionary chains with k-di erences. We also present an O(n(log m+log j j)) algorithm for the same problem that makes use of su x trees; this algorithm require O(kn) time for xed alphabets. Furthermore we present O(n 2 ) algorithms for several variants of the computing overlapping evolutionary chains with k di erences, where n is the size of the input string.

Here we study the computation of the longest evolutionary chain as well as the chain with least number of errors in total. Several variants to the evolutionary chain problem are still open. The choice of suitable similarity criteria in music and biology is still under investigation. The use of penalty tables may be more suitable than the k-di erences criterion in certain applications. Additionally, further investigation whether methods such as [START_REF] Galil | An improved algorithm for approximate string matching[END_REF][START_REF] Landau | Fast string matching with k di erences[END_REF] can be adapted to solve the above problems is needed.

The paper is organised as follows. In the next section we present some basic de nitions for strings and background notions for pattern-matching with k-di erences. In Section 3 we describe the algorithms for non-overlapping evolutionary chains. In Section 4 we describe the algorithms for several variants of overlapping evolutionary chains. Finally in Section 6 we present our conclusions and open problems.

2 Background and basic string de nitions A string is a sequence of zero or more symbols from an alphabet ; the string with zero symbols is denoted by . The set of all strings over the alphabet is denoted by . A string x of length n is represented by x 1 : : : x n , where x i 2 for 1 i n. A string w is a substring of x if x = uwv for u; v 2 ; we equivalently say that the string w occurs at position juj + 1 of the string x. The position jwj + 1 is said to be the starting position of u in x and the position jwj + juj the end position of u in x. A string w is a pre x of x if x = wu for u 2 . Similarly, w is a su x of x if x = uw for u 2 .

The string xy is a concatenation of two strings x and y. The concatenations of k copies of x is denoted by x k . For two strings x = x 1 : : : x n and y = y 1 : : : y m such that x n i+1 : : : x n = y 1 : : : y i for some i 1, the string x 1 : : : x n y i+1 : : : y m is a superposition of x and y. We say that x and y overlap Let x be a string of length n. A pre x x 1 : : : x p , 1 p < n, of x is a period of x if x i = x i+p for all 1 i n p. The period of a string x is the shortest period of x. A string b is a border of x if b is a pre x and a su x of x.

Consider the sequences 1 2 ::: l and 1 2 ::: l with i ; i 2 f g , i 2 f1::lg. If i 6 = i , then we say that i di ers to i . We distinguish among the following three types of di erences:

1. A symbol of the rst sequence corresponds to a di erent symbol of the second one, then we say that we have a mismatch between the two characters, i.e., i 6 = and i 6 = .

2. A symbol of the rst sequence corresponds to \no symbol" of the second sequence, that is i 6 = and i = . This type of di erence is called a deletion.

3. A symbol of the second sequence corresponds to \no symbol" of the rst sequence, that is i = and i 6 = . This type of di erence is called an insertion.

As an example, let the text be abcdefghi and the pattern be bxdyegh (see Figure 2). In positions 1 and 3 of t and p we have no di erences (the symbols \match") but in position 2 we have a mismatch. In position 4 we have a \deletion" and in position 5 we have a \match". In position 6 we have an \insertion" and in positions 7 and 8 we have \matches". Another way of seeing this di erence is that one can transform the sequence to by performing insertions, deletions and replacements of the mismatched symbols. Types of di erences: mismatch, insertion, deletion.

Let t = t 1 t 2 : : : t n and p = p 1 p 2 : : : p m with m < n. We say that p occurs at position q of t with at most k-di erences if there are a sequences a 1 ; :::; a r , b 1 ; :::; b r such that 1. There is a subsequence of the sequence a such that a s1 ; a s2 ; :::; a sr = t q ; t q+1 ; :::t q+r 1 with s 1 < s 2 < ::: < s r and a i = for all i 2 f1::rg fs 1 ; s 2 ; :::s r g.

2.

There is a subsequence of the sequence b such that b v1 ; b v2 ; :::b vr = p 1 ; p 2 ; :::p m with v 1 < v 2 < ::: < v r and b i = for all i 2 f1::rg fv 1 ; v 2 ; :::v r g .

3.

The number of di erences between the sequence a and b is at most k. 4. There are no sequences that satisfy 1 and 2 and have less than k di erences.

The problem of string searching with k-di erences is de ned as follows: given a text t = t 1 t 2 : : : t n , a pattern p = p 1 p 2 : : : p m and an integer k, nd all occurrences of the pattern p in the text t with at most k di erences. String searching with k-di erences.

Let the text be t = abcdefghi and the pattern be p = bxdyegh (see Figure 3). The pattern p occurs at position 4 of x with at most 3 di erences. The pattern p also occurs in position 2 with at most 5 di erences and the pattern p occurs in position 5 with at most 3 di erences.

Computing Non-overlapping Evolutionary Chains

The problem of non-overlapping evolutionary chains (abbreviated NOEC) is as follows: given a text t, an integer k and a pattern p, nd whether the strings of the a sequence u 1 = p; u 2 ; : : : ; u l occur in the text t such that:

1. The number of di erences between any two consecutive strings u i and u i+1 in the evolutionary chain is at most k, for all i 2 f1::lg. 2. The starting position of the string u i+1 in t is nearest one to the right of the end position of u i for all i 2 f1::lg.

The rst condition ensures that the strings in the evolutionary chain have errors within some tolerance and the second condition enforces the strings in the chain not to overlap. The non-overlapping evolutionary chain for p = abcd with at most one di erence.

The pattern p rst occurs in position 2. The rst re-occurrence of the pattern to the right of position 5 with at most 1-di erence is at position 7. Consider the pattern abb in position 14. The nearest re-occurrence of abb with at most one di erence is at position 15 (i.e. the string bb) but it is not part of the chain because it overlaps with abb; the rst re-occurrence with at most one di erence that is part of the chain is in position 17. The non-overlapping evolutionary chain is fabcd; abd; adb; abb; bb; bbg.

The modi ed dynamic programming Algorithm

First we consider an O(nm) algorithm for computing the non-overlapping evolutionary chain of a text of length n and a pattern of lenght m. The algorithm NOEC presented below is based on the Dynamic-Programming procedure presented in [START_REF] Landau | Introducing e cient parallelism into approximate string matching and a new serial algorithm[END_REF][START_REF] Landau | Fast string matching with k di erences[END_REF]. The main idea is to construct a matrix D 1::m; 1::n], where D i;j is the minimum number of di erences between the pre x of the pattern p 1 :::p i and any contiguous substring of the text ending at t j . The Dynamicprogramming procedure below terminates when it nds the rst occurrence of the pattern with at most k di erences.

G G G T C T A G 0 0 0 1 1 1 1 G 1 0 0 1 2 2 2 G 2 1 0 1 2 3 3 T 3 2 1 0 1 2 3

Figure 5

The matrix D i;j for p = GGGT and t = GGGTCTA Procedure Dynamic-Programming(t; p; k) begin n jtj; m jpj; D i;j 0; 0 i m; 0 j n; D i;0 i; 0 i m ;

for i := 1 to m do for j := 1 to n do if p i] = t j] then D i;j = minfD i 1;j + 1; D i;j 1 + 1; D i 1;j 1 g else D i;j = minfD i 1;j + 1; D i;j 1 + 1; D i 1;j 1 + 1g if D i;j k then return i; u comment u is the su x of t 1 :::t i is the one that achieves the score D i;j . od od end Next, the algorithm NOEC makes repeated applications of the Dynamicprogramming procedure; every time that an occurrence of the pattern is found ending at position i of the text, then we re-apply the Dynamic-programming procedure to the su x t i+1 :::t n . is the length of the pattern.

A fast dynamic programming algorithm

The matrix D computed by the Dynamic-Programming procedure above contains a lot of redundant data which are not of used by algorithm NOEC. In fact it will su ce to nd the index of the largest row of each diagonal of the matrix D, which has an entry less than k. This computation can be done in linear time with the aid of su x trees (see 1]) . The alternative dynamic programming algorithm given in 17] can be modi ed as above and it will lead to the following theorem (for details and proofs see 17]).

Theorem 2. There exists an algorithm that computes the non-overlapping evolutionary chain in O(kn) time for xed alphabets, where n is the length of the input text and k the is maximum number of di erences allowed between consecutive members of the chain.

Theorem 3. There exits an algorithm that computes the non-overlapping evolutionary chain in O(n(log m + log j j)) time for a general alphabet , where n is the length of the input text , m is the length of the pattern and k is the maximum number of di erences allowed consecutive members of the chain.

Computing Overlapping Evolutionary Chains

The problem of overlapping evolutionary chains (abbreviated OEC) is de ned as follows: given a text t, a pattern p and an integer k < jpj=2, nd whether the strings of the a sequence u 1 = p; u 2 ; : : : ; u l occur in t and satisfy the following conditions:

1. The number of di erences between u i and u i+1 is at most k, for all i 2 f1::lg. 2. Let s i he starting position of string u i in t for all i 2 f1::lg. The starting position of u i+1 for all i 2 f1::lg is to the right of s i + ju i j=2.

In this case we allow the strings of the evolutionary chain to overlap. These strings have been constrained the overlap at most jpj=2 symbols. Without such constraint, we can obtain trivial chains such as u i = t i :::t m 1 , where u i and u i+1 have at most one di erence. First we present a method for nding all possible members of an overlapping evolutionary chain Let D i;j be as in section 3 but the pattern is identical to the text, i.e. p = t; thus D is an n n matrix. In order to e ciently compute the matrix D i;j with both i; j 2 f1::ng; we need to evaluate the following matrix M; we mark M i;j := p if there is the alignment of p 1 :::p i with t 1 :::t j with the least number of di erences requires that p 1 matching t l for some l; otherwise we mark M i;j := . The matrix M i;j for t = GGGTCTA

G G G T C T

The computation of matrix M can easily be done using the matrix D. Consider two consecutive entries in a column of D, say D i;j and D i+1;j . We have to consider two cases:

1. The case p i+1 6 = t j . If D i+1;j D i;j , then the only way that we can align p i :::p i+1 and t 1 :::t j and achieve D i+1;j di erences is by aligning and matching p 1 with t l for some l; hence M i+1;j = p . Otherwise M i+1;j = .

2. The case p i+1 = t j . We have the following subcases: { D i+1;j = D i;j+1 + 1. In this case one can see that M i+1;j = M i;j+1 . { D i+1;j = D i;j 1 + 1. In this case one can see that M i+1;j = M i;j 1 . { D i+1;j = D i 1;j 1 . In this case one can see that M i+1;j = M i 1;j 1 . { i = 1. One can see that M i+1;j = .

If more than one of the above subcases hold, then we opt for the one that leads to M i+1;j = . Thus the computation M can easily done in parallel with the computation of D. In order to simplify the exposition the computation of M is omitted in the pseudocode below.

G G G T C T A G 0 0 0 1 1 1 1 G 1 0 0 1 2 2 2 G 2 1 0 1 2 3 3 T 3 2 1 0 1 2 3 C 3 2 2 1 0 1 2 Figure 7
The matrix D i;j for t = GGGTCTA using M i;j with m = 3 Let's consider Figure 7. We compute the rows 1,2,3, and 4 of the matrix D as in section 3 for the pattern p = GGGT. We also compute the matrix M as above. We will now proceed to compute approximate matches of GGTC with t 1 :::t i for all i. Lets consider the evaluation of D 5;2 ; its value depends on the values of D 5;1 ; D 4;1 and D 4;2 . If we were to use D 5;1 , then we have to increase its value by 1 for the mismatch of p 5 = C and t 2 = G and decrease it by 1 because M 4;1 = ; note p 1 is no longer taking part in this alignment. If were to use D 4;1 , then we have to increase its value by 1 for the mismatch of p 5 = C and t 2 = G and decrease it by 1 because M 4;1 = . If were to use D 4;2 , then we have to increase its value by 1 for the mismatch of p 5 = C and t 2 = G and decrease it by 1 because M 4;1 = . Whenever there is a match then we only use the three neighbouring values unaltered (see Figure 6). The correctness proof will appear in the full paper. The pseudocode for the procedure is outlined below.

Procedure Dynamic-Programming-II(t; p; k) begin n jtj; m jpj; D i;j 0; 0 l n; 0 i m; D i;0 i; 0 i m; for i := 1 to n do for j := 1 to n do if M i 1;j = p OR i < m then q = 0; else q = 1; if p i] = t j] then D i;j = minfD i 1;j + 1 q; D i;j 1 + 1 q; D i 1;j 1 g else D i;j = minfD i 1;j + 1 q; D i;j 1 + 1 q; D i 1;j 1 + 1 qg if D i;j k then return i; u end end Algorithm OEC(t; p; k) begin while i < n do (i; p) Dynamic-Programming-II(t; p; k) t t i+1 :::t n ; end Theorem 4. Algorithm OEC computes the all possible overlapping chains in O(n 2 ) time, where n is the length of the input text.

The de nition of the problem OEC does not specify which of the overlapping patterns is chosen as members of the overlapping evolutionary chain. The following variants of the OEC problem give three choices with di erent criteria.

Computing the nearest-neighbour evolutionary chain.

The problem of nearest-neighbour overlapping evolutionary chains (abbreviated NNOEC) is de ned as follows: given a text t, a pattern p and an integer k < jpj=2, nd whether the strings of the sequence u 1 = p; u 2 ; : : : ; u l occur in t and satisfy the conditions for the OEC problem and the string u i+1 is the nearest one to the right of s i + ju i j=2 that has at most k di erences with u i for all i 2 f1::lg.

Next, the algorithm NNOEC makes repeated applications of the Dynamicprogramming procedure; every time that an occurrence of the pattern is found ending at position i of the text, then we re-apply the Dynamic-programming procedure to the su x t i+1 :::t n . The NNOEC algorithm can be speeded up in a similar manner to the procedure Dynamic-Programming (see Theorems 2 & 3). The details will be shown in the full paper. Hence, we have the following theorems: Theorem 6. There exists an algorithm that computes the nearest neighbour evolutionary chain in O(kn) time over xed alphabets, where n is the length of the input text and k is the maximum number of di erences allowed between consecutive members of the chain. Theorem 7. There exists an algorithm that computes the nearest neighbour evolutionary chain in O(n(log m + log(j j)) time over an alphabet j j, where n is the length of the input text , m is the length of the pattern and k is maximum number of di erences allowed between consecutive members of the chain.

Computing the maximal length evolutionary chain.

The problem of computing longest overlapping evolutionary chains (abbreviated LOEC) is de ned as follows: given a text t, a pattern p and an integer k < jpj=2, nd whether the strings of the a sequence u 1 = p; u 2 ; : : : ; u l occur in t and satisfy the conditions as in the OEC problem and maximizes l. The computation of the maximal chain requires the full matrix D as is computed in Theorem 4 and the evaluation of the following recursion l max = l j ; if d i;j < k and d i;r > k 8r max r fl i+j and d i;r > kg; otherwise. where i + jpj=2 < r jpj.

Computing the minimal weight evolutionary chain

The problem of computing minimal-weight overlapping evolutionary chains (abbreviated WOEC) is de ned as follows: given a text t, a pattern p and an integer k < jpj, nd whether the strings of the a sequence u 1 = p; u 2 ; : : : ; u l occur in t and satisfy the conditions as in the OEC problem and minimize d = l X i=1 i + i where i is the sum of the di erences between u i and u i+1 and i = f(s i+1 s i ju i j), where f is a penalty table.

The computation of the maximal chain requires the full matrix D as computed in Theorem 4 and the evaluation of the following recursion w min (i) = j i jpj + w j ; if d i;j < k and d i;r > k 8r min r fw i+j and d i;r > kg; otherwise. where i + jpj=2 < r jpj.

Conclusions and Open problems

Our primary goal is to identify e cient algorithms for computational problems which arise in computer-assisted analysis of music, and to also formalise their relation to well known string pattern-matching problems. The major obstacle to applying computational and mathematical techniques developed in the context of string pattern-matching problems to problems of computer-assisted music analysis appears to be the di culty of communication and mutual comprehension between computer scientists and musicologists.

The primary direction of this research is towards a formal de nition of musical similarity between musical entities (i.e. complete pieces of music or meaningful subsets of pieces, e.g. `themes' or `motifs') (See 5,6,7] for details). In particular we are aiming at producing a quantitative measure or 'characteristic signature' of a musical entity. This measure is essential for melodic recognition and it will have many uses including, for example, data retrieval from musical databases.

Here we presented the practical algorithms NOEC and OEC for the computation of non-overlapping and overlapping evolutionary chains. Furthermore, we presented theoretical algorithms for the same problems with improved upper bounds on their time complexity. Additionally we presented two variants of the OEC problem, the maximal evolutionary chains and minimum-weight evolutionary chains, both of which are of practical importance.

The problems presented here need to be further investigated under a variety of similarity or distance rules (see 7,21]). For example, Hamming distance of two strings u and v is de ned to be the number of substitutions necessary to get u from v (u and v have the same length).

Finally comparisons of the empirical results obtained (to be presented in the full paper) and to those that can be obtained from software library on string algorithms (see 9]) should be drawn. Music Example Francesco da Milano, monothematic lute recercar (Cavalcanti Lutebook, f. 71v) The ve successive entries, A-E, are audibly related and can be treated as stages in the 'evolution' of a diatonic motif by a series of alterations of edit distance 2 (where the deletion, insertion, replacement and time-displacement operations each have weight 1). Thr example was taken from Cavalcanti Lutebook, Brussels, Belgium, Biblioth eque Royale (B-Br), MS II 275.

Appendix: Music Example

  Figure 2

1 2 3

 3 Figure 3

  Figure 4

  Figure 6

  Algorithm NOEC computes the non-overlapping evolutionary chain in O(nm) time and O(nm) space, where n is the length of the input text and m

	Algorithm NOEC(t; p; k) begin while i < n do (i; p) Dynamic-Programming(t; p; k) t t i+1 :::t n ; end
	Theorem 1.

  Algorithm NNOEC computes the nearest neighbour evolutionary chain in O(nm) time, where n is the length of the input text and m is the size of the input pattern.

	Theorem 5.
	Algorithm NNOEC(t; p; k) begin while i < n do (i; p) Dynamic-Programming(t; p; k) t t i+jui j=2+1 :::t n ; end

? Partially supported by the C.N.R.S. Program \G enomes" ?? Partially supported by the EPSRC grant GR/J 17844.


M Crochemore

F Mignosi

A Restivo
email: restivo]@altair.math.unipa.it

Minimal Forbidden Words and Factor Automata

Keywords: factorial language, anti-factorial language, factor code, factor automaton, forbidden word, avoiding a word, failure function

Let L(M) be the (factorial) language avoiding a given antifactorial language M. We design an automaton accepting L(M) and built from the language M. The construction is e ective if M is nite. If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.

Introduction

Let L A be a factorial language, i.e., a language containing all factors of its words. A word w 2 A is called a minimal forbidden word for L if w = 2 L and all proper factors of w belong to L. We denote by MF(L) the language of minimal forbidden words for L.

The study of combinatorial properties of MF(L) helps investigate the structure of the language L or of the system it describes. For instance, locally testable factorial languages (cf 8]) are characterized by the fact that the corresponding languages of minimal forbidden words are nite. In the context of Symbolic Dynamics they correspond to systems of nite type.

Another example is given by a language L that is the set of factors of an in nite word: in this case, as shown in 2], the elements of MF(L) are closely related to the bispecial factors (cf. 6], 7] and 3]) of the in nite word.

A measure of complexity of the language L is introduced in 2] based on the function F L , that counts, for any n, the number of words of length n in MF(L). Authors prove that the growth of F L (n) as well as the topological entropy of MF(L) are topological invariants of the dynamical system de ned by L. This result provides a usefull tool to show that some systems are not isomorphic, which comes in addition to other notion like the ordinary notion of entropy and the zeta function, for example.

Finally, 5] considers properties of languages de ned by nite forbidden sets of words. Authors de ne the M obius function for these languages.

In this paper we focus on the transformations between L and MF(L). We rst design an automaton accepting L(M) and that is built from the language M. When M is a nite set the transformation is e ective. Moreover, if M is given by its digital tree, that is, its tree-like deterministic automaton, the algorithm is very similar to the algorithm of Aho and Corasick that builds a pattern-matching machine for a nite set of words 1].

In a second part we consider the particular situation of a language that is the set of factors of a single word v. The construction of its factor automaton, the minimal deterministic automaton accepting the factors of v (see 4]) is known to be rather intricate. It is remarkable that the preceding transformation yields exactly the factor automaton of v when the input if the set M of minimal forbidden words of v. We also give an algorithm that realizes the converse transformation, building the trie of M from the factor automaton of v. A corollary of the algorithm is a non-trivial upper bound on the number of minimal forbidden words of a word.

The complexities of algorithms described in this paper are all linear in the size of their input or output. Therefore, the design of possible faster algorithms relies on di erent representations of objects, which is not the aim of the paper.

Avoiding an anti-factorial language

Let A be a nite alphabet and A be the set of nite words drawn from the alphabet A, the empty word included. Let L A be a factorial language, i.e. a language satisfying: 8u; v 2 A uv 2 L =) u; v 2 L. The complement language L c = A n L is a (two-sided) ideal of A . Denote by MF (L) the base of this ideal, we have L c = A MF (L)A .

The set MF (L) is called the set of minimal forbidden words for L. A word v 2 A is forbidden for the factorial language L if v = 2 L, which is equivalent to say that v occurs in no word of L. In addition, v is minimal if it has no proper factor that is forbidden.

One can note that the set MF (L) uniquely characterizes L, just because L = A n A MF (L)A :

(1) The following simple observation provides a basic characterization of minimal forbidden words.

Remark 1 A word v = a 1 a 2 a n belongs to MF (L) i the two conditions hold: { v is forbidden, (i.e., v = 2 L), { both a 1 a 2 a n?1 2 L and a 2 a 3 a n 2 L (the pre x and the su x of v of length n ? 1 belong to L).

The remark translates into the equality:

MF (L) = AL \ LA \ (A n L):
(2) As a consequence of both equalities (1) and (2) we get the following proposition.

Proposition 1 For a factorial language L, languages L and MF (L) are simultaneously rational, that is, L 2 Rat(A ) i MF(L) 2 Rat(A ).

The set MF (L) is an anti-factorial language or a factor code, which means that it satis es: 8u; v 2 MF (L) u 6 = v =) u is not a factor of v, property that comes from the minimality of words of MF (L).

We introduce a few more de nitions.

De nition 1 A word v 2 A avoids the set M, M A , if no word of M is a factor of v, (i.e., if v = 2 A MA ). A language L avoids M if every words of L avoid M.

From the de nition of MF (L), it readily comes that L is the largest (according to the subset relation) factorial language that avoids MF (L). This shows that for any anti-factorial language M there exists a unique factorial language L(M) for which M = MF (L). The next remark summarizes the relation between factorial and anti-factorial languages.

Remark 2 There is a one-to-one correspondence between factorial and antifactorial languages. If L and M are factorial and anti-factorial languages respectively, both equalities hold: MF (L(M)) = M and L(MF(L)) = L.

We also refer to the next de nition that is to be considered in the context of dynamical systems (see 9] for example).

De nition 2

The factorial language L is said to be of nite type when MF (L) is nite.

Finally, with an anti-factorial nite language M we associate the nite automaton A(M) as described below. The automaton is deterministic and complete, and, as shown at the end of the section by Theorem 3, the automaton accepts the language L(M).

The automaton A(M) is the tuple (Q; A; i; T; F) where { the set Q of states is fw j w is a pre x of a word in Mg, { A is the current alphabet, { the initial state i is the empty word , { the set T of terminal states is Q n M. States of A(M) that are words of M are sink states. The set F of transitions is partitioned into the three (pairwise disjoint) sets F 1 , F 2 , and F 3 de ned by: { F 1 = f(u; a; ua) j ua 2 Q; a 2 Ag (forward edges or tree edges),

{ F 2 = f(u; a; v) j u 2 Q n M; a 2 A; ua = 2 Q; v longest su x of ua in Qg (backward edges),
{ F 3 = f(u; a; u) j u 2 M; a 2 Ag (loops on sink states). The transition function de ned by the set F of arcs of A(M) is noted . Remark 3 One can easily prove from de nitions that 1. if q 2 Q n (M f g), all transitions arriving on state q are labeled by the same letter a 2 A, 2. from any state q 2 Q we can reach a sink state, i.e., q can be extended to a word of M.

De nition 3 For any v 2 A , q v denotes the state ( ; v), target of the unique path in A(M) starting at the initial state and labeled by v.

Since A(M) is a complete automaton, q v is always de ned. In the automaton A(M) states are words, but to avoid misunderstandings we sometimes write \the word corresponding to q v " instead of just \the word q v ".

Remark 4 Note that if v is a state of A(M) we have q v = v.

We are now ready to state the next lemma (which proof is by induction on v) that is used in the proof of Theorem 3, the main result of the section.

Lemma 2 Let M be an anti-factorial language and consider A(M). Let v 2 A be such that, for any proper pre x u of v, q u is not a sink state (q u = 2 M). Then, 1. the word q v is a su x of v, 2. q v is the longest su x of v that is also a state of A(M) (or 8q 2 Q q su x of v =) q su x of q v ). Proof. By induction on jvj.

./ Denoting by Lang(A) the language accepted by an automaton A, we get the main theorem of the section.

Theorem 3 For any anti-factorial language M, Lang(A(M)) = L(M). Proof. We rst prove L(M) Lang(A(M)). We have to show that if v is a word that avoids M then v 2 Lang(A(M)). Assume ab absurdo that v = 2 Lang(A(M)); therefore q v is a sink state. Let u be the shortest pre x of v for which q u is a sink state (note that q u = q v ). By lemma 2 statement 1, q u is a su x of u, but q v is by de nition an element of M, and so v does not avoid M, a contradiction.

We then prove Lang(A(M)) L(M). Let v 2 Lang(A(M)). Let us suppose ab absurdo that v does not avoid M, i.e., v = uwz for some w 2 M; u; z 2 A . We choose uw as the shortest pre x of v that belongs to A M. Since w 2 M it is by de nition a state of A(M); since w is a state that is a su x of uw, by Lemma 2 statement 2, w is a su x of q uw . But q uw , which is by de nition a state of A(M), is a pre x of an element w 0 of M. Since w is a su x of a pre x of w 0 , w is a factor of w 0 , a contradiction because M is anti-factorial.

./

The above de nition of A(M) turns into the algorithm below, called Lautomaton, that builds the automaton from a nite anti-factorial set of words.

The input is the trie T that represents M. It is a tree-like automaton accepting the set M and, as such, it is noted (Q; A; i; T; 0 ). The procedure can be adapted to test whether T represents an anti-factorial set, or even to generate the trie of the anti-factorial language associated with a set of words.

In view of Equality 1, the design of the algorithm remains to adapt the construction of a pattern matching machine (see 1] or 4]) The algorithm uses a function f called a failure function and de ned on states of T as follows. States of the trie T are identi ed with the pre xes of words in M. For a state au (a 2 A, u 2 A ), f(au) is 0 (i; u), quantity that may happen to be u itself. Note that f(i) is unde ned, which justi es a speci c treatment of the initial state in the algorithm.

L-automaton (trie T = (Q; A; i; T; 0 )) 1. for each a 2 A 2.

if 0 (i; a) de ned 3.

set (i; a) = 0 (i; a); Theorem 4 Let T be the trie of an anti-factorial language M. Algorithm Lautomaton builds a complete deterministic automaton accepting L(M).

Proof. The automaton produced by the algorithm has the same set of states as the input trie. It is clear that the automaton is deterministic and complete.

Let u 2 A + and p = (i; u). A simple induction on juj shows that the word corresponding to f(p) is the longest proper su x of u that is a pre x of some word in M. This notion comes up in the de nition of the set of transitions F 2 in the automaton A(M). Therefore, the rest of the proof just remains to check that instructions implement the de nition of A(M).

./ Theorem 5 Algorithm L-automaton runs in time O(jQj jAj) on input T = (Q; A; i; T; 0 ) if transition functions are implemented by transition matrices.

3 Factor automaton of a single word

In this section we specialize the previous results to the language of factors of a single word. It is proved below that the contruction of Section 2 yields the factor automaton (minimal dterministic automaton accepting the factors) of the word (see Theorem 7). The minimality of the automaton seems to be exceptional because, for example, the same construction applied to the set faa; abg does not provide a minimal automaton. The reverse construction that produces the trie of minimal forbidden words from the factor automaton is described in the next section.

We consider a xed word v 2 A and denote by F(v) be the language of factors of v. Proposition 6 The language F(v) is of nite type. Proof. Indeed, factors of v, of lengths less than jvj+1, avoid all words of length exactly jvj + 1. Therefore, every minimal forbidden word of F(v) has length at most jvj + 1.

./

The result of the previous proposition is made more precise in the next section, but an immediate consequence of it and of the de nition of the automaton A(M) for an anti-factorial language M, the automaton A(MF(F(v))) has anite number of states. The next statement gives a complete characterization of the automaton as the factor automaton of v.

Theorem 7 For any v 2 A , the automaton obtained from A(MF(F(v))) by removing its sink states is the minimal deterministic nite automaton accepting the language F(v) of factors of v. Proof. The automaton A(MF(F(v))) is already a deterministic nite automaton that accepts the language F(v) by Theorem 3. We only have to prove that it is minimal after removing the sink states.

Suppose ab absurdo that there exist two equivalent non-sink states p; q in Q. By the standard equivalence relation of undistinginshability and by construction p; q 2 F(v). Hence, v = xpy and v = x 0 qy 0 and we can choose x and x 0 of minimal length. We consider two cases:

(i) jxpj 6 = jx 0 qj, (ii) jxpj = jx 0 qj. Case (i). We can suppose for example that jxpj < jx 0 qj (the case jxpj > jx 0 qj is handled symmetrically). Then, xpy 2 F(v) implies that (p; y) is not a sink state, hence, by the equivalence (q; y) is not a sink state, that is, qy 2 F(v) by Remark 4. Therefore, v = x"qyz where jx"j jx 0 j by the choice of x 0 (of minimal length). Hence, jvj jx 0 j + jqj + jyj + jzj > jxpj + jyj = jvj, a contradiction. Case (ii). The equality jxpj = jx 0 qj implies either that p is a su x of q or the converse. Let us suppose for example that p = sq for some word s 6 = . By Remark 3 statement 2, there exists w = pz that belongs to MF(F(v)). By the equivalence, qz is also a sink state and, again by the equivalence, for no proper pre x u of qz, q u is a sink state. Hence, by Lemma 2.1, q qz is an element of MF(F(v)), that is, a su x of qz. Since p = sq; s 6 = , q qz is a proper su x of pz against the anti-factorial property of MF (F(v)). A contradiction again.

After cases (i) and (ii) it appears that there cannot exist two di erent nonsink states p; q in Q that are equivalent. Therefore the automaton without sink states is minimal, which ends the proof.

./

Minimal forbidden words of a word

We end the article by an algorithm that builds the trie accepting the language MF(F(v)) of minimal words avoided by v. This is an implementation of the inverse of the transformation described in Section 2. Its design follows Equality 2.

A corollary of the transformation gives a bound on the number of minimal forbidden words of a single word, which improves on the bound coming readily from Proposition 6. else if (p; a) = q and q not already treated 5. set 0 (p; a) = q;

6. return (Q; A;i; fsinksg; 0 );

The input of algorithm MF-trie is the factor automaton of word v. It includes the failure function de ned on the states of the automaton and called s. This function is a by-product of e cient algorithms that build the factor automaton (see 4]). It is de ned as follows. Let u 2 A + and p = (i; u). Then, s(p) = (i; u 0 ) where u 0 is the longest su x of u for which (i; u) 6 = (i; u 0 ). It can be shown that the de nition of s(p) does not depend on the choice of u.

-m m m m m m Theorem 8 Let A be the factor automaton of a word v 2 A . (It accepts the language F(v).) Algorithm MF-trie builds the tree-like deterministic automaton accepting MF (F(v)) the set of minimal forbidden words of F(v). Corollary 9 A word v 2 A has no more than 2(jvj?2)(jA v j?1)+jAj minimal forbidden words if jvj 3, where A v is the set of letters occurring in v. The bound becomes jAj + 1 if jvj < 3.

Proof. The number of words in MF (F(v)) is the number of sink states created during the execution of algorithm MF-trie. These states have exactly one ingoing arc originated at a state of the factor automaton A of v. So, we have to count these arcs.

From the initial state of A there is exactly jAj ? jA v j such arcs. From the (unique) state of A without outgoing arc, there are at most jA v j such arcs. From other states there are at most jA v j ? 1 such arcs.

For jvj 3, it is known that A has at most 2jvj?2 states (see 4]). Therefore, jMF(F(v))j (jAj?jA v j)+jA v j+(2jvj?4)(jA v j?1) = 2(jvj?2)(jA v j?1)+jAj.

When jvj < 3, it can be checked directly that jMF(F(v))j jAj + 1. ./ Theorem 10 Algorithm MF-trie runs in time O(jvj jAj) on input word v if transition functions are implemented by transition matrices.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Trie of the factor code faa; bbaa; bbbg on the alphabet fa; bg. Squares represent terminal states.

  ; a) unde ned and (p = i or (s(p); a) de ned 3. set 0 (p; a) = new sink; 4.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Factor automaton of abbab; all states are terminal.


M Crochemore

F Mignosi

A Restivo

S Salemi

Text Compression Using Antidictionaries

Keywords: data compression, information theory, nite automaton, forbidden word, pattern matching

We give a new text compression scheme based on Forbidden Words ("antidictionary"). We prove that our algorithms attain the entropy for equilibrated binary sources. One of the main advantage of this approach is that it produces very fast decompressors. A second advantage is a synchronization property that is helpful to search compressed data and to parallelize the compressor. Our algorithms can also be presented as \compilers" that create compressors dedicated to any previously xed source. The techniques used in this paper are from Information Theory and Finite Automata; as a consequence, this paper shows that Formal Language Theory (in particular Finite Automata Theory) can be useful in Data Compression.

Introduction

We present a simple text compression method called DCA (Data Compression with Antidictionaries) that uses some \negative" information about the text, which is described in terms of antidictionaries. Contrary to other methods that make use, as a main tool, of dictionaries, i.e., particular sets of words occurring as factors in the text (cf. 6], 13], 17], 19] and 20]), our method takes advantage from words that do not occur as factor in the text, i.e., that are forbidden. Such sets of words are called here antidictionaries.

Let w be a text on the binary alphabet f0; 1g and let AD be an antidictionary for w. By reading the text w from left to right, if at a certain moment the current pre x v of the text admits as su x a word u 0 such that u = u 0 x 2 AD with x 2 f0; 1g, i.e., u is forbidden, then surely the letter following v in the text cannot be x and, since the alphabet is binary, it is the letter y 6 = x. In other Web page at URL http://www-igm.univ-mlv.fr/ mac/DCA.html y Institut Gaspard-Monge z Universit a di Palermo 1 terms, we know in advance the next letter y, that turns out to be redundant or predictable. The main idea of our method is to eliminate redundant letters in order to achieve compression. The decoding algorithm recovers the text w by predicting the letter following the current pre x v of w already decompressed.

The method here proposed presents some analogies with ideas discussed by C. Shannon at the very beginning of Information Theory. In 18] Shannon designed psychological experiments in order to evaluate the entropy of English. One of such experiments was about the human ability to reconstruct an english text where some characters were erased. Actually our compression methods erases some characters and the decompression reconstruct them.

We prove that the compression rate of our compressor reaches the entropy almost surely, provided that the source is equilibrated and produced from a nite antidictionary. This type of source approximates a large class of sources, and consequently, a variant of the basic scheme gives an optimal compression for them. The idea of using antidictionaries is founded on the fact that there exists a topological invariant for Dynamical Systems based on forbidden words and independent of the entropy 4].

The use of the antidictionary AD in coding and decoding algorithms requires that AD must be structured in order to answer to the following query on a word v: does there exists a word u = u 0 x, x 2 f0; 1g, in AD such that u 0 is a su x of v? In the case of positive answer the output should also include the letter y de ned by y 6 = x. One of the main features of our method is that we are able to implement e ciently nite antidictionaries in terms of nite automata. This leads to e cient and fast compression and decompression algorithms, which can be realized by sequential transducers (generalized sequential machines). This is especially relevant for xed sources. It is then comparable to the fastest compression methods because the basic operation at compression and decompression time is just table lookup.

A central notion of the present method is that of minimal forbidden words, which allows to reduce the size of antidictionaries. This notion has also some interesting combinatorial properties. Our compression method includes algorithms to compute antidictionaries, algorithms that are based on the above combinatorial properties and that are described in details in 8] and 9].

The compression method shares also an interesting synchronization property, in the case of nite antidictionaries. It states that the encoding of a block of data does not depend on the left and right contexts except for a limited-size pre x of the encoded block. This is helpful to search compressed data, which is not a common feature of other compression methods. The same property allows to design e cient parallel compression algorithms.

The paper is organized as follows.

In Section 2 we give the de nition of Forbidden Words and of antidictionaries. We describe DCA, our text compression and decompression algorithms (binary oriented) assuming that the antidictionary is given and that we can perform special kinds of queries on this antidictionary.

In Section 3 we describe a data structure for nite antidictionaries that allows to answer in e cient way to the queries needed by our compression and decompression algorithms; we show how to implement it given a nite antidictionary. The compression is also described in terms of transducers, which is valid only in the case of rational antidictionaries. We end the section by proving the synchronizion property.

In Section 4 we evaluate the compression rate of our compression algorithm relative to a given antidictionary.

In Section 5 we show how to construct antidictionaries for single words and sources. As a consequence we obtain a family of linear time optimal algorithms for text compression that are universal for equilibrated sources generated from antidictionaries.

We report in Section 6 experimental results made with a dynamic prototype of DCA. It shows that the compression rate is similar to those of most common compressors.

We consider possible generalizations in the conclusion (Section 7).

Forbidden Words and the Basic Algorithms

Let us rst introduce the main ideas of our algorithm. Let w be a nite binary word and let F (w) be the set of factors of w.

For instance, if w = 01001010010 F (w) = f"; 0; 1; 00; 01; 10; 001; 010; 100; 101; : : :g where " denotes the empty word.

Let us take some words in the complement of F (w), i.e., let us take some words that are not factors of w and that we call forbidden. The set of such words AD is called an antidictionary of the language F (w). Antidictionaries can be nite as well in nite.

For instance, if w = 01001010010 the words 11, 000, and 10101 are forbidden and the set AD = f000; 10101; 11g is an antidictionary of F (w).

The compression algorithm treats the input word in an online manner. At a certain moment in this process we have read the word v pre x of w. If there exists a word u = u 0 x, x 2 f0; 1g, in the antidictionary AD such that u 0 is a su x of v, then surely the letter following v cannot be x, i.e., the next letter is y, y 6 = x. In other words, we know in advance the next letter y that turns out to be \redundant" or predictable. Remark that this argument works only in the case of binary alphabets.

The main idea in the algorithm we describe is to eliminate redundant letters in order to achieve compression.

In what follows we rst describe the compression algorithm, Encoder and then the decompression algorithm, Decoder. The word to be compressed is noted w = a 1 a n and its compressed version is denoted by (w).

Encoder (anti-dictionary AD, word w 2 f0; 1g ) 1. v "; ";

2. for a rst to last letter of w 3. 4. if for any su x u 0 of v, u 0 0; u 0 1 6 2 AD 5.

:a; 6. return (jvj, );

As an example, let us run the algorithm Encoder on the string w = 01001010010 with the antidictionary AD = f000; 10101; 11g. The steps of the treatment are described in the next array by the current values of the pre x v i = a 1 a i of w that has been just considered and of the output (w). In the case of positive answer to the query to the antidictionary AD, the array also indicates the value of the corresponding forbidden word u. The number of times the answer is positive in a run corresponds to the number of bits erased.

" (w) = " v 1 = 0 (w) = 0 v 2 = 01 (w) = 01 u = 11 2 AD v 3 = 010 (w) = 01 v 4 = 0100
(w) = 010 u = 000 2 AD v 5 = 01001 (w) = 010 u = 11 2 AD v 6 = 010010 (w) = 010 v 7 = 0100101 (w) = 0101 u = 11 2 AD v 8 = 01001010 (w) = 0101 u = 10101 2 AD v 9 = 010010100 (w) = 0101 u = 000 2 AD v 10 = 0100101001 (w) = 0101 u = 11 2 AD v 11 = 01001010010 (w) = 0101 Remark that the function is not injective. For instance (010010100) = (0100101001) = 0101. In order to have an injective mapping we can consider the function 0 (w) = (jwj; (w)). In this case we can reconstruct the original word w from both 0 (w) and the antidictionary.

The decoding algorithm works as follow. The compressed word is (w) = b 1 b h and the length of w is n. The algorithm recovers the word w by predicting the letter following the current pre x v of w already decompressed. If there exists a word u = u 0 x, x 2 f0; 1g, in the antidictionary AD such that u 0 is a su x of v, then, the output letter is y, y 6 = x. Otherwise, the next letter is read from the input . Decoder (anti-dictionary AD, integer n, word 2 f0; 1g ) 1. v "; 2. while jvj < n 3.

if for some u 0 su x of v and x 2 f0; 1g, u 0 x 2 AD 4. 8. return (v);

The antidictionary AD must be structured in order to answer to the following query on a word v: does there exist a word u = u 0 x, x 2 f0; 1g, in AD such that u 0 is a su x of v? In case of a positive answer the output should also include the letter y de ned by y 6 = x.

The method presented here brings to mind some ideas proposed by C. Shannon at the very beginning of Information Theory. In 18] Shannon designed psychological experiments in order to evaluate the entropy of English. One of such experiments was about the human ability to reconstruct an english text where some characters were erased. Actually our compression methods erases some characters and the decompression reconstruct them. For instance in previous example the input string is 01 00 1 01 0 0 1 0;

where bars indicate the letters erased in the compression algorithm.

In this approach the encoder must send to the decoder the length of the word jwj, the compressed word (w) as well the antidictionary in the case the decoder has not yet a copy of the antidictionary.

In order to have a good compression rate we need to minimize in particular the size of the antidictionary. Remark that if there exists a forbidden word u = u 0 x, x 2 f0; 1g in the antidictionary such that u 0 is also forbidden then our algorithm will never use this word u in the algorithms. So that we can erase this word from the antidictionary without any loss for the compression of w.

This argument leads to introduce the notion of minimal forbidden word with respect to a factorial language L, notion that is discussed in the next section.

Implementation of Finite Antidictionaries

The queries on the antidictionary required by the algorithm of the previous section are realized as follows. We build the deterministic automaton accepting the words having no factor in the antidictionary. Then, while reading the text to encode, if a transition leads to a sink state, the output is the other letter. What remains to explain is how the automaton is built from the antidictionary.

The wanted automaton accepts a factorial language L. Recall that a language L is factorial if L satis es the following property: for any words, u, v, uv 2 L ) u 2 L and v 2 L.

The complement language L c = A nL is a (two-sided) ideal of A . Denoting by MF (L) the base of this ideal, we have L c = A MF (L)A . The set MF (L) is called the set of minimal forbidden words for L. A word v 2 A is forbidden for the factorial language L if v = 2 L, which is equivalent to say that v occurs in no word of L. In addition, v is minimal if it has no proper factor that is forbidden. One can note that the set MF (L) uniquely characterizes L, just because L = A n A MF (L)A :

(1) Indeed, there is a duality between factorial and anti-factorial languages, because we also have the equality:

MF (L) = AL \ LA \ (A n L):
(2) As a consequence of both equalities (1) and (2) we get the following proposition.

Proposition 1 For a factorial language L, languages L and MF (L) are simultaneously rational, that is, L 2 Rat(A ) i MF (L) 2 Rat(A ).

The set MF (L) is an anti-factorial language or a factor code, which means that it satis es: 8u; v 2 MF (L) u 6 = v =) u is not a factor of v, property that comes from the minimality of words of MF (L).

We introduce a few more de nitions.

De nition 1 A word v 2 A avoids the set M, M A , if no word of M is a factor of v, (i.e., if v = 2 A MA ). A language L avoids M if every word of L avoid M.

From the de nition of MF (L), it readily comes that L is the largest (according to the subset relation) factorial language that avoids MF (L). This shows that for any anti-factorial language M there exists a unique factorial language L(M) for which M = MF (L). The next remark summarizes the relation between factorial and anti-factorial languages.

Remark 1 There is a one-to-one correspondence between factorial and antifactorial languages. If L and M are factorial and anti-factorial languages respectively, both equalities hold: MF (L(M)) = M and L(MF(L)) = L.

Finally, with a nite anti-factorial language M we associate the nite automaton A(M) as described below. The automaton is deterministic and complete, and, as shown at the end of the section by Theorem 1, it accepts the language L(M). the set Q of states is fw j w is a pre x of a word in Mg, A is the current alphabet, the initial state i is the empty word ", the set T of terminal states is Q n M. States of A(M) that are words of M are sink states. The set F of transitions is partitioned into the three (pairwise disjoint) sets F 1 , F 2 , and F 3 de ned by: F 1 = f(u; a; ua) j ua 2 Q; a 2 Ag (forward edges or tree edges), F 2 = f(u; a; v) j u 2 Q n M; a 2 A; ua = 2 Q; v longest su x of ua in Qg (backward edges), F 3 = f(u; a; u) j u 2 M; a 2 Ag (loops on sink states).

The transition function de ned by the set F of arcs of A(M) is noted .

The next result is proved in 8].

Theorem 1 For any anti-factorial language M, A(M) accepts the language L(M).

The above de nition of A(M) turns into the algorithm below, called Lautomaton, that builds the automaton from a nite anti-factorial set of words.

The input is the trie T that represents M. It is a tree-like automaton accepting the set M and, as such, it is noted (Q; A; i; T; 0 ). In view of Equality 1, the design of the algorithm remains to adapt the construction of a pattern matching machine (see 1] or 7]). The algorithm uses a function f called a failure function and de ned on states of T as follows. States of the trie T are identi ed with the pre xes of words in M. For a state au (a 2 A, u 2 A ), f(au) is 0 (i; u), quantity that may happen to be u itself.

Note that f(i) is unde ned, which justi es a speci c treatment of the initial state in the algorithm. Example. Figure 1 displays the trie that accepts M = f000; 10101; 11g. It is an anti-factorial language. The automaton produced from the trie by algorithm L-automaton is shown in Figure 2. It accepts all the words avoiding M.

- 0 - 1 - 0 - 1 - 0 - 1 @ @ @ @ R 1 ? 1 1 6 0 H H H H H H H H H Y 0 0,1 0,1 0,1
Theorem 2 Let T be the trie of an anti-factorial language M. Algorithm Lautomaton builds a complete deterministic automaton accepting L(M).

Proof. The automaton produced by the algorithm has the same set of states as the input trie. It is clear that the automaton is deterministic and complete.

Let u 2 A + and p = (i; u). A simple induction on juj shows that the word corresponding to f(p) is the longest proper su x of u that is a pre x of some word in M. This notion comes up in the de nition of the set of transitions F 2 in the automaton A(M). Therefore, the rest of the proof just remains to check that instructions implement the de nition of A(M). ./

The algorithm L-automaton can be adapted to test whether T represents an anti-factorial set, to generate the trie of the anti-factorial language associated with a set of words, or even to built the automaton associated with the antifactorial language corresponding to any set of words.

Transducers

From the automaton A(M) we can easily construct a ( nite-state) transducer B(M) that realizes the compression algorithm Encoder, i.e., that computes the function .

The input part of B(M) coincides with A(M) and the output is given as follows: if a state of A(M) has two outgoing edges, then the output labels of these edges coincide with their input label; if a state of A(M) has only one outgoing edge, then the output label of this edge is the empty word.

The transducer B(M) works as follows on an input string w. Consider the (unique) path in B(M) corresponding to w. The letters of w that correspond to an edge that is the unique outgoing edge of a given state are erased; other letters are unchanged.

We can then state the following theorem.

Theorem 4 Algorithm Encoder is realized by a sequential transducer (generalized sequential machine).

As to concern the algorithm Decoder, remark (see Section 2) that the function is not injective and that we need some additional information, for instance the length of the original uncompressed word, in order to reconstruct it without ambiguity. We show that Decoder can be realized by the same transducer as above, by interchanging input and output labels (denote it by B 0 (M)), with a supplementary instruction to stop the decoding.

Let Q = Q 1 Q 2 be a partition of the set of states Q, where Q i is the set of states having i outpoing edges (i = 1; 2). For any q 2 Q 1 , de ne p(q) = (q; q 1 ; : : :; q r ) as the unique path in the tranducer for which q j 2 Q 1 for j < r and q r 2 Q 2 .

Given an input word v = b 1 b 2 : : : b m , there exists in B 0 (M) a unique path i; q 1 ; : : : ; q m 0 such that q m 0 1 2 Q 2 and the transition from q m 0 1 to q 0 m correspond to the input letter b m If q m 0 2 Q 2 , then the output word corresponding to this path in B 0 (M) is the unique word w such that (w) = v.

If q m 0 2 Q 1 , then we can stop the run of the decoding algorithm realized by B 0 (M) in any state q 2 p(q m 0 ), and, for di erent states, we obtain di erent decoding. So, we need a supplementary information (for instance the length of the original uncompressed word) to perform the decoding. In this sense we can say that B 0 (M) realizes sequentially the algorithm Decoder.

The constructions and the results given above can be generalized also to the case of rational antidictionaries, or, equivalently, when the set of words \produced by the source" is a rational language. In these cases it is not, in a strict sense, necessary to introduce explicitely antidictionaries and all the methods can be presented in terms of automata and tranducers, as above. Remark however that the presentation given in Section 2 in terms of antidictionaries is more general, since it includes the non rational case. Moreover, even in the nite case, the construction of automata and transducers from a xed text, given in the next section, makes an explicit use of the notion of minimal forbidden words and of antidictionaries.

A Synchronization Property

In the sequel we prove a synchronization property of automata built fromnite antidictionaries, as described above. This property also \characterizes" in some sense nite antidictionaries. This property is a classical one and it is of fundamental importance in practical applications.

We start with a de nition.

De nition 2 Given a deterministic nite automaton A, we say that a word w = a 1 a n is synchronizing for A if, whenever w represents the label of two paths (q 1 ; a 1 ; q 2 ) (q n ; a n ; q n+1 ) and (q 0 1 ; a 1 ; q 0

2 ) (q 0 n ; a n ; q 0 n+1 ) of length n, then the two ending states q n+1 and q 0 n+1 are equal.

If L(A) is factorial, any word that does not belong to L(A) is synchronizing. Clearly in this case synchronizing words in L(A) are much more interesting.

Remark also that, since A is deterministic, if w is synchronizing for A, then any word w 0 = wv that has w as pre x is also synchronizing for A.

Remark that if A is n-local then it is m-local for any m n. Given a nite antifactorial language M, let A(M) be the automaton associated with M as described in Section 4. Recall that it has no sink state, that all states are terminal, and that L(A(M)) is factorial.

Theorem 5 Let M be a nite antifactorial antidictionary and let n be the length of the longest word in M. Then automaton A(M) associated to M is (n 1)-local.

Proof. Let u = a 1 a n 1 be a word of length n 1. We have to prove that u is synchronizing. Suppose that there exist two paths (q 1 ; a 1 ; q 2 ) (q n 1 ; a n 1 ; q n ) and (q 0 1 ; a 1 ; q 0 2 ) (q 0 n 1 ; a n 1 ; q 0 n ) of length n 1 labeled by u. We have to prove that the two ending states q n and q 0 n are equal. Recall that states of A are words, and, more precisely they are the proper pre xes of words in M. A simple induction on i, 1 i n shows that q i (respectively q 0 i ) \is" the longest su x of the word q 1 a 1 a i (respectively q 0 1 a 1 a i ) that is also a \state", i.e., a proper pre x of a word in M. Hence q n (respectively q 0 n ) is the longest su x of the word q 1 u (respectively q 0 1 u) that is also a proper pre x of a word in M. Since all proper pre xes of words in M have length at most n 1, both q n and q 0 n have length at most n 1. Since u has length n 1, both they are the longest su x of u that is also a proper pre x of a word in M, i.e., they are equal. ./

The previous theorem admits a \converse" that we state without proof and that shows that locality characterizes in some sense nite antidictionaries (cf. Propositions 2.8 and 2.14 of 3]). Theorem 6 If automaton A is local and L(A) is a factorial language then there exists a nite antifactorial language M such that L(A) = L(M).

Let M be an antifactorial antidictionary and let n be the length of the longest word in M. Let also w = w 1 uvw 2 2 L(M) with juj = n 1 and let (w) = y 1 y 2 y 3 be the word produced by our encoder of Section 2 with input M and w. The word y 1 is the word produced by our encoder after processing w 1 u, the word y 2 is the word produced by our encoder after processing v and the word y 3 is the word produced by our encoder after processing w 2 .

The proof of next theorem is an an easy consequence of previous de nitions and of the statement of Theorem 5.

Theorem 7 The word y 2 depends only on the word uv and it does not depend on the contexts of it, w 1 and w 2 .

The property stated in the theorem has an interesting consequence for the design of pattern matching algorithms on words compressed by the algorithm Encoder. It implies that, to search the compressed word for a pattern, it is not necessary to decode the whole word. Just a limited left context of an occurrence of the pattern needs to be processed (cf. 10]). This is not a common feature of other compression methods. They have to split the input to get the same advantage, but this may weaken the e ciency of the nal compression algorithm.

The same property allows the design of highly parallizable compression algorithms. The idea is that the compression can be performed independently and in parallel on any block of data. If the text to be compressed is parsed into blocks of data in such a way that each block overlaps the next block by a length not smaller than the length of the longest word in the antidictionary, then it is possible to run the whole compression process.

E ciency

In this section we evaluate the e ciency of our compression algorithm relatively to a source corresponding to the nite antidictionary M .

Indeed, the antidictionary M de nes naturally a source S(M ) in the following way. Let A(M) be the automaton constructed in the previous section and that recognizes the language L(M ), and let us eliminate the sink states and edges going to them. Since there is no possibility of misunderstanding, we denote the resulting automaton by A(M) again. To avoid trivial cases we suppose that in this automaton all the states have at least one outgoing edge. Recall that, since our algorithms work on binary alphabets, all the states have at most two outgoing edges.

For any state of A(M) with only one outgoing edge we give to this edge probability 1. For any state of A(M) with two outgoing edge we give to these edges probability 1=2. This de nes a deterministic (or uni lar, cf. 2]) Markov source, denoted S(M ). A binary Markov source with this probability distribution is called an equilibrated source.

Remark that our compression algorithm is de ned exactly for all the words \emitted" by S(M ).

In what follows we suppose that the graph of the source S, i.e., the graph of automaton A(M) is strongly connected. The results that we prove can be extended to the general case by using standard techniques of Markov Chains (cf. 2] and 14]). Recall (cf. Theorem 6.4.2 of 2]) that the entropy H(S) of a deterministic markov source S is H(S) = n i;j=1 i i;j log 2 ( i;j ); where ( i;j ) is the stochastic matrix of S and ( 1 ; ; n ) is the stationary distribution of S.

We rst start with two preliminary lemmas.

Lemma 1 The entropy of an equilibrated source S is given by H(S) = i2D i where D is the set of all states that have two outgoing edges.

Proof. By de nition H(S) = n i;j=1 i i;j log 2 ( i;j ):

If i is a state with only one outgoing edge, by de nition this edge must have probability 1. Then j i i;j log 2 ( i;j ) reduces to i log 2 (1), that is equal to 0. Hence H(S) = i2D n j=1 i i;j log 2 ( i;j ):

Since from each i 2 D there are exactly two outgoing edges having each probability 1=2, one has

H(S) = i2D 2 i (1=2) log 2 (1=2) = i2D i as stated.
./ Lemma 2 Let w = a 1 a m be a word in L(M) and let q 1 q m+1 be the sequence of states in the path determined by w in A(M) starting from the initial state. The length of (w) is equal to the number of states q i , i = 1; : : :; m, that belong to D, where D is the set of all states that have two outgoing edges.

Proof. The statement is straightforward from the description of the compression algorithm and the implementation of the antidictionary with automaton A(M).

./ Next lemma reports a well known \large deviation" result (cf. Theorem 1.4.3 of 12]). Let q= q 1 ; q m be the sequence of m states of a path of A(M) and let L m;i (q) be the frequency of state q i in this sequence, i.e., L m;i (q) = m i =m, where m i is the number of occurrences of q i in the sequences q. Let also X m ( ) = f q j q has m states and max i jL m;i (q) i j g; where q represents a sequence of m states of a path in A(M).

In other words, X m ( ) is the set of all sequences of states representing path in A(M) that \deviate" at least of in at least one state q i from the theoretical frequency i . Lemma 3 For any > 0, the set X m ( ) satis es the equality lim 1 m log 2 Pr(X m ( )) = c( ); where c( ) is a positive constant depending on .

We now state and prove the main theorem of this section. We prove that for any the probability that the compression rate (v) = j (v)j=jvj of a string of length n is greater than H(S(M)) + , goes exponentially to zero. Hence, as a corollary, almost surely the compression rate of an in nite sequence emitted by S(M) reaches the entropy H(S(M)), that is the best possible result.

Let K m ( ) be the set of words w of length m such that the compression rate (v) = j (v)j=jvj is greater than H(S(M)) + . Theorem 8 For any > 0 there exist a real number r( ), 0 < r( ) < 1, and an integer m( ) such that for any m > m( ), Pr(K m ( )) r( ) m :

Proof. Let w be a word of length m in the language L(M) and let q 1 ; ; q m+1 be the sequence of states in the path determined by w in A(M) starting from the initial state. Let q= (q 1 ; ; q m ) be the sequence of the rst m states. We know, by Lemma 2, that the length of (w) is equal to the number of states q i , i = 1 m, in q that belong to D, where D is the set of all states having two outgoing edges.

If w belog to K m ( ), i.e., if the compression rate (v) = j (v)j=jvj is greater than H(S(M)) + , then there must exists an index j such that L m;j (q) > j + =d, where d is the cardinality of the set D. In fact, if for all j, L m;j (q) j + =jDj then, by de nitions and by Lemma 1, (v) = j2D L m;j (q) j2D j + = H(S(M)) + ; a contradiction. Therefore the sequence of states q belongs to X m ( =d).

Hence Pr(K m ( )) Pr(X m ( =d)). By Lemma 3, there exists an integer m( ) such that for any m > m( ) one has 1 m log 2 Pr(X m ( d )) 1 2 c( d ): Then Pr(K m ( )) 2 (1=2)c( =d)m . If we set r( ) = 2 (1=2)c( =d) , the statement of the theorem follows.

./

Corollary 1 The compression rate (x) of an in nite sequence x emitted by the source S(M) reaches the entropy H(S(M)) almost surely.

How to build Antidictionaries

In practical applications the antidictionary is not a priori given but it must be derived either from the text to be compressed or from a family of texts belonging to the same source to which the text to be compressed is supposed to belong. There exist several criteria to build e cient antidictionaries that depend on di erent aspects or parameters that one wishes to optimize in the compression process. Each criterium gives rise to di erent algorithms and implementations.

We present a simple construction to build nite antidictionaries. It is the base on which several variations are developed. It can be used to build antidictionaries for xed sources. In this case our scheme can be considered as a compressor generator (compressor compiler). In the design of a compressor generator, or compressor compiler, statistic considerations play an important role, as discussed in Section 6 (cf. 11]).

Algorithm Build-AD below builds the set of minimal forbidden words of length k (k > 0) of the word w. It takes as input an automaton accepting the words that have the same factors of length k (or less) than w, i.e., accepting the language L = fx 2 f0; 1g j (u 2 F (x) and juj k) ) u 2 F (w)g:

The preprocessing of the automaton is done by the algorithm Build-Fact whose central operation is described by the function Next. The automaton is represented by both a trie and its failure function f . If p is a node of the trie associated with the word av, v 2 f0; 1g and a 2 f0; 1g, f (p) is the node associated with v. This is a standard technique used in the construction of su x trees (see 7] for example). It is used here in algorithm Build-AD (line 4) to test the minimality of forbidden words according to the equality 2.

Build-Fact (word w 2 f0; 1g , integer k > 0) (p; a) q; 9.

if (p = i) f (q) i; else f (q) Next(f(p); a; k);

return q;

Build-AD (trie (Q; i; Q; ), function f , integer k > 0) 1. T ;; 0 ; 2. for each p 2 Q, 0 < level (p) < k, in width-rst order 3.

for a 0 then 1 4.

if (p; a) unde ned and (f(p); a) de ned 5. q new state; T T fqg; 6. 0 (p; a) q;

7. Q Q n fstates of Q from which no 0 -path leads to T g 8. return trie (Q T; i; T; 0 );

The above construction gives rise to a static compression scheme in which we need to read twice the text: the rst time to construct the antidictionary M and the second time to encode the text.

Informally, the encoder sends a message z of the form (x; y; (n)) to the decoder, where x is a description of the antidictionary M , y is the text coded according to M , as described in Section 2, and (n) is the usual binary code of the length n of the text. The decoder rst reconstructs from x the antidictionary and then decodes y according to the algorithm in Section 2. We can choose the length k of the longest minimal forbidden word in the antidictionary such that, by coding the trie associated to M with standard techniques, one has that jxj = o(n). Since the compression rate is the size jzj of z divided by the length n of the text, we have that jzj=n = jyj=n + o(n). Assuming that for n and k large enough the source S(M ), as in Section 4, approximates the source of the text, then, by the results of Section 4, the compression rate is \optimal".

Example 1

Let w= a 1 a 2 be a binary in nite word that is periodic (i.e., there exists integer P > 0 such that for any index i the letter a i is equal to the letter a i+P ), and let w n be the pre x of w of length n.

We want to compress the word w n following our simple scheme informally described above. Since w has period P , then for any i > P , letter a i is uniquely determined by the P previous letters. Therefore, we de ne the antidictionary M = fua j u 2 F (w); juj = P 1; and ua = 2 F (w)g;

where F (w) is the language of all factors of w. Then it is easy to prove that for any pre x w n of w, the length of the text y coded using M is constantly equal to P . Hence the compression rate for w n is jzj=n

= O( (n)) = O(log 2 (n)),
which means that the method can achieve an exponential compression. It is possible to generalize the previous example to any binary in nite word, w= a 1 a 2 , that is ultimately periodic (i.e., there exist integers M > 0, P > 0 such that for any index i M the letter a i is equal to the letter a i+P ).

Example 2

This example is a bit more complex, and the compression rate is no more exponential in the size of the text.

We start with the classical recursive de nition of nite Fibonacci words f n (cf. 5]). Let f 1 = 0, f 2 = 01 and let f n+1 = f n f n 1 for n 2. In particular we have f 3 = 010, f 4 = 01001 and f 5 = 01001010. The in nite Fibonacci word f is the limit of the sequence of the nite Fibonacci words, i.e., the unique in nite word that have all the f n as pre xes. It is know that the length jf n j is the n-th bonacci number and, consequently, lim jf n j = (' n ) where ' 1:618 is the golden ratio. Let L(f) and L(f n ) be the factorial languages composed respectively by all factors of the Fibonacci in nite word f and of the nite Fibonacci word f n . It is known (cf. 16]) that any factor of f of length 4m contains as factors all factors of length m of the whole word f. In particular L(f n ) \ f0; 1g m = L(f) \ f0; 1g m for any m jf n j=4. Consequently, the minimal forbidden words of f up to length m are also the minimal forbidden words of f n up to length m for any m jf n j=4.

If we call g n to be the pre x of length jf n j 2 of f n for n 2, it is known (cf. Example 2 of 4]) that all the minimal forbidden words of L(f) are f1g 2i 1 j i 1g f0g 2i+1 0 j i 1g;

i.e., they are 11, 000, 10101, 00100100, .

We now compress the word f 2n following our simple scheme informally described above. We choose as length k of the longest minimal forbidden word the number k = jf n j. By previous observations M = (f1g 2i 1 j i 1g f0g 2i+1 0 j i 1g) \ f0; 1g k ; and consequently it is not di cult to prove that the size of a standard coding

x of the trie associated to M is x = O(jf n j) = O(' n ) = o(jf 2n j).

It is possible to prove that the size of the compressed version y of f 2n by using our algorithm with the antidictionary M is jyj = O(jf n j). Therefore the global compression rate is O(jf n j=jf 2n j) = O((1=') n ). This means that the compression ratio converges exponentially to zero as n goes up to in nity.

Improvements and experimental results

In the previous section we presented a static compression scheme in which we need to read twice the text. Starting from the static scheme, several variations and improvements can be proposed. These variations are all based on clever combinations of two elements that can be introduced in our model: a) statistic considerations, b) dynamic approaches.

These are classical features that are sometimes included in other data compression methods. Statistic considerations are used in the construction of antidictionaries. If a forbidden word is responsible of \erasing" few bits of the text in the compression algorithm of Section 2 and its \description" as an element of the antidictionary is \expensive" then the compression rate improves if it is not included in the antidictionary. On the contrary, one can introduce in the antidictionary a word that is not forbidden but that occurs very rarely in the text. In this case, the compression algorithm will produce some \mistakes". In order to have a lossless compression, the encoder must take account of such mistakes and must also send them to the decoder. Typical \mistakes" occur in the case of antidictionaries built for xed sources and in the dynamic approach. Even with mistakes, assuming that the mistakes are rare with respect to the longest word (length) of the antidictionary, our compression scheme preserves the synchronization property for xed sources.

In the dynamic approach we construct the antidictionary and we encode the text at the same time. The antidictionary is constructed (also with statistical consideration) by taking account of (a part of) the text previously read.

We have realized prototypes of the compression and decompression algorithms. They also implement the dynamic version of the method. They have been tested on the Calgary Corpus, and the next table reports the size of compressed les. The total size of compressed data is equivalent to most common compressors such as pkzip.

Conclusion and Generalizations

We have described DCA, a text compression method that uses some \negative" informations about the text, which are described in terms of antidictionaries.

The advantages of the scheme are: fast at decompressing data, it is similar to a compressor generator (compressor compiler) for xed sources, fast at compressing data for xed sources, it has a synchronization property in the case of nite antidictionaries that leads to parallel compression and to search engines on compressed data.

We are considering several generalizations:

compressor scheme and implementationof antidictionaries on more general alphabets, the use of lossy compression especially to deal with images, the combination of DCA with other compression scheme. For instance using both dictionaries and antidictionaries like positive and negative sets of examples as in Learning Theory, the design of chips dedicated to xed sources.

Figure 1 :

 1 Figure 1: Trie of the factor code f000; 10101; 11g. Squares represent terminal states.

Figure 2 :

 2 Figure 2: Automaton accepting the words that avoid the set f000; 10101; 11g. Squares represent non-terminal states (sink states).

  L-automaton runs in time O(jQj jAj) on input T = (Q; A; i; T; 0 ) if transition functions are implemented by transition matrices. Proof. If transition functions and 0 are implemented by transition matrices, access to or de nition of (p; a) or 0 (p; a) (p state, a 2 A) are realized in constant amount of time. The result follows immediately.

De nition 3 A deterministic nite automaton A is local if there exists an integer n such that any words of length n is synchronizing. Automaton A is also called n-local.

Acknowledgements We thanks F.M. Dekking for useful discussions.