Text Compression Using Antidictionaries^{∗}

M. Crochemore^{†}, F. Mignosi^{‡}, A. Restivo^{‡}, S. Salemi^{‡}

June 10, 1998

Abstract

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 fixed 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.

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

1 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 {0, 1} and let AD be an antidictionary for w. By reading the text w from left to right, if at a certain moment the current prefix v of the text admits as suffix a word u′ such that u = u′x ∈ AD with x ∈ {0, 1}, 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 ≠ x. In other 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 prefix v of w already decompressed.

∗Web page at URL http://www-igm.univ-mlv.fr/∼mac/DCA.html

†Institut Gaspard-Monge

‡Università di Palermo

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 finite 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′x, x ∈ {0, 1}, in AD such that u′ is a suffix of v? In the case of positive answer the output should also include the letter y defined by y ≠ x. One of the main features of our method is that we are able to implement efficiently finite antidictionaries in terms of finite automata. This leads to efficient and fast compression and decompression algorithms, which can be realized by sequential transducers (generalized sequential machines). This is especially relevant for fixed 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 finite 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 prefix 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 efficient parallel compression algorithms.

The paper is organized as follows.

In Section 2 we give the definition 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 finite antidictionaries that allows to answer in efficient way to the queries needed by our compression and decompression algorithms; we show how to implement it given a finite 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).

2 Forbidden Words and the Basic Algorithms

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

For instance, if w = 01001010010

F (w) = {ε, 0, 1, 00, 01, 10, 001, 010, 100, 101, …}

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 finite as well infinite.

For instance, if w = 01001010010 the words 11, 000, and 10101 are forbidden and the set AD = {000, 10101, 11} 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 prefix of w. If there exists a word u = u′x, x ∈ {0, 1}, in the antidictionary AD such that u′ is a suffix of v, then surely the letter following v cannot be x, i.e., the next letter is y, y ≠ 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 first 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 ∈ {0, 1}^{∗})

1. v ← ε; γ ← ε;

2. for a ← first to last letter of w

3. v ← v.a;

4. if for any suffix u′ of v, u′0, u′1 ∉ AD

5. γ ← γ.a;

6. return (|v|, γ);

As an example, let us run the algorithm Encoder on the string w = 01001010010 with the antidictionary AD = {000, 10101, 11}. The steps of the treatment are described in the next array by the current values of the prefix 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 ∈ AD
v_{3} = 010  γ(w) = 01
v_{4} = 0100  γ(w) = 010 u = 000 ∈ AD
v_{5} = 01001  γ(w) = 010 u = 11 ∈ AD

           v_{6} = 010010  γ(w) = 010
           v_{7} = 0100101  γ(w) = 0101 u = 11 ∈ AD
           v_{8} = 01001010  γ(w) = 0101 u = 10101 ∈ AD
           v_{9} = 010010100  γ(w) = 0101 u = 000 ∈ AD
           v_{10} = 0100101001 γ(w) = 0101 u = 11 ∈ 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 γ′(w) = (|w|, γ(w)). In this case we can reconstruct the original word w from both γ′(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 prefix v of w already decompressed. If there exists a word u = u′x, x ∈ {0, 1}, in the antidictionary AD such that u′ is a suffix of v, then, the output letter is y, y ≠ x. Otherwise, the next letter is read from the input γ.

Decoder (anti-dictionary AD, integer n, word γ ∈ {0, 1}^{∗})

1. v ← ε;

2. while |v| < n

3. if for some u′ suffix of v and x ∈ {0, 1}, u′x ∈ AD 4. v ← v · ¬x;

5. else

6. b ← next letter of γ;

7. v ← v · b;

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′x, x ∈ {0, 1}, in AD such that u′ is a suffix of v? In case of a positive answer the output should also include the letter y defined by y ≠ 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 |w|, 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′x, x ∈ {0, 1} in the antidictionary such that u′ 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.

3 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 satisfies the following property: for any words, u, v, uv ∈ L ⇒ u ∈ L and v ∈ L.

The complement language L^{c} = A^{∗} \L 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 ∈ A^{∗} is forbidden for the factorial language L if v ∉ 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^{∗} \ 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^{∗} \ 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 ∈ Rat(A^{∗}) iff MF (L) ∈ Rat(A^{∗}).

The set MF (L) is an anti-factorial language or a factor code, which means that it satisfies: ∀u, v ∈ MF (L) u ≠ v ⟹ u is not a factor of v, property that comes from the minimality of words of MF (L).

We introduce a few more definitions.

Definition 1 A word v ∈ A^{∗} avoids the set M, M ⊆ A^{∗}, if no word of M is a factor of v, (i.e., if v ∉ A^{∗}MA^{∗}). A language L avoids M if every word of L avoid M.

From the definition 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 finite anti-factorial language M we associate the finite 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 automaton A(M) is the tuple (Q, A, i, T, F) where

[figure: 1; 2; 3; 0; 4; 5; 6; 7; 8; 9; 0; 0; 0; 1; 0; 1; 0; 1; 1]

Figure 1: Trie of the factor code {000, 10101, 11}. Squares represent terminal states.

• the set Q of states is {w | w is a prefix of a word in M},

• A is the current alphabet,

• the initial state i is the empty word ε,

• the set T of terminal states is Q \ 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} defined by:

