Universal entropy estimation via block sorting
Universal entropy estimation via block sorting
复制标题
DOI：
10.1109/tit.2004.830771
复制
发表时间：
2004-07-01
影响因子：
2.5
通讯作者：
Verdú, S
中科院分区：
文献类型：
--
作者：
Cai, HX;Kulkarni, SR;Verdú, S
在这篇通信中，我们给出了平稳遍历源的一个新的泛熵估计，证明了几乎必然收敛，并建立了有限字母表有限记忆源的收敛速度的一个上界。该算法的动机是使用Burrow-Wheeler块排序变换(BWT)进行数据压缩。通过利用BWT输出序列接近分段平稳无记忆信源的特性，我们可以分割输出序列并估计每个分段中的概率。实验结果表明，该算法的性能优于基于Lempel-Ziv(LZ)的字符串匹配算法。
In this correspondence, we present a new universal entropy estimator for stationary ergodic sources, prove almost sure convergence, and establish an upper bound on the convergence rate for finite-alphabet finite memory sources. The algorithm is motivated by data compression using the Burrows-Wheeler block sorting transform (BWT). By exploiting the property that the BWT output sequence is close to a piecewise stationary memoryless source, we can segment the output sequence and estimate probabilities in each segment. Experimental results show that our algorithm outperforms Lempel-Ziv (LZ) string-matching-based algorithms.