Run Length Encoding Compression With Nested Level

Question

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?

Answer 1

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