Sorry, you need to enable JavaScript to visit this website.

Data Compression

Approximating Optimal Bidirectional Macro Schemes.

Ana Sofia Correia

Lempel-Ziv is an easy-to-compute member of a wide family of so-called macro schemes; it restricts pointers to go in one direction only. Optimal bidirectional macro schemes are NP-complete to find, but they may provide much better compression on highly repetitive sequences. We consider the problem of approximating optimal bidirectional macro schemes. We describe a simulated annealing algorithm that usually converges quickly. Moreover, in some cases, we obtain bidirectional macro schemes that are provably a 2-approximation of the optimal.

Paper Details

Authors:
Ana Sofia Correia
Luís M. S. Russo, Ana D. Correia, Gonzalo Navarro, Alexandre P. Francisco
Submitted On:
31 March 2020 - 4:25pm
Short Link:
Type:
Event:
Session:

Document Files

DCC-2020-Approximating_Optimal_Bidirectional_Macro_Schemes.pptx

(45)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[1] Luís M. S. Russo, Ana D. Correia, Gonzalo Navarro, Alexandre P. Francisco, "Approximating Optimal Bidirectional Macro Schemes.", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5083. Accessed: Jul. 14, 2020.
@article{5083-20,
url = {http://sigport.org/5083},
author = {Luís M. S. Russo; Ana D. Correia; Gonzalo Navarro; Alexandre P. Francisco },
publisher = {IEEE SigPort},
title = {Approximating Optimal Bidirectional Macro Schemes.},
year = {2020} }
TY - EJOUR
T1 - Approximating Optimal Bidirectional Macro Schemes.
AU - Luís M. S. Russo; Ana D. Correia; Gonzalo Navarro; Alexandre P. Francisco
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5083
ER -
Luís M. S. Russo, Ana D. Correia, Gonzalo Navarro, Alexandre P. Francisco. (2020). Approximating Optimal Bidirectional Macro Schemes.. IEEE SigPort. http://sigport.org/5083
Luís M. S. Russo, Ana D. Correia, Gonzalo Navarro, Alexandre P. Francisco, 2020. Approximating Optimal Bidirectional Macro Schemes.. Available at: http://sigport.org/5083.
Luís M. S. Russo, Ana D. Correia, Gonzalo Navarro, Alexandre P. Francisco. (2020). "Approximating Optimal Bidirectional Macro Schemes.." Web.
1. Luís M. S. Russo, Ana D. Correia, Gonzalo Navarro, Alexandre P. Francisco. Approximating Optimal Bidirectional Macro Schemes. [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5083

Grammar compression with probabilistic context-free grammar

Diptarama Hendrian

We propose a new approach for universal lossless text compression, based on grammar compression. In the literature, a target string T has been compressed as a context-free grammar G in Chomsky normal form satisfying L(G) = T. Such a grammar is often called a straight-line program (SLP). In this work, we consider a probabilistic grammar G that generates T, but not necessarily as a unique element of L(G). In order to recover the original text T unambiguously, we keep both the grammar G and the derivation tree of T from the start symbol in G, in compressed form.

Paper Details

Authors:
Diptarama Hendrian
Hiroaki Naganuma, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara, Naoki Kobayashi
Submitted On:
31 March 2020 - 2:53am
Short Link:
Type:
Event:
Presenter's Name:
Session:
Document Year:
Cite

Document Files

dcc_poster.pdf

(45)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[1] Hiroaki Naganuma, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara, Naoki Kobayashi, "Grammar compression with probabilistic context-free grammar", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5074. Accessed: Jul. 14, 2020.
@article{5074-20,
url = {http://sigport.org/5074},
author = {Hiroaki Naganuma; Diptarama Hendrian; Ryo Yoshinaka; Ayumi Shinohara; Naoki Kobayashi },
publisher = {IEEE SigPort},
title = {Grammar compression with probabilistic context-free grammar},
year = {2020} }
TY - EJOUR
T1 - Grammar compression with probabilistic context-free grammar
AU - Hiroaki Naganuma; Diptarama Hendrian; Ryo Yoshinaka; Ayumi Shinohara; Naoki Kobayashi
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5074
ER -
Hiroaki Naganuma, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara, Naoki Kobayashi. (2020). Grammar compression with probabilistic context-free grammar. IEEE SigPort. http://sigport.org/5074
Hiroaki Naganuma, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara, Naoki Kobayashi, 2020. Grammar compression with probabilistic context-free grammar. Available at: http://sigport.org/5074.
Hiroaki Naganuma, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara, Naoki Kobayashi. (2020). "Grammar compression with probabilistic context-free grammar." Web.
1. Hiroaki Naganuma, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara, Naoki Kobayashi. Grammar compression with probabilistic context-free grammar [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5074

Towards Better Compressed Representations

Michal Ganczorz

We introduce the problem of computing a parsing where each phrase is of length at most m and which minimizes the zeroth order entropy of parsing. Based on the recent theoretical results we devise a heuristic for this problem. The solution has straightforward application in succinct text representations and gives practical improvements. Moreover the proposed heuristic yields structure which size can be bounded both by |S|H_{m-1}(S) and by |S|/m(H_0(S) + ... + H_{m-1}(S)),where H_{k}(S) is the k-th order empirical entropy of S.

Paper Details

Authors:
Michal Ganczorz
Michał Gańczorz
Submitted On:
25 March 2020 - 1:11pm
Short Link:
Type:
Event:
Presenter's Name:
Paper Code:
Session:

Document Files

poster_dcc.pdf

(44)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[1] Michał Gańczorz, "Towards Better Compressed Representations", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5029. Accessed: Jul. 14, 2020.
@article{5029-20,
url = {http://sigport.org/5029},
author = {Michał Gańczorz },
publisher = {IEEE SigPort},
title = {Towards Better Compressed Representations},
year = {2020} }
TY - EJOUR
T1 - Towards Better Compressed Representations
AU - Michał Gańczorz
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5029
ER -
Michał Gańczorz. (2020). Towards Better Compressed Representations. IEEE SigPort. http://sigport.org/5029
Michał Gańczorz, 2020. Towards Better Compressed Representations. Available at: http://sigport.org/5029.
Michał Gańczorz. (2020). "Towards Better Compressed Representations." Web.
1. Michał Gańczorz. Towards Better Compressed Representations [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5029

Edge minimization in de Bruijn graphs

Uwe Baier

This paper introduces the de Bruijn graph edge minimization problem, which is related to the compression of de Bruijn graphs: find the order-k de Bruijn graph with minimum edge count among all orders. We describe an efficient algorithm that solves this problem. Since the edge minimization problem is connected to the BWT compression technique called "tunneling", the paper also describes a way to minimize the length of a tunneled BWT in such a way that useful properties for sequence analysis are preserved.

Paper Details

Authors:
Uwe Baier
Thomas Büchler, Enno Ohlebusch, Pascal Weber
Submitted On:
24 March 2020 - 5:56am
Short Link:
Type:
Event:
Presenter's Name:
Session:
Document Year:
Cite

Document Files

slides_dcc_20.pdf

(33)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[1] Thomas Büchler, Enno Ohlebusch, Pascal Weber, "Edge minimization in de Bruijn graphs", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5023. Accessed: Jul. 14, 2020.
@article{5023-20,
url = {http://sigport.org/5023},
author = {Thomas Büchler; Enno Ohlebusch; Pascal Weber },
publisher = {IEEE SigPort},
title = {Edge minimization in de Bruijn graphs},
year = {2020} }
TY - EJOUR
T1 - Edge minimization in de Bruijn graphs
AU - Thomas Büchler; Enno Ohlebusch; Pascal Weber
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5023
ER -
Thomas Büchler, Enno Ohlebusch, Pascal Weber. (2020). Edge minimization in de Bruijn graphs. IEEE SigPort. http://sigport.org/5023
Thomas Büchler, Enno Ohlebusch, Pascal Weber, 2020. Edge minimization in de Bruijn graphs. Available at: http://sigport.org/5023.
Thomas Büchler, Enno Ohlebusch, Pascal Weber. (2020). "Edge minimization in de Bruijn graphs." Web.
1. Thomas Büchler, Enno Ohlebusch, Pascal Weber. Edge minimization in de Bruijn graphs [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5023

Weighted Adaptive Huffman Coding

Dana Shapira

Huffman coding is known to be optimal in case the alphabet is known in advance, the set of codewords is fixed and each codeword consists of an integral number of bits. If one of these conditions is violated, optimality is not guaranteed.
In the {\it dynamic\/} variant of Huffman coding the encoder and decoder maintain identical copies of the model; at each position, the model consists of the frequencies of the elements processed so far.

Paper Details

Authors:
Dana Shapira
Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira
Submitted On:
24 April 2020 - 2:45pm
Short Link:
Type:
Event:
Session:
Document Year:
Cite

Document Files

Weighted_Adaptive_Huffman_Coding.pdf

(52)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[1] Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira, "Weighted Adaptive Huffman Coding", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5022. Accessed: Jul. 14, 2020.
@article{5022-20,
url = {http://sigport.org/5022},
author = {Aharon Fruchtman; Yoav Gross; Shmuel T. Klein; Dana Shapira },
publisher = {IEEE SigPort},
title = {Weighted Adaptive Huffman Coding},
year = {2020} }
TY - EJOUR
T1 - Weighted Adaptive Huffman Coding
AU - Aharon Fruchtman; Yoav Gross; Shmuel T. Klein; Dana Shapira
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5022
ER -
Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira. (2020). Weighted Adaptive Huffman Coding. IEEE SigPort. http://sigport.org/5022
Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira, 2020. Weighted Adaptive Huffman Coding. Available at: http://sigport.org/5022.
Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira. (2020). "Weighted Adaptive Huffman Coding." Web.
1. Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira. Weighted Adaptive Huffman Coding [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5022