Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 37
Писали-писали, но как будто не дописали.
Зачем кодировать таблицу в текстовом виде? Оптимальнее ведь было бы записать в файл как-то так (для архива, вмещающего только один файл):
1. Сигнатура типа файла — 4 байта
2. Версия формата файла — 2 байта
3. CRC32 несжатого файла для проверки правильности разархивации и общей целостности — 4 байта
4. Размер несжатого файла — 4 байта (хотя бы)
5. Размер сжатого файла — 4 байта (хотя бы)
6. Размер таблицы символов — 2 байта
7. Таблица символов — 2 * (количество знаков) байт [парами: символ — код]
8. Сжатые данные — сколько уже получится байт
Зачем кодировать таблицу в текстовом виде? Оптимальнее ведь было бы записать в файл как-то так (для архива, вмещающего только один файл):
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)В каком смысле несжатое дерево? Вы имеете ввиду несжатую кодовую таблицу, полученную с помощью дерева?
2)В каком смысле несжатое дерево? Вы имеете ввиду несжатую кодовую таблицу, полученную с помощью дерева?
Да не нужна там кодовая таблица, она только мешать будет! Создавать надо дерево, паковать надо по дереву, сохранять надо дерево и распаковывать надо дерево.
Мой юный друг! Я уже не однократно говорил, что показываю наиболее простой(по моему мнению) метод. Вы имеете в виду класть объект дерева в файл? В следующей статье буду портировать нашего Хаффмана на андроид и обязательно расскажу про этот(и не только) метод оптимизации. Спасибо за замечание!
Мой юный друг!
Если информация на вашем профиле вконтакте правдива, то я вам в отцы гожусь.
Вы имеете в виду класть объект дерева в файл?
Я имею в виду не формировать кодовую таблицу. Для упаковки она конечно может дать выигрыш в производительности (хотя судя по 27 минутам, упомянутым выше, вам не помогло), но для сохранения и распаковки лучше дерево. Как дерево сохранять — вопрос отдельный, но тоже изобретать велосипед не придётся — всё уже придумано до нас.
И бонусный вопрос, если есть желание присмотреться пристальнее: как можно реализовать построение дерева за константное и малое количество шагов? Вопрос актуален для аппаратных реализаций (например fpga), когда за каждый такт выдаётся очередной символ и нужно динамически построить таблицу для блока в десяток КБ, а возможности буферизации на кристалле очень ограничены.
PS: я бы не использовал try catch для выхода из цикла.
PS: я бы не использовал try catch для выхода из цикла.
Хм, у вас есть решение? Я вообще сомневаюсь, что дерево может быть построено за O(1). Насчет try catch согласен, но я проверял, исключения кроме NullPointerException возникнуть не могут. Но все же, предложите более безопасную реализацию (я начинающий Java кодер, совмещаю Шилдта и практику).
С ассимптотическими оценками я определенно спорить не буду. У меня решения нет, однако наблюдаю коммерческие IP-ядра для FPGA, которые по данным их спецификации поддерживают пропускную способность до 100Гбит/с, и раз уж в этой статье речь о кодах Хаффмана, то не вижу причин не спросить об эффективной реализации. Что касается try-catch: обычная проверка if-ом чем вас не устраивает?
Раскрывал тему сжатия Хаффмана в одной из своих статей по реверс-инжинирингу досовской игры. С разбором реализации оригинального сжатия на ассемблере и декодера на С. Там этот алгоритм (несколько модифицированный) активно применялся для сжатия ресурсов.
Для сравнения можно посмотреть реализацию на чистом си без плюсов по ссылке:
dxdy.ru/post1324268.html#p1324268
dxdy.ru/post1324268.html#p1324268
Я чего-то не понимаю или автор на полпути к изобретению 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 не только Хаффманом сжимает, но еще и ссылками на подстроки. Наример, если подстрока «Таблица» ранее встречалась, то даст ссылку «длина-смещение» вместо самой подстроки.
habr.com/ru/post/274825 — как пример тех самых таблиц из предыдущего комментария.
www.ietf.org/rfc/rfc1951.txt — ну и сам rfc-1951.
www.ietf.org/rfc/rfc1951.txt — ну и сам rfc-1951.
В обычном текстовом файле один символ кодируется 8 битами(кодировка ASCII) или 16(кодировка Unicode).
ДА ЛАДНО?! Вот прям шишнадцать и усё, ни больше ни меньше? :) А если найду? :))))))
Могу добавить, что динамическое кодирование Хаффмана используется в Quake3 для компрессии передаваемых данных (как дельта состояния, так и полного).
Мне кажется в главе «Построение дерева Хаффмана», в визуализации, на последнем этапе допущена ошибка, справа вместо «sp» должно быть «s», как я понимаю.
С теорией у вас все в порядке, но вот что-то реализация больно сложная :(
Вот делал на паскале Huffman, переписывал со своих исходников на Си. На Java можно как то поизящней сделать было.
Ведь алгоритм Haffman это же классика жанра. Он используется в формате JPEG после того как произойдет квантизация изображения.
И на сколько помню, хранить коды Хоффмана в выходном файле не обязательно. главное отсортированную таблицу сохранить, а код Хоффмана строиться однозначно при кодировании и декодировании. Нужно только знать кол-во кодированных символов и их порядок по мере убывания частоты встречи символа в файле.
Вот делал на паскале Huffman, переписывал со своих исходников на Си. На Java можно как то поизящней сделать было.
Ведь алгоритм Haffman это же классика жанра. Он используется в формате JPEG после того как произойдет квантизация изображения.
И на сколько помню, хранить коды Хоффмана в выходном файле не обязательно. главное отсортированную таблицу сохранить, а код Хоффмана строиться однозначно при кодировании и декодировании. Нужно только знать кол-во кодированных символов и их порядок по мере убывания частоты встречи символа в файле.
Я не понимаю, что вам могло не понравиться в реализации(поясните). Насчет хранения таблицы — да, окей, согласен. Но опять же, я показывал наиболее простой для понимания(по моему мнению) способ.
У Вас в работе с файлами полный сумбур! Так никто никогда не делает, полная путаница!
Для того чтобы сжать Хаффманом нужно сделать всего 2 прохода:
1. проход — сбор статистики по байтам! не строкам!
2. строим таблицу Хаффмана
3. проходим снова файл от начала до конца и кодируем согласно построенной таблицы Хоффмана.
У Вас же какие-то хелперы, читаете входной файл строкам! сразу все в память! Зачем?! Вы кодируете, а если это несколько Гигабайт или Терабайт? И куча других вопросов по работе с обычными БИНАРНЫМИ (не текстовыми) файлами!
Короче это не код, а помойка! Нет стройности в реализации алгоритма.
В алгоритме Хоффмана есть 2 изюминки: генерация кодов Хоффмана (но это описано 10000+ раз) и работа с битами. Я даже не могу найти в Вашем коде работу с битами! Код должен быть понятен при разборе алгоритма, у Вас же сумбур :(
Для того чтобы сжать Хаффманом нужно сделать всего 2 прохода:
1. проход — сбор статистики по байтам! не строкам!
2. строим таблицу Хаффмана
3. проходим снова файл от начала до конца и кодируем согласно построенной таблицы Хоффмана.
У Вас же какие-то хелперы, читаете входной файл строкам! сразу все в память! Зачем?! Вы кодируете, а если это несколько Гигабайт или Терабайт? И куча других вопросов по работе с обычными БИНАРНЫМИ (не текстовыми) файлами!
Короче это не код, а помойка! Нет стройности в реализации алгоритма.
В алгоритме Хоффмана есть 2 изюминки: генерация кодов Хоффмана (но это описано 10000+ раз) и работа с битами. Я даже не могу найти в Вашем коде работу с битами! Код должен быть понятен при разборе алгоритма, у Вас же сумбур :(
Вот так бы сразу! Действительно, читать входной файл по строкам, мягко говоря, нерационально. Спасибо большое, учту. Я новичок в этих кодерских делах, поэтому был рад услышать корректирующие советы, которые последовали в Вашем живописном комментарии.
Я наверное что-то не понимаю, но таблица что вы в примере сохраняете в файл не совпадает с данными из приведенной выше таблицы и дерева. Что я упускаю?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сжатие данных алгоритмом Хаффмана