loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Data Compression Conference (dcc 2008)
March 25-March 27
ISBN: 978-0-7695-3121-2
ASCII Text
x 
 
Gonzalo Navarro, Lu? Russo, "Re-pair Achieves High-Order Entropy," Data Compression Conference, pp. 537, Data Compression Conference (dcc 2008), 2008.
 
 
BibTex
x
 
@article{ 10.1109/DCC.2008.79,
author = {Gonzalo Navarro and Lu? Russo},
title = {Re-pair Achieves High-Order Entropy},
journal ={Data Compression Conference},
volume = {0},
year = {2008},
issn = {1068-0314},
pages = {537},
doi = {http://doi.ieeecomputersociety.org/10.1109/DCC.2008.79},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Data Compression Conference
TI - Re-pair Achieves High-Order Entropy
SN - 1068-0314
SP
EP
A1 - Gonzalo Navarro,
A1 - Lu? Russo,
PY - 2008
KW - empirical entropy
KW - grammar-based compression
VL - 0
JA - Data Compression Conference
ER -
 
Re-Pair is a dictionary-based compression method invented in 1999 by Larssonand Moffat. Although its practical performance has been established through experiments, the method has resisted all attempts of formal analysis. In thispaper we show that Re-Pair compresses a sequence T[1,n] over an alphabet ofsize $\sigma$ and k-th order entropy H_k, to at most 2nH_k+o(n\log\sigma)bits, for any k=o(log_sigma n).
Index Terms:
empirical entropy, grammar-based compression
Citation:
Gonzalo Navarro, Lu? Russo, "Re-pair Achieves High-Order Entropy," dcc, pp.537, Data Compression Conference (dcc 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.