Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Laura Giambruno

Alessio Langiu
email: alangiu@math.unipa.it

Filippo Mignosi
email: filippo.mignosi@di.univaq.it

Antonio Restivo
email: restivo]@math.unipa.it

Dictionary-Symbolwise Flexible Parsing

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In [START_REF] Matias Nd S"uleyman | On the optimality of parsing in dynamic dictionary based data compression[END_REF] Mathias and Shainalp gave a linear time optimal parsing algorithm in the case of dictionary compression where the dictionary is prefix closed and the cost of encoding dictionary pointer is constant. They called their parsing algorithm Flexible Parsing. The basic idea of one-step-lookahead parsing that is at the base of flexible parsing was firstly used to our best knowledge in [START_REF] Hartman | Optimal parsing of strings[END_REF] in the case of dictionary compression where the dictionary is prefix closed and the cost of encoding dictionary pointer is constant and the dictionary is static. A first intuition, not fully exploited, that this idea could be successful used in the case of dynamic dictionaries was given in [START_REF] Horspool | The effect of non-greedy parsing in ziv-lempel compression methods[END_REF] and also in [START_REF] Young | On-line optimal parsing in dictionary-based coding adaptive[END_REF], where it was called parsing MTPL (maximum two-phrase-length parsing).

Optimal parsing algorithms are rare and linear time optimal parsing results are rather rare. We can only also cite the fact that greedy parsing is optimal and linear for LZ77 alike dictionaries and constant cost dictionary pointers (cf. [START_REF] Storer | Data compression via textural substitution[END_REF]) and its generalization to suffix closed dictionaries and constant cost dictionary pointers (cf. [START_REF] Cohn | Parsing with prefix and suffix dictionaries[END_REF]) later used also in [START_REF] Young | On-line optimal parsing in dictionary-based coding adaptive[END_REF].

In this paper we consider the case of a free mixture of a dictionary compressor and a symbolwise compressor and we extend, in some sense, the result of Mathias and Shainalp. We have indeed an optimal parsing algorithm in the case of dictionary-symbolwise compression where the dictionary is prefix closed and the cost of encoding dictionary pointer is variable and the symbolwise is any classical one that works in linear time. Our algorithm works under the assumption that a special graph that will be described in next section is well defined. Even in the case where this condition is not satisfied it is possible to use the same method to obtain almost optimal parses. In particular, when the dictionary is LZ78-alike our algorithm can be implemented in linear time and when the dictionary is LZ77-alike our algorithm can be implemented in time O(n log(n)).

The study of free mixtures of two compressor is quite involved and it represents a new theoretical challenge. Free mixture have been implicitly or explicitly using for a long time in many fast and effective compressors such as gzip (cf. [6]), PkZip (cf. [START_REF] Katz | Pkzip archiving tool[END_REF]) and Rolz algorithms (cf. [START_REF] Martelock | Rzm order-1 rolz compressor[END_REF]). For a quick look to compression performance on texts see Mahony challenge's page (cf. [START_REF] Mahoney | Large text compression benchmark[END_REF]).

In our case, using a simple static Huffman coding as symbolwise compressor we improved the compression ratio of the Flexible Parsing of 6% -4% on texts such as prefixes of English Wikipedia data base with a negligible slow down in compressing and decompressing time. The slow down comes from the fact that we have to add to the dictionary compression and decompression time the Huffman coding and decoding time. The same experimental result holds in general when the dictionary is LZ78-alike. Indeed a dictionary-symbolwise compressor when the dictionary is LZ78-alike and the symbolwise is a simple Huffman coding with optimal parsing has a compression ratio that is is more or less 5% better than the compression ratio of a pure pure LZ78-alike dictionary compressor that uses an optimal parsing. In general smaller is the file greater is the gain. The 5% refers to text sizes of around 20 megabytes. Moreover, preliminary results show that using more powerful but still fast symbolwise compressor, such as an arithmetic encoder of order 1, there is a further 10% gain in compression ratio.

When the dictionary is, instead, LZ77-alike the gain in compression when we use a dictionarysymbolwise compressor with optimal parsing and Huffman coding with respect to a pure dictionary compressor with optimal parsing reduces down to more or less 3%. The compression ratio seems to be sensibly better than in the case of LZ78-alike dictionaries when we use, in both cases, unbounded dictionaries. The distance, however, between the compression ratio of dictionary-symbolwise compressors that use LZ78-alike dictionaries and the ones that use LZ77-alike dictionaries is much smaller, following our preliminary results, when we use an arithmetic encoder of order 1 instead than an Huffman encoding.

We have experimental evidence that many of the most relevant commercial compressors use, following our definition, optimal parsing in the dictionary-symbolwise case where the dictionary is LZ77alike. The method described in this paper therefore has as a consequence the possibility of optimizing the trade-off between some of the main parameters used for evaluating commercial compressors, such as compression ratio, decompression time, compression time and so on. So, why linear time optimal parsing algorithms are rather rare? Classically (cf. [START_REF] Schuegraf | A comparison of algorithms for data base compression by use of fragments as language elements[END_REF]), for static dictionaries it is possible to associate to any dictionary algorithm A and to any text T a weighted graph G A,T such that there is a bijection between optimal parsings and minimal paths in this graph. The extension of this approach to dynamical dictionaries has been firstly studied, to our best knowledge, in [START_REF] Della Penna | Optimal parsing in dictionary-symbolwise data compression schemes[END_REF] and it has also been later used in [START_REF] Ferragina | On the bit-complexity of lempel-ziv compression[END_REF]. More details will be given in next sections. The graph G A,T is a Directed Acyclic Graph and it is possible to find a minimal path in linear time with respect to the size of it (cf. [START_REF] Thomas H Cormen | Introduction to Algorithms[END_REF]). Unfortunately the size of the graph can be quadratic in the size of the text and this approach was not recommended in [START_REF] Schuegraf | A comparison of algorithms for data base compression by use of fragments as language elements[END_REF], because it is too time consuming. From a philosophical point of view, the graph G A,T represents a mathematical modeling of the optimal parsing problem. Thus, finding an optimal parsing in linear time corresponds to discovering a strategy for using only a subgraph of linear size.

Indeed, in order to get over the quadratic worst case problem, there are many different approaches and many papers deal with optimal parsing in dictionary compressions. For instance the reader can see [START_REF] Bell | The relationship between greedy parsing and symbolwise text compression[END_REF][START_REF] Cohn | Parsing with prefix and suffix dictionaries[END_REF][START_REF] Ferragina | On the bit-complexity of lempel-ziv compression[END_REF][START_REF] Hartman | Optimal parsing of strings[END_REF][START_REF] Katajainen | An approximation algorithm for space-optimal encoding of a text[END_REF][START_REF] Katajainen | An analysis of the longest match and the greedy heuristics in text encoding[END_REF][START_REF] Young | On-line optimal parsing in dictionary-based coding adaptive[END_REF][START_REF] Shmuel | Efficient optimal recompression[END_REF][START_REF] Matias | The effect of flexible parsing for dynamic dictionarybased data compression[END_REF][START_REF] Matias Nd S"uleyman | On the optimality of parsing in dynamic dictionary based data compression[END_REF][START_REF] Storer | Data compression via textural substitution[END_REF][START_REF] Wagner | Common phrases and minimum-space text storage[END_REF]. Among them, we stress [START_REF] Ferragina | On the bit-complexity of lempel-ziv compression[END_REF] where it is shown that a minimal path can be obtained by using a subgraph of G A,T of size O(n log(n)), in the LZ77 case under some natural assumptions on the cost function, by exploiting the discreteness of the cost functions.

In this paper we use a similar strategy, i.e. we consider static or dynamical dictionaries, following the approach of [START_REF] Della Penna | Optimal parsing in dictionary-symbolwise data compression schemes[END_REF] and we discover a "small" subgraph of G A,T that is linear in the size of the text for LZ78-alike dictionaries and O(n log(n)) for LZ77-alike dictionaries. This "small" subgraph is such that any minimal path in it is also a minimal path in G A,T . Our algorithm has therefore two advantages with respect to the classical Flexible Parsing. First, it can handle variable cost of dictionary pointers. This fact allows to extend the range of application of Flexible Parsing to almost all LZ78-alike known algorithms of our extension. Secondly, our Dictionary-Symbolwise Flexible Parsing implemented in the case of LZ77 dictionary gives as particular case when the symbolwise is not in use, a result that is similar to the one presented in [START_REF] Ferragina | On the bit-complexity of lempel-ziv compression[END_REF] that has O(n log(n)) complexity, using a completely different and simpler subgraph and a simpler data structure. Last but not least our algorithm allows to couple classical LZ-alike algorithms with several symbolwise algorithms to obtain dictionary-symbolwise algorithms that achieve better compression with prove of optimality.

