论文标题
近似最佳双向宏观方案
Approximating Optimal Bidirectional Macro Schemes
论文作者
论文摘要
Lempel-Ziv是一个易于计算的所谓宏观方案家族的成员；它限制了指针只能朝一个方向前进。最佳双向宏观方案是NP完整的，但它们可能会在高度重复的序列上提供更好的压缩。我们考虑近似最佳双向宏观方案的问题。我们描述了一种模拟的退火算法，通常会迅速收敛。此外，在某些情况下，我们获得了双向宏观方案，这些宏观方案可证明是最佳的2-焦点。我们在许多人工重复文本上测试了算法，并验证它在实践中是有效的，并且优于lempel-ziv，有时会宽大。
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. We test our algorithm on a number of artificial repetitive texts and verify that it is efficient in practice and outperforms Lempel-Ziv, sometimes by a wide margin.
