Comments 13
Раз уж речь зашла об эффективной реализации Хаффмана, то просто для комплекта оставлю ссылку на блог человека, который реально заморочился производительной реализацией кодирования/декодирования Хаффмана (и не только) на реальном железе.
Там большой цикл постов, предыдущие и следующие статьи несложно найти по истории блога.
Написано очень хорошо и увлекательно, особенно для тех, кто заинтересуется этой темой.
https://fgiesen.wordpress.com/2021/08/30/entropy-coding-in-oodle-data-huffman-coding/
Не понятно, почему это обозначено как "Сложный"? На первом курсе в 90-х помнится для тренировки писал на C, а потом сравнивал со степенью сжатия по другим алгоритмам - в то время были популярны pcx, arj
https://ru.wikipedia.org/wiki/PCX
https://ru.wikipedia.org/wiki/ARJ
PS. не обязательно алгоритм должен работать в 2 этапа - статистику и дерево можно перестраивать "на ходу" по факту получения символа (группы символов) из потока.
>> PS. не обязательно алгоритм должен работать в 2 этапа - статистику и дерево можно перестраивать "на ходу" по факту получения символа (группы символов) из потока.
Об этом сказано в статье уже в третьем абзаце:
>> также существуют однопроходные адаптивные варианты алгоритма
Не понятно, почему это обозначено как "Сложный"?
Я всегда понимал это как признак статьи, а не материала как такового. Я знаю Хаффмана с начала 90-х, но в статье понял очень мало.
Да и в начале 90 в журнале Радиолюбитель или Радиоаматор были массовые тогда алгоритмы сжатия, с дополнительно написанными реализациями на Си. После Хаффмана были различные вариации Лемпела-Зива, lz77, lz78, lzw.
Да и если учитывать таблицу для перекодировке - то там далеко не 1 как минимальный коэффициент. Но это я уже ворчу. :)
А так - красиво оформленая статья, которая вполне может спокойно на популярных порталах появляться раз в 10-15 лет.
почти полное отсутствие информации на русском языке относительно эффективной реализации алгоритма оптимального префиксного кодирования алфавита с минимальной избыточностью, известного по имени своего создателя как алгоритм Хаффмана.
Сложно судить за давностью лет по поводу оптимальности, но когда я учился в прошлом тысячелетии на 22.01, то у нас были и методички, и практические занятия по алгоритму Хаффмана.
Привет Омскому Политеху и лично великому преподавателю Флоренсову А.Н.!
Видимо правда говорят, что новое - это хорошо забытое старое.
Автору - спасибо большое! С удовольствием окунулся в некогда любимый предмет.
На всякий случай оставлю здесь ссылку на русскоязычное видео, в котором автор достаточно подробно с картинками рассказывает и реализует на java алгоритм Хаффмана, вдруг кому пригодится - https://www.youtube.com/watch?v=IEe3qkdZ99c
Такие коды носят название канонических [5,7] и позволяют проводить быстрое кодирование и декодирование
Хотелось бы уточнить как это влияет на скорость?
Канонические коды позволяют построить две структуры данных: одномерный массив FirstCode[] и двумерный массив DecTable[][], которые используются для декодирования. Тогда вместо того, чтобы считывать кодированные данные бит за битом, мы можем сразу считать L бит за раз (L - максимальная длина кода). Это избавляет нас от использования дополнительных битовых операций, не говоря уже о том, чтобы явно производить обход двоичного дерева для декодирования каждого символа.
Решения алгоритма Хаффман на разных языках программирования:
https://rosettacode.org/wiki/Huffman_coding
Ещё раз про алгоритм сжатия Хаффмана