Энтропийное кодирование rANS или как написать собственный архиватор

[seven_hh]

Как-то в апреле 2018 или в июле создал архиватор для книг.
При размере исходника в 1,195,045 байт родной архиватор 7zip сделал архив в 386,588 байт.
Мой самописный сделал промежуточный в 605,624 байт и 7zip потом помог его сжать в 300,022 байт.

Своей цели я добился (хотел узнать возможно ли сделать архив ещё меньше) и на этом забросил. Так что разархиватора у меня нет, пруфоф тоже не дам.

[nsmcan]

Экий у Вас спортивный дядя на заглавной картинке! Аляксандра Рыгоравiча напоминает, однако… :)

[mwizard]

А как же сравнение с lzma, lz77, bzip2 и т.д.?

[Biga]

Ответил на аналогичный вопрос тут.

[Biga]

Возьмём для примера алгоритм Deflate, который находится внутри gzip. Deflate состоит из алгоритма lz77 и кодера Хаффмана. Так вот, Хаффмана можно заменить на rANS, и это даст заметный выигрыш.

Если хотите сравнить два архиватора на практике, посмотрите Zstandard. У zstd внутри используется FSE, а не rANS, но они очень похожи и выдают практически одинаковый результат. Популярных архиваторов с применением rANS пока не встречал, но можно найти неплохие экспериментальные варианты на форуме encode.ru.

Брать какой-нибудь готовый архиватор и заменять в нём Хаффмана (или арифметический кодер) на rANS чисто в целях эксперимента — достаточно трудоёмкая задача. Может кто-нибудь другой за это возьмётся ради интереса.

[a5b]

У gzip (deflate, он же pkzip 2) и zstd в основе вроде бы один и тот же алгоритм lz77, однако в середине 1990-х памяти в компьютерах было сравнительно мало и в формат deflate заложено ограничение окна (distance) в 32 КБ (rfc1951 3.2.5.; ""deflate" format limits distances to 32K bytes and lengths to 258 bytes", https://www.zlib.net/zlib_tech.html "(but no more than the maximum size of 32 KB, obviously)"). Поэтому если уж ломать совместимость, то лучше сразу использовать zstd c более адекватными размерами окна для нынешней эпохи — "The minimum Window_Size is 1 KB. The maximum Window_Size is (1<<41) + 7*(1<<38) bytes, which is 3.75 TB." из https://tools.ietf.org/id/draft-kucherawy-dispatch-zstd-00.html#comp_window_descr
http://fastcompression.blogspot.com/2015/01/zstd-stronger-compression-algorithm.html "Current default window size is 512 KB, but this value will be configurable, from very small (KB) to very large (GB)"

Разные реализации lz77 можно сравнить в таблице http://mattmahoney.net/dc/text.html (поиском по "LZ77")

FSE в zstd только на минимальных уровнях, чаще будет использоваться хаффман: 2.4. Entropy Encoding "Two types of entropy encoding are used by the Zstandard format: FSE, and Huffman coding." https://tools.ietf.org/id/draft-kucherawy-dispatch-zstd-00.html#rfc.section.2.4

[sci_nov]

спасибо за статью! делал нормализацию частот, оказалось намного проще alias-ов.