• F_{1} = {(u, a, ua) | ua ∈ Q, a ∈ A} (forward edges or tree edges),

• F_{2} = {(u, a, v) | u ∈ Q \ M, a ∈ A, ua ∉ Q, v longest suffix of ua in Q} (backward edges),

• F_{3} = {(u, a, u) | u ∈ M, a ∈ A} (loops on sink states).

The transition function defined 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 definition of A(M) turns into the algorithm below, called Lautomaton, that builds the automaton from a finite 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, δ′).

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 defined on states of T as follows. States of the trie T are identified with the prefixes of words in M. For a state au (a ∈ A, u ∈ A^{∗}), f(au) is δ′(i, u), quantity that may happen to be u itself. Note that f(i) is undefined, which justifies a specific treatment of the initial state in the algorithm.

       [figure: 1; 2; 3; 0; 4; 5; 6; 7; 8; 9; 0; 0; 0; 1; 0; 1; 0; 1; 1; 1; 1; 0; 0; 0,1; 0,1; 0,1]

Figure 2: Automaton accepting the words that avoid the set {000, 10101, 11}. Squares represent non-terminal states (sink states).

L-automaton (trie T = (Q, A, i, T, δ′))

1. for each a ∈ A

2. if δ′(i, a) defined

3. set δ(i, a) = δ′(i, a);

4. set f(δ(i, a)) = i;

5. else

6. set δ(i, a) = i;

7. for each state p ∈ Q \ {i} in width-first search and each a ∈ A 8. if δ′(p, a) defined

9. set δ(p, a) = δ′(p, a);

10. set f(δ(p, a)) = δ(f(p), a);

11. else if p ∉ T

12. set δ(p, a) = δ(f(p), a);

13. else

14. set δ(p, a) = p;

15. return (Q, A, i, Q \ T, δ);

Example. Figure 1 displays the trie that accepts M = {000, 10101, 11}. 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.

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 ∈ A^{+} and p = δ(i, u). A simple induction on |u| shows that the word corresponding to f(p) is the longest proper suffix of u that is a prefix of some word in M. This notion comes up in the definition 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 definition of A(M). ▷◁

Theorem 3 Algorithm L-automaton runs in time O(|Q|×|A|) on input T = (Q, A, i, T, δ′) if transition functions are implemented by transition matrices.

