1
$\begingroup$

I am studying about some compression methods, and I'm very interested in RLE Algorithms. But are there any Nested-Level RLE methods, such as:

ABABABCABABABC --> 3(AB)C3AB(C) --> 2(3(AB)C) ?

It's easily to decompress it by using some techniques like stack, but what is the most efficient way to compress it, any formal algorithms or how to evaluate that?

$\endgroup$
  • $\begingroup$ I think I'm expert in lossless data compression, and I've never seen idea of nested RLE before. My best guess that it doesn't pay its speed on real data. You are welcome to encode.ru/forums/2-Data-Compression forum where you can find some compression experts $\endgroup$ – Bulat Apr 23 at 5:05
2
$\begingroup$

Yes. The Sequitur algorithm could be viewed as doing more or less what you've asked for.

For instance, Sequitur would encode abababcabababc to the grammar

S → WW
T → ab
U → TT
V → UT
W → Vc

You can think of this as having your form. V is basically an encoding of 3(ab). W is basically an encoding of 3(ab)c. WW is basically an encoding of 2(W). So, the final grammar is equivalent to 2(3(ab)c) -- it is just a different way to write it. Sequitur writes the output as a context-free grammar, instead of using your notation, but its grammar is equivalent to the answer you were hoping for.


Here is the sequence of steps that Sequitur would use to reach that result.

First, we have the grammar

S → abababcabababc

The first digram encountered is ab, so it replaces that with a non-terminal:

S → TTTTcTTTc
T → ab

Then this becomes

S → UTcUTc
T → ab
U → TT

and then to

S → VcVc
T → ab
U → TT
V → UT

and then to

S → WW
T → ab
U → TT
V → UT
W → Vc

$\endgroup$
  • $\begingroup$ I wonder that could this algorithms provide the best method to compress data (in term of final string's length)? $\endgroup$ – Le Duong Tuan Anh Apr 24 at 6:44
  • $\begingroup$ @LeDuongTuanAnh, unlikely. Finding the best compression is NP-hard (or something), I think. $\endgroup$ – D.W. Apr 24 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.