Asymmetry in Ziv/Lempel '78 parsing
M. Cohn, Harald Andrés Helfgott · 2002
We the compare the number of phrases created by Ziv/Lempel '78 parsing of a binary sequence and of its reversal. We show that the two parsings can vary by a factor that grows at least as fast as the logarithm of the sequence length. We then show that under a suitable condition, the factor can even become polynomial, and argue that the condition may not be necessary.