Комментарии 7
Спасибо за статью.
Хотелось бы также отметить, что построение этого самого отсортированного списка циклических перестановок можно написать более эффективнее, чем алгоритмом «в лоб». Для этого используется такая структура данных, как суффиксный массив и его можно построить за линейное время.
Хотелось бы также отметить, что построение этого самого отсортированного списка циклических перестановок можно написать более эффективнее, чем алгоритмом «в лоб». Для этого используется такая структура данных, как суффиксный массив и его можно построить за линейное время.
Насколько я понимаю, обратное преобразование BWT можно также выполнить за O(N) времени (например здесь описано).
Move-To-Front, если я не ошибаюсь, можно выполнить за O(N log N) посредством нетривиального использования сбалансированных деревьев. Для алфавита более 256 символов это может быть существенно.
Наконец, мне кажется не совсем правильным делать акцент на том, что арифметическое кодирование сжимает лучше Хаффмана. Дело в том, код Хаффмана невероятно прост (префиксный код), его можно очень быстро кодировать и декодировать. В случае небольшого алфавита можно в кодер Хаффмана подавать блоки по два-три символа — это приблизит коэффициент сжатия к оптимуму (энтропии источника).
В то же время арифметическое кодирование требует умножений и делений, и жутко тормозит по сравнению с Хаффманом. Реальное преимущество арифметического кодирования состоит в возможности варьировать веса символов входного алфавита в процессе кодирования. Вместе с хорошей моделью предсказания последующих символов входного потока арифметическое кодирование может обеспесить коэффициент сжатия лучше, чем арифметическое кодирование само по себе.
Move-To-Front, если я не ошибаюсь, можно выполнить за O(N log N) посредством нетривиального использования сбалансированных деревьев. Для алфавита более 256 символов это может быть существенно.
Наконец, мне кажется не совсем правильным делать акцент на том, что арифметическое кодирование сжимает лучше Хаффмана. Дело в том, код Хаффмана невероятно прост (префиксный код), его можно очень быстро кодировать и декодировать. В случае небольшого алфавита можно в кодер Хаффмана подавать блоки по два-три символа — это приблизит коэффициент сжатия к оптимуму (энтропии источника).
В то же время арифметическое кодирование требует умножений и делений, и жутко тормозит по сравнению с Хаффманом. Реальное преимущество арифметического кодирования состоит в возможности варьировать веса символов входного алфавита в процессе кодирования. Вместе с хорошей моделью предсказания последующих символов входного потока арифметическое кодирование может обеспесить коэффициент сжатия лучше, чем арифметическое кодирование само по себе.
Я бы поспорил насчёт простоты Хаффмана. У меня, конечно, весьма специфические задачи, но всё же. Представьте себе алфавит состоящий из 90*10^6 «букв», и сообщение, состоящее из 17*10^9 таких «букв». Уверяю Вас, построить дерево Хафффмана для таких сообщений очень и очень непростая задача.
А что-то можно вообще построить простое для таких задач? ;)
Код Хаффмана можно построить за O(KlogK), где K — количество символов алфавита. Также для простоты кодирования можно построить за O(KL) оптимальный код с ограничением L на длину слова сверху (например 31 бит). Для приведенных вами масштабов это ничтожно мало по сравнению с O(N) времени (линейный проход), которое требуется для собственно кодирования. Единственная проблема с использованием традиционного кода Хаффмана — это большие затраты памяти кодера и декодера (ни в какой кеш не влезает). Но и арифметическое кодирование естественным образом эту проблему не решает.
Арифметическое и Хаффмана объединяют под названием «энтропийное кодирование». Они основаны исключительно на условной энтропии каждого символа.
А вы говорите про сжатие цепочек. Конечно, перед энтропийным кодированием применяют всякие преобразования, которые улучшают кодирование — Барроуза-Уиллера, или LZ. Это касается любого энтропийного кодирования. Deflate так устроен — LZ77, за которым Хаффман.
А по поводу тормозов — на больших блоках BWT тормозит не хуже арифметического, причём в обе стороны. Как пример: bzip2 (bwt+huffman) — медленно сжимает, медленнее всех распаковывает. xz (lzma) — сложный алгоритм с марковскими цепочками, сжимает медленнее, но распаковывает быстрее, чем bzip2. gzip (lz77+huffman) быстрее всех сжимает, по скорости распаковки лишь ненамного быстрее xz
А вы говорите про сжатие цепочек. Конечно, перед энтропийным кодированием применяют всякие преобразования, которые улучшают кодирование — Барроуза-Уиллера, или LZ. Это касается любого энтропийного кодирования. Deflate так устроен — LZ77, за которым Хаффман.
А по поводу тормозов — на больших блоках BWT тормозит не хуже арифметического, причём в обе стороны. Как пример: bzip2 (bwt+huffman) — медленно сжимает, медленнее всех распаковывает. xz (lzma) — сложный алгоритм с марковскими цепочками, сжимает медленнее, но распаковывает быстрее, чем bzip2. gzip (lz77+huffman) быстрее всех сжимает, по скорости распаковки лишь ненамного быстрее xz
Совершенно согласен.
Я просто хотел подчеркнуть, что преимущества арифметического кодирования перед кодированием Хаффмана чисто в форме энтропийного кодирования довольно малы. А вот при «кодировании цепочек» арифметическое кодирование действительно существенно лучше. Очень нетривиально адаптировать код Хаффмана к подобной задаче.
Я просто хотел подчеркнуть, что преимущества арифметического кодирования перед кодированием Хаффмана чисто в форме энтропийного кодирования довольно малы. А вот при «кодировании цепочек» арифметическое кодирование действительно существенно лучше. Очень нетривиально адаптировать код Хаффмана к подобной задаче.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сжатие информации без потерь. Часть вторая