Proof. If transition functions δ and δ′ are implemented by transition matrices, access to or definition of δ(p, a) or δ′(p, a) (p state, a ∈ A) are realized in constant amount of time. The result follows immediately. ▷◁

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 (finite-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′(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 ∈ Q_{1}, define p(q) = (q, q_{1}, …, q_{r}) as the unique path in the tranducer for which q_{j} ∈ Q_{1} for j < r and q_{r} ∈ Q_{2}.

Given an input word v = b_{1}b_{2} … b_{m}, there exists in B′(M) a unique path i, q_{1}, …, q_{m′} such that q_{m′−1} ∈ Q_{2} and the transition from q_{m′−1} to q′_{m} correspond to the input letter b_{m}

If q_{m′} ∈ Q_{2}, then the output word corresponding to this path in B′(M) is the unique word w such that γ(w) = v.

If q_{m′} ∈ Q_{1}, then we can stop the run of the decoding algorithm realized by B′(M) in any state q ∈ p(q_{m′}), and, for different states, we obtain different 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′(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 finite case, the construction of automata and transducers from a fixed 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 from finite antidictionaries, as described above. This property also “characterizes” in some sense finite antidictionaries. This property is a classical one and it is of fundamental importance in practical applications.

We start with a definition.

Definition 2 Given a deterministic finite 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′_{1}, a_{1}, q′_{2}) ⋯ (q′_{n}, a_{n}, q′_{n+1}) of length n, then the two ending states q_{n+1} and q′_{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′ = wv that has w as prefix is also synchronizing for A.

Definition 3 A deterministic finite 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.

Remark that if A is n-local then it is m-local for any m ≥ n.

Given a finite 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 finite 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′_{1}, a_{1}, q′_{2}) ⋯ (q′_{n−1}, a_{n−1}, q′_{n}) of length n − 1 labeled by u. We have to prove that the two ending states q_{n} and q′_{n} are equal. Recall that states of A are words, and, more precisely they are the proper prefixes of words in M. A simple induction on i, 1 ≤ i ≤ n shows that q_{i} (respectively q′_{i}) “is” the longest suffix of the word q_{1}a_{1} ⋯ a_{i} (respectively q′_{1}a_{1} ⋯ a_{i}) that is also a “state”, i.e., a proper prefix of a word in M. Hence q_{n} (respectively q′_{n}) is the longest suffix of the word q_{1}u (respectively q′_{1}u) that is also a proper prefix of a word in M. Since all proper prefixes of words in M have length at most n − 1, both q_{n} and q′_{n} have length at most n−1. Since u has length n−1, both they are the longest suffix of u that is also a proper prefix 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 finite 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 finite 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} ∈ L(M) with |u| = 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 definitions 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 efficiency of the final 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.

4 Efficiency

In this section we evaluate the efficiency of our compression algorithm relatively to a source corresponding to the finite antidictionary M.

Indeed, the antidictionary M defines 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 defines a deterministic (or unifilar, 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 defined 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) = −Σ_{i,j=1}^{n}μ_{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 first start with two preliminary lemmas.

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

Proof. By definition

H(S) = −Σ_{i,j=1}^{n}μ_{i}γ_{i,j} log_{2}(γ_{i,j}).

If i is a state with only one outgoing edge, by definition 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) = −Σ_{i∈D}Σ_{j=1}^{n}μ_{i}γ_{i,j} log_{2}(γ_{i,j}).

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

H(S) = −Σ_{i∈D}2μ_{i}(1/2) log_{2}(1/2) = Σ_{i∈D}μ_{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}(ϵ) = { q | q has m states and max_{i} |L_{m,i}(q) − μ_{i}| ≥ ϵ},

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}(ϵ) satisfies the equality

lim\frac{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) = |γ(v)|/|v| 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 infinite 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) = |γ(v)|/|v| is greater than H(S(M)) + ϵ.

