Комментарии 4
BWT и MTF – вспомогательные инструменты-катализаторы, которые не меняют размер блоков, но переставляют в них байты таким образом, что их становится легче сжимать.
Это не совсем верно. Все циклические сдвиги строки S при проведении BWT образуют одинаковую таблицу. А это значит, что для того, чтобы совершить обратное BWT преобразование, необходимо либо пометить начало/конец исходной строки специальным символом, либо записать индекс исходной строки в получившейся таблице. Т.е. BWT не только не сжимает данные, но и делает их чуточку больше.
А статья действительно классная, побольше бы таких на хабре.
Подход глубоко вторичный зато работает плохо 👍
Проблема RLE в том, что в реальной жизни редко встретишь данные вида «АААБВВВВ».
На синтетических картинках (например, скриншотах) очень даже встречается, посему rle широко использовалось, например, в форматах картинок типа .tga или .pcx.
Самый суровый РЛЕ алгоритм был в TIFF group4. Сканированный А4 в один бит на точку занимал 10-20 КБ и что главное оставался читаемым.
Как я создал архиватор из задачки с техсобеса: сжатие файлов с помощью RLE