Деревья хаффмана - как с ними работать

[psb]

определенно есть пакеры, которые строят дерево в реальном времени по ходу работы.

[Advertiser]

[jerri]

GriV, а я кого спрашиваю?

я разобрался как оно работает

[jerri]

вобщем так

есть набор чисел

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
есть повторяемость каждого числа

как мне из этих данных сделать дерево?
желательно в виде примера кодирования и использования

при этом может оказаться что каких то из чисел вообще нет

[jerri]

Sameone, для частного случая сойдет
для моего - нет
я уже во всем разобрался
если интересно могу показать

и кстати ты не прав
есть деревья нормальные, есть вырожденные
и это оооочень видно при использовании

[esl]

???
Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — алгоритм, осуществляющий поиск подстроки в строке.

[Vitamin]

Метод Хаффмана максимально эффективен если вероятность нахождения символов убывает как 1/(2^N), где N - номер символа в упорядоченном по убыванию списке. Если отличие отой этой зависимости велико, результат далёк от оптимального.

Откуда сия инфа?

время сортировки линейно зависит от количества сортируемых символов

А можно такой алгоритм? А то сортировка за O(n) нобелевкой попахивает.

---------- Post added at 07:54 ---------- Previous post was at 07:53 ----------

Я составил его после вдумчивого прочтения главы о методе Хаффмана в указанной мной книге, там традиционно - обход деревьев. Подметил свойства формируемой последовательности битов и решил ими воспользоваться.

Почитай еще раз. Особенно главу, где объясняется, что такое энтропия.

[jerri]

Sameone, тут такой момент
в текстовом блоке может не быть символов с кодом #00 #01
в кодовом блоке и картинке их как грязи
если паковать сразу данные то у тебя 256 вариантов
если формировать набор ссылок на предыдущие данные то у тебя 65280 вариантов

теперь разберем алгоритм RNC

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

0 +1 (2-3)
10 принимаем за 1
11 принимаем за 0
010 +2 (4-7)
100 +3 (8-15)

итого самая короткая ссылка - 2 бита
самая длинная -6 бит

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

[elf/2]

Потому и предложил jerri посмотреть в сторону арифметического кодирования, которое даёт более близкий к идеалу результат.

ты ведь про арифметическое кодирование на спекки пошутил?

[Vitamin]

И вот с этой последовательностью символов ("КТОАЙ-_ЕС") и работает мой алгоритм.

Не увиливай от ответа. alco тебя спросил про конкретный пример- набор букв и их относительные частоты (можешь множить на 100 и получить абсолютные частоты для какого-то абстрактного текста). Вот распиши сколько бит на каждый символ потребуется после работы твоего алгоритма и какие это будут битовые цепочки.

5) Vitamin По поводу 1/(2^N) А как ты ещё представляеш себе "алгоритм Хаффмана приближает относительные частоты появления символов в потоке частотами, кратными степени двойки"? (Указанная мною книга, с 35).
Я в курсе, что иногда результат работы по методу Хаффмана бывает далёк от идеала, предписываемого теоремой Шеннона.

Это означает, что разница между реальной энтропией в исходных данных и оценкой по методу Хаффмана не будет превышать 1 бита на каждый символ- отсюда и степени двойки (вероятности 1/2, 1/4, 1/8 и т.п.). Для арифметического кодирования погрешность не превышает 1 бита на все сообщение.

ты ведь про арифметическое кодирование на спекки пошутил?

Я его реализовывал в свое время Ну оооочень медленно работает...

[jerri]

Sameone, я не ошибся
вот тебе таблица из упакованного файла

00 длина 0
01 длина 1
10 длина 2-3
110 длина 4-7
1110 длина 8-15
11110 длина 16-31
111110 длина 32-63
111111 длина 64-127

но это не очень красивая таблица

у меня были и покрасивее

---------- Post added at 16:24 ---------- Previous post was at 16:22 ----------

Я его реализовывал в свое время Ну оооочень медленно работает...

а осталось чтонибудь? в виде исходников