Комментарии 9
BWT и MTF – вспомогательные инструменты-катализаторы, которые не меняют размер блоков, но переставляют в них байты таким образом, что их становится легче сжимать.
Это не совсем верно. Все циклические сдвиги строки S при проведении BWT образуют одинаковую таблицу. А это значит, что для того, чтобы совершить обратное BWT преобразование, необходимо либо пометить начало/конец исходной строки специальным символом, либо записать индекс исходной строки в получившейся таблице. Т.е. BWT не только не сжимает данные, но и делает их чуточку больше.
А статья действительно классная, побольше бы таких на хабре.
Подход глубоко вторичный зато работает плохо 👍
Проблема RLE в том, что в реальной жизни редко встретишь данные вида «АААБВВВВ».
На синтетических картинках (например, скриншотах) очень даже встречается, посему rle широко использовалось, например, в форматах картинок типа .tga или .pcx.
Да, мне тоже сразу вспомнился формат .pcx - в школьные годы даже написал на Turbo Pascal (с небольшими ассемблерными вставками) "графический редактор" с поддержкой pcx, правда, кодирование 16-цветных режимов я не осилил, поэтому реализовал только монохромный режим и 256 цветов - они работали через прямое обращение к видеопамяти... это была моя "курсовая" на УПК.
Самый суровый РЛЕ алгоритм был в TIFF group4. Сканированный А4 в один бит на точку занимал 10-20 КБ и что главное оставался читаемым.
У меня получилось сжать переведённую "Войну и Мир" обычным RLE вне зависимости от числа повторений, попробуйте Энтропийное кодирование для потока битовых флагов.
p=2.45%
theoretical limit=66453.89161197383
rANS= 66477
rANS inefficiency=0.03%
origin=3202320
result=3190338
factor=0.37%
Вот код. Вроде бы и немного (21+18 строк), но он довольно таки ёмок на математику, легко допустить ошибку. Если будет несложно дополните статью, так она станет гораздо информативнее.
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?
Интересная мысль. Не проверял.
4 бита на счётчик в PackBits будет оптимально, если дина повторов И длина промежутков между ними находятся в интервале ![[4;8]](https://habrastorage.org/getpro/habr/upload_files/1ef/169/d06/1ef169d06ddb1d1018219daf86c772f8.svg)
(один бит уйдёт на знак).
В предобработанных данных появляются очень длинные повторы (сотни символов), и на их кодирование затраты увеличатся. На вскидку почему-то кажется, что оптимум должен быть ближе к 6 битам (когда значения счётчиков не превосходят 32), но нужно проверять.
Как я создал архиватор из задачки с техсобеса: сжатие файлов с помощью RLE