In Section 2 we recall some literature notions about dictionary and dictionary-symbolwise compression algorithms and we define the graph G A,T . In Section 3 we formalize the definition of optimal algorithm and optimal parsing and extend them to the dictionary-symbolwise domain. In Section 4 we present the Dictionary-Symbolwise Flexible Parsing, a parsing algorithm that extends in some sense the Flexible Parsing (cf. [START_REF] Matias Nd S"uleyman | On the optimality of parsing in dynamic dictionary based data compression[END_REF]). We prove its optimality by showing that it corresponds to a shortest path in the full graph, and in Section 5 we describe some data structures that can be used for our algorithm in the two main cases of LZ78-alike and LZ77-alike dictionaries together the time analysis. In Section 6 we state a theoretical result that shows that dictionary-symbolwise compressors can be asymptotically better than dictionary-alone compressors when the dictionary is LZ78 based or when it is LZ77 based. In Section 7 we present some experimental results that show the effectiveness of the dictionary-symbolwise approach. Finally, Section 8 reports our conclusions.

Preliminaries

In [START_REF] Bell | The relationship between greedy parsing and symbolwise text compression[END_REF] it is possible to find a survey on Dictionary methods and Symbolwise methods and a description of deep relationships among them (see also [START_REF] John | Text compression[END_REF][START_REF] Crochemore | Pattern-matching and text-compression algorithms[END_REF]).

A dictionary compression algorithm, as noticed in [START_REF] Bell | The relationship between greedy parsing and symbolwise text compression[END_REF], can be fully described by:

1. The dictionary description, i.e. a static collection of phrases or a complete algorithmic description on how the dynamic dictionary is built and updated. 2. The encoding of dictionary pointers in the compressed data. 3. The parsing method, i.e. the algorithm that splits the uncompressed data in dictionary phrases.

We notice that any of the above 3 specifics can all depend on each other, i.e. they can be mutually interdependent.

It is possible to associate a directed weighted graph G A,T = (V, E, L) to any compression algorithm A, any text T = a 1 a 2 a 3 • • • a n and any cost function C : E → R + in the following way.

The set of vertices is V = {0, 1, . . . , n}, where vertex i corresponds to a i , i.e. the i-th character in the text T , for 1 ≤ i ≤ n and vertex 0 correspond to the position at the beginning of the text, before any characters. The empty word ǫ is associated to vertex 0 that is also called the origin of the graph.

The set of directed edges is E = {(p, q) ⊂ (V × V ) | p < q and ∃ w = T [p + 1 : q] ∈ D p }, where T [p + 1 : q] = a p+1 a p+2 • • • a q and D p is the dictionary relative to the processing step p-th, i.e. the step in which the algorithm either has processed the input text up to character a p , for 0 < p, or it has to begin, for p = 0. For each edge (p, q) in E, we say that (p, q) is associated to the dictionary phrase w = T [p + 1 : q] = a p+1 • • • a q ∈ D p . In the case of static dictionary D i is constant along the algorithm steps, i.e.

D i = D j , ∀i, j = 0 • • • n.
L is the set of edge labels L p,q for every edge (p, q) ∈ E, where the label L p,q is defined as the cost of the edge (p, q) when the dictionary D p is in use, i.e. L p,q = C((p, q)). Practically speaking, the cost of an edge is usually set to be the length in bits of its representation in the output, i.e. the selected cost function associate to each edge a cost equal to the length of the encoded dictionary pointer that points out to the phrase in the dictionary that the edge is associated to. Let us notice that the cost of encoding pointers should be a total function, in order to have L p,q always defined for each edge of the graph. There are cases where the cost function is a partial function, i.e. L p,q is not defined for some p and q, and G A,T in such cases is not defined. In this case, one can assign special values, for instance +∞, to labels of edges for which cost function is undefined in order to build an usable graph. When L p,q is always defined for each edge of the graph we say that G A,T is well defined. Graph G A,T is not allways well defined and we refer to [START_REF] Della Penna | Optimal parsing in dictionary-symbolwise data compression schemes[END_REF] for further discussions on this subject.

Let us remember that the cost function can depend on the parsing if the encoding of dictionary pointers does. For example dictionary pointers could be encoded with Huffman code, as gzip does, and two pointers to the same phrase could have different costs at different time.

Given a compression algorithm A, we call cost of the encoded text the sum of all the edges labels in the path from 0 to n relative to the parsing of the algorithm. Fig. 1. Graph GA,T for the text T = abccacbbabbcbcbb, for the dictionary algorithm A with static dictionary D = {ab, cbb, ca, bcb, abc, c} and the cost function C as defined in the graph. The dictionary phrase associated to an edge is reported near the edge label within parenthesis.

Let a scheme of dictionary algorithms be a set of algorithms that share the first two specifics, i.e. (1) the dictionary description and (2) the encoding of dictionary pointers. A scheme does not necessarily contain all algorithms sharing the first two specifics. A parsing algorithm univocally identify a dictionary compression algorithm within a scheme, whenever it belongs to the scheme. Let us notice that the word scheme has been used by other authors with other related meaning.

The theory of Dictionary-Symbolwise compression algorithms started in [START_REF] Della Penna | Optimal parsing in dictionary-symbolwise data compression schemes[END_REF] improve and generalize previous results stated for dictionary algorithms and allows to obtain new ones. In what follow, we recall the fundamental notions of the Dictionary-Symbolwise theory.

A dictionary-symbolwise algorithm uses both dictionary and symbolwise compression. Such compressors parse the text as a free mixture of dictionary phrases and literal characters, which are substituted by the corresponding pointers or literal codes, respectively. Therefore, the description of a dictionary-symbolwise algorithm should also include the so called flag information, that is the technique used to distinguish the actual compression method (dictionary or symbolwise) used for each segment or factor of the parsed text. Often, as in the case of LZSS (cf. [START_REF] Storer | Data compression via textural substitution[END_REF]), an extra bit is added either to each pointer or encoded character to distinguish between them. Encoded information flag can require less (or more) space than one bit.

For instance, a dictionary-symbolwise compression algorithm with a fixed dictionary D = {ab, cbb, ca, bcb, abc} and the static symbolwise codeword assignment [a = 1, b = 2, c = 3] could compress the text abccacbbabbcbcbb as

F d 1F s 3F d 3F d 2F d 1F d 4F d 2,
where F d is the information flag for dictionary pointers and F s is the information flag for the symbolwise code.

More formally, a parsing of a text T in a dictionary-symbolwise algorithm is a pair (parse , F l) where parse is a sequence (u 1 , • • • , u s ) of words such that T = u 1 • • • u s and where F l is a boolean function that, for i = 1, . . . , s indicates whether the word u i has to be coded as a dictionary pointer or as a symbol. See Table 1 for an example of dictionary-symbolwise compression.

A dictionary-symbolwise compression algorithm is specified by: 1. The dictionary description. 2. The encoding of dictionary pointers. 3. The symbolwise encoding method. 4. The encoding of the flag information. 5. The parsing method.

We can naturally extend the definition of the graph associated to an algorithm for the dictionarysymbolwise case. Given a dictionary-symbolwise algorithm A, a text T and a cost function C defined

Input ab c ca cbb ab bcb cbb Output F d 1 Fs3 F d 3 F d 2 F d 1 F d 4 F d 2
Table 1. Example of compression for the text abccacbbabbcbcbb by a simple Dyctionary-Symbolwise algorithm that use D = {ab, cbb, ca, bcb, abc} as static dictionary, the identity as dictionary encoding and the mapping [a = 1, b = 2, c = 3] as symbolwise encoding. Graph GA,T for the text T = abccacbbabbcbcbb, for the dictionary-symbolwise algorithm A with static dictionary D = {ab, cbb, ca, bcb, abc, c} and cost function C as defined in the graph. The dictionary phrase or the symbol associated to an edge is reported near the edge label within parenthesis.

on edges, the graph G A,T = (V, E, L) is defined as follows. The vertexes set is

V = {0 • • • n}, with n = |T |. The set of directed edges E = E d E s , where E d = {(p, q) ⊂ (V × V ) | p < q -1, and ∃w = T [p+1 : q] ∈ D p }
is the set of dictionary edges and E s = {(q-1, q) | 0 < q ≤ n} is the set of symbolwise edges. L is the set of edge labels L p,q for every edge (p, q) ∈ E, where the label L p,q = C((p, q)). Let us notice that the cost function C hereby used has to include the cost of the flag information to each edge, i.e. either C(p, q) is equal to the cost of the encoding of F d + the cost of the encoded dictionary phrase w ∈ D p associated to the edge (p, q) if (p, q) ∈ E d or C(p, q) is equal to ( the cost of encoded F s ) + ( the cost of the encoded symbol a q ) if (p, q) ∈ E s . Moreover, since E d does not contain edges of length one by definition, G A,T = (V, E, L) is not a multigraph. Since this graph approach can be extended to multigraph, with a overhead of formalism, one can relax the p < q -1 constrain in the definition of E d to p ≤ q -1. All the results we will state in this paper, naturally extend to the multigraph case. We call dictionary-symbolwise scheme a set of algorithms having in common the same first four specifics (i.e. they differ one each other for just the parsing methods). A scheme does not need to contain all algorithms having the same first four specifics. We notice that any of the specifics from 1 to 5 above can depend on all others, i.e. they can be mutually interdependent. Fixed a dictionarysymbolwise scheme, whenever the specifics of the parsing method are given, exactly one algorithm is completely described. Notice that the word scheme has been used by other authors with other related meaning. For us the meaning is rigorous.

On Optimality

In this section we recall some background notions for the reader to understand the algorithms given in the rest of the paper. However, we assume that the reader is familiar with LZ alike dictionary encoding and with some simple statistical encodings such as the Huffman encoding.

Definition 1. Fixed a dictionary description, a cost function C and a text T , a dictionary (dictionarysymbolwise) algorithm is optimal within a set of algorithms if the cost of the encoded text is minimal with respect to all others algorithms in the same set. The parsing of an optimal algorithm is called optimal within the same set.

When the length in bit of the encoded dictionary pointers is used as cost function, the previous definition of optimality is equivalent to the classical well known definition of bit-optimality for dictionary algorithm.

Notice that the above definition of optimality strictly depends on the text T and on a set of algorithms. A parsing can be optimal for a text and not for another one. Clearly, we are mainly interested on parsings that are optimal either for all texts over an alphabet or for classes of texts. Whenever it is not explicitly written, from now on when we talk about optimal parsing we mean optimal parsing for all texts. About the set of algorithm it make sense to find sets as large as possible.

Classically, there is a bijective correspondence between parsings and paths in G A,T from vertex 0 to vertex n, where optimal parses correspond to minimal paths and vice-versa. We say that a parse (resp. path) induces a path (resp. parse) to denote this correspondence. This correspondence was firstly stated in [START_REF] Schuegraf | A comparison of algorithms for data base compression by use of fragments as language elements[END_REF] only in the case of sets of algorithms sharing the same static dictionary and where the encoding of pointers has constant cost. For example, in Figure 1 we have that the path along vertexes (0, 2, 3, 5, 8, 10, 13, 16) is minimal and it correspond to the optimal parsing of the text for the scheme represented by the graph. While the path along vertexes (0, 3, 4, 5, 6, 7, 8, 10, 13, 14, 15, 16) is the shortest path for the graph in Figure 2. Authors of [START_REF] Della Penna | Optimal parsing in dictionary-symbolwise data compression schemes[END_REF] were the firsts to formally extend the Shortest Path approach to dynamically changing dictionaries and variable costs.

Since graph G A,T are DAGs (Directed Acyclic Graph) that are naturally topologically ordered, classical shortest path algorithms linear in the size of the graph are known. Unfortunately the size of the graph can be quadratic in the size of the text and this approach was not recommended in [START_REF] Schuegraf | A comparison of algorithms for data base compression by use of fragments as language elements[END_REF] because it is too time consuming. In the case of LZ78 alike algorithms it is not difficult to show that the size of this graph can be O(n 3 2 ), where n is the size of the text. In order to get over the quadratic (or the O(n 3 2 )) worst case problem, there are many different approaches to limit the size of the graph, as already pointed out in the introductive section.

Linear time optimal parsing solution are known for some particular cases. Indeed, under the constant cost assumption, it is proved in [START_REF] Cohn | Parsing with prefix and suffix dictionaries[END_REF] the optimality of the greedy parsing for suffix-closed static dictionary. In [START_REF] Matias | On the optimality of parsing in dynamic dictionary based data compression[END_REF][START_REF] Matias Nd S"uleyman | On the optimality of parsing in dynamic dictionary based data compression[END_REF][START_REF] Matias | The effect of flexible parsing for dynamic dictionarybased data compression[END_REF] Flexible Parsing is described and it is given a linear time implementation. It is proved that Flexible Parsing is optimal within the set of all algorithms that have the same dictionary of LZW with constant-cost pointers encoding and some experimental results are also described.

The theory of Dictionary-Symbolwise compression algorithms started in [START_REF] Della Penna | Optimal parsing in dictionary-symbolwise data compression schemes[END_REF] improve and generalize previous results stated for dictionary algorithms and allows to obtain new ones.

Let us give the following definition on same class of schemes: Definition 2. A scheme S has the Schuegraf property if, for any text T and for any pair of algorithms

A, A ′ ∈ S, the graph G A,T = G A ′ ,T with G A,T well defined.
This property of schemes is called property of Schuegraf in honor to the first of the authors in [START_REF] Schuegraf | A comparison of algorithms for data base compression by use of fragments as language elements[END_REF]. In this case we define G S,T = G A,T as the graph of (any algorithm of) the scheme. There is a bijective correspondence between optimal parsings and shortest paths in G S,T from vertex 0 to vertex n. Definition 3. Let us consider an algorithm A and a text T and suppose that graph G A,T is well defined. We say that A is dictionary optimal (with respect to T ) if its parsing induces a shortest path in G A,T from the origin to vertex n, with n = |T |. In this case we say that its parsing is dictionary optimal.

Let A be an algorithm such that for any text T the graph G A,T is well defined. We want to associate to it a scheme SC A in the following way. Let S be the set of all algorithms A such that for any text T G A,T exists (i.e. it is well defined). Let B and C two algorithms in S. We say that B and C are equivalent or B ≡ C if for any text T G B,T = G C,T . We define the scheme SC A to be the equivalence class that has A as a representative. It is easy to prove that SC A has the Schuegraf property.

We can connect the definition of dictionary optimal parsing with the previous definition of SC A to obtain the next proposition, that says, roughly speaking, that dictionary optimality implies scheme (or global) optimality within the scheme SC A .

Proposition 1. Let us consider an algorithm A such that for any text T the graph G A,T is well defined. Suppose further that for a text T the parsing of A is dictionary optimal. Then the parsing of A of the text T is (globally) optimal within the scheme SC A .

We have simple examples where a parsing of a text is dictionary optimal and the corresponding algorithm belongs to a scheme that has not the Schuegraf property and it is not (globally) optimal within the same scheme. For pure dictionary scheme having the Schuegraf Property we mean a dictionary-symbolwise scheme having the Schuegraf Property where all algorithms in the scheme are pure dictionary. We have to be a bit careful using this terminology. Indeed, LZ78, LZW, LZ77 and related algorithms often parse the text with a dictionary pointer and then add a symbol, i.e. the parse phrase is composed by a dictionary pointer and a symbol. In these cases all edges of G A,T denote parse phrases coupled to the corresponding symbol. Edges are labeled by the cost of the dictionary pointer plus the cost of the symbol. We consider these cases included in the class of "pure dictionary" algorithms and schemes.

It is possible to obtain a new statement of the main result concerning flexible parsing revisited in our formalism as follows. The proof is omitted since it is implicitly contained in [START_REF] Matias Nd S"uleyman | On the optimality of parsing in dynamic dictionary based data compression[END_REF][START_REF] Matias | The effect of flexible parsing for dynamic dictionarybased data compression[END_REF]. It holds for all dictionary algorithms, under the assumptions that the dictionary is at any moment prefix closed and that the cost of encoding pointers is constant. The reader can refer to [START_REF] Matias Nd S"uleyman | On the optimality of parsing in dynamic dictionary based data compression[END_REF][START_REF] Matias | The effect of flexible parsing for dynamic dictionarybased data compression[END_REF] for further notations and definitions.

Theorem 1. Flexible Parsing is dictionary optimal.

Dictionary-Symbolwise Flexible Parsing Algorithm

In this section we extend the notion of flexible parsing to the dictionary-symbolwise case and we prove that it is still optimal within any scheme having the Schuegraf Property. We assume here that the dictionary must be at any moment prefix closed. The algorithm is quite different from the original Flexible Parsing but it has some analogies with it and, in the case of LZ78-alike dictionaries, it makes use of one of the main data structures used for the original flexible parsing in order to be implemented in linear time.

Concerning the costs of encoding pointers, we recall that costs can vary but that they assume positive values and that they include the cost of flag information.

Concerning the symbolwise compressor, the costs of symbols must be positive, including the flag information cost. They can vary depending on the position of the character in the text and on the symbol itself.

We suppose further that a text T of length n is fixed and that we are considering the graph G A,T , where A is a dictionary-symbolwise algorithm, and G A,T is well defined under our assumption. We denote by d the function that represent the distance of the vertexes of G A,T from the origin of the graph. Such a distance d(i) is classically defined as the minimal cost of all possible weighted paths from the origin to the vertex i, where d(0) = 0. This distance obviously depends on the cost function. We say that cost function C is prefix-non-decreasing at any moment if for any u, v ∈ D p phrases associated to edges (p, i), (p, q), with p < i < q, that implies that u is prefix of v, one has that C((p, i)) ≤ C((p, q)).

Lemma 1.

Let A be a dictionary-symbolwise algorithm such that for any text T the graph G A,T is well defined. If the dictionary is always (at any moment) prefix-closed and if the cost function is always (at any moment) prefix-non-decreasing then the function d is non-decreasing monotone.

Proof. It is sufficient to prove that for any i, 0 ≤ i < n one has that d(i) ≤ d(i + 1). Let j ≤ i be a vertex such that (j, i+1) is an edge of the graph and d(i+1) = d(j)+C((j, i+1)). If j is equal to i then d(i+1) = d(i)+C((i, i+1)) and the thesis follows. If j is smaller than i then, since the dictionary D j is prefix closed, (j, i) is still an edge in D j and d(i) ≤ d(j) + C((j, i)) ≤ d(j) + C((j, i + 1)) = d(i + 1) and the thesis follows. The last inequality in previous equation depend on the fact that the cost function is prefix-non-decreasing.

In what follows in this paper we suppose that the graph G A,T is well defined.

Let us call vertex j a predecessor of vertex i ⇐⇒ ∃(j, i) ∈ E such that d(i) = d(j) + C((j, i)). Let us define pre(i) to be the smallest of the predecessors of vertex i, 0 < i ≤ n, that is pre(i) = min{j | d(i) = d(j) + C((j, i))}. In other words pre(i) is the smallest vertex j that contributes to the definition of d(i). Clearly pre(i) has distance smaller than d(i). Moreover the function pre is not necessarily injective. For instance, a vertex can be a predecessor either "via" a dictionary edge or "via" a symbol edge.

It is also possible to extend previous definition to pointers having a cost smaller than or equal to a fixed c. Definition 4. For any cost c we define pre c (i) = min{j | d(i) = d(j) + C((j, i)) and C((j, i)) ≤ c}. If none of the predecessor j of i is such that C((j, i)) ≤ c then pre c (i) is undefined.

If all costs of the pointers are smaller than or equal to c then for any i one has obviously that pre c (i) is equal to pre(i).

Analogously to the notation of [START_REF] Matias | The effect of flexible parsing for dynamic dictionarybased data compression[END_REF], we want to define two boolean operations Weighted-Extend and Weighted-Exist. Definition 5. Given an edge (i, j) in G A,T and its associated phrase w, a cost value c and a character 'a', the operation Weighted-Extend((i, j), a, c) finds out whether the word wa is a phrase in D i having cost smaller than or equal to c. More formally, let (i, j) be such that w = T [i + 1 : j] ∈ D i and, then, (i, j) is in G A,T . Weighted-Extend((i, j), a, c) = "yes" ⇐⇒ wa = T [i + 1 : j + 1] ∈ D i and C((i, j + 1)) ≤ c, where C is the cost function associated to the algorithm A. Otherwise Weighted-Extend((i, j), a, c) = "no". Definition 6. Given 0 < i, j ≤ n and a cost value c, the operation Weighted-Exist(i, j, c) finds out whether or not the phrase w = T [i + 1 : j] is in D i and the cost of the corresponding edge (i, j) is smaller than or equal to c.

Let us notice that doing successfully a Weighted-Extend operation on ((i, j), a, c) means that wa ∈ D i is the weighted extension of w and the encoding of (i, j + 1) has cost less or equal to c. Similarly, doing a Weighted-Exist operation on (i, j, c) means that an edge (i, j) exist in G A,T having cost less or equal to c. Let E c be the subset of all edges of the graph having cost smaller than or equal to c. Definition 7. Let us also define, for any cost c the set M c ⊆ E c to be the set of c-supermaximal edges, where (i, j) ∈ M c ⇐⇒ (i, j) ∈ E c and ∀p, q ∈ V , with p < i and j < q, the arcs (p, j), (i, q) are not in E c . For any (i, j) ∈ M c let us call i a c-starting point and j a c-ending point.

Proposition 2. Suppose that (i, j) and (i ′ , j ′ ) are in M c . One has that i < i ′ if and only if j < j ′ .

Proof. Suppose that i < i ′ and that j ≥ j ′ . By the fact that the dictionary D i is prefix closed we have that (i, j ′ ) is still in D i and therefore it is an edge of G A,T . By the prefix-non-decreasing property of function C we have that C((i, j ′ )) ≤ C((i, j)) = c, i.e. (i, j ′ ) ∈ E c . This contradicts the fact that (i ′ , j ′ ) is in M c and this proves that if i < i ′ then j < j ′ . Conversely suppose that j < j ′ and that i ≥ i ′ . If i > i ′ by previous part of the proof we must have that j > j ′ that is a contradiction. Therefore i = i ′ . Hence (i, j) and (i, j ′ ) both belongs to M c and they have both cost smaller than or equal to c. This contradicts the fact that (i, j) is in M c and this proves that if j < j ′ then i < i ′ . By previous proposition, if (i, j) ∈ M c we can think j as function of i and conversely. Therefore it is possible to represent M c by using an array

M c [j] such that if (i, j) is in M c then M c [j] = i otherwise M c [j] = Nil.
Moreover the non-Nil values of this array are strictly increasing. The positions j having value different from Nil are the ending positions.

We want now describe a simple algorithm that outputs all c-supermaximal edges scanning the text left-to-right. We call it Find Supermaximal(c). It uses the operations Weighted-Extend and Weighted-Exist. The algorithm starts with i = 0, j = 1 and w = a 1 .The word w is indeed implicitely defined by the arc (i, j) and therefore it will not appear explicitely in the algorithm. At each step j is increased by one and w is set to w concatenated to T [j]. The algorithm executes a series of Weighted-Extend until this operation give a positive answer or the end of the text is reached. After a negative answer of Weighted-Extend, the algorithm does a series of Weighted-Exist increasing i by one until a positive answer.

The algorithm is stated more formally in the following pseudo code.

Find Supermaximal (c) 01. i ← 0, j ← 1 02. WHILE j < n 03. DO 04.

WHILE Weighted-Extend((i, j), a j+1 , c) = "yes" AND j < n 05. DO 06. j ← j + 1 07.

INSERT (i, j) in M c , j ← j + 1 08. DO 09.

i ← i + 1 10.

WHILE Weighted-Exist(i, j, c) = "no" AND i < j

We notice that when exiting from cycle of lines 4 -6, the cost of the edge (i, j) could still be strictly smaller than c. The function INSERT simply insert the edge (i, j) in the dynamical set M c . If we represent M c by an array as described after Proposition 2, function INSERT sets M c [j] equal to i. Array M c [j] was initialized by setting all its entries to Nil.

Proposition 3. Above algorithm correctly computes M c

Proof. First of all let us prove that if ( î, ĵ) is inserted by the algorithm in M c then ( î, ĵ) is csupermaximal. First of all, since C(( î, ĵ)) ≤ c then the first part of the definition is verified. Since Weighted-Extend(( î, ĵ), a ĵ+1 , c) = "no" then ( î, ĵ + 1) / E c . Since D i is prefix closed and the function cost C is prefix-non decreasing ∀q ∈ V with ĵ < q the arc ( î, q) is not in E c for otherwise ( î, ĵ + 1) would be in E c .

It remains to prove that ∀p ∈ V with p < î the arc (p, ĵ) is not in E c . Suppose by contradiction that there exists one such arc (p, ĵ) in E c . If p = 1, since D 1 is prefix closed and the function cost is prefix-non-decreasing then variable j must reach a value greater than or equal to ĵ + 1 after the first round of Weighted-Extend and no further operations can lead to INSERT the arc ( î, ĵ). This leads to a contradiction.

If p > 1 then p has been reached by the variable i after a round of Weighted-Exist operations described in lines 8 -10. Let j p be the corresponding value that the variable j assumes when i = p. If j p > ĵ then no further operations can lead to INSERT the arc ( î, ĵ). A contradiction. If j p ≤ ĵ, since (p, ĵ) in E c and the dictionary D p is prefix closed and the function cost is prefix-non-decreasing we have that for any j with j p ≤ j ≤ ĵ the arc (p, j) ∈ E c . Therefore when variable i reaches p it must start a round of Weighted-Extend until j assume a value greater than or equal to ĵ + 1. Even in this case no further operations can lead to INSERT the arc ( î, ĵ). This leads to a contradiction. Therefore if ( î, ĵ) is inserted by the algorithm in M c then ( î, ĵ) is c-supermaximal.

We have now to prove that if ( î, ĵ) is c-supermaximal then it is inserted by the algorithm in M c . Suppose that variable i never assumes the value î. The algorithm ends when variable j is equal to n. Let i n be the value of variable i just before that j becomes n. Since variable j increases only in line 6 after that the operation Weighted-Extend outputs "yes", we know that (i n , n) ∈ E c . Since The dictionary D in is prefix closed and ĵ ≤ n and since the function cost is prefix-non-decreasing then (i n , ĵ) ∈ E c . Since variable i ranged from 1 up to i n then i n < î and this contradicts the fact that ( î, ĵ) is c-supermaximal.

Therefore at a certain moment variable i is assuming the value î. Let j î be the value of variable j in that moment. Variable i increases only during a round of operations Weighted-Exist. Before this round there must have been a round of operations Weighted-Extend. Let us consider the last one of this round. Variable i is assuming the value i ′ < î and, before increasing the variable j we know that (i ′ , j î -1) is in E c .

If, at this point, j î > ĵ then j î -1 ≥ ĵ. Since the dictionary D i ′ is prefix closed and since the function cost is prefix-non-decreasing, (i ′ , ĵ) ∈ E c . This contradicts the fact that ( î, ĵ) is c-supermaximal. Hence j î ≤ ĵ.

Since ( î, ĵ) is in E c , again since the dictionary D î is prefix closed and since the function cost is prefix-non-decreasing, for all j, j î ≤ j ≤ ĵ we have that ( î, j) ∈ E c . Therefore when variable i reaches î it starts a sequence of Weighted-Extend and the variable j reaches the value ĵ. It and cannot go further for otherwise ( î, ĵ) would not be c-supermaximal. Therefore ( î, ĵ) is inserted in M c . Proposition 4. For any edge (i, j) ∈ E c there exists a c-supermaximal edge ( î, ĵ) containing it, e.g. such that î ≤ i and j ≤ ĵ.

Proof. We build ( î, ĵ) in algorithmic fashion. The algorithm is described in what follows in an informal but rigorous way. If edge (i, j) is not c-supermaximal then we proceed with a round of Weighted-Extend((i, j), a j+1 , c) analogously as described in algorithm Find Supermaximal and increase j of one unit until Weighted-Extend outputs "no". Let j 1 be last value of j for which Weighted-Extend output "yes". Clearly (i, j 1 ) ∈ E c and (i, j) = (i, j 1 ). If (i, j 1 ) is not c-supermaximal the only possibility is that there exists at least one i 1 < i such that (i 1 , j 1 ) ∈ E c . At this point we keep iterating previous two steps starting from (i 1 , j 1 ) instead of (i, j) and we stops whenever we get a c-supermaximal edge, that we call ( î, ĵ).

By previous proposition for any node

v ∈ G A,T if there exists a node i < v such that C((i, v)) = c and d(v) = d(i) + c
then there exists a c-supermaximal edge ( î, ĵ) containing (i, v) and such that ĵ is the closest arrival point greater that v. Let us call this c-supermaximal edge ( îv , ĵv ). We use îv in next proposition. Proof. Since ( îv , ĵv ) contains (i, v) and the dictionary at position îv is prefix close then ( îv , v) is an edge of G A,T . Since ( îv , ĵv ) has cost smaller than or equal to c then, by the suffix-non-decreasing property, also ( îv , v) has cost smaller than or equal to c. Since the distance d is non-decreasing we know that d( îv ) ≤ d(i). By very definition of the distance d we know that d(v) ≤ d( îv ) + C(( îv , v)).

Putting all together we have that

d(v) ≤ d( îv ) + C(( îv , v)) ≤ d(i) + c = d(v).
Hence the inequalities in previous equation must be equalities and, further,

d( îv ) = d(i) and C(( îv , v)) = c.
Corollary 1. For any vertex v, the edge ( îv , v) is the last edge of a path of minimal cost from the origin to vertex v.

Proof. Any edge x in G A,T that is such that d(v) = d(x) + C((x, v)) is the last edge of a path of minimal cost from the origin to vertex v.
In what follows we describe a graph G ′ A,T that is a subgraph of G A,T that is such that for any node v ∈ G A,T there exists a minimal path from the origin to v in G ′ A,T that is also a minimal path from the origin to v in G A,T . The proof of this property, that will be stated in the subsequent proposition, is a consequence of Proposition 5 and Corollary 1.

We describe the building of G ′ A,T in an algorithmic way. Even if we do not give the pseudocode, algorithm Build G ′ A,T is described in a rigorous way and it makes use, as a part of it, of algorithm Find Supermaximal.

The set of nodes of G ′ A,T is the same of G A,T . First of all we insert all symbolwise edges of G A,T in G ′ A,T . Let now C be the set of all possible costs that any dictionary edge has. This set can be build starting from G A,T but in all known meaningful situations the set C is usually well known and can be ordered and stored in an array in a time that is linear in the size of the text.

For any c ∈ C we use algorithm Find Supermaximal to obtain the array M c [j]. For any csupermaximal edge (i, j), we add in G ′ A,T all edges of the form (i, x) where x varies from j down to (and not including) the previous arrival position j ′ if this position is greater than i + 1 otherwise down to i + 2. More formally, for any j such that M c [j] = Nil let j ′ be the greatest number smaller than j such that M c [j] = Nil. For any x, such that max(j ′ , i + 2) ≤ x ≤ j, add (i, x) to G ′ A,T together with its label. This concludes the construction of G ′ A,T .

Since (i, j) and the dictionary D i is prefix closed then all previous arcs of the form (i, x) are also arcs of G A,T and, therefore, G ′ A,T is a subgraph of G A,T . Proposition 6. For any node v ∈ G A,T there exists a minimal path from the origin to v in G ′ A,T that is also a minimal path from the origin to v in G A,T .

Proof. The proof is by induction on v. If v is the origin there is nothing to prove. Suppose now that v is greater than the origin and let (i, v) the last edge of a minimal path in G A,T from the origin to v. By inductive hypothesis there exists a minimal path P from the origin to i in G ′ A,T that is also a minimal path from the origin to i in G A,T . Since (i, v) is a symbolwise arc then it is also in G ′ A,T and the concatenation of above minimal path P with (i, v) is a minimal path from the origin to v in G ′ A,T that is also a minimal path from the origin to v in G A,T .

Suppose now that (i, v) is a dictionary arc and that its cost is c. Since it is the last edge of a minimal path we have that

d(v) = d(i) + c. By Proposition 5 d(v) = d( îv ) + C(( îv , v)) and, moreover, d( îv ) = d(i) and C(( îv , v)) = c.
By Corollary 1, the edge ( îv , v)) is the last edge of a path of minimal cost from the origin to vertex v. By inductive hypothesis there exists a minimal path P from the origin to îv in G ′ A,T that is also a minimal path from the origin to i in G A,T . Since ( îv , v)) has been added by construction in G ′ A,T , the concatenation of above minimal path P with ( îv , v)) is a minimal path from the origin to v in G ′ A,T that is also a minimal path from the origin to v in G A,T .

