Наконец-то добрался и переписал вариант арифметического сжатия под 16-битныый алфавит. Раньше я как-то прикидывал эффект от такого перехода для кодирования Хаффмана, но на небольшом множестве символов в тексте.
Насколько помню, считал для трех символом и пробела. Там получалось, что переходе с 8-битного алфавита исходного файла на 16-битный, сжатие на 8-битном кодеком ухудшалось из-за добавления к каждому символу служебного байта, который существенно менял модель, а 16-битное сжатие давало такой же по размерам результат, как и 8-битное сжатие на 8-битном файле.
С другой стороны, при сжатии 8-битного файла 16-битным кодеком размер сжатого файла получался ровно такой же, как и при использовании кодека с 8-битным алфавитом.
Таким образом, для этого случая 16-битный кодек всегда оказывался как минимум не хуже по коэффициенту сжатия, чем 8-битный. Но будет ли это выполняться для текста с большим множеством используемых в нем символов?
Я предполагал, что 16-битный кодек даст даже лучший результат на обычных, человекочитаемых текстах в 8-битной кодировке, исходя из того, что в них часто повторяются двухбуквенные сочетания, которые 8-битный кодек заметить просто не может.
С другой стороны, при нечетном расстоянии между такими буквосочетаниями, они уже не будут восприниматься 16-битным кодеком как одинаковые.
Но в процессе отладки на небольшом 8-битном тексте я получил гораздо более худший результат по сжатию 16-битным кодеком.
А вот при тестировании на больших текстах, как я и предполагал, результаты 16-битного кодека оказались лучше.
Это связано, по всей видимости, с большим временем на адаптацию 16-битной статистической модели к реальным данным. Я для теста использую равновероятную модель появления всех 65536 символов, что, конечно, для человекочитаемого текста очень не точно. Из-за большого размера алфавита более-менее точная адаптация модели требует и большего количества обработанных символов.
Поэтому для сжатия небольших блоков текста лучше использовать 8-битный кодек, но еще лучше, если есть возможность, перед сжатием данных формировать более адекватную модель, хоть для 8-битного, хоть для 16-битного варианта.
Ну и собственно результаты:
Как видим, на больших файлах 16-битный кодек всегда лучше 8-битного. Удивительно, но факт: UTF-16 сжимается 16-битным кодеком лучше, чем UTF-8.
Так же любопытно, что текст в UTF-16 сжался немного хуже 16-битным кодеком, чем WIN-1251 8-битным. Ведь теоретически они должны были сжаться в один и тот же размер. Это связано, как я уже упоминал выше, с большим размером модели в 16-битном кодеке, поэтому первые несколько тысяч символов он кодирует менее оптимально, чем 8-битный, в котором модель адаптируется к тексту гораздо быстрее.
Так же любопытно посмотреть на сжатие двоичных файлов. В качестве примере я взял WAV-файл, в котором находились несжатые данные в формате PSM S16LE. Так как данные в 16-битном формате, не удивительно, что 16-битный кодек сжал их лучше 8-битного.
Интересно то, что коэффициент сжатия оказался сравним с некоторыми методами сжатия звуковых файлов без потерь. Впрочем, он лежит на нижней границе этих методов, обычно же они все обеспечивают более высокое сжатие.
Удивительно, но производительность 16-битного варианта сжатия оказалась немного выше, чем у 8-битного! 8.1 МиБ/сек сжатие и 4.6 МиБ/сек распаковка против 7.5 и 4.6 соответственно.
Но тут неожиданно вылез небольшой технический нюанс: при тестировании сжатия бинарных файлов выяснилось, что точности UInt32 для 16-битного кодека не всегда хватает.
Пришлось переходить на UInt64, и вот тут скорость упала примерно в 1.5 раза. Но это чисто технический момент, связанный с неудачным оптимизатором Pascal для таких выражений. Уверен, что на ассемблере разницы между вариантами не будет никакой.
Вывод же можно сделать такой: практически всегда 16-битный кодек оказывается лучше, чем 8-битный.
Единственное исключение, которое я сейчас вижу – небольшие блоки данных, в которых некоторые 8-битные символы встречаются чаще других, но при этом не образуют таких же более часто встречающих пар символов.
Если же блок данных достаточно большой, то такие часто встречающиеся 8-битные символы неминуемо будут образовывать и более часто встречающиеся пары, что даст возможность 16-битному кодеку показать как минимум не худший результат.
Спасибо за сравнение и анализ!
ОтветитьУдалить> Удивительно, но факт: UTF-16 сжимается 16-битным кодеком лучше, чем UTF-8.
По мне так ничего удивительного: в UTF-8 символ может занимать от 1 до 4-х байт, и 1-но и 3-х байтовые символы могут привести к разбивки потока не по границе символов, что ухудшает модель частот символов. С 8-ми битном же кодеком такого не происходит и UTF-8 сжимается чуть-чуть лучше.
> но производительность 16-битного варианта сжатия оказалась немного выше, чем у 8-битного
На одной стороне была более большая пирамида не помещающаяся целиком в L1 кэш, а на другой 2 деления и чуток другой математики, в итоге деления и анализ битов проиграли :))) Но может там можно что-нибудь сооптимизировать?
> UInt32 для 16-битного кодека не всегда хватает Пришлось переходить на UInt64
Мне понравилась https://marknelson.us/posts/2014/10/19/data-compression-with-arithmetic-coding.html статья, она написана чуток в необычном стиле: сначала приводят неработающий код, а после обсуждают и правят, но более-менее понятна. В итоге для их реализации, получается что на UInt32, можно безопасно хранить частоты до 15-бит, а дальше масштабировать, а на UInt64 соответственно 31-бит, но возможно у Вас реализовано по другому... Было бы интересно посмотреть :)))
> ...а на другой 2 деления и чуток другой математики...
Удалитьматематика одинакова в обоих случаях, и вроде деления там нигде нет )
Просто закодировать два символа по байту оказалось медленнее, чем один двухбайтовый. Несмотря на более частые промахи кэша. Видимо, не такие уж они и частые.
> Мне понравилась ... статья
Да, она интересная. Пока пробежал по диагонали, надо будет вдумчиво почитать.
> В итоге для их реализации, получается что на UInt32, можно безопасно хранить частоты до 15-бит...
Немножко тут о разном. У меня проблема вылезла для 16-битного алфавита, а автор вроде за рамки 8-битного алфавита не уходит, рассуждая о количестве бит, используемых для хранения частот каждого символа. Но я не сильно внимательно читал, может, чего не понял. Хотя его рассуждения косвенно связаны, конечно, и с переходом на 16-битный алфавит.
>... но возможно у Вас реализовано по другому...
Почти один в один, просто операции сдвига заменены на операции сложения/вычитания.
Вообще предыстория этого проекта достаточно любопытна. Мне многие темы из программирования были интересны, но нехватка времени плюс собственная лень не давали возможности разобраться во многих таких вещах. Поэтому, пока работал преподавателем, я этим беззастенчиво пользовался, выдавая интересные лично для меня темы в качестве курсовых работ для студентов.
Сжатие данных было мне всегда интересно, поэтому, судя по остаткам информации, я выдал курсовую на тему "Арифметическое сжатие" Александру Шендрикову в 2002 году вроде. И это была одна из немногих удачных курсовых, которая привела к интересному результату. Я даже на практике немного пользовался арифметическим сжатием для каких-то второстепенных задач. В общем, Александр вполне успешно реализовал арифметическое сжатие, очевидно портировав его с какой-то С(++) версии, а я уже потом его программку всяко разно "мучил", пытаясь оптимизировать. Собственно, это наследие еще с тех времен.
К сожалением, в то время я был не очень опытным преподавателем, поэтому в отчете по курсовой не оказалось ссылок на использованную литературу, в связи с чем восстановить, какой исходный материал использовал Александр для написания версии программы на Pascal, я не могу.
Так вот, в исходной версии, которая была у Александра, поддерживалась как обычная частота символов, так и она же с накоплением. На самом деле конкретно для кодирования исходная частота в общем-то не нужна, и первое, что я сделал для оптимизации еще в те времена - отказался от таблицы исходной частоты при кодировании, использую ее только для формирования модели в каких-то случаях, еще до начала самого кодирования.
> Было бы интересно посмотреть
Значит, как-нибудь покажу в одном из постов ) Целиком, правда, пока выкладывать не готов - кое-где код там совсем нехороший, сначала надо бы его причесать. Да и версия это скорее не рабочая, а чисто исследовательская, что бы разобраться с производительностью, поэтому непосредственно использовать её для сжатия произвольных данных не получится.
> вроде деления там нигде нет
УдалитьХм... интересно, под Арифметическим кодированием я подразумевал https://en.wikipedia.org/wiki/Arithmetic_coding, статья что я привел тоже о нем и что-то я не представляю как его реализовать без деления... Еще есть https://en.wikipedia.org/wiki/Range_coding с очень похожей идеей и для него вроде деление не нужно.
Там давольно забавная история: арифметическое кодирование остается в тени других алгоритмов в основном из-за патентов, часть из них истекла и это дало возможность свободно реализовывать интервальное кодирование. Оно как бы тоже арифметическое кодирование, но обычно в статьях под арифметическим подразумевают оригинальный алгоритм, и я считал что Вы его реализовали, но там нужно деление. В общем я запутался :)))
> У меня проблема вылезла для 16-битного алфавита, а автор вроде за рамки 8-битного алфавита не уходит
Возможно у Вас другая проблема, но для той что я имел ввиду размер алфавита не важен, просто ее легче поймать на маленьком алфавите. Алгоритму важна возможность закодировать символ с минимальной частотой, думаю можно попробовать воспроизвести проблему на большом файле в котором один из символов начинает встречаться только в конце, тогда его частота будет близка к 1/2^32 и даже 64 битной математики может быть недостаточно чтобы такая маленькая частота изменила интервал, по крайней мере так в реализации автора.
> Поэтому, пока работал преподавателем, я этим беззастенчиво пользовался, выдавая интересные лично для меня темы в качестве курсовых работ для студентов.
По моему это круто :))) Всяко лучше чем мусолить заезженные темы!
>статья что я привел тоже о нем и что-то я не представляю как его реализовать без деления...
УдалитьВидимо, мы просто про разное говорим. ) Сам алгоритм, понятное дело, с делением. Но!..
> На одной стороне была более большая пирамида не помещающаяся целиком в L1 кэш, а на другой 2 деления и чуток другой математики...
Я вроде в этой статье сравниваю одинаковые реализации кодека, просто для разных алфавитом. Математика там абсолютно одинакова. В рамках твоего последнего замечания я подумал, что, возможно, ты про подсчет частот символов, там в некоторых реализациях может быть деление, но я от него избавился, про что и написал.
И только сейчас я тебя, похоже, понял. Ты, наверное, имел в виду, что на 8 битах потребуется в два раза больше делений, чем на 16 битах, но меньше движений по пирамиде?
>Возможно у Вас другая проблема... ...тогда его частота будет близка к 1/2^32 и даже 64 битной математики может быть недостаточно чтобы такая маленькая частота изменила интервал...
Да, у меня была другая проблема, и она встретилась почти в самом начале большого бинарного файла: интервал (Range в терминах программы, что ты привел в первом комментарии?) оказался настолько большим, что не влез в 32 бита.
> По моему это круто :)))
Складывается ощущение, что министерство образования с этим не очень согласно. ) Ну, по крайней мере судя по требованиям, которые действовали на момент моего увольнения.
> Ты, наверное, имел в виду...
УдалитьАга, именно так
> по крайней мере судя по требованиям
Про это я не знаю, я так с моей колокольни. Я думал требования очень расплывчатые. Например мы на Компьютерной графике учили корел с автокадом, а ребята в НГУ писали свой рей трейсер с нуля, ничего общего, кроме как и там и там результат - картинка :) В образовании все запутанно и не очевидно!
> Я думал требования очень расплывчатые.
УдалитьТак и было в те времена. Точнее, требований особых и вовсе не было. Преподаватель сам был волен выбирать, что давать в рамках курса. Вроде и на Западе везде так.
А потом ввели очень жесткие бюрократические требования. В частности, каждое практическое или лабораторное задание должно быть очень подробно расписано, в том числе способ исполнения, утверждено на заседании кафедры и прочее... То же самое с курсовыми... В общем, гибко менять каждый год темы стало очень муторно...
> ...тогда его частота будет близка к 1/2^32 и даже 64 битной математики
Кстати, такое ограничение есть, только не в этом месте. За счет вот этих команд
high = low + (range * p.high / p.count) - 1;
low = low + (range * p.low / p.count);
где range - достаточно большое число, а p.high и p.low - частоты с накоплением, то даже частота встреч, равная 1/(2^32) вроде должна обрабатываться нормально, в том случае, если выражение (range * p.low / p.count) будет рассчитываться с удвоенной точностью, то есть для этого примера в 64 бита. Здесь самое значение 1/(2^32) нигде не встречается, так как частота 1 - это p.high-p.low, а вот сами эти числа достаточно велики.
Но проблема возникнет, если p.count - 32-разрядное беззнаковое. В этом случае при кодировании данных длиной более 4 млрд. символов возникнет переполнение и метод будет работать неверно. Вот это и будет ограничением используемой разрядной сетки. Переход на 64 бита полностью решит эту проблему, так как на практике вряд ли даже в отдаленная время возникнет малейшая возможность закодировать блок данных размером 2^64 символов.
Там чуток все интереснее:
УдалитьПосле обновления high и low, мы кодируем общий префикс анализируя 1-е 2 бита, изменяем low и high в итоге range всегда больше MAX_RANGE / 4 = 2^(CODE_VALUE_BITS - 2)
Для кодирования всех допустимых p.low и p.high необходимо выполнение 2-х условий:
1. не допустить переполнения при вычислении range * p.high, получается CODE_VALUE_BITS + FREQUENCY_BITS <= PRECISION
2. чтобы иметь возможность закодировать минимальную частоту p.high - p.low = 1 должно выполнятся range >= p.count, а значит MAX_RANGE / 4 >= MAX_FREQUENCY или в битах CODE_VALUE_BITS - 2 >= FREQUENCY_BITS
Мы стремимся максимизировать FREQUENCY_BITS, значит решаем систему:
CODE_VALUE_BITS + FREQUENCY_BITS = PRECISION
CODE_VALUE_BITS - 2 = FREQUENCY_BITS
Получаем:
FREQUENCY_BITS = (PRECISION - 2) / 2
CODE_VALUE_BITS = FREQUENCY_BITS + 2
Если PRECISION = 64, то FREQUENCY_BITS = 31, а CODE_VALUE_BITS = 33
Как я понимаю разницы между 8-ми и 16-ти битной модели нет, просто на 16-ти битной некоторые проблемы проявляются раньше.