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

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

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

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

Из дерева Хаффмана, вероятнее всего, и получается код Хаффмана. =)
Я тоже не совсем понял, что имел в виду 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

2 Kernel Panic: Moderatorial [ * ]
2 Demo_s: Moderatorial [ * ]

 Выбирайте "более другие" примеры

Сообщение отредактировано: vot - 24.04.02, 08:01

vot, ну вот (забавный каламбур, а? ). Пришёл Поручик Ржевский и всё опошлил.. Ок, теперь буду просто использовать слово из трёх букв, которые дети пишут на заборах, без которого не могут жить женщины и которое так бережно охраняют мужчины. (Слово "мир". А ты что подумал? )

2vot фидошник блин!.. что и плюсомет имееться? а как ты будешь [!] ставить и в рид-онли переводить?

2Kernel_Panic
по поводу конкретного примера самостабилизирующегося кода.
Пусть для алфавита ABCDE есть такие коды
A - 1
B 000
C 001
D 010
E 011
Последоватлеьность BCDAEB представляеться как
B     C     D  A  E     B   ABCCCC
000 001 010 1 011 000  xxxxxx
возьмем и выкинем первый бит.
00 001 010 1 011 000 xxxxxx
тогда эта последовательность битов раскодируеться как
000 010 1 010 1 1 000 xxxxxx
B     D  A  D   A A B    ABCCCC
то есть после буквы B (второй) начался код такой же, как и был. изменение его не затронуло.
Так происходит для многих вариантов кодов хаффмана.
Этот факт обьясняеться тем, что много кодовых слов (011 и 1 например) оканчиваються одинаковой последов символов, поэтому при искажении даных оказываеться что кодер и декодер достигают концов этих последовательностей одновременно.
Для префиксных кодов:
пусть S - суффикс кодового слова. Если существует последовательность кодовых слов Г и Л таких что SГ=Л то Г являеться синхронизирующей последоватлеьностью для суффикса S.
В нашем примере Г=1 (код для А)
для суффикса 01 синхронизирующая поселедовательность такая
01 1=Л (011 - одно из кодовых слов)
S  Г

для суффикса 10:
10    011          = 100 1 1.
суф  код слово
Если люб суффикс любого кодов слова имеет синхр последоватлеьность, то код будет полностью самосинхронизирующимся.
не для любого суфф есть синхр послед - частичноо самосинхр,
ни для одного - полностью не самосинхр.


Теорема 1 (доказывать не буду)
Последовательность кодов символов будет самосинхронизирующейся когда наибольший общий делитель длин всех кдов будет равен 1.
Теорема 2. Послед никогда не будет самосинхронизирующейся, если ни один из суфиксов не являеться кодовым словом.


Ы-Ы-Ы-ЫХ.
надеюсь, хоть что-то будет понятно, и местами интерестно:)

ЗЫ  а где же примеры арифметического кодирования?
ЗЗЫ а кто мне в слове "колебаться" две звезды вставил? ты его решил чтоли на части разбить. Надо тогда что-нить со словом "мультиканальный" придумать:)))

7in, ок, верю на слово. Я, правда, не совсем понимаю, что ты имеешь в виду. Понятно, что есть случаи, в которых в конце концов всё стабилизируется и т. д. Однако это далеко не всегда так, и скорее в большинстве случаев ниччё не получится. А как с этим обстоит дело в адаптивных алгоритмах - хз. Не задумывался. Но чё-то мне кажется, что будет приблизительно то же самое, хотя я могу и ошибаться.

Начиная с разных суффиксов не совсем понятно, но это не страшно..

Примеры мыльну.

Вопрос.
У меня сейчас в файл сохраняется статистика символов в виде:

char c;
long f;

Если f пронормировать по байту и сохранять

char c;
unsigned char f;

то можно ли будет восстанавливать дерево без глюков???

Цитата Kernel Panic, 25.04.02, 02:14:22

7in, ок, верю на слово.

\%))

Цитата

Я, правда, не совсем понимаю, что ты имеешь в виду. Понятно, что есть случаи, в которых в конце концов всё стабилизируется и т. д. Однако это далеко не всегда так, и скорее в большинстве случаев ниччё не получится.

что не свосем понятно- это да, я тоже не сразу вьехал\%)
случаев, в которых все стабилизируеться, больше.
почти всегда, когда наибольший общий делитель длин всех кодов хаффмана равен 1.
а у тебя очень часто в дереве будут коды длиной 1,
или коды длиной 2 и 3, или 3 и 5.
(хотя в принципе это как бы неактуально, тк технологии хранения и передачи данных достаточно надежны)

Цитата

Примеры мыльну.

ловлю:)


2andyag не факт, однако если ты себе придумаешь соглашение
сохраняю символ, потом его частоту вхождений, нормироманную по байту,
потом след символ, частота вхождений которого меньше, то думаю нормально.
то есть если есть нпример
а 12
б 13
после нормиромания будет
а -0
б -0
надо сохранить
б - 0
а - 0

но можно же сохранять частоты в порядке следвоания символов в алфавите (это чтобы сами символы не писать) и
х1х2х3 где х1  вхождение символа а, х2 - символа б и т.д.
тогда точно не восстановишь.
кстати, идея о такой сохранении дерева - крута, я когда себе делал архивер, даже и не подумал о ней:) теперь сделаю:) спасибо.

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

Если нужна инфа что есть коды элиаса - пиши, расскажем:))

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

Цитата Kernel Panic, 25.04.02, 02:14:22

7in, ок, верю на слово.

Спасибо тебе огромное!!!
P.S. А чему именно ты веришь?

Апыска. Мои извенения.

Цитата

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

Енто почему же? Представь, что ты сохранял всю инфу о количестве символов в 64-битных переменных. Что тебе помешало бы вернуться к 32-битным? Ты немного потерял бы точность, и вследствие этого слегка пострадала бы степень сжатия. Не больше. Если ты сохранил всё в виде 8-битных чисел, что тут такого??

И уж совсем не понял, о каких "уровнях дерева" ты говоришь..

не понял, что там за потери точности....
если надо хранитьчастоты символов, которые больше 256, то вполне могут начаться глюки при восстановлении по ним дерева (если ты их все переворотишь в байт).
я так понимаю, что воротить в байт из ворда будешь просто делением на 256. (ну или там насколько) при этом получишь целые числа.
так вот, пусть есть некие символы "а,б,в,г" с частотами 1000,3, 2 и 2.
так бы ты при восстановлении дерева сделал
1000 3 2 2  
1000 4(2+2) 3
1000 7(4+3)
1007

коды симолов
а -0
б -11
в 100
г 101
а после деления всего на 256
а б в г
3 0 0 0
3 0 0(в+г)
3 0
3

коды будут
а -0
б -10
в 110
г 111
дерево не то.... значит и восстановить правлиьно не сумеем...

Сообщение отредактировано: Demo_S - 27.04.02, 16:28

Аа.. ты об этом. Я просто не понял вопроса - я думал, типа, временно сохранять дерево до начала кодирования. Короче, неважно..

ладно, проехали:))
и так уже топик растянули до невозможности:))).

Цитата

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

Нет. Достаточно сохранить сам вид дерева. 2 бита на узел. Можно и ещё компактнее.

Что-то в последнее время некрофилы стали доставать заступы и вилы...

Люди!!!помогите)))где можно найти код примера решения задачи по алгоритму Хаффмана на бейсике????