Lempel-Ziv Factorization Powered by Space Efficient Suffix Trees

摘要

We show that both the Lempel–Ziv-77 and the Lempel–Ziv-78 factorization of a text of length n on an integer alphabet of size $$sigma $$ σ can be computed in $$mathop {}mathopen {}mathcal {O}mathopen {}left( nright) $$ O n time with either $$mathop {}mathopen {}mathcal {O}mathopen {}left( n lg sigma right) $$ O n lg σ bits of working space, or $$(1+epsilon ) n lg n + mathop {}mathopen {}mathcal {O}mathopen {}left( nright) $$ ( 1 + ϵ ) n lg n + O n bits (for a constant $$epsilon >0$$ ϵ > 0 ) of working space (including the space for the output, but not the text).