Comments 18
В обычном deflate-кодере есть режим передачи с предвычисленными (неадаптивными) деревьями Хаффмана. В этом случае, конечно же, деревья передаются в сжатом виде. А суть алгоритма сжатия заключается в том, что коды перестраиваются, чтобы удовлетворять условиям:
1. Все более короткие коды лексикографически расположены ранее более длинных
2. Все коды одной длины упорядочены лексикографически в соответствии с порядком символов
Такую последовательность кодов очень просто сжать обычным RLE.
Это очень напоминает второе преобразование, которые Вы сделали над деревом. Было бы очень интересно сравнить работу deflate-кодировщика с Вашим алгоритмом.
1. Все более короткие коды лексикографически расположены ранее более длинных
2. Все коды одной длины упорядочены лексикографически в соответствии с порядком символов
Такую последовательность кодов очень просто сжать обычным RLE.
Это очень напоминает второе преобразование, которые Вы сделали над деревом. Было бы очень интересно сравнить работу deflate-кодировщика с Вашим алгоритмом.
Было бы интересно почитать про то как жмёте видео. И кстати, почему выбрали хаффмана а не арифметическое кодирование?
Напишу обязательно. Я использую не Хаффмана, а кодирование с помощью специального бинарного дерева, которые разработали на кафедре. А арифметическое кодирование тут применять вообще равносильно самоубийству. Вы хоть представляете какая точность арифметики понадобится?
Может быть, RangeCoder вам сгодится? Есть реализация в отечественном PPMd, правда, я в своё время не смог с наскоку с ней разобраться.
Есть эффективные реализации, например, можно посмотреть в книге «Numerical Recipes in C++» (скачивается бесплатно). Точность арифметики в арифметическом кодировании не является фактором, ограничивающим масштабирование алгоритма. Можно кодировать массивы любой длины. Думаю, это делается всеми современными архиваторами.
Было бы странно, если бы автор не знал, что суть арифметическое кодирование, и при этом утверждал про лучшее в мире сжатие видео без потерь ;)
Особенностью нашего метода является то, что сжимаются массивы из миллиардов элементов, при этом алфавиты составляют десятки миллионов элементов. При таких масштабах даже концептуально простые алгоритмы реализовать становится если не невозможно, то очень и очень сложно. А учитывая, что работа имеет не только академическую, но и практическую ценность, вычислительную сложность тоже надо учитывать.
А вы пытались реализовать конкретно арифметическое кодирование? Или отвергли его, не пытаясь реализовать? Я могу с уверенностью утверждать, что количество кодируемых элементов не предъявляет к реализации арифм. кодирования никаких особенных требований. Время работы упаковщика и используемая им память не зависят от размеров кодируемого массива символов.
Что касается больших алфавитов — не знаю. Должно быть, это усложнит реализацию, но сделает ли ее невозможной — не знаю. Надо пробовать.
Что касается больших алфавитов — не знаю. Должно быть, это усложнит реализацию, но сделает ли ее невозможной — не знаю. Надо пробовать.
Помимо прочих приёмов, всегда можно разделить алфавит на группы и кодировать сначала номер группы, а потом уже частоту внутри группы. Скажем, кодирование элемента из алфавита в 1000000 таким образом можно свести к кодированию двух элементов из алфавита в 1000. Вобщем, не вижу я принципиальных проблем тут…
А в плане скорости (это ответ автору) — если частоты статические, то можно свести общую сумму к степени двойки при кодировании. В этом случае арифметика будет использовать только битовые сдвиги и умножения, так что медленно уж точно не будет ;)
А в плане скорости (это ответ автору) — если частоты статические, то можно свести общую сумму к степени двойки при кодировании. В этом случае арифметика будет использовать только битовые сдвиги и умножения, так что медленно уж точно не будет ;)
Мне не приходилось работать с такими большими алфавитами (десятки миллионов элементов), но давайте посчитаем, как арифметическое кодирование могло бы справиться с ними. Допустим, размер алфавита = E. Нам нужно хранить частоту для каждого символа, то есть всего E*K байт, где 1<=K<=4 — размер типа для частоты, зависящий от того, насколько Ваши частоты могут различаться. Далее, чтобы посчитать отрезок вероятности для конкретного символа, нужно просуммировать частоты от 0 до этого символа.
Если схема статическая — то эти суммы можно просто хранить для каждого элемента. Если динамическая — то мы можем хранить иерархические суммы частот: p0 — сумма от 0 до E/2, p1 — сумма от E/2 до E, p00 — сумма от 0 до E/4, p01 — сумма от E/4 до E/2, p10 — сумма от E/2 до E/4, и т.д. В этом случае нужно дополнительно E*K байт памяти, а поиск отрезка для символа и его обновление будут выполняться зя O(log(E)).
Итого, затраты к памяти: около 2*E*K <= 8*E байт. Асимптотическая сложность кодирования N символов: O(N*log(E)) для динамической адаптации или O(N) для статической. При этом арифметическое кодирование обещат почти оптимальное представление частот, то есть лучшее сжатие, чам любые бинарные деревья.
А какие параметры Вашего алгоритма кодирования?
Если схема статическая — то эти суммы можно просто хранить для каждого элемента. Если динамическая — то мы можем хранить иерархические суммы частот: p0 — сумма от 0 до E/2, p1 — сумма от E/2 до E, p00 — сумма от 0 до E/4, p01 — сумма от E/4 до E/2, p10 — сумма от E/2 до E/4, и т.д. В этом случае нужно дополнительно E*K байт памяти, а поиск отрезка для символа и его обновление будут выполняться зя O(log(E)).
Итого, затраты к памяти: около 2*E*K <= 8*E байт. Асимптотическая сложность кодирования N символов: O(N*log(E)) для динамической адаптации или O(N) для статической. При этом арифметическое кодирование обещат почти оптимальное представление частот, то есть лучшее сжатие, чам любые бинарные деревья.
А какие параметры Вашего алгоритма кодирования?
А можно по-подробнее про чем не устраивает арифметическое кодирование?
Есть еще один способ эффективной передачи таблицы кодировки:
1. Пусть мы для каждого элемента знаем его глубину. Тогда, пользуясь вашим соображением про структуру дерева (что все листы сброшены в одну часть) мы может легко восстановить и дерево, и таблицу кодировки.
2. Тогда надо для каждого элемента закодировать его глубину. Итого, если у нас в алфавите 256 элементов, надо передать 256 чисел не очень большого (в среднем) размера, если нет сильного дисбаланса.
3. Более того — эти данные тоже можно сжать по Хаффману. Теперь у нас всего ~20 разных элементов, и они совсем хорошо жмутся.
4. Тогда получается одна маленькая таблица на 20 элементов, потом закодированная большая таблица, а потом, собственно, сами данные.
1. Пусть мы для каждого элемента знаем его глубину. Тогда, пользуясь вашим соображением про структуру дерева (что все листы сброшены в одну часть) мы может легко восстановить и дерево, и таблицу кодировки.
2. Тогда надо для каждого элемента закодировать его глубину. Итого, если у нас в алфавите 256 элементов, надо передать 256 чисел не очень большого (в среднем) размера, если нет сильного дисбаланса.
3. Более того — эти данные тоже можно сжать по Хаффману. Теперь у нас всего ~20 разных элементов, и они совсем хорошо жмутся.
4. Тогда получается одна маленькая таблица на 20 элементов, потом закодированная большая таблица, а потом, собственно, сами данные.
Если у нас алфавит из десятков миллионов, то и размер описания дерева тоже будет — десятки миллионов байтов.
Как ни крути, а перед передачей данных придётся отправить тяжеленный заголовок.
А как насчёт адаптивного кодирования? Да, степень сжатия меньше, скорость декодирования тоже меньше, нагрузка на память больше… но при этом уменьшается латентность, что для онлайн-кодирования большой плюс.
Как ни крути, а перед передачей данных придётся отправить тяжеленный заголовок.
А как насчёт адаптивного кодирования? Да, степень сжатия меньше, скорость декодирования тоже меньше, нагрузка на память больше… но при этом уменьшается латентность, что для онлайн-кодирования большой плюс.
Если у нас алфавит из десятков миллионов, то и размер описания дерева тоже будет — десятки миллионов байтов.
И экономия хотя бы одного бита на символ выльется в сотни мегабайт экономии.
Кодирование Хаффмана в принципе не очень подходит для решения задач в таких масштабах. В моей работе используется разработанный специально для подобных задач вид бинарных деревьев.
1) Правильно я понял идею, что алгоритмом Хаффмана мы находим целочисленный вес (длину кода), а потом строим под эти длины произвольный префиксный код, чтобы описание его дерева было наиболее компактным? Но в основе — всё равно Хаффман?
2) Цель — оптимизировать размер файла, а скорость и латентность на втором месте?
Для повышения скорости можно было БЫ уменьшить разрядность переменной части кода.
Т.е. если алфавит у нас 32-битный, то Хаффманом кодируем старшие 16-24 бит, а младшие идут постоянной серией. (Или наоборот, — зависит от природы распределения данных).
Дерево хорошо ляжет в память, — меньше кэшмиссов и всё такое.
2) Цель — оптимизировать размер файла, а скорость и латентность на втором месте?
Для повышения скорости можно было БЫ уменьшить разрядность переменной части кода.
Т.е. если алфавит у нас 32-битный, то Хаффманом кодируем старшие 16-24 бит, а младшие идут постоянной серией. (Или наоборот, — зависит от природы распределения данных).
Дерево хорошо ляжет в память, — меньше кэшмиссов и всё такое.
Дерево кодирования однозначно восстанавливается, если задан порядок встречавшихся элементов(сортирован по частоте) и количество элементов определённой длинны (для быстрого декодера, длину кода часто ограничивают сверху в 32 бит). Такой метод используют много кодировщиков, ведь частоты — это абсолютно лишняя информация. Если элементов много, то таким способом расходы по памяти даже меньше, чем предлагаемым. По сути, в статье приводится заведомо плохой алгоритм «Обычная передача», и велосипед для решения этой давно решенной проблемы.
Sign up to leave a comment.
Об особенностях реализации префиксного энтропийного кодирования для больших алфавитов