Как стать автором
Обновить

Комментарии 37

Писали-писали, но как будто не дописали.
Зачем кодировать таблицу в текстовом виде? Оптимальнее ведь было бы записать в файл как-то так (для архива, вмещающего только один файл):
1. Сигнатура типа файла — 4 байта
2. Версия формата файла — 2 байта
3. CRC32 несжатого файла для проверки правильности разархивации и общей целостности — 4 байта
4. Размер несжатого файла — 4 байта (хотя бы)
5. Размер сжатого файла — 4 байта (хотя бы)
6. Размер таблицы символов — 2 байта
7. Таблица символов — 2 * (количество знаков) байт [парами: символ — код]
8. Сжатые данные — сколько уже получится байт
7. Таблица символов — 2 * (количество знаков) байт [парами: символ — код]

Ну так во-первых не получится, во-вторых неэффективно. Не получится — потому что код произвольной длины, и надо как-то её задавать. Неэффективно — потому что тогда мы будем хранить избыточные пустые биты плюс байт длины. Для кодирования декодирования нужно дерево а не таблица, деревом и надо сохранять. Но да, без сохранения дерева статья выглядит неполной.
Допускаю, в ваших словах что-то есть. Даже не задумывался об этом способе. Я показал лишь наиболее понятный и простой (по моему мнению) метод. Согласен, ваш способ более рациональный.
Я правильно понял, что на выходе у вас получается 2 файла? Зачем? Пишите таблицу в начале закодированного файла.
Знаете, в универе когда-то писал такой курсач/лабу. И первым вопросом попросили замерить производительность (скорость, степень сжатия и т.д.) моей реализации на стандартных бенчмарках, например Calgary Corpus. А какие скорости и коэффициенты сжатия у вас? Второй вопрос: не пробовали ли сделать ещё и статическую реализацию? То, что у вас, насколько понимаю терминологию, называется динамической реализацией, когда таблица частот не фиксирована. Есть и статическая, когда таблица постоянна и задаётся пользователем самостоятельно. Деревья Хаффмана со статической/динамической таблицей есть в алгоритме сжатия Deflate, который используется в архиваторах, поддерживающих формат Zip.
Файл объемом 631 кБит сжимался 27 минут. Как видите, этот результат оставляет желать лучшего на луну быстрее долететь можно. Коэффициент при этом не компенсирует время — 1.79. Статическую реализацию делать не пробовал.
НЛО прилетело и опубликовало эту надпись здесь
1)Да, про 27 минут я серьезно)).
2)В каком смысле несжатое дерево? Вы имеете ввиду несжатую кодовую таблицу, полученную с помощью дерева?
Да не нужна там кодовая таблица, она только мешать будет! Создавать надо дерево, паковать надо по дереву, сохранять надо дерево и распаковывать надо дерево.
Мой юный друг! Я уже не однократно говорил, что показываю наиболее простой(по моему мнению) метод. Вы имеете в виду класть объект дерева в файл? В следующей статье буду портировать нашего Хаффмана на андроид и обязательно расскажу про этот(и не только) метод оптимизации. Спасибо за замечание!
Мой юный друг!

Если информация на вашем профиле вконтакте правдива, то я вам в отцы гожусь.

Вы имеете в виду класть объект дерева в файл?

Я имею в виду не формировать кодовую таблицу. Для упаковки она конечно может дать выигрыш в производительности (хотя судя по 27 минутам, упомянутым выше, вам не помогло), но для сохранения и распаковки лучше дерево. Как дерево сохранять — вопрос отдельный, но тоже изобретать велосипед не придётся — всё уже придумано до нас.
И бонусный вопрос, если есть желание присмотреться пристальнее: как можно реализовать построение дерева за константное и малое количество шагов? Вопрос актуален для аппаратных реализаций (например fpga), когда за каждый такт выдаётся очередной символ и нужно динамически построить таблицу для блока в десяток КБ, а возможности буферизации на кристалле очень ограничены.
PS: я бы не использовал try catch для выхода из цикла.
Хм, у вас есть решение? Я вообще сомневаюсь, что дерево может быть построено за O(1). Насчет try catch согласен, но я проверял, исключения кроме NullPointerException возникнуть не могут. Но все же, предложите более безопасную реализацию (я начинающий Java кодер, совмещаю Шилдта и практику).
С ассимптотическими оценками я определенно спорить не буду. У меня решения нет, однако наблюдаю коммерческие IP-ядра для FPGA, которые по данным их спецификации поддерживают пропускную способность до 100Гбит/с, и раз уж в этой статье речь о кодах Хаффмана, то не вижу причин не спросить об эффективной реализации. Что касается try-catch: обычная проверка if-ом чем вас не устраивает?
Раскрывал тему сжатия Хаффмана в одной из своих статей по реверс-инжинирингу досовской игры. С разбором реализации оригинального сжатия на ассемблере и декодера на С. Там этот алгоритм (несколько модифицированный) активно применялся для сжатия ресурсов.
Я чего-то не понимаю или автор на полпути к изобретению deflate? На полпути потому, что таблицу тоже надо сжимать.
Или это просто туториал по алгоритму Хаффмана?
Да, это скорее просто мануал по Хаффману. Но вернемся к вашему предложению. Допустим, мы сжали кодировочный файл(таблицу), ок. Как будем читать оттуда данные?
Как будем читать оттуда данные?


