Иван предложил интересную идею, как ускорить процесс арифметического сжатия. Долго я ломал голову, как бы его оптимальней реализовать. В конце концов получилось, сейчас поделюсь результатами, а вот детали реализации чуть позже, скорее всего когда вернусь из поездки. Там интересный алгоритм получается.
Итак, сжимал я большой текстовый файл, самый большой, что смог найти в своей свалке на компьютере.
Почему текстовый файл? Потому что я хочу сравнить, какой вариант сжатия эффективнее для текстовых данных в различных представлениях: на 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.
Из любопытного: более медленный метод сжимает чуть лучше быстрого. Дело в том, что точность у него чуть меньше, поэтому приходится на больших данных частоты делить на два во избежания переполнения. В силу этого модель более адаптивна, и если в разных частях файла частоты распределения символов отличаются, то она даст лучшей результат, что и случилось.
Впрочем, для того, что бы получить сравнимый эффект более быстрым методом, можно сжимать данные не целиком, а сравнительно небольшими блоками, частично огрубляя модель данных (распределение частоты символов) при переходе от блока к блоку.
Спасибо за реализацию и тестирование. Буду ждать деталей :)))
ОтветитьУдалить> на 8 или 16-битном алфавите
Я правильно понимаю что Вы пока протестировали только 8-ми битный алфавит?
> 16-битных текстовых данных (2-байтный Unicode) всегда лучше
16-битный Unicode так себе формат для хранения я бы не стал на нем фокусироваться, по мне так он скорее мертв чем жив :))) Изначально придумали UCS-2 (фиксированные 2 байта), но потом осознали что его не хватает для всех символов, тогда его расширили до UTF-16, где один символ занимает 2 или 4 байта. В итоге UTF-16 ничем не лучше UTF-8: ни тот ни другой не позволяют найти смещение символа в байтах по индексу символа за константное время, но UTF-16 чаще занимает больше места чем UTF-8. Я бы именно на UTF-8 ориентировался. А с ним не все так однозначно при 2-байтном размере словаря: символ может занимать от 1 до 4 байт соответственно 2 байтная разбивка может проходить не по границам символов. Хотя так наверное даже интереснее :)))
> поэтому оптимизация с их частичным расчетом тут не прокатывает.
Вроде все еще можно частично расчитывать:
1. Мы знаем индекс последнего символа с правильно рассчитанной частотой (это последний распакованный символ)
2. Сравниваем его с требуемой частотой, если требуемая частота меньше, то бинарным поиском находим символ в левой части массива
3. А если больше то считаем итоговые частоты следующих символов пока не наберем нужную частоту.
> смогу ли выйти за 20 МиБ/с?
Я в Вас верю :)))
> Еще надо попробовать потестить на бинарных данных
Да было бы интересно, дело в том что на тексте алгоритм частичного расчета частоты наверное в несколько более выгодных условиях: текстовые символы идут в основном близко друг другу, тогда как алгоритм на дереве этим никак не пользуется.
Еще я тут подумал что сложность алгоритма на дереве не зависит от размера словаря: увеличиваем словарь с 1 до 2 байт, дерево становится в 2 раза глубже, но ведь и читаем в 2 раза больше байтов из потока. Но это я забегаю вперед...
> Я правильно понимаю что Вы пока протестировали только 8-ми битный алфавит?
ОтветитьУдалитьДа, совершенно верно.
> Изначально придумали UCS-2 (фиксированные 2 байта), но потом осознали что его не хватает для всех символов,
> тогда его расширили до UTF-16
Желание объять необъятное )
До сего дня таких деталей я не знал. Но UTF-16 - это надстройка на USC-2, поэтому если не брать крайне редко используемые в европейской традиции суррогатные пары, то UTF-16 вполне себе оказывается двухбайтным и прямо индексируемым. Кроме того, суррогатные пары также кратны 2 байтам, поэтому хорошо ложатся на 16-битный алфавит кодера. Но UTF-8 я тоже обязательно протестю. )
> Вроде все еще можно частично расчитывать:
Кстати, да, можно будет попробовать. Но в любом случае с пирамидой получится быстрее.
> Еще я тут подумал что сложность алгоритма на дереве не зависит от размера словаря...
Я тоже об этом думал. Вроде как на пирамиде вообще может получится быстрее, но так как размер алфавита существенно больше, то промахи мимо кэша будут чаще, что может быть причиной дополнительных потерей производительности.