Restructuring Compressed Texts without Explicit Decompression

Details Restructuring Compressed Texts without Explicit Decompression Restructuring Compressed Texts without Explicit Decompression

2011-07-14

arxiv.org/abs/1107.2729v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the problem of {\em restructuring} compressed texts without explicit decompression. We present algorithms which allow conversions from compressed representations of a string $T$ produced by any grammar-based compression algorithm, to representations produced by several specific compression algorithms including LZ77, LZ78, run length encoding, and some grammar based compression algorithms. These are the first algorithms that achieve running times polynomial in the size of the compressed input and output representations of $T$. Since most of the representations we consider can achieve exponential compression, our algorithms are theoretically faster in the worst case, than any algorithm which first decompresses the string for the conversion.

Affiliated with

Also associated with

No associations

Rating

Restructuring Compressed Texts without Explicit Decompression 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 Restructuring Compressed Texts without Explicit Decompression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Restructuring Compressed Texts without Explicit Decompression will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-224772