We can now finally describe the Dictionary-symbolwise flexible parsing.

The Dictionary-symbolwise flexible parsing firstly uses algorithm Build G ′ A,T and then uses the classical Single Source Shortest Path algorithm to recover a minimal path from the origin to the end of graph G A,T . The correctness of above algorithm is stated in the following theorem and it follows from above description and from Proposition 6 Theorem 2. Dictionary-symbolwise flexible parsing is dictionary optimal.

With respect to the original Flexible Parsing algorithm we gain the fact that it can works with variable costs of pointers and that it is extended to the dictionary-symbolwise case. But we loose the fact that the original one was "on-line". A minimal path has to be recovered, starting from the end of the graph backward. But this is an intrinsic problem that cannot be eliminated. Even if the dictionary edges have just one possible cost, in the dictionary-symbolwise case it is possible that any minimal path for a text T is totally different from any minimal path for the text T a, that is the previous text T concatenated to the symbol 'a'. Even if the cost of pointers is constant. The same can happen when we have a "pure dictionary" case with variable costs of dictionary pointers. In both cases for this reason, there cannot exists "on-line" optimal parsing algorithms, and, indeed, flexible parsing fails being optimal in the pure dictionary case when costs are variable.

On the other hand our algorithm is suitable when the text is cut in several blocks and, therefore, in practice there is not the need to process the whole text but it suffices to end the current block in order to have the optimal parsing (relative to that block). As another alternative, one can keep track of just one minimal path all along the text and can use some standard tricks to arrange it if it does not reach the text end, i.e. the wished target node. In the last cases one get a suboptimal solution that is a path with a cost extremely close to the minimal path.

