Дерево Хаффмана

Слышал, что можно строить сабж по коду Хаффмана. Это реально?

скорее всего "да конечно"

только не очень понятно, что же ты имел ввиду
под построением дерева по коду..
что это за код и откуда ты его берешь?

Из дерева Хаффмана, вероятнее всего, и получается код Хаффмана. =)
Я тоже не совсем понял, что имел в виду andyag. Дерево Хаффмана - это, фактически, двоичное дерево, по которому можно узнать (при наличии статистических данных) какой последовательностью бит выгоднее всего кодировать данный символ. Алгоритм Хаффмана используется статический и динамический (с построением дерева на лету). Последний - самый медленный, но также и наиболее эффективный. А вообще, я бы порекоммендовал пользовать т.н. арифметическое кодирование.. Алгоритм Хаффмана позволяет кодировать один байт (или, скажем, слово, или что ты там выберешь) минимум одним битом. Арифметическое кодирование позволяет сжимать одну единицу (байт, слово и т. д.) до бесконечного малой доли бита.

ЗЫ. Кстати, если серьёзно занимаешься этим, почитай "The Data Compression Book" Марка Нельсона.

Сообщение отредактировано: Kernel_Panic - 19.04.02, 18:44

Цитата Kernel_Panic, 19.04.02, 22:42:31

Алгоритм Хаффмана используется статический и динамический (с построением дерева на лету). Последний - самый медленный, но также и наиболее эффективный.

имхо наоборот.

кстати, про арифметическое кодирование:
я думал оно несколько медлненнее, труднее в реализации и сжимает чуть хуже чем статический метод хаффмана.
нам на лекции это вроде даже доказали, через энтропии всякие...
(хотя может доказывали и не совсем это, я не очень внимательно слушал, кстати зря..)

Цитата

имхо наоборот

Да нет. Представь, что ты некоторое время вычилсяешь какую-то функцию, потом запоминаешь её результат и с этим результатом работаешь. С другой стороны, представь, что ты эту функцию вычисляешь для каждого байта данных .
То же самое и со статическим методом Хаффмана против динамического (адаптивного). Для динамического тебе придётся после каждого байта данных подправлять дерево, т.к. статистика изменилась. В общем, при динамическом методе каждый символ рассматривается, как последний. Т.е. это можно представить, так: ты прочитал один байт - создал дерево. Переместился в файле на байт дальше - создал дерево заново. Ещё дальше - опять. ...Только всё это можно оптимизировать.. Вот поэтому и получаются быстрые динамические алгоритмы сжатия ..

Арифметическое кодирование действительно медленнее, но позволяет сжимать данные гораздо лучше, чем метод Хаффмана, т.к., как я уже писал, максимальное сжатие по Хаффману - 8:1 (8 битов к одному биту, если использовать 8-битные слова), а для арифметического способа соотношение не ограничено .

ЗЫ. Доказательство - всё в той же книге: "The Data Compression Book".

Я имею ввиду, для пользования сжатия по Хаффману обязательно ли сохранять в файл статистику символов???

Для статического метода - да. И у упаковщика, и у распаковщика должна быть копия дерева. Т.е. или ты должен сохранять дерево в файл, или использовать всегда одно и то же дерево (но это очень редко применяется; к тому же, для каждого типа файлов статистика будет разная, поэтому этот способ эффективен только при сжатии одного типа файлов).

При использовании динамического метода дерево сохранять не нужно. И упаковщик, и распаковщик начинают работу с пустым деревом (или с одним символом типа Escape, которым ты будешь указывать, что следующий символ нужно добавить в дерево). И по ходу дела перестраивают его.

2Kernel_Panic
Для динамического метода дерево не создаеться заново для каждого символа, а перестраиваеться. и все данные (закодированные) созадаютсья за один проход, в то время, как для статического метода нужно два прохода по файлу данных - один для вычисления частот, другой для кодирования.

Насчет кто лучше сжимает -
насколько я помню, для динамического есть оценка
[S-N+1,2S+t-4N+2]
где S - длина статического кода хаффмана для этой последовательности,
N - длина алфавита,
t - число сообщений (хз, наверное длина незакодированного сообщения)

отсюда - на некоторых наборах данных динамический может быть лучше статического, на N-1 код, в на других наборах данных - почти в два раза длиннее...
хотя в среднем статический все же чуть лучше сживает, чем динамический.

А вот с арифметическим буду разбираться... надо, и полезно будет наверное:)

слушай, а книги, что ты говоришь, в инете нет случайно?

Сообщение отредактировано: Demo_S - 20.04.02, 19:37

Люди, а арифметическое сжатие сильно жмет???

Цитата

Для динамического метода дерево не создаеться заново для каждого символа

Угу, я ж писал типа "это можно представить, как...". Фактически дерево становится таким, как если бы его построили заново.

