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

[Sameone]

Не надо заниматься лесоводством - оставь это тем, кто пишет умные математические книжки. В программировании ты можеш выполнять действия, которых нет в математике (например читать память или писать в неё), поэтому в жизни всё проще. В методе Хаффмана непосредственно значения вероятностей отдельных символов напрямую использовать не обязательно, достаточно чтобы i-й символ был маловероятнее i-1го.
Пусть у тебя есть входной текст (последовательность символов, которую надо сжать) известной длины и список использованных в нём символов, отсортированных по убыванию их встречаемости в тексте. Тогда для всех символов входного текста, по порядку от первого до последнего:
1)читаешь символ из входного текста и находиш его в списке символов;
2)если это самый первый элемент, пишеш в выходной текст (закодированный) "0" и переходиш к обработке следующего символа входного текста;
3)иначе создаёш битовую строку длиной N, где N - номер символа в списке, но не длиннее чем M - номер предпоследнего элемента списка. Создаваемая битовая строка состоит из чередующихся "1" и "0", начинается с "1" (т. е. имеет вид 1010101...);
4)если N<>M, инвертируеш последний бит в последовательности (т. е. теперь битовая строка заканчивается двумя одинаковыми битами);
5)записываеш битовую строку в выходной текст.
ПРИМЕЧАНИЯ:
На 4-м шаге можно инвертировать бит для всех элементов списка кроме предпоследнего, но тогда заархивированный файл не сможет быть правильно прочитан архиватором-лесоводом (написанным математиком). Метод Хаффмана максимально эффективен если вероятность нахождения символов убывает как 1/(2^N), где N - номер символа в упорядоченном по убыванию списке. Если отличие отой этой зависимости велико, результат далёк от оптимального. Поэтому метод Хаффмана считается устаревшим и заменяется арифметическим кодированием, которое никогда не хуже, но в неудобных для метода Хаффмана случаях может быть в разы эффективнее. Подробнее об арифметическом кодировании смотри http://compression.ru/book/pdf/compr...ll_scanned.pdf с35-43 - там даже есть образцы реализации компрессора и декомпрессора (правда, на Си). Книга выложена её авторами на их собственном сайте.

[jerri]

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

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

[Sameone]

Jerry, в моём алгоритме деревьев вообще нет. Разобрался с деревьями - молодец, но ИМХО отсортировать одномерный массив проще чем обходить бинарное дерево. Алгоритмов сортировки море - от банальной пузырьковой до Кнут-Морриса-Пратта (время сортировки линейно зависит от количества сортируемых символов).
Интересно, к какому набору символов не подходит мой алгоритм? Я составил его после вдумчивого прочтения главы о методе Хаффмана в указанной мной книге, там традиционно - обход деревьев. Подметил свойства формируемой последовательности битов и решил ими воспользоваться.

[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 бит

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

[alone]

Jerry, в моём алгоритме деревьев вообще нет. Разобрался с деревьями - молодец, но ИМХО отсортировать одномерный массив проще чем обходить бинарное дерево. Алгоритмов сортировки море - от банальной пузырьковой до Кнут-Морриса-Пратта (время сортировки линейно зависит от количества сортируемых символов).
Интересно, к какому набору символов не подходит мой алгоритм? Я составил его после вдумчивого прочтения главы о методе Хаффмана в указанной мной книге, там традиционно - обход деревьев. Подметил свойства формируемой последовательности битов и решил ими воспользоваться.

Составь по своему алгоритму дерево для символов со следующими вероятностями:
А - 25%
Б - 25%
В - 12,5%
Г - 12,5%
Д - 12,5%
Е - 12,5%

[Sameone]

По порядку:
1) Про Кнута сотоварищи ошибся маленько...
2) я недаром писал "входной текст (набор символов)". Любая информация в компьютере (текст в обыденном понимании, звук, картинка, и даже поток телепатированных мыслей) представляется в виде байтов, каждый из которых может иметь 1 из 256 значений, ровно столько различных значений в таблице символов АСКИИ. То есть каждый байт картинки - это один символ (стандартный экран спектрума - это 6912 байт или 6912 символов для архиватора).
Коды символов значения не имеют. В список заносятся и сортируются только коды символов, встречающихся в шифруемом наборе символов (или, что тоже самое - образцы байт, из которых состоит шифруемый набор данных, если так кому-то понятнее).
3) alone, у меня нет деревьев в обычном понимании... только список символов. Одномерный массив. Вектор.
Для сприведённого тобой примера он вполне может иметь вид АБВГДЕ ещё какой-то, подходящий под формулу "сначала символы с вероятностью 25%, потом с вероятностью 12,5%". Фактически, ты уже привел список, непосредственно с которым и должен работать мой алгоритм. Только ему достаточно одной колонки - которая с буквами. А вероятности нужны были на предварительном этапе, когда составлялся и сортировался список использованных символов. А мой алгоритм осуществляет непосредственно кодирование.
Но если ты хочеш понять, как именно нужно предварительно обработать исходный набор символов, чтобы скормить его моему алгоритму - пожалуйста. Пусть у нас есть текст
КАКОЙ-ТО_ТЕКСТ
Двигаясь по порядку слева на право, составляем список использованных символов:
К А О Й - Т _ Е С
и список количества раз, которое каждый из них встретился в тексте:
3 1 2 1 1 3 1 1 1
После сортировки список символов принимает вид:
К Т О А Й - _ Е С
И вот с этой последовательностью символов ("КТОАЙ-_ЕС") и работает мой алгоритм.
4)jerri, ты где-то ошибся - если методом Хаффмана кодировать текст, состоящий из 6 различных символов, то самый короткий код будет состоять из одного бита, самый длинный - из 5.
5) Vitamin По поводу 1/(2^N) А как ты ещё представляеш себе "алгоритм Хаффмана приближает относительные частоты появления символов в потоке частотами, кратными степени двойки"? (Указанная мною книга, с 35).
Я в курсе, что иногда результат работы по методу Хаффмана бывает далёк от идеала, предписываемого теоремой Шеннона. Потому и предложил jerri посмотреть в сторону арифметического кодирования, которое даёт более близкий к идеалу результат.

[elf/2]

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

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

[Vitamin]

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

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

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

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

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

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