Как я создал архиватор из задачки с техсобеса: сжатие файлов с помощью RLE

[ek1224]

BWT и MTF – вспомогательные инструменты-катализаторы, которые не меняют размер блоков, но переставляют в них байты таким образом, что их становится легче сжимать.

Это не совсем верно. Все циклические сдвиги строки S при проведении BWT образуют одинаковую таблицу. А это значит, что для того, чтобы совершить обратное BWT преобразование, необходимо либо пометить начало/конец исходной строки специальным символом, либо записать индекс исходной строки в получившейся таблице. Т.е. BWT не только не сжимает данные, но и делает их чуточку больше.

А статья действительно классная, побольше бы таких на хабре.

[NikolayTheSquid]

Подход глубоко вторичный зато работает плохо 👍

[haqreu]

Проблема RLE в том, что в реальной жизни редко встретишь данные вида «АААБВВВВ».

На синтетических картинках (например, скриншотах) очень даже встречается, посему rle широко использовалось, например, в форматах картинок типа .tga или .pcx.

[zuek]

Да, мне тоже сразу вспомнился формат .pcx - в школьные годы даже написал на Turbo Pascal (с небольшими ассемблерными вставками) "графический редактор" с поддержкой pcx, правда, кодирование 16-цветных режимов я не осилил, поэтому реализовал только монохромный режим и 256 цветов - они работали через прямое обращение к видеопамяти... это была моя "курсовая" на УПК.

[ciuafm]

Самый суровый РЛЕ алгоритм был в TIFF group4. Сканированный А4 в один бит на точку занимал 10-20 КБ и что главное оставался читаемым.

[gchebanov]

У меня получилось сжать переведённую "Войну и Мир" обычным RLE вне зависимости от числа повторений, попробуйте Энтропийное кодирование для потока битовых флагов.

p=2.45%
theoretical limit=66453.89161197383
rANS= 66477
rANS inefficiency=0.03%
origin=3202320
result=3190338
factor=0.37%

Вот код. Вроде бы и немного (21+18 строк), но он довольно таки ёмок на математику, легко допустить ошибку. Если будет несложно дополните статью, так она станет гораздо информативнее.

[sentenzo]

Ого! Большое спасибо за наводку.

Посмотрю-поизучаю как будет время.

[Dima4ka]

Can we do PackBits with fixed but smaller-than-byte counters? If we know that most of the time counter will fit in, say, 4 bits?

[sentenzo]

Интересная мысль. Не проверял.

4 бита на счётчик в PackBits будет оптимально, если дина повторов И длина промежутков между ними находятся в интервале (один бит уйдёт на знак).

В предобработанных данных появляются очень длинные повторы (сотни символов), и на их кодирование затраты увеличатся. На вскидку почему-то кажется, что оптимум должен быть ближе к 6 битам (когда значения счётчиков не превосходят 32), но нужно проверять.