Does this compression method already exist?

[Lasse Reinhold]

I was wondering if this compression method already exists:

If we have a sequence of bytes, we translate them into offsets pointing backwards at the nearest occurence of the same byte (kind of like in normal LZ compression).

For example, following sequence:

...
...
48
69
0
132
69
69
132
48

could translate into:

...
...
129
6627
9
150
3
1
3
7

In the result, frequent bytes turn into smaller numbers which can be stored in less bits - just like in Huffman. Infrequent bytes can turn into numbers larger than 255.

Compared to Huffman, you avoid building a huffman tree and the method also adapts to changes in frequency through the data.

I've tested it in practise with mixed results on different kinds of data...

For now, I just wanted to know if it was already existing

[Bulat Ziganshin]

move-to-front will be better, anyway

[Lasse Reinhold]

But isn't move-to-front slow at encoding?

This implementation is just O(n) for encoding.

[Matt Mahoney]

Very interesting. That is LZ77 with the match length fixed at 1.
If you remove the duplicates then that is move to front encoding, which has a shorter encoding. Then if you do a Burrows-Wheeler transform first, you get very good compression (although I don't use MTF in BBB. I use a fast adaptive order 0 model and arithmetic coding).

Also, symbol ranking compressors use MTF (srank, sr2), but you keep a separate list in each order 3 or 4 context, and the list is short, only the last 3 distinct values. The other bytes are modeled in a lower order context. This keeps it fast, and also it doesn't help compression much to have a longer list. In sr2 I model the other values in an order 1 context and arithmetic code. Compression speed is about like zip -9 but compression is 5-20% better for text. However, decompression time is about the same as compression.
http://cs.fit.edu/~mmahoney/compression/#sr2

srank uses a trick to speed up MTF. First it models the last 3 values in an order 3 context, then it models the remaining bytes in an order 0 context in a pseudo-MTF queue. Instead of moving to the front, it swaps with a randomly picked byte about half way to the front. To make this fast, it maintains an index mapping bytes to queue location. srank uses a fixed Huffman code and is about twice as fast as sr2, although the compression is not very good. Of course srank is very old and it was designed when speed depended more on number of instructions (especially multiplication) instead of memory speed and cache locality.

[giorgiotani]

Which models of data you found are compressed better and worser after that coding?
Analogic data compression filed comes to mind; the method seem good for being applied after a differential filtering of the input (simplest example, each byte is coded as the difference with the previous byte, if samples are coded as bytes) since on data from analogic sources (images, audio...) this tend to leave a quite repetitive patters since deta values are related each other too.
IMHO this coding would do a better job on this type of input after a differential filtering stage (just an idea, I've not tested it)