Насчёт степени сжатия. Статический упаковщик должен будет хранить в файле дерево. А если делать упаковщик второго или третьего порядка (когда кодирование каждого символа зависит от предыдущего), то вместо 256 элементов в дереве получаем 65536 и больше. Поэтому дерево в файл не пишется; оно создаётся на лету. При этом используется управляющий символ, который в сжатом потоке указывает, что следующий символ нужно добавить в таблицу. Таким образом, этот управляющий символ - единственное, что влияет на размер получающегося при сжатии файла. Насколько я понимаю.

Книги в инете вроде нету.

арифметическое сжатие само по себе - не так уж хорошо, но и к нему можно прикрутить словарь и будет рулез. Мне казалось, что рар на этом основан, хотя это догадки.

Сообщение отредактировано: murph - 23.04.02, 14:34

Об арифметическом сжатии можно лишь сказать, что оно лучше, чем сжатие по Хаффману. Оно (само по себе) не использует словарей, и поэтому его возможности ограничены.

Кстати, в ЗИПе действительно используется словарный метод (один из LZ*) в сочетании с кодом Хаффмана (статическим, насколько я помню). А в LHA (по-моему) пользуют вместо Хаффмана арифметическое.

Цитата Kernel Panic, 23.04.02, 12:29:21

Насчёт степени сжатия. Статический упаковщик должен будет хранить в файле дерево. А если делать упаковщик второго или третьего порядка (когда кодирование каждого символа зависит от предыдущего), то вместо 256 элементов в дереве получаем 65536 и больше

Не понял, что есть кодирование 2, 3 порядка.
есть способы, чтобы хранить дерево, так чтобы оно не занимало много места.
например тот способ, какой использует жпег. там от дерева хранятсья только количества кодов определенной длины. то есть массив 1..16 - i-тый эл-т которого - кол-во кодов длины i. Только для этого нужно дерево специальное строить, чтобы его омжно было так записать.

Цитата Kernel Panic, 23.04.02, 12:29:21

Книги в инете вроде нету.

жаль...
а пример или дока по этому арифметическому кодированию есть?.


насчет архиваторов, насколько я знаю, рар пользует LZW+HUFFMAN(статический)

О еще вспомнил, статический вариант есть самовосстанавливающийся. т.е. если возникнетошибка в записи данных (пропадет один бит, или измениться на противоположный) то глюкавая обл-ть затронет только какую-то часть архива.
например для оригинального архива 12341234123412341234
если где-то сглючит, то получиться типа 12341223321212341234
Это конечно неприемлеме для прог, а вот для картинок можно.
А вот динамический не обладает таким сво-вом. в нем если испортиться хоть один бит (выпадет, измениться с 1 на 0 или с 0 на 1) то заглючит вся оставшаяся частьархива.

Цитата

Не понял, что есть кодирование 2, 3 порядка.

Не знаю, так ли это называется по-нашему, но суть такова. Вместо обыкновенного сжатия (когда создаётся статистика для каждого символа) используется более продвинутый метод. Т.к. в большинстве случаев можно предсказать вероятность употребления определённого символа после предыдущего (скажем, в английских текстах: вероятность более 99%, что после q идёт u), этим фактом нельзя не воспользоваться. В результате получаем следующее. Встречается нам в английском тексте буква q. Мы знаем, что по статистике (возможно, нами же и выявленной) после неё в 99% случаев следует u, поэтому при построении деревьев Хаффмана (а их уже 256, т.е. для каждого байта; а может, и больше) мы указываем, что для _данного_контекста_ (сразу после буквы q) единицу следует использовать для обозначения буквы u, а на ноль разветвлять все остальные буквы (ну, может, сокращение какое-нибудь). Надеюсь, идея более или менее ясна. Так же и для модели третьего порядка. Теперь уже учитываются _два_ предыдущих символа. В примере с тем же q и u наибольшую вероятность следования после них имеют (насколько я знаю) символы e и a. Поэтому их расписываем на 00 и 01 (двоичные), а единицу отдаём на откуп врагам. Ээ.. хмм.. другим, в общем, символам. А если представить, что мы работали бы в модели 1-го порядка (вообще-то, по-моему, это называется модель 0-го порядка; так что не мешало бы у всех порядков поотнимать по единице; я вполне мог чё-нить перепутать) - так вот, в модели этого-самого 1-го (или нулевого) порядка буквы u и a имели бы совсем не такие вероятности. Вследствие чего сжималось бы всё хреновее. Надеюсь, я излагаю более или менее доступно.

Цитата

там от дерева хранятсья только количества кодов

Вот этого я не совсем понял. Нельзя ли поподробнее?

Цитата

а пример или дока по этому арифметическому кодированию есть?.

%) Если хочешь, могу отмылить сырцы примеров из той книжки. Она с двумя пятидюймовыми дискетами продаётся, так что.. =)

Цитата

А вот динамический не обладает таким сво-вом. в нем если испортиться хоть один бит (выпадет, измениться с 1 на 0 или с 0 на 1) то заглючит вся оставшаяся часть архива.

