# Run Length Encoding Compression With Nested Level

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?

• 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 – Bulat Apr 23 '19 at 5:05

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

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