Data Structures and Time Analysis

In this subsection we analyze Dictionary-symbolwise flexible parsing in both LZ78 and LZ77 alike algorithms.

Concerning LZ78 alike algorithms, the dictionary is prefix closed and it is usually implemented by using a technique that is usually referred as LZW implementation. We do not enter in details of this technique. We just recall that the cost of pointers increases by one unit whenever the dictionary size is "close" to a power of 2. The moment when the cost of pointers increases is clear to both encoder and decoder. In our dictionary-symbolwise setting, we suppose that the flag information for dictionary edges is constant. We assume therefore that it takes O(1) time to determine the cost of all dictionary edges outgoing node i.

The maximal cost that a pointer can assume is smaller than log 2 (n) where n is the text-size. Therefore the set C of all possible costs of dictionary edges has logarithmic size and it is cheap to calculate.

In [START_REF] Matias | The effect of flexible parsing for dynamic dictionarybased data compression[END_REF] it is used a data structure, called trie-reverse pair, that is able to perform the operation of Extend and Contract in O(1) time.

Since at any position we can calculate in O(1) time the cost of outgoing edges, we can use the same data structure to perform our operations of Weighted-Extend and of Weighted-Exist in constant time. In order to perform a Weighted-Extend we simply use the Extend on the same non-weight parameters and, if the answer is "yes" we perform a further check in O(1) time on the cost. In order to perform a Weighted-Exist we simply use the contract on the same non-weight parameters and, if the answer is "yes" we perform a further check in O(1) time on the cost.