Да, в deflate таблица сжата. Схема такая.
1. Если для каждого символа известна длина кода, не сам код, а его длина, то по длинам можно восстановить и коды. Есть правило, записано в протоколе, как по длинам восстанавливать коды, так что разночтений быть не может.
2. Для исходных данных максимальная длина кодов 15 бит. Значит каждому символу нужно сопоставить длину, число от 0 до 15 (нулевая длина — символ не используется).
3. Таблица (список длин по всему алфавиту) сначала подлежит RLE-сжатию, — серии одинаковых длин и нулевые серии кодируются особыми символами. Всего этих символов 19:
0-15 -длины кодов;
16-18 -серии.
4. Таблица после RLE кодируется другими кодами Хаффмана, этих кодов не более 19-ти, а максимальная длина 7 бит.
5. Таблица для этих «других» кодов Хаффмана, вернее длины этих кодов, даются напрямую без всякого сжатия, длины эти трёхбитные, и занимают максимум
3*19=57 бит. Еще 17 бит занимает заголовок заголовка блока. Итого блок содержит следующее (сплошным битовым потоком, без выравнивания на границы байтов):
1. Заголовок заголовка — 17 бит.
2. Таблица «других» кодов Хаффмана (их длины) — до 57 бит.
3. Таблица настоящих кодов Хаффмана (их длины) — сколько получится.
4. Собственно сжатые исходные данные.
Да, вот такая двухуровневая «хаффманизация», там всё продумано.

Примечание.
deflate не только Хаффманом сжимает, но еще и ссылками на подстроки. Наример, если подстрока «Таблица» ранее встречалась, то даст ссылку «длина-смещение» вместо самой подстроки.
Спасибо
В обычном текстовом файле один символ кодируется 8 битами(кодировка ASCII) или 16(кодировка Unicode).


ДА ЛАДНО?! Вот прям шишнадцать и усё, ни больше ни меньше? :) А если найду? :))))))

Буду признателен

Я думаю anikavoi в несколько грубой форме хотел сказать, что существует также стандарт юникода, где используется 32 бита. Другое дело, что он нигде не используется…
Ничего что в utf16 один символ может кодироваться двумя 16-битніми словами?
Могу добавить, что динамическое кодирование Хаффмана используется в Quake3 для компрессии передаваемых данных (как дельта состояния, так и полного).
Мне кажется в главе «Построение дерева Хаффмана», в визуализации, на последнем этапе допущена ошибка, справа вместо «sp» должно быть «s», как я понимаю.
«sp» (space) — это пробел
С теорией у вас все в порядке, но вот что-то реализация больно сложная :(
Вот делал на паскале Huffman, переписывал со своих исходников на Си. На Java можно как то поизящней сделать было.
Ведь алгоритм Haffman это же классика жанра. Он используется в формате JPEG после того как произойдет квантизация изображения.
И на сколько помню, хранить коды Хоффмана в выходном файле не обязательно. главное отсортированную таблицу сохранить, а код Хоффмана строиться однозначно при кодировании и декодировании. Нужно только знать кол-во кодированных символов и их порядок по мере убывания частоты встречи символа в файле.
Я не понимаю, что вам могло не понравиться в реализации(поясните). Насчет хранения таблицы — да, окей, согласен. Но опять же, я показывал наиболее простой для понимания(по моему мнению) способ.
У Вас в работе с файлами полный сумбур! Так никто никогда не делает, полная путаница!
Для того чтобы сжать Хаффманом нужно сделать всего 2 прохода:
1. проход — сбор статистики по байтам! не строкам!
2. строим таблицу Хаффмана
3. проходим снова файл от начала до конца и кодируем согласно построенной таблицы Хоффмана.
У Вас же какие-то хелперы, читаете входной файл строкам! сразу все в память! Зачем?! Вы кодируете, а если это несколько Гигабайт или Терабайт? И куча других вопросов по работе с обычными БИНАРНЫМИ (не текстовыми) файлами!
Короче это не код, а помойка! Нет стройности в реализации алгоритма.
В алгоритме Хоффмана есть 2 изюминки: генерация кодов Хоффмана (но это описано 10000+ раз) и работа с битами. Я даже не могу найти в Вашем коде работу с битами! Код должен быть понятен при разборе алгоритма, у Вас же сумбур :(
Вот так бы сразу! Действительно, читать входной файл по строкам, мягко говоря, нерационально. Спасибо большое, учту. Я новичок в этих кодерских делах, поэтому был рад услышать корректирующие советы, которые последовали в Вашем живописном комментарии.
Вот так бы сразу! Действительно, читать входной файл по строкам, мягко говоря, нерационально. Спасибо большое, учту. Я новичок в этих кодерских делах, поэтому был рад услышать корректирующие советы, которые последовали в Вашем живописном комментарии.
Я наверное что-то не понимаю, но таблица что вы в примере сохраняете в файл не совпадает с данными из приведенной выше таблицы и дерева. Что я упускаю?
Т.е. не совпадает? Опишите подробнее.
Понял, что вы имели в виду. Исправил статью
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.