Неееее..... =) Падажи... %) Предположим, есть у тебя последовательность битов:
01 010111 101011110
и т. п., которая раскодируется как

Это к примеру, конечно.
И представь, что второй бит превратился из единицы в ноль. Получится:
000 101 11 1010 11110

Вариант не идеальный, но придумывать что-то умное впадляк. И объясни мне, в чём в этом случае принципиальная разница между статическим и динамическим методами? В любом случае получится не то, что нужно.. Это только если использовать фиксированные длины кодируемых данных, то можно чего-то такого избежать. Но тогда.. почему бы не пользовать ASCII?

Цитата Kernel Panic, 24.04.02, 02:12:54

Надеюсь, я излагаю более или менее доступно.

да, спасибо, я понял, очень интерестно:)

Цитата

Вот этого я не совсем понял. Нельзя ли поподробнее?

вот тебе кусок из книжки/доки

Дерево кода хаффмана непосредственноне представлено маркером, но оно может быть восстановлено из списка чисело кодов каждой битовой
длины. Для каждой битовой длины коды этой длины численно меншье чем префиксы всех кодов большей длины. Недопустимы одинаковые
коды - в этой модели они могут быть только префиксами более длинных кодов.
 
Например, еслине сущ кодов длины 1 и 2, имеються два кода длины 3, пять длины 4, тогда первые семь кодов хаффмана будут:
000, 001, 0100, 0101, 0110, 0111, 1000. Болеедлинные коды начнуться с 4-битовых последовательностей 1001 и более. Эти первые семь кдодов будт ассоциироваться
с первыми семью символами в списке Vij.
Последний байт кждого сегмента данных, закодированных по методу хаффмана, заполняеться битом 1. Это не может вызвать распознавание ложного кода хаффмана, поскольку нет кода, содержищго все биты,
равыне 1. Дещифратор достигнет следующего маркера JPEG перед получением полного кода хаффмана.

суть такова:
храниться 16 чисел - кол-во кодов хаффмана соотв длин.
после них идут некие числа/символы Vi- это символы, находящиеся в листьях дерева хаффмана.
на основании этих 16 чисел мы строим дерево хаффмана.
берем число 0. если есть 1 коддлины 1, то коду в дереве 0 ставим в соответствие первый из символов V1;
добавляем к числу 1. сдвигаем на 1 влево. получаем 10 (если бы коды с длиной 1 не было,получили бы 00)
если есть код с длиной 2, то коду 10 ставим в соответствие V2.
(если число 00, то если есть коды с диной 2, например из 16 чисел второе равно 2, то коду 00 ставим в соотв число V1 (на первом шаге его не поставили) коду 01 ставим в соотв V2 (если бы было 3 кода, то коду 10 поставили бы V3) )
...
есть число 10010. есть 5 кодов длины 5.
в 10010 - первый из них
в 10011 - второй
в 10100 - третий
в 10101 - 4
в 10110 - 5.
потом число становиться 101100 и снова таже история для кодов дины 6.

только дерево должно облдать каким-то св-вом типа "каждое левое поддерево небольше правого" т.е. любое дерево сохранить так не удасться... хотя сдаеться мне, что есть способы сохранения любых деревьев, тоже экономные. поспрошаю еще:)

Цитата

%) Если хочешь, могу отмылить сырцы примеров из той книжки. Она с двумя пятидюймовыми дискетами продаётся, так что.. =)

давай.

Цитата

Неееее..... =) Предположим, есть у тебя последовательность битов:
01 010111 101011110
и т. п., которая раскодируется как
Это к примеру, конечно.
И представь, что второй бит превратился из единицы в ноль. Получится:
000 101 11 1010 11110
Вариант не идеальный, но придумывать что-то умное впадляк. И объясни мне, в чём в этом случае принципиальная разница между статическим и динамическим методами? В любом случае получится не то, что нужно.. Это только если использовать фиксированные длины кодируемых данных, то можно чего-то такого избежать. Но тогда.. почему бы не пользовать ASCII?

Ы... как бы долго обьяснять, но ...
в статическом после определенного места пойдет неповредженный код.
после изменения бита станет
могу привести конкретные примеры.
вообще этот эффект наблюдается не для каждого набора данных, но как правило он присутствует. только вот длина участка стабилизации (на котором глюки, но после которого неизменный текст) может колебаться.
кроме того, к самостабилизирующимся относиться также метод фиббоначчи.
а вот динамический ХАффмана, коды элиаса (вроде бы), и шеннона-фано не явл. самостабилизирующимися.
причем динамич хаффмана не самостабилизир, из-за того, что алфавит храниться вместе с кодами.
ЗЫ конкретный пример даду завтра, седни лом искать, поздно.
ЗЗЫ классная у тебя подпись:))

Сообщение отредактировано: Math - 22.04.09, 19:20