Очень меня поразил тот факт, что внутри очень эффективного архиватора bzip2 работает алгоритм RLE. Да, после очень хитрых перестановок данных, но RLE!

Это очень простое семейство алгоритмов сжатия, с которым я познакомился ещё в то время, когда у меня был «Спектрум».

У него может быть много разных реализаций, но та, что я тогда программировал, выглядела следующим образом.

Последовательности одинаковых значений мы кодируем как один и тот же байт, записанный дважды, плюс счётчик — сколько таких байтов надо дописать; остальное оставляем как есть.

Например:

01 02 03 03 03 03 03 03 03 04 04 04 → 01 02 03 03 05 04 04 01

Как я уже написал, могут быть варианты. Например, можно счётчик делать больше, чем один байт или записывать количество повторений около каждого байта, всё зависит от характера сжимаемых данных, но суть плюс-минус одна и та же.

И как-то похожий простой алгоритм трудится внутри bzip2! Мне кажется, этому нельзя не изумиться!