For any cost c finding M c and the corresponding arcs in order to build G ′ A,T takes then linear time. Therefore, at a first look, performing the algorithm Build G ′ A,T would take O(n log(n)). But, since there is only one cost active at any position then if c < c ′ then M c ⊆ M c ′ as stated in the following proposition.

Proposition 7. Suppose that for any i the cost of all dictionary pointers in D i is a constant c i and that for any i, 0 ≤ i < n one has that c

i ≤ c i+1 . If c < c ′ then M c ⊆ M c ′ .
Proof. We have to prove that for any (i, j) ∈ M c then (i, j) ∈ M c ′ . Clearly if (i, j) ∈ M c then its cost is smaller than or equal to c < c ′ . It remains to prove that (i, j) is c ′ -supermaximal, e.g. that ∀p, q ∈ V , with p < i and j < q, the arcs (p, j), (i, q) are not in E c ′ . Since (i, j) ∈ M c and since the cost of (i, j) is by hypothesis equal to c i , we have that c

i ≤ c. If arc (p, j) is in E c ′ then its cost is c p ≤ c i ≤ c
and therefore it is also in E c contradicting the c-supermaximality of (i, j). If arc (i, q) is in E c ′ then its cost is c i ≤ c and therefore it is also in E c contradicting the c-supermaximality of (i, j).

