Author name cluster

Alessio Langiu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2018 Journal Article

On optimal parsing for LZ78-like compressors

Salvatore Aronica
Alessio Langiu
Francesca Marzi
Salvatore Mazzola
Filippo Mignosi

Flexible parsing algorithm, a two-steps-greedy parsing algorithm for text factorisation, has been proved to be an optimal parsing for LZ78-like compressors in the case of constant-cost phrases [1, 2]. Whilst in early implementations of LZ78-like compressors the phrases have constant cost, in common modern implementations the cost of the k-th phrase is ⌈ log 2 ⁡ k + C ⌉ where C is a real constant [3, 4]. Indeed we show examples where Flexible parsing is not optimal under the above more realistic setting. In this paper we prove that, under the assumption that the cost of a phrase is block-wise constant and non-decreasing, the Flexible parsing is almost optimal. For almost optimal we mean that, for any text T, the difference between the sizes of the compressed text obtained by using a Flexible parsing and an optimal parsing is bounded by the maximal cost of a phrase in T, i. e. it is logarithmic in practical cases. Furthermore we investigate how an optimal parsing, and hence an almost optimal parsing, affects the rate of convergence to the entropy of LZ78-like compressors. We discuss some experimental results considering the ratio between the speed of convergence to the entropy of compressors with and without an optimal parsing. This ratio presents a kind of wave effect that increases as the entropy of a memoryless source decreases but it seems always to slowly converge to one. According to the theory, this wave can be a tsunami for some families of highly compressible strings and, although the optimal (and the almost optimal) parsing does not improve the asymptotical speed of convergence to the entropy, it can improve compression ratio, and hence the decoding speed, in many practical cases.

Details DOI

TCS Journal 2016 Journal Article

Abelian powers and repetitions in Sturmian words

Gabriele Fici
Alessio Langiu
Thierry Lecroq
Arnaud Lefebvre
Filippo Mignosi
Jarkko Peltomäki
Élise Prieur-Gaston

Richomme, Saari and Zamboni (2011) [39] proved that at every position of a Sturmian word starts an abelian power of exponent k for every k > 0. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period m starting at a given position in any Sturmian word of rotation angle α. By considering all possible abelian periods m, we recover the result of Richomme, Saari and Zamboni. As an analogue of the critical exponent, we introduce the abelian critical exponent A ( s α ) of a Sturmian word s α of angle α as the quantity A ( s α ) = lim sup k m / m = lim sup k m ′ / m, where k m (resp. k m ′ ) denotes the maximum exponent of an abelian power (resp. of an abelian repetition) of abelian period m (the superior limits coincide for Sturmian words). We show that A ( s α ) equals the Lagrange constant of the number α. This yields a formula for computing A ( s α ) in terms of the partial quotients of the continued fraction expansion of α. Using this formula, we prove that A ( s α ) ≥ 5 and that the equality holds for the Fibonacci word. We further prove that A ( s α ) is finite if and only if α has bounded partial quotients, that is, if and only if s α is β-power-free for some real number β. Concerning the infinite Fibonacci word, we prove that: i) The longest prefix that is an abelian repetition of period F j, j > 1, has length F j ( F j + 1 + F j − 1 + 1 ) − 2 if j is even or F j ( F j + 1 + F j − 1 ) − 2 if j is odd, where F j is the jth Fibonacci number; ii) The minimum abelian period of any factor is a Fibonacci number. Further, we derive a formula for the minimum abelian periods of the finite Fibonacci words: we prove that for j ≥ 3 the Fibonacci word f j, of length F j, has minimum abelian period equal to F ⌊ j / 2 ⌋ if j = 0, 1, 2 mod 4 or to F 1 + ⌊ j / 2 ⌋ if j = 3 mod 4.

Details DOI

TCS Journal 2016 Journal Article

Order-preserving indexing

Maxime Crochemore
Costas S. Iliopoulos
Tomasz Kociumaka
Marcin Kubica
Alessio Langiu
Solon P. Pissis
Jakub Radoszewski
Wojciech Rytter

Kubica et al. [33] and Kim et al. [29] introduced order-preserving pattern matching: for a given text the goal is to find its factors having the same ‘shape’ as a given pattern. Known results include a linear-time algorithm for this problem (in case of polynomially-bounded alphabet) and a generalization to multiple patterns. We propose an index that enables order-preserving pattern matching queries in time proportional to pattern length. The index can be constructed in O ( n log ⁡ log ⁡ n ) expected time or in O ( n log 2 ⁡ log ⁡ n / log ⁡ log ⁡ log ⁡ n ) worst-case time. It is an incomplete order-preserving suffix tree which may miss a single edge label at each branching node. For most applications such incomplete suffix trees provide the same functional power as the complete ones. We show a number of their applications, including computation of longest common factors, longest previously occurring factors and squares in a string in the order-preserving setting. We also give an O ( n log ⁡ n ) -time algorithm constructing complete order-preserving suffix trees.

Details DOI

TCS Journal 2014 Journal Article

Note on the greedy parsing optimality for dictionary-based text compression

Maxime Crochemore
Alessio Langiu
Filippo Mignosi

Dynamic dictionary-based compression schemes are the most daily used data compression schemes since they appeared in the foundational paper of Ziv and Lempel in 1977, commonly referred to as LZ77. In dynamic setting, LZ77 considers a portion of the previous text as a dictionary and it uses a greedy approach to select, at each step, the longest match between the text and the dictionary. Compression is achieved by replacing matches with encoded dictionary pointers. LZ77 is the base of gzip, zip, rar, 7zip and many others compression software. All these compression schemes use variants of the greedy approach to parse (or factorise) the text into dictionary phrases. Greedy parsing optimality with respect to the number of phrases was proved by Storer et al. (1982) for unbounded LZ77-based dictionaries and by Cohn et al. (1996) for static suffix-closed dictionaries. The optimality of the greedy parsing was never proved for bounded size dictionary which is actually required by all of these practical schemes. In this article, we define the suffix-closed property for dynamic dictionaries, and we show that LZ77-based compression schemes, including the bounded dictionary variants, satisfy this property. Under this condition we prove the optimality of the greedy parsing as a variant of the proof by Cohn et al.

Details DOI