Новый вариант

Иван предложил интересную идею, как ускорить процесс арифметического сжатия. Долго я ломал голову, как бы его оптимальней реализовать. В конце концов получилось, сейчас поделюсь результатами, а вот детали реализации чуть позже, скорее всего когда вернусь из поездки. Там интересный алгоритм получается.

Итак, сжимал я большой текстовый файл, самый большой, что смог найти в своей свалке на компьютере.
Почему текстовый файл? Потому что я хочу сравнить, какой вариант сжатия эффективнее для текстовых данных в различных представлениях: на 8 или 16-битном алфавите?
Мои грубые прикидки на основе кода Хаффмана вроде показывают, что сжатие с 16-битным алфавитом всегда как минимум не хуже, а на 16-битных текстовых данных (2-байтный Unicode) всегда лучше. Но и медленнее. Мне любопытно, как будет себя в этом смысле вести арифметический кодек.
Но всё это будет как-нибудь потом.

Пока что результаты. Коэффициент сжатия русскоязычного текста оказался примерно 1.6, что очень неплохо, я считаю, для чисто энтропийного сжатия. Если перед этим пройтись по тексту словарным сжатием, то получится очень может получится очень достойный вариант.

В первую очередь я оттестировал свой вариант, смесь двух таблиц: с чистыми частотами встреч символов и с накоплением.
Скорость сжатия оказалась 5.4 МиБ/c, скорость распаковки 1.3 МиБ/с. Столь большая разница связана с тем, что при распаковке нам нужно иметь готовую всю таблицу частот с накоплением, поэтому оптимизация с их частичным расчетом тут не прокатывает.
Зато данные в таблице с накоплением находятся в отсортированном порядке, поэтому использование двоичного поиска вместо линейного сразу улучшило результат распаковки: 2 МиБ/с.

После чего я протестировал вариант без отдельной таблицы с частотами с накоплениями. Расчет был на то, что таблица обычных частот (без накопления) в два раза меньше по размеру, чем с накоплением, поэтому за счет уменьшения количества записей в память возможно производительность улучшиться.
Но это предположение не оправдалось. Сжатие без частот с накоплением дало всего лишь 3.9 МиБ/с, поэтому делать вариант распаковки даже не стал, как бесперспективный.

Ну а теперь с результаты работы программы с использованием пирамидальной структуры, предложенной Иваном: сжатие – 7.5, распаковка – 4.6 МиБ/с. Соответственно, прирост в 1.4 раза для распаковки и в 2.2 раза для сжатия! Что ж, очень неплохо вышло.
Интересно, оптимизировав на ассемблере, смогу ли выйти за 20 МиБ/с? Ах да, все замеры выполнял на своем стандартном PileDriver FX-4350.

Еще надо попробовать потестить на бинарных данных, вдруг какой глюк вылезет с символами #0 или #255.

Из любопытного: более медленный метод сжимает чуть лучше быстрого. Дело в том, что точность у него чуть меньше, поэтому приходится на больших данных частоты делить на два во избежания переполнения. В силу этого модель более адаптивна, и если в разных частях файла частоты распределения символов отличаются, то она даст лучшей результат, что и случилось.
Впрочем, для того, что бы получить сравнимый эффект более быстрым методом, можно сжимать данные не целиком, а сравнительно небольшими блоками, частично огрубляя модель данных (распределение частоты символов) при переходе от блока к блоку.

Дилемма

Лежит у меня старенький модуль, реализующий арифметическое кодирование. Что-то захотел довести его до ума и максимально оптимизировать. Непонятно зачем, но хочется.

Одно из узких мест такого сжатия – поддержка частоты встречи символов в случае использования адаптивной модели. Собственно, поддержка именно таблицы частот банальна, но алгоритму нужны частоты нарастающим итогом.
То бишь, если у нас алфавит из трех символов A, B, C, каждый из которых встречается 3, 5, 2 раза (это собственно и есть таблица частот), то для алгоритма нужно вот так: 3, 8, 10.

В исходном алгоритме, который я взял в качестве основы, использовались 16-битные беззнаковые целые. Достаточно быстрая реализация, но на больших объемах данных возникало переполнения таблицы частот, поэтому когда частота достигала максимально возможного значения, вся таблица просто делилась на два, что в общем, не очень эффективно. Это гарантированно происходило каждые 65536 символов.

Для решения этой проблемы я заменил 16-битное целое на 32-битное, что позволило просто забыть про деление на два, если не сжимать данные размером больше 4 ГиБ.
С другой стороны, при добавлении каждого очередного символа приходилось пересчитывать достаточно большую таблицу частот, хоть зачастую и не полностью.

В результате сейчас у меня две идеи: хранить в памяти только классическую таблицу частот, а нарастающий итог рассчитывать каждый раз при добавлении очередного символа. Плюсы: снижается количество операций с памятью, так как таблицу частот (без нарастающего итога) можно сделать 16-битной, иногда нормируя ее делением на 2 (но не каждые 65536 символов, реже) и избежать обильной записи в память.
Минус: для расчета нарастающего итога придется суммировать всю таблицу до нужно символа.

Вторая идея состоит в том, что бы хранить все же обе таблицы, одновременно запоминая то место, где нарастающий итог уже посчитан верно. Поэтому при расчете нарастающего итога для нового символа можно будет пересчитывать не всю таблицу, а только небольшую часть, надеюсь, гораздо меньшую, чем в первоначальном варианте.Минус здесь следующий: придется все же выполнять на каждой итерации достаточно много записей в память, хоть и не так много, как в моем первоначальном варианте.

На текущий момент у меня есть подозрение, что первая идея хороша для коротких алфавитов. Наверное, для 8-битного и меньше она будет оптимальна. А вот для длинных алфавитов, видимо, интереснее второй вариант.

Но пока до конца не уверен. Надо будет потестить что ли разные варианты.