Comments 59
// _pos нужен для рекурсии
int ZipTree(Element *_buf, Element *_tree, int _pos)
{
Element *c;
_buf[_pos] = *_tree; // кладем листик в массив
c = &_buf[_pos]; // запоминаем место, куда положили
_pos++; // едем дальше
if(_tree->left)
{
c->left = (Element *)_pos; // меняем адрес на локальный
_pos = ZipTree(_buf, _tree->left, _pos); // кладем оставшуюся левую сторону дерева
}
if(_tree->right)
{
c->right = (Element *)_pos;
_pos = ZipTree(_buf, _tree->right, _pos);
}
return _pos;
}
Смысл в том, что нужно все указатели на листья перевести в относительную форму(относительно начала массива или файла.
Распаковка так-же просто. Заменяем локальные адреса на реальные адреса в памяти.
Недавно реализовывал этот алгоритм. Интереса ради.
То-же думал над упаковкой дерева. Но все оказалось слишком просто :-(
Алгоритм так себе.
Для сжатия изображений подходит слабо.
Те, где цветов мало сжимает достойно. Но никак не лучше LZW.
Фотографии сжимает всего на 10-20%. Что недостаточно.
Зато прост в реализации.
Алгоритм так себе.
Для сжатия изображений подходит слабо.
Те, где цветов мало сжимает достойно. Но никак не лучше LZW.
Фотографии сжимает всего на 10-20%. Что недостаточно.
Зато прост в реализации.
То-то все его используют направо и налево. Например, для сжатия изображений (png, jpeg), произвольных файлов (zip, gzip, zlib)
deflate = lz77 (кодирование последовательностей) + huffman (энтропийное кодирование)
jpeg = dct и квантование (препроцессинг) + huffman (энтропийное кодирование)
Алгоритм Хаффмана — это оптимальный префиксный код; другого префиксного кода, более эффективного, не существует. Обычно он чуть слабее, но некоторых случаях он (на один бит) эффективнее, чем второй широко используемый сегодня алгоритм энтропийного кодирования — арифметическое кодирование. Однако, алгоритм Хаффмана всегда значительно быстрее арифметического кодирования.
habrahabr.ru/post/142242/
habrahabr.ru/post/132289/
Очень популярное, буквально на пальцах, объяснение того, как работает алгоритм компрессии Хаффмана. Действительно, более доступного разжевывания не встречал. Никто не хочет перевести на русский?
К слову, одна Ваша ссылка изобилует математикой, а вторая написана так страшно, что лично я бы ничего не понял (да и сейчас не слишком понятно, хотя как работает алгоритм я вроде как знаю). Мой вариант рассказывает именно что максимально просто, так что не надо думать, всё уже разжёвано.
Все символы исходного алфавита сортируются и помещаются в очередь №1. Все вершины, получившиеся в результате операции связывания, помещаются в очередь №2 (их сортировать не нужно, они уже идут в правильном порядке).
Когда по алгоритму нам нужно найти вершину с минимальным приоритетом, мы просто сравниваем первые элементы этих двух очередей и выбираем нужный.
На ассемблере и Си когда писал в 90-е, мне было как-то проще делать реализацию таких вещей. А сейчас на C# например делать именно так, как пишете вы, наверное даже неразумно.
Это очень странный комментарий. Разумеется, в C# реализовать то, что предлагаю я, ничуть не сложнее чем на ассемблере или на Си.
не могу спорить, я не спец на C#, но на ассемблере/Си я просто работаю с памятью и указателями, а на C# что не делаешь везде какие-то припоны то с памятью, то с хэшами, в итоге в голове придумываешь какую-то альтернативу эмуляции сишных вещей, а это уже говнокод по определению. Пока не могу освоить парадигму современной разработки на ООП.
Вы на Си умеете использовать структуры или выделяете массив байт и оперируете смещениями в нём?
Если второе — то понятно откуда у вас проблемы, но в первом случае вам всего-то нужно заменить struct на class, а malloc — на оператор new. Для этого знать ООП не требуется, и никакие хеши тоже не нужны.
я делаю, например, связанный однонаправленный список, памяти он занимает ровно столько, сколько нужно, понятно как её использовать и освобождать если потребуется. Освободившиеся ячейки используются другим элементом. А писать свой класс с Add, Append, Delete и т.п. элементарными вещами я считаю извращением. Я знаю что такое ООП и как с ним работать, но для небольшого кода ООП это 80% воды. Поэтому даже на C# я пишу структурно, получается минимально компактный код. Например писал программу для расчета энтропии файла, на ООП это заняло 8 экранов кода, при структурном программировании - полтора. Для чего мне еще 6,5 экранов кода? Там только описания классов, методов и т.п. А же не пишу новую Windows.
Еще, так как учусь писать под CPU 6502, то хочу, как тренировку, написать EXE Packer для него под ATARI DOS. Ваш вариант решения весьма пригодится. Но там я хочу применять адаптивное сжатие, которое будет учитывать вероятности появления одного символа за другим, чтобы лучше сжимать исполнимую часть файла. И, наверное, ограничусь фиксированной таблицей частот, но отдельно для кода и отдельно для графики. Это позволит не хранить таблицы в итоговом файле, так как исполнимый файл обычно находится в рамках 8К-64К, то 256-512 байт таблицы слишком сильно ухудшат конечное сжатие.
Так никто вам не мешает не писать никаких методов в этом самом классе. Это же вы выбрали сначала писать их, а потом хейтить.
Кстати, ничего что связные списки требуют дополнительной памяти под указатели, что несколько отличается от "памяти он занимает ровно столько, сколько нужно"?
Никто не мешает, так и получается структурный код, о котором я написал выше и на который накидали минусов. Не по какону же.
И я ничего не хейчу.
Не вижу противоречий в моих словах про "столько сколько нужно" и списки. Я же не говорю о минимальном использовании памяти. Вы же в курсе, что изменение алгоритма в сторону скорости будет жрать и память?
Вы пишете, что на C# "везде какие-то припоны то с памятью, то с хэшами", что не соответствует действительности.
а еще я пишу "я не спец на C#" и описываю то, как я вижу и с чем сталкиваюсь. На многие вещи мне делают замечания, что мол это не Си и так делать нельзя, так как каждый раз у тебя копируются ВСЕ данные, что это говнокод в кубе. Когда начинаешь использовать что-то еще - опять проблемы, так как для поиска сравниваются не сами данные, а их хэш, что может приводить к коллизиям. В итоге чтобы сделать какую-то простую вещь приходится переходить в небезопасный код и городить городушку.
Если у вас "для поиска сравниваются не сами данные, а их хэш, что может приводить к коллизиям" — значит, вы используете Dictionary. А если вы используете Dictionary — значит, вы уже пишете не так, как на Си.
Что же заставляет вас писать на C# как на C#, а не как на Си? Тут одно из двух — или вы сам чувствуете, что Си не дают вам нужного уровня абстракции, или команда устала искать баги в вашем коде, и вынуждает вас писать тот код, который они понимают. В обоих случаях это означает, что вы не такой спец по языку Си, как пытаетесь изобразить. За это и минусы.
а вы профессиональный троль ну или...
Я больше думаю что "или".
И я уже написал, что если я программирую на C#, то появляются те или иные заморочки, отчего мне приходится переставать пользоваться C# и изобретать костыли. В чём сложность читать что вам пишут?
И я нигде не писал что я "спец по языку Си", отсюда не нужно придумывать то чего нет, а минусы вы ставите только потому что можете, а не потому что это объективно требуется.
Мы, кстати, в заголовок заархивированного файла сохраняли таблицу частот, по которой затем восстанавливали дерево для декодирования.
«Предположим, у нас есть строка «beep boop beer!», для которой, в её текущем виде, на каждый знак тратится по одному байту»
Откуда Вы взяли 1 байт? В строке всего 5 различных символов: «b»,«e»,«p»,«o»,«r». Для их кодирования 8 бит слишком много: даже 3 бит хватит с избытком.
Есть ровно два способа — хранить длину где-то или кодировать специальный символ «конец».
Если использовать второй способ, последовательность на выходе будет 00000000 0100000 и таблица «0» — «а», «1» — конец, вопросов при распаковке не возникнет.
P.S. Мне, кстати, способ с заданием длины последовательности кажется более логичным.
Ну вот и как вы, передавая по сети поток из произвольного количества бит, объявите конец последовательности? Часто алгоритм Хаффмана используют для известных систем с известной статистикой символов, т.е. на приёмнике и передатчике есть статическая таблица, которая по каналу связи не передаётся. И вот тут куда логичнее использовать именно специальный символ-сообщение «конец последовательности».
Даже в этом примере из статьи префиксный код лучше. Не лучше он только в случае, когда частоты всех символов абсолютно одинаковы ;)
При различных расчётах встречаемости каких-либо данных сложилась ситуация, что использовать настоящие частоты неудобно. Например, вы работаете со словарём употребляемости слов в языке. Если использовать честные частоты, то как только вы решаете добавить какое-то слово из нового текста, добавленного в корпус, надо будет пересчитывать частоты всех без исключения слов.
Поэтому используется абсолютная величина, которая называется частотой (в русском языке её часто называют «частотность», но встречаются оба вариант) и понимается как «количество попаданий этого слова на весь корпус». При публикации итогового словаря, данные для удобства использования совместно с другими источниками нормируются — например, в величину ipm (instances per million) — но при работе использовать удобнее абсолютные значения, которые тоже называются частотой. Просто за скобкой остаётся дополнение, что величина 42 — это «42 совпадения на один полный источник данных».
Это всего лишь моё мнение. Ещё раз подчеркну, что по-моему не стоит устраивать спор на эту тему в комментариях.
Это не спор, а дискуссия. Мы обмениваемся мнениями, каждый аргументирует свою точку зрения, у меня, например, нет цели заставить вас делать так, как я, но в поддержку автора я выскажусь. Слово "frequency" используется примерно лет 80, может 90 и задолго до Хаффмана и относительные величины тоже используется и так и называются, это просто удобно. Ну а то что в вашем ВУЗе кто-то там устраивает репрессии, то это непедагогично, ведь такой преподаватель не сможет аргументировать свою позицию, а значит это вкусовщина и его глубочайшее имхо, на которое мы можем смело наплевать.
Хаффман занимается устранением избыточности в коде. Почитайте про то, что такое энтропия. Она всегда стремится к 8, для большинства файлов например RAR она равняется 7,96 +-, то есть методом Хаффмана такой файл вы уже закодировать не сможете. Именно поэтому Хаффмана используют на финальной стадии сжатия, так как для вашего примера можно применить сначала RLE а потом Хаффмана.
и что в моих словах кому-то не понравилось?
для примера возьмём файл nethasp.ini, распакованный, сжатый 7z normal и ultra:
Count Entropy Dic Size Files
1 7,75579750 252 1,3K nethasp.7z
2 5,22182203 77 3,5K nethasp.ini
3 7,76327868 254 1,3K nethasp_ultra.7z
Здесь мы видим что с применением более сильного сжатия меняется размер словаря - 77 символов в оригинале, 252 в нормальной степени и 254 в ультре (столбец Dic). Так же растёт значение энтропии - да-да, она таки стремится к 8 (мы же посимвольно читаем данные). Собственно степень сжатия для Хаффмана не может превышать 8 раз, так как вы даже имея 2 байта в словаре и кодируя их в 1 бит будете иметь всегда не менее 1/8 части исходных данных, плюс небольшой заголовок для распаковки, например у вас не будет стоп-слова для данных, поэтому скорее всего вы просто укажете размер данных, после которых распаковка и прекратится.
Хаффман как раз занимается устранением избыточности в представлении данных. Есть другие способы сжатия (или точнее кодирования данных), которые я затронул например у себя в статье. Можете ознакомиться.
Не соглашусь с автором что его вариант простой в понимании - картинки только путают и если не знаешь как всё работает (я знаю), то и не сможешь понять что там за шарики и почему они скачут туда-сюда. Всё же требуется отдельно показывать суммы "1+1" и показывать что вы потом делаете сортировку.
Алгоритм Хаффмана на пальцах