Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/978-3-030-86692-1_10 | SPIRE |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takumi Ideue | 1 | 0 | 0.34 |
| Takuya Mieno | 2 | 4 | 3.48 |
| Mitsuru Funakoshi | 3 | 1 | 2.06 |
| Yuto Nakashima | 4 | 57 | 19.52 |
| Shunsuke Inenaga | 5 | 595 | 79.02 |
| Masayuki Takeda | 6 | 902 | 79.24 |