On the Approximation Ratio of LZ-End to LZ77
On the Approximation Ratio of LZ-End to LZ77
复制标题
关于LZ-End与LZ77的近似比
DOI：
10.1007/978-3-030-86692-1_10
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Takumi Ideue;Takuya Mieno;Mitsuru Funakoshi;Yuto Nakashima;Shunsuke Inenaga;Masayuki Takeda
Lempel-Ziv分解族是一种研究得很好的弦结构。LZ-End分解是实现更快提取任何子字符串的家族成员（Kreft & Navarro, TCS 2013）。LZ-End分解的一个有趣之处是LZ-End和LZ77分解的大小之间可能存在的差异。他们还展示了LZ-End短语数量与LZ77短语数量的近似比值渐近于2的字符串族。然而，这些字符串的字母表大小是无限的。本文分析了倍周期序列的LZ-End分解。我们还证明了对于二进制字母表，周期加倍序列的近似比值渐近于2。
A family of Lempel-Ziv factorizations is a well-studied string structure. The LZ-End factorization is a member of the family that achieved faster extraction of any substrings (Kreft & Navarro, TCS 2013). One of the interests for LZ-End factorizations is the possible difference between the size of LZ-End and LZ77 factorizations. They also showed families of strings where the approximation ratio of the number of LZ-End phrases to the number of LZ77 phrases asymptotically approaches 2. However, the alphabet size of these strings is unbounded. In this paper, we analyze the LZ-End factorization of the period-doubling sequence. We also show that the approximation ratio for the period-doubling sequence asymptotically approaches 2 for the binary alphabet.