Theorem 8 For any ϵ > 0 there exist a real number r(ϵ), 0 < r(ϵ) < 1, and an integer \overline{m}(ϵ) such that for any m > \overline{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 first 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) = |γ(v)|/|v| 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} + ϵ/|D| then, by definitions and by Lemma 1,

τ(v) = Σ_{j∈D}L_{m,j}(q) ≤ Σ_{j∈D}μ_{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 \overline{m}(ϵ) such that for any m > \overline{m}(ϵ) one has

\frac{1}{m}log_{2}Pr(X_{m}(\frac{ϵ}{d})) ≤ −\frac{1}{2}c(\frac{ϵ}{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 infinite sequence x emitted by the source S(M) reaches the entropy H(S(M)) almost surely.

5 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 efficient antidictionaries that depend on different aspects or parameters that one wishes to optimize in the compression process. Each criterium gives rise to different algorithms and implementations.

We present a simple construction to build finite antidictionaries. It is the base on which several variations are developed. It can be used to build antidictionaries for fixed 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 = {x ∈ {0, 1}^{∗} | (u ∈ F (x) and |u| ≤ k) ⇒ u ∈ F (w)}.

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 ∈ {0, 1}^{∗} and a ∈ {0, 1}, f(p) is the node associated with v. This is a standard technique used in the construction of suffix 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 ∈ {0, 1}^{∗}, integer k > 0)

1. i ← new state; Q ← {i};

2. level(i) ← 0;

3. p ← i;

4. while not end of string w

5. a ← next letter of w;

6. p ← Next(p, a, k);

7. return trie (Q, i, Q, δ), function f;

Next (state p, letter a, integer k > 0)

1. if δ(p, a) defined

2. return δ(p, a);

3. else if level(p) = k

4. return Next(f(p), a, k);

5. else

6. q ← new state; Q ← Q ∪ {q};

7. level(q) ← level(p) + 1;

8. δ(p, a) ← q;

9. if (p = i) f(q) ← i; else f(q) ← Next(f(p), a, k);

10. return q; Build-AD (trie (Q, i, Q, δ), function f, integer k > 0)

1. T ← ∅; δ′ ← δ;

2. for each p ∈ Q, 0 < level(p) < k, in width-first order 3. for a ← 0 then 1

4. if δ(p, a) undefined and δ(f(p), a) defined

5. q ← new state; T ← T ∪ {q};

6. δ′(p, a) ← q;

7. Q ← Q \ {states of Q from which no δ′-path leads to T } 8. return trie (Q ∪ T, i, T, δ′);

The above construction gives rise to a static compression scheme in which we need to read twice the text: the first 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 first 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 |x| = o(n). Since the compression rate is the size |z| of z divided by the length n of the text, we have that |z|/n = |y|/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 infinite 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 prefix 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 define the antidictionary

M = {ua | u ∈ F (w), |u| = P − 1, and ua ∉ F (w)},

where F (w) is the language of all factors of w. Then it is easy to prove that for any prefix 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 |z|/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 infinite 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 definition of finite 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 infinite Fibonacci word f is the limit of the sequence of the finite Fibonacci words, i.e., the unique infinite word that have all the f_{n} as prefixes. It is know that the length |f_{n}| is the n-th fibonacci number and, consequently, lim |f_{n}| = Θ(φ^{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 infinite word f and of the finite 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}) ∩ {0, 1}^{m} = L(f) ∩ {0, 1}^{m} for any m ≤ |f_{n}|/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 ≤ |f_{n}|/4.

If we call g_{n} to be the prefix of length |f_{n}| − 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

{1g_{2i}1 | i ≥ 1} ∪ {0g_{2i+1}0 | i ≥ 1},

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 = |f_{n}|. By previous observations

M = ({1g_{2i}1 | i ≥ 1} ∪ {0g_{2i+1}0 | i ≥ 1}) ∩ {0, 1}^{k},

and consequently it is not difficult to prove that the size of a standard coding x of the trie associated to M is x = O(|f_{n}|) = O(φ^{n}) = o(|f_{2n}|).

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 |y| = O(|f_{n}|).

Therefore the global compression rate is O(|f_{n}|/|f_{2n}|) = O((1/φ)^{n}). This means that the compression ratio converges exponentially to zero as n goes up to infinity.

6 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 fixed 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 fixed 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 files. The total size of compressed data is equivalent to most common compressors such as pkzip.

File compressed size
bib  35535
book1  295966
book2  214476
geo  79633
news  161004
obj1  13094
obj2  111295
paper1  21058
paper2  32282
pic  70240
progc  15736
progl  20092
progp  13988
trans  22695
Total  1,107094

7 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 fixed sources,

• fast at compressing data for fixed sources,

• it has a synchronization property in the case of finite antidictionaries that leads to parallel compression and to search engines on compressed data.

We are considering several generalizations:

• compressor scheme and implementation of 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 fixed sources.

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

References

[1] A. V. Aho and M. J. Corasick. Efficient string matching: an aid to bibliographic search. Comm. ACM 18:6 (1975) 333–340.

[2] R. Ash. Information Theory. Tracts in mathematics, Interscience Publishers, J. Wiley & Sons, 1985.

[3] M. P. Béal. Codage Symbolique. Masson, 1993.

[4] M.-P. Béal, F. Mignosi, and A. Restivo. Minimal Forbidden Words and Symbolic Dynamics. in (STACS’96, C. Puech and R. Reischuk, eds., LNCS 1046, Springer, 1996) 555–566.

[5] J. Berstel. Fibonacci Words — a Survey. in (The Book of L, G. Rozenberg, A. Salomaa, eds., Springer Verlag, 1986).

[6] T. C. Bell, J. G. Cleary, I. H. Witten. Text Compression. Prentice Hall, 1990.

[7] M. Crochemore, C. Hancart. Automata for matching patterns. in (Handbook of Formal Languages, G. Rozenberg, A. Salomaa, eds.”, Springer-Verlag”, 1997, Volume 2, Linear Modeling: Background and Application) Chapter 9, 399–462.

[8] M. Crochemore, F. Mignosi and A. Restivo. Minimal Forbidden Words and Factor Automata. Accepted at the conference MFCS’98.

[9] M. Crochemore, F. Mignosi and A. Restivo. Automata and Forbidden Words. Technical Report, IGM 98-5, Institut Gaspard-Monge, 1998. Submitted to Information Processing Letters.

[10] M. Crochemore, F. Mignosi, A. Restivo and S. Salemi. Search in Compressed Data. in preparation.

[11] M. Crochemore, F. Mignosi, A. Restivo and S. Salemi. A Compressor Compiler. in preparation.

[12] R. S. Ellis. Entropy, Large Deviations, and Statistical Mechanics. Springer Verlag, 1985.

[13] J. Gailly. Frequently Asked Questions in data compression, Internet. Avail-

able at http://www.landfield.com/faqs/compression-faq/part1/preamble.html or
ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/.

[14] J. G. Kemeny and J. L. Snell. Finite Markov Chains. Van Nostrand Reinhold, 1960.

[15] R. Krichevsky. Universal Compression and Retrieval. Kluver Academic Publishers, 1994.

[16] M. Morse and G. Hedlund. Symbolic Dynamics II: Sturmian trajectoires. Amer. J. Math. 62, 1-40, 1940.

[17] M. Nelson and J. Gailly. The Data Compression Book. 2nd edition. M&T Books, New York, NY 1996.

[18] C. Shannon. Prediction and entropy of printed english. Bell System Technical J., 50-64, January, 1951.

[19] J. A. Storer. Data Compression: Methods and Theory. Computer Science Press, Rockville, MD, 1988.

[20] I. H. Witten, A. Moffat and T. C. Bell. Managing Gigabytes. Van Nostrand Reinhold, 1994.