Re-pair Achieves High-Order Entropy
Re-pair Achieves High-Order Entropy
复制标题
修复实现高阶熵
DOI：
10.1109/dcc.2008.79
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
L. Russo
中科院分区：
文献类型：
--
作者：
G. Navarro;L. Russo
RePair是J. Larsson和A. Moffat在1999年发明的一种基于字典的压缩方法[基于离线词典的压缩。 Proc。 IEEE，88（11）：1722-1732，2000]，现在缺乏效率分析。我们表明，对于任何k = o（logsigma n），re pair在大小sigma的字母上压缩一个序列t [1，n]至最多为2nhk + o（n log sigma）位，其中hk是经典的信息理论或经验K-th Order熵（在后者中，从序列统计数据推断出该模型）。
Re-pair is a dictionary-based compression method invented in 1999 by J. Larsson and A. Moffat [Off-line dictionary-based compression. Proc. IEEE, 88(11):1722-1732, 2000], lacking up to now an efficiency analysis. We show that re-pair compresses a sequence T[1,n] over an alphabet of size sigma to at most 2nHk + o(n log sigma) bits, for any k = o(logsigma n), where Hk is either the classical information-theory or the empirical k-th order entropy (in the latter, the model is inferred from the sequence statistics).