Definition 8. We say that a cost function C is LZW-alike if for any i the cost of all dictionary pointers in D i is a constant c i and that for any i, 0 ≤ i < n one has that c i ≤ c i+1 .

At this point, in order to build G ′ A,T it suffices to build M c where c is the greatest possible cost. Indeed it is useless checking for the cost and one can just use the standard operation Extend and Contract. Those operation can be implemented in O(1) time using the trie reverse trie data structure for LZ78 standard dictionary or for the LZW dictionary or for the FPA dictionary (cf. [START_REF] Matias | The effect of flexible parsing for dynamic dictionarybased data compression[END_REF]). Indeed we call a dictionary LZ78-alike if the operations Extend and Contract can be implemented in O(1) time using the trie reverse trie data structure.

Let us consider a string S that is the concatenation of all the prefixes of 1..k in increasing order. Let consider the string T ′ that is the concatenation of the first

√ k suffixes of 2..k, i.e. T ′ = 2..k • 3..k • . . . • √ k.
.k and a string T = S • T ′ . We use S to build a dictionary formed by just the string 1..k and its prefixes and no more. We assume that both the dictionary and the symbolwise methods work the same up to the end of the S string, so they produce an output that is very similar in terms of space. It is not difficult to prove that an optimal LZ78 compressor would produce on T a parse having cost at least O(k + k log(k)) = O(k log(k)) while the optimal dictionary-symbolwise compressor (under the constant cost assumption on encoding pointers) has a cost that is O(k + √ k log(k)) = O(k). A similar result can be stated and proved also in the case of LZ77 dictionary.

Experimental Results

We present some experimental results on LZ78 alike dictionaries that show the effectiveness of this approach. We did some experiments focused on the gain of an optimal dictionary-symbolwise over an optimal pure dictionary methods, using our flexible version of a LZ78 dictionary-symbolwise compressor, where the dictionary size (number of phrases) is 2 24 , the symbolwise compressor is an Huffman coding over all symbols and the parse is optimal. We mean that the cost of a symbol is set to be the cost in bits that a static Huffman coding over the whole text assigns to it. We further used an Huffman coding on the flag information by considering 8 consecutive flag information as a character. In order to see the gain over a pure dictionary method, we forced the parsing not to use symbolwise arcs. Therefore, what we call "the pure dictionary method" is essentially the Flexible Parsing of Mathias and Shainalp.

We tested our compressors over some prefixes of the English wikipedia that are widely used as dataset for benchmark, (cf. [START_REF] Mahoney | Large text compression benchmark[END_REF]). The prefix of length 10 8 symbols is called ENWIK8. Over ENWIK8 the gain of our dictionary-symbolwise with respect to the pure dictionary method was close to 5%.

We observed a similar gain for other prefixes of English wikipedia, slowly decreasing as the size of the prefix was increasing.

From a formal point of view, for the compression algorithm used by us we cannot build the weighted graph G A,T , i.e. the cost of arcs cannot be given "a priori". Nevertheless, in practice we assigned a presumed cost to each arc and we worked as in the case of a compressor that is such that for any text the weighted graph G A,T exists. So, we cannot say that the obtained parse is optimal, but we believe that it is very close to the optimal one. Actually our compressed version of ENWIK8 is less than 90% of the corresponding version compressed by gzip with the option -9. Next table shows the percentage of our compressed version w.r.t. gzip-9 ones.

The results described in [START_REF] Matias | The effect of flexible parsing for dynamic dictionarybased data compression[END_REF] do not use LZ78 but the LZW with a dictionary of size 2 16 and the FPA algorithm with a dictionary of size 2 16 and 2 24 . This last seems to behave better than LZW and of our LZ78 optimal pure dictionary. Our results are then not directly comparable but they seem to be compatible. Some percentile can be lost or gained by the ability of the programmer. Our program is just a working prototype and its purpose is to compare the gain obtained when an simple Huffman is coupled with a LZ78 with respect to a pure LZ78, both with an optimal parsing. The reader can make other comparisons with other standard compressors such as Bzip2 by using the URL in [START_REF] Mahoney | Large text compression benchmark[END_REF] and gzip -9 as a benchmark.

As further improvement, we gained few percentile points by using a dynamic Huffman coding on the symbols chosen by the parse. We decided to make more "rounds" of compression by assigning the value corresponding to the last distribution to the next round of compression. We noticed an extremely fast stabilization of the values, i.e. just after 3 or at most 4 rounds. We noticed further that different starting distributions could lead to different, even if close, stabilized or stationary distributions, that, in turn, lead to different compressed outputs of similar but not equal size.

As a preliminary result, we observed a much higher gain of a further 10% when the Huffman coding was replaced by an order-1 arithmetical coding. In this case we have just evaluated the cost of the chosen parsing because we have not yet the working compression -decompression program.

Concerning LZ77 dictionary-symbolwise we have implemented a generalisation to larger dictionary size of gzip, that we call Lgzip (Large gzip). When the dictionary size is smaller that or equal to 32 Kb we obtain files that are .gz compliant, i.e. they can be decompressed by usual decompressors. Our compression ratios are almost equal (usually few bytes more indeed) than the equivalent files compressed by deflate64 with maximal compression parameters. These files have by far a much better compression ratio than the one obtained by gzip with the option -9. The library deflate64 is included in the widely used 7zip program.

When we enlarge the dictionary size we obtain similar compression ratio of other commercial compression programs.

When we deal with files of size of 20 megas the advantage of using a symbolwise coupled with a LZ77 dictionary reduces down to a 2 -3%, less than the 5% of the LZ78 case.

The compression ratio in the LZ77+Huffman case is better than the one in the LZ78+Huffman case. The distance seems to reduce when instead of an Huffmann coding it is used an order-1 arithmetical coding.

We plan to continue these experiments since this direction seems to be very promising. As further experimental work we plan to check our algorithm by using as dictionary some version of FPA algorithm and, eventually, a Rolz compressor.

Conclusions

In this paper we present some advancement on dictionary-symbolwise theory. We describe the Dictionary-Symbolwise Flexible Parsing, a parsing algorithm that extends in non obvious way the Flexible Parsing (cf. [START_REF] Matias Nd S"uleyman | On the optimality of parsing in dynamic dictionary based data compression[END_REF]) to variable and unbounded costs and to the dictionary-symbolwise algorithm domain. We prove its optimality for prefix-closed dynamic dictionaries under some reasonable assumption. Dictionary-Symbolwise Flexible Parsing is linear for LZ78 alike dictionaries and even if it is not able to run online it allow to easily make a block programming implementation and a near to optimal online implementation, too. In the case of LZ77 alike dictionary and under lighter constrains on cost function, we have reobtained the O(n log(n)) complexity as authors of [START_REF] Ferragina | On the bit-complexity of lempel-ziv compression[END_REF] recently did and we use a completely different and simpler subgraph and a simpler data structure. We proved that dictionary-symbolwise compressors can be asymptotically better than optimal pure dictionary compression algorithms in compression ratio terms, with LZ78 based dictionary and the same can be proved for LZ77 based dictionary.

Finally, we easily obtained experimentally a 5% enhancement in compression ratio with respect of the pure dictionary compressor building the dictionary-symbolwise LZ78-Huffman compressor. We plan to extend our experimentation on LZ alike dictionary algorithms and many other symbolwise algorithms, since this direction seems to be very promising.

  Fig.2. Graph GA,T for the text T = abccacbbabbcbcbb, for the dictionary-symbolwise algorithm A with static dictionary D = {ab, cbb, ca, bcb, abc, c} and cost function C as defined in the graph. The dictionary phrase or the symbol associated to an edge is reported near the edge label within parenthesis.

Proposition 5 .

 5 Suppose that v ∈ G A,T is such that there exists a previous node i such that C((i, v)) = c and d(v) = d(i) + c. Then îv is a predecessor of v, e.g. d(v) = d( îv ) + C(( îv , v)) and, moreover, d( îv ) = d(i) and C(( îv , v)) = c.

Table 2 .

 2 16M B 32M B 64M B 100M B pure dictionary 112.97% 109.29% 104.41% 100.88% 98.68% 95.92% 94.28% dict-symbolwise 107.43% 103.97% 99.37% 96.04% 94.07% 91.51% 89.98% Compression evaluation against gzip -9.

	input file size	2M B	4M B	8M B

We notice that previous definition of LZ78-alikeness can be relaxed by asking that the operations Extend and Contract can be implemented in O(1) amortized time using any data structure, including obviously the time used for building such data structure.

The overall time for building G ′ A,T is therefore linear, as well as its size. The Single Source Shortest Path over G ′ A,T , that is a DAG topologically ordered, takes linear time.

In conclusion we have proved the following theorem.

Theorem 3. Suppose that we have a dictionary-symbolwise scheme, where the dictionary is LZ78alike and the cost function is LZW-alike. The symbolwise compressor is supposed to be, as usual, linear time. Using the trie-reverse pair data structure, Dictionary-Symbolwise flexible parsing is linear.

Concerning LZ77, in [START_REF] Ferragina | On the bit-complexity of lempel-ziv compression[END_REF] it has been given, with a similar shortest path approach, an optimal parsing algorithm under some assumptions on the cost function. Our prefix-non-decreasing assumption is weaker than their assumptions in the sense that it is a consequence of their assumptions (cf. [START_REF] Ferragina | On the bit-complexity of lempel-ziv compression[END_REF]Fact 4]). The maximal cost that a pointer can have under their assumption is still O(log(n)) where n is the size of the text. It seems that it is possible to use the data structure used in [START_REF] Ferragina | On the bit-complexity of lempel-ziv compression[END_REF] to perform, for any cost, Weighted-Extend and Weighted-Exist in amortized O(1) time. Then the overall time for the Dictionary-symbolwise flexible parsing when the dictionary is LZ77 alike would be O(n log(n)), extending their result to the dictionary-symbolwise case. The subgraph G ′ A,T of G A,T is totally different from the one used in [START_REF] Ferragina | On the bit-complexity of lempel-ziv compression[END_REF].

Indeed, quite recently, we discovered a simpler data structure that allows us to perform, for any cost, Weighted-Extend and Weighted-Exist in amortized O(1) time. This data structure is built by using in a clever way O(log(n)) suffix trees and it will be described in the journal version of this paper.

Dictionary-Symbolwise Can Have Better Ratio

In this section we prove that there exists a family of strings such that the ratio between the compressed version of the strings obtained by using an optimal LZ78 parsing (with constant cost encoding of pointers) and the compressed version of the strings obtained by using an optimal dictionary-symbolwise parsing is unbounded. The dictionary, in the dictionary-symbolwise compressor is still the LZ78 dictionary, while the symbolwise is a simple Last Longest Match Predictor that will be described later. We want to notice here that similar results were proved in [START_REF] Matias Nd S"uleyman | On the optimality of parsing in dynamic dictionary based data compression[END_REF] between flexible parsing and the classical LZ78 and in [START_REF] Ferragina | On the bit-complexity of lempel-ziv compression[END_REF] between a compressor that uses optimal parsing over a LZ77 dictionary and the standard LZ77 compressor (cf. also [START_REF] Kosaraju | Compression of low entropy strings with lempel-ziv algorithms[END_REF]). Last but not least we notice that in this example, analogously as done in [START_REF] Matias Nd S"uleyman | On the optimality of parsing in dynamic dictionary based data compression[END_REF], we use an unbounded alphabet just to make the example clearer. An analogous result can be obtained with a binary alphabet with a more complex example.

Let us define a Dictionary-Symbolwise compressor that uses LZ78 as dictionary method, the Last Longest Match Predictor as symbolwise method, Run Length Encoder to represent the flag information and one optimal parsing method. Let us call it OptDS-LZ78. We could have used a PPM* as symbolwise compressor but Last Longest Match Predictor fits our purposes and it is simple to analyze. Last Longest Match Predictor is just a simple symbolwise compression method that uses the last longest seen match to predict next char.

The symbolwise searches, for any position k of the text, the closest longest block of consecutive letters up to position k -1 that is equal to a suffix ending in position k. This compressor predicts the (k + 1)-th character of the text to be the character that follows the block. It writes a symbol 'y' (that is supposed not to be in the text) if this is the case. Otherwise it uses an escape character 'n' (that is supposed not to be in the text) and then writes down the correct character plainly. A temporary output alphabet has therefore two characters more than the characters in the text. This temporary output will be subsequently encoded by a run-length encoder. This method is like the Yes?No version of Symbol Ranking by P. Fenwick.


Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Marcin Kubica
email: [kubica@mimuw.edu.pl

Jakub Radoszewski ⋆2

Wojciech Rytter
email: rytter@mimuw.edu.pl

Tomasz Waleń
email: walen]@mimuw.edu.pl

On the Maximal Sum of Exponents of Runs in a String

A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition v with a period p such that 2p ≤ |v|. The exponent of a run is defined as |v|/p and is ≥ 2. We show new bounds on the maximal sum of exponents of runs in a string of length n. Our upper bound of 4.1 n is better than the best previously known proven bound of 5.6 n by Crochemore & Ilie (2008). The lower bound of 2.035 n, obtained using a family of binary words, contradicts the conjecture of Kolpakov & Kucherov (1999) that the maximal sum of exponents of runs in a string of length n is smaller than 2n.

Introduction

Repetitions and periodicities in strings are one of the fundamental topics in combinatorics on words [START_REF] Berstel | Combinatorics on words: a tutorial[END_REF][START_REF] Lothaire | Combinatorics on Words[END_REF]. They are also important in other areas: lossless compression, word representation, computational biology, etc. In this paper we consider bounds on the sum of exponents of repetitions that a string of a given length may contain. In general, repetitions are studied also from other points of view, like: the classification of words (both finite and infinite) not containing repetitions of a given exponent, efficient identification of factors being repetitions of different types and computing the bounds on the number of various types of repetitions occurring in a string. The known results in the topic and a deeper description of the motivation can be found in a survey by Crochemore et al. [START_REF] Crochemore | Repetitions in strings: Algorithms and combinatorics[END_REF].

The concept of runs (also called maximal repetitions) has been introduced to represent all repetitions in a string in a succinct manner. The crucial property of runs is that their maximal number in a string of length n (denoted as Kolpakov & Kucherov [10]. This fact is the cornerstone of any algorithm computing all repetitions in strings of length n in O(n) time. Due to the work of many people, much better bounds on ρ(n) have been obtained. The lower bound 0.927 n was first proved by Franek & Yang [START_REF] Franek | An asymptotic lower bound for the maximal number of runs in a string[END_REF]. Afterwards, it was improved by Kusano et al. [START_REF] Kusano | New lower bounds for the maximum number of runs in a string[END_REF] to 0.944565 n employing computer experiments, and very recently by Simpson [START_REF] Simpson | Modified Padovan words and the maximum number of runs in a word[END_REF] to 0.944575712 n. On the other hand, the first explicit upper bound 5 n was settled by Rytter [START_REF] Rytter | The number of runs in a string: Improved analysis of the linear upper bound[END_REF], afterwards it was systematically improved to 3.48 n by Puglisi et al. [START_REF] Puglisi | How many runs can a string contain?[END_REF], 3.44 n by Rytter [START_REF] Rytter | The number of runs in a string[END_REF], 1.6 n by Crochemore & Ilie [2, 3] and 1.52 n by Giraud [START_REF] Giraud | Not so many runs in strings[END_REF]. The best known result ρ(n) ≤ 1.029 n is due to Crochemore et al. [START_REF] Crochemore | Towards a solution to the "runs" conjecture[END_REF], but it is conjectured [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF] that ρ(n) < n. Some results are known also for repetitions of exponent higher than 2. For instance, the maximal number of cubic runs (maximal repetitions with exponent at least 3) in a string of length n (denoted ρ cubic (n)) is known to be between 0.406 n and 0.5 n, see Crochemore et al. [START_REF] Crochemore | On the maximal number of cubic runs in a string[END_REF].

ρ(n)) is O(n), see
A stronger property of runs is that the maximal sum of their exponents in a string of length n (notation: σ(n)) is linear in terms of n, see Kolpakov & Kucherov [START_REF] Kolpakov | On the sum of exponents of maximal repetitions in a word[END_REF]. It has applications to the analysis of various algorithms, such as computing branching tandem repeats: the linearity of the sum of exponents solves a conjecture of [START_REF] Gusfield | Simple and flexible detection of contiguous repeats using a suffix tree (preliminary version)[END_REF] concerning the linearity of the number of maximal tandem repeats and implies that all can be found in linear time. For other applications, we refer to [START_REF] Kolpakov | On the sum of exponents of maximal repetitions in a word[END_REF]. The proof that σ(n) < cn in Kolpakov and Kucherov's paper [START_REF] Kolpakov | On the sum of exponents of maximal repetitions in a word[END_REF] is very complex and does not provide any particular value for the constant c. A bound can be derived from the proof of Rytter [START_REF] Rytter | The number of runs in a string: Improved analysis of the linear upper bound[END_REF] but he mentioned only that the bound that he obtains is "unsatisfactory" (it seems to be 25 n). The first explicit bound 5.6 n for σ(n) was provided by Crochemore and Ilie [START_REF] Crochemore | Maximal repetitions in strings[END_REF], who claim that it could be improved to 2.9 n employing computer experiments. As for the lower bound on σ(n), no exact values were previously known and it was conjectured [START_REF] Kolpakov | On maximal repetitions in words[END_REF][START_REF] Kolpakov | On the sum of exponents of maximal repetitions in a word[END_REF] that σ(n) < 2n.

In this paper we provide an upper bound of 4.1 n on the maximal sum of exponents of runs in a string of length n and also a stronger upper bound of 2.5 n for the maximal sum of exponents of cubic runs in a string of length n. As for the lower bound, we bring down the conjecture σ(n) < 2n by providing an infinite family of binary strings for which the sum of exponents of runs is greater than 2.035 n.

Preliminaries

We consider words (strings) u over a finite alphabet Σ, u ∈ Σ * ; the empty word is denoted by ε; the positions in u are numbered from 1 to |u|. For u = u 1 u 2 . . . u m , let us denote by u[i . . j] a factor of u equal to u i . . . u j (in particular

u[i] = u[i . . i]). Words u[1 .
. i] are called prefixes of u, and words u[i . . |u|] suffixes of u.

We say that an integer p is the (shortest) period of a word u = u 1 . . . u m (notation: p = per(u)) if p is the smallest positive integer such that u i = u i+p holds for all 1 ≤ i ≤ mp. We say that words u and v are cyclically equivalent (or that one of them is a cyclic rotation of the other) if u = xy and v = yx for some x, y ∈ Σ * .

A run (also called a maximal repetition) in a string u is an interval [i .

. j] such that:

the period p of the associated factor u[i . . j] satisfies 2p ≤ ji + 1, -the interval cannot be extended to the right nor to the left, without violating the above property, that is,

u[i -1] = u[i + p -1] and u[j -p + 1] = u[j + 1].
A cubic run is a run [i . . j] for which the shortest period p satisfies 3p ≤ ji + 1.

For simplicity, in the rest of the text we sometimes refer to runs and cubic runs as to occurrences of the corresponding factors of u. The (fractional) exponent of a run is defined as (ji + 1)/p. For a given word u ∈ Σ * , we introduce the following notation:

ρ(u) and ρ cubic (u) are the numbers of runs and cubic runs in u resp.

σ(u) and σ cubic (u) are the sums of exponents of runs and cubic runs in u resp.

For a non-negative integer n, we use the same notations ρ(n), ρ cubic (n), σ(n) and σ cubic (n) to denote the maximal value of the respective function for a word of length n.

3 Lower bound for σ(n)

Tables 1 and 2 list the sums of exponents of runs for several words of two known families that contain very large number of runs: the words x i defined by Franek and Yang [START_REF] Franek | An asymptotic lower bound for the maximal number of runs in a string[END_REF] (giving the lower bound ρ(n) ≥ 0.927 n, conjectured for some time to be optimal) and the modified Padovan words y i defined by Simpson [START_REF] Simpson | Modified Padovan words and the maximum number of runs in a word[END_REF] (giving the best known lower bound ρ(n) ≥ 0.944575712 n). These values have been computed experimentally. They suggest that for the families of words x i and y i the maximal sum of exponents could be less than 2n. We show, however, a lower bound for σ(n) that is greater than 2n.

Theorem 1. There are infinitely many binary strings w such that σ(w) |w| > 2.035.

Proof. Let us define two morphisms φ : {a, b, c} → {a, b, c} and ψ : {a, b, c} → {0, 1} as follows:

φ(a) = baaba, φ(b) = ca, φ(c) = bca ψ(a) = 01011, ψ(b) = ψ(c) = 01001011
We define w i = ψ(φ i (a)). Table 3 4 Upper bounds for σ(n) and σ cubic (n)

In this section we utilize the concept of handles of runs as defined in [START_REF] Crochemore | On the maximal number of cubic runs in a string[END_REF]. The original definition refers only to cubic runs, but here we extend it also to ordinary runs. Let u ∈ Σ * be a word of length n. Let us denote by P = {p 1 , p 2 , . . . , p n-1 } the set of inter-positions in u that are located between pairs of consecutive letters of u. We define a function H assigning to each run v in u a set of some interpositions within v (called later on handles) -H is a mapping from the set of runs occurring in u to the set 2 P of subsets of P . Let v be a run with period p and let w be the prefix of v of length p. Let w min and w max be the minimal and maximal words (in lexicographical order) cyclically equivalent to w. H(v) is defined as follows: a) if w min = w max then H(v) contains all inter-positions within v, b) if w min = w max then H(v) contains inter-positions between consecutive occurrences of w min in v and between consecutive occurrences of w max in v.

Note that H(v) can be empty for a non-cubic-run v. Proofs of the following properties of handles of runs can be found in [START_REF] Crochemore | On the maximal number of cubic runs in a string[END_REF]:

1. Case (a) in the definition of H(v) implies that |w min | = 1.

2. H(v 1 ) ∩ H(v 2 ) = ∅ for any two distinct runs v 1 and v 2 in u.

To prove the upper bound for σ(n), we need to state an additional property of handles of runs. Let R(u) be the set of all runs in a word u, and let R 1 (u) and R ≥2 (u) be the sets of runs with period 1 and at least 2 respectively.

Lemma 1. If v ∈ R 1 (u) then σ(v) = |H(v)| + 1. If v ∈ R ≥2 (u) then ⌈σ(v)⌉ ≤ |H(v)| 2 + 3.
Proof. For the case of v ∈ R 1 (u), the proof is straightforward from the definition of handles. In the opposite case, it is sufficient to note that both words w k min and w k max for k = ⌊σ(v)⌋ -1 are factors of v, and thus

|H(v)| ≥ 2 • (⌊σ(v)⌋ -2).

⊓ ⊔

Now we are ready to prove the upper bound for σ(n). In the proof we use the bound ρ(n) ≤ 1.029 n on the number of runs from [START_REF] Crochemore | Towards a solution to the "runs" conjecture[END_REF].

Theorem 2. The sum of the exponents of runs in a string of length n is less than 4.1 n.

Proof. Let u be a word of length n. Using Lemma 1, we obtain:

v∈R(u) σ(v) = v∈R1(u) σ(v) + v∈R ≥2 (u) σ(v) ≤ v∈R1(u) (|H(v)| + 1) + v∈R ≥2 (u) |H(v)| 2 + 3 = v∈R1(u) |H(v)| + |R 1 (u)| + v∈R ≥2 (u) |H(v)| 2 + 3 • |R ≥2 (u)| ≤ 3 • |R(u)| + A + B/2, (1)

⊓ ⊔

A similar approach for cubic runs, this time using the bound of 0.5 n for ρ cubic (n) from [START_REF] Crochemore | On the maximal number of cubic runs in a string[END_REF], enables us to immediately provide a stronger upper bound for the function σ cubic (n).

Theorem 3. The sum of the exponents of cubic runs in a string of length n is less than 2.5 n.

Proof. Let u be a word of length n. Using same inequalities as in the proof of Theorem 2, we obtain:

v∈R cubic (u) σ(v) < 3 • |R cubic (u)| + n ≤ 3 • ρ cubic (n) + n ≤ 3 • 0.5 n + n = 2.5 n,
where R cubic (u) denotes the set of all cubic runs of u.

⊓ ⊔

b a b a a b a b a a b a b a a 1 Fig. 1 .

 11 Fig.1. An example of a word with two highlighted runs v1 and v2. For v1 we have w min1 = w max1 and for v2 the corresponding words are equal to b (a one-letter word). The inter-positions belonging to the sets H(v1) and H(v2) are pointed by arrows

  where A = v∈R1(u) |H(v)| and B = v∈R ≥2 (u) |H(v)|. Due to the disjointness of handles of runs (the second property of handles), A + B < n, and thus, A + B/2 < n. Combining this with (1), we obtain:v∈R(u) σ(v) < 3 • |R(u)| + n ≤ 3 • ρ(n) + n ≤ 3 • 1.029 n + n < 4.1 n.

Table 1 .

 1 Number of runs and sum of exponents of runs in Franek & Yang's [7] words xi.

	shows the sums of exponents of runs in words
	w i , computed experimentally.
	Clearly, for any word w = (w 8 ) k , k ≥ 1, we have
	σ(w) |w|	> 2.035.
		⊓ ⊔

Table 2 .

 2 Number of runs and sum of exponents of runs in Simpson's[START_REF] Simpson | Modified Padovan words and the maximum number of runs in a word[END_REF] modified Padovan words yi.

	i	|wi|	σ(wi) σ(wi)/|wi|
	1	31	47.10	1.5194
	2	119	222.26	1.8677
	3	461	911.68	1.9776
	4	1751	3533.34	2.0179
	5	6647	13498.20	2.0307
	6	25205	51264.37	2.0339
	7	95567	194470.30	2.0349
	8	362327	737393.11	2.0352
	9 1373693	2795792.39	2.0352
	10 5208071 10599765.15	2.0353

Table 3 .

 3 Sums of exponents of runs in words wi.