Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding

Details Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding

2012-04-25

arxiv.org/abs/1204.5524v1

Computer Science

Data Structures and Algorithms

Scientific paper

We propose a new approach for calculating the Lempel-Ziv factorization of a text efficiently, based on run length encoding (RLE). We present a conceptually simple off-line algorithm based on a variant of suffix arrays, as well as an on-line algorithm based on a variant of directed acyclic word graphs (DAWGs). Both algorithms run in $O(N+n\log n)$ time and O(n) extra space, where $N$ is the size of the text, $n\leq N$ is the number of RLE factors. The time dependency on $N$ is only in the conversion of the text to RLE, which can be computed very efficiently in O(N) time and O(1) extra space. When the text is compressible via RLE, i.e., $n = o(N)$, our algorithms are, to the best of our knowledge, the first algorithms which require only o(N) extra space while running in $o(N\log N)$ time.

Affiliated with

Also associated with

No associations

Rating

Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-137247