Просмотр полной версии : Деревья хаффмана - как с ними работать
много я ковырял паковщиков и архиваторов
но так и не понял как преобразуются данные из битов в байты и слова
а самое главное как создается свое дерево для архива
для примера взят паковщик RNC_propack
вот из него 2 куска кода
создание таблицы
.MakeHuff:
ld a,5
call .GetBits
ld a,(rncdat)
or a
ret z
ld (temp1),a
ld (temp2),a
ld hl,tmptab
.MakeHuff2:
push hl
ld a,4
call .GetBits
ld hl,temp2
dec (hl)
pop hl
ld a,(rncdat)
ld (hl),a
inc hl
jr nz,.MakeHuff2
xor a
ld (regy),a
ld (hufcde),a
ld (hufcde+1),a
ld (hufbse),a
inc a
ld (bitlen),a
ld a,#80
ld (hufbse+1),a
.MakeHuff3:
ld a,(temp1)
ld (temp2),a
xor a
ld (temp3),a
.MakeHuff4:
ld a,[temp3]
ld [regx],a
ld hl,tmptab
add a,l
ld l,a
jr nc,$+3
inc h
ld a,(bitlen)
cp (hl)
jp nz,.MakeHuff8
ld (regx),a
add a,a
ld hl,msktab
add a,l
ld l,a
jr nc,$+3
inc h
ld b,(hl)
ld a,(regy)
ld c,a
add a,2
ld (regy),a
ld a,(hufftab)
add a,c
ld e,a
ld a,(hufftab+1)
adc 0
ld d,a
ld a,b
ld (de),a
inc hl
inc de
ld a,(hl)
ld (de),a
ld bc,(rncdat)
ld de,(hufcde)
ld a,(regx)
.MakeHuff5:
sla e
rl d
rr b
rr c
dec a
jr nz,.MakeHuff5
ld hl,rncdat+3
ld (hl),d
dec hl
ld (hl),e
dec hl
ld a,(bitlen)
ld e,a
ld a,16
sub e
jr z,.MakeHuff7
ld d,a
.MakeHuff6:
srl b
rr c
dec d
jr nz,.MakeHuff6
.MakeHuff7:
ld (hl),b
dec hl
ld (hl),c
ld a,(regy)
ld b,a
add 2
ld (regy),a
ld hl,(hufftab)
add a,l
ld l,a
jr nc,$+3
inc h
ld a,(rncdat)
ld (hl),a
inc hl
ld a,[rncdat+1]
ld (hl),a
inc hl
ld a,l
add 15*4
ld l,a
jr nc,.nocarry2
inc h
.nocarry2:
ld a,(temp3)
ld (hl),a
inc hl
ld a,(bitlen)
ld (hl),a
ld bc,(hufbse)
ld a,(hufcde)
add a,c
ld (hufcde),a
ld a,(hufcde+1)
adc a,b
ld (hufcde+1),a
.MakeHuff8:
ld hl,temp3
inc (hl)
ld hl,temp2
dec (hl)
jp nz,.MakeHuff4
ld hl,hufbse+1
srl (hl)
dec hl
rr (hl)
ld a,(bitlen)
inc a
ld (bitlen),a
cp 17
jp nz,.MakeHuff3
ret
и выбор 16 битных данных из нее
.GetVal:
ld hl,(hufftab)
dec hl
.GetVal2:
inc hl
.GetVal3:
ld a,(bitbufl)
and (hl)
ld b,a
ld (rncdat),a
inc hl
ld a,(bitbufl+1)
and (hl)
ld c,a
ld (rncdat+1),a
inc hl
ld a,b
cp (hl)
inc hl
jr nz,.GetVal2
ld a,c
cp (hl)
inc hl
jr nz,.GetVal3
ld a,l
add 15*4
ld l,a
jr nc,.nocarry
inc h
.nocarry:
ld a,(hl)
inc hl
push af
ld a,(hl)
call .GetBits
pop af
cp 2
jr nc,.GetVal4
ld (rncdat),a
ld hl,rncdat+1
ld (hl),0
ret
.GetVal4:
dec a
push af
call .GetBits
pop af
cp 8
jr c,.GetVal5
ld hl,bittabl-8
add a,l
ld l,a
jr nc,$+3
inc h
ld a,(rncdat+1)
or (hl)
ld (rncdat+1),a
ret
.GetVal5:
ld hl,bittabl
add a,l
ld l,a
jr nc,$+3
inc h
ld a,[rncdat]
or [hl]
ld [rncdat],a
ret
.bittabl:
DB 1,2,4,8,16,32,64,128
вообще имеются 3 таблицы по 128 байт и 1 таблица 16 байт
исходники во вложении
на кривость кода не смотрите - это тупой порт М68000 - MOS6502 - Z80gb_edition
так что тут править и править
что мне нужно - понять как оно работает
и как создается таблица
github.com/gildas-lormeau/zip.js
внутри deflate.js и inflate.js. это нормально откоментированые исходники для упаковки/распаковки с использованием классического метода deflate из pkzip, т.е. сначала жмем LZ77, а то что получилось уже динамическим хафманом.
не поможет?
все здорово но мне надо как ААА обьяснять... я уперся в стену
все здорово но мне надо как ААА обьяснять... я уперся в стену
1. http://zxpress.ru/book_articles.php?id=252
2. http://zxpress.ru/article.php?id=8569 = (txt file (http://zxdn.narod.ru/coding/ig7hpack.txt)) by alone
3. http://algolist.manual.ru/compress/standard/huffman.php ~ (http://zxpress.ru/article.php?id=11234)
Принцип построения дерева очень простой:
берем самый частый символ - это бит 0,
следующий по частоте будет 10,
потом 110, и т.д.
Нарисуйте бинарное дерево:
0 - Root - 1
затем из 1 выводите 0 и 1 следующего уровня и т.д.
Во вложении таблица с данными анализатора
как на основе хаффмановских телодвижений эту таблицу ужать?
хотя там 3 таблицы
последний вариант депакера прилагаю
Принцип построения дерева очень простой:
берем самый частый символ - это бит 0,
следующий по частоте будет 10,
потом 110, и т.д.
Нарисуйте бинарное дерево:
0 - Root - 1
затем из 1 выводите 0 и 1 следующего уровня и т.д.
Неправильно.
Надо отсортировать листья по частоте, потом объединить два самых редких в узел и засунуть его в тот же список с суммарной частотой, потом снова два самых редких и т.д., пока не объединим все. Это и будет дерево Хаффмана.
alone, а как это делается в виде программы для Z80 есть?
alone, а как это делается в виде программы для Z80 есть?
А не ты ли jpeg viewer писал?:)
Vitamin, нет не я :) его РРА писал - я только оболочку к его декодеру прикручивал.
высшая математика в мои достоинства не входит :(
alone, а как это делается в виде программы для Z80 есть?
Нет. Да и зачем оно отдельно? Потом всё равно урезать дерево до 15 ярусов, сортировать символы в ярусах, кодировать длины ярусов. Да и без LZ это не нужно. Проще переделать ZXRar под нужный формат, как сделано в mRIP.
alone, у меня уже есть данные которые надо както оптимизированно утоптать
есть данные 16 бит +16 бит которые желательно упихать в 2-16 бит
---------- Post added at 15:33 ---------- Previous post was at 15:09 ----------
есть 6 байт
1 2 3 4 5 5
и есть вот такой генератор таблиц
.MakeHuff:
ld a,5
call .GetBits
ld a,(rncdat)
or a
ret z
ld (temp1),a
ld b,a
ld hl,tmptab
.MakeHuff2:
push bc
push hl
ld a,4
call .GetBits
pop hl
ld a,(rncdat)
ld (hl),a
inc hl
pop bc
djnz .MakeHuff2
xor a
ld (regy),a
inc a
ld (bitlen),a
ld hl,0
ld (hufcde),hl
ld hl,#8000
ld (hufbse),hl
.MakeHuff3:
ld a,(temp1)
ld (temp2),a
xor a
ld (temp3),a
.MakeHuff4:
ld a,(temp3)
ld (regx),a
ld hl,tmptab
call hla
ld a,(bitlen)
cp (hl)
jp nz,.MakeHuff8
ld (regx),a
add a,a
ld hl,.msktab
call hla
ld a,(regy)
ld c,a
add a,2
ld (regy),a
ld de,(hufftab)
ld a,c
call dea
ldi
ldi
ld bc,(rncdat)
ld de,(hufcde)
ld a,(regx)
.MakeHuff5:
sla e
rl d
rr b
rr c
dec a
jr nz,.MakeHuff5
ld hl,rncdat+3
ld (hl),d
dec hl
ld (hl),e
dec hl
ld a,(bitlen)
ld e,a
ld a,16
sub e
jr z,.MakeHuff7
.MakeHuff6:
srl b
rr c
dec a
jr nz,.MakeHuff6
.MakeHuff7:
ld (hl),b
dec hl
ld (hl),c
ld a,(regy)
ld b,a
add 2
ld (regy),a
ld hl,(hufftab)
ld a,b
call hla
ld de,(rncdat)
ld (hl),e
inc hl
ld (hl),d
inc hl
ld de,15*4
add hl,de
ld a,(temp3)
ld (hl),a
inc hl
ld a,(bitlen)
ld (hl),a
ld bc,(hufbse)
ld hl,(hufcde)
add hl,bc
ld (hufcde),hl
.MakeHuff8:
ld hl,temp3
inc (hl)
ld hl,temp2
dec (hl)
jp nz,.MakeHuff4
ld hl,hufbse+1
srl (hl)
dec hl
rr (hl)
ld a,(bitlen)
inc a
ld (bitlen),a
cp 17
jp nz,.MakeHuff3
ret
hla
add a,l
ld l,a
ret nc
inc h
ret
dea
add a,e
ld e,a
ret nc
inc d
ret
и потом оно
вот этой подпрограммой хрен пойми как что то там выколупывает
;**********************************
.GetVal:
ld hl,(hufftab)
dec hl
.GetVal2:
inc hl
.GetVal3:
ld bc,(bitbufl)
ld a,c
and (hl)
ld c,a
inc hl
ld a,b
and (hl)
ld b,a
inc hl
ld (rncdat),bc
ld a,c
cp (hl)
inc hl
jr nz,.GetVal2
ld a,b
cp (hl)
inc hl
jr nz,.GetVal3
ld de,15*4
add hl,de
ld a,(hl)
inc hl
push af
ld a,(hl)
call .GetBits
pop af
cp 2
jr nc,.GetVal4
ld hl,rncdat
ld (hl),a
inc hl
xor a
ld (hl),a
ret
.GetVal4:
dec a
push af
call .GetBits
pop af
ld b,a
inc b
ld hl,1
jr .GetVal5a
.GetVal5:
add hl,hl
.GetVal5a:
djnz .GetVal5
ld de,(rncdat)
ld a,e
or l
ld e,a
inc hl
ld a,d
or h
ld d,a
ld (rncdat),de
ret
есть 6 байт
1 2 3 4 5 5
Это частоты? Нужны частоты для всех литералов.
alone, я не знаю что это
я надеялся ты расскажешь :(
Юра, ты в получаешь те же самые вопросы, что я тебе задавал.
Для каждого случая ты будешь получать свое дерево, если ты хочешь наиболее оптимальный хаффман.
Хранить деревья просто, достаточно указать группы бит, по которым группируются значения, по хаффману.
Я не знаю, есть ли пакеры, которые строят каждый раз своё дерево, лучше спроси АлКо.
определенно есть пакеры, которые строят дерево в реальном времени по ходу работы.
GriV, а я кого спрашиваю? :)
я разобрался как оно работает
вобщем так
есть набор чисел
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
есть повторяемость каждого числа
как мне из этих данных сделать дерево?
желательно в виде примера кодирования и использования
при этом может оказаться что каких то из чисел вообще нет
распаковщик для спектрума RNC_propack
переписан под спек
1 2 3 4 5 5
Это частоты? Нужны частоты для всех литералов.
нет это не частоты
это длина этой позиции в битах в дереве хаффмана
позиция же указывает сколько бит нужно взять из потока для получения ссылки
исключением являются позиции 0 и 1 - они считаются безусловными цифрами
т.е если меньше 2х то возвращаем число
если n больше или равно 2 то берем n-1 бит из потока и устанавливаем бит n-1
Не надо заниматься лесоводством - оставь это тем, кто пишет умные математические книжки. В программировании ты можеш выполнять действия, которых нет в математике (например читать память или писать в неё), поэтому в жизни всё проще. В методе Хаффмана непосредственно значения вероятностей отдельных символов напрямую использовать не обязательно, достаточно чтобы 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/compression_methods_full_scanned.pdf с35-43 - там даже есть образцы реализации компрессора и декомпрессора (правда, на Си). Книга выложена её авторами на их собственном сайте.
Sameone, для частного случая сойдет
для моего - нет
я уже во всем разобрался
если интересно могу показать :)
и кстати ты не прав
есть деревья нормальные, есть вырожденные
и это оооочень видно при использовании
Jerry, в моём алгоритме деревьев вообще нет. Разобрался с деревьями - молодец, но ИМХО отсортировать одномерный массив проще чем обходить бинарное дерево. Алгоритмов сортировки море - от банальной пузырьковой до Кнут-Морриса-Пратта (время сортировки линейно зависит от количества сортируемых символов).
Интересно, к какому набору символов не подходит мой алгоритм? Я составил его после вдумчивого прочтения главы о методе Хаффмана в указанной мной книге, там традиционно - обход деревьев. Подметил свойства формируемой последовательности битов и решил ими воспользоваться.
???
Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — алгоритм, осуществляющий поиск подстроки в строке.
Метод Хаффмана максимально эффективен если вероятность нахождения символов убывает как 1/(2^N), где N - номер символа в упорядоченном по убыванию списке. Если отличие отой этой зависимости велико, результат далёк от оптимального.
Откуда сия инфа?
время сортировки линейно зависит от количества сортируемых символов
А можно такой алгоритм? А то сортировка за O(n) нобелевкой попахивает.
---------- Post added at 07:54 ---------- Previous post was at 07:53 ----------
Я составил его после вдумчивого прочтения главы о методе Хаффмана в указанной мной книге, там традиционно - обход деревьев. Подметил свойства формируемой последовательности битов и решил ими воспользоваться.
Почитай еще раз. Особенно главу, где объясняется, что такое энтропия.
Sameone, тут такой момент
в текстовом блоке может не быть символов с кодом #00 #01
в кодовом блоке и картинке их как грязи
если паковать сразу данные то у тебя 256 вариантов
если формировать набор ссылок на предыдущие данные то у тебя 65280 вариантов
теперь разберем алгоритм RNC
у меня есть дерево хаффмана
в котором каждой ветви соответствует сколько битов мне надо взять из потока
0 +1 (2-3)
10 принимаем за 1
11 принимаем за 0
010 +2 (4-7)
100 +3 (8-15)
итого самая короткая ссылка - 2 бита
самая длинная -6 бит
причем в следующий раз здесь могут быть совершенно другие значения
но алгоритм сжатия останется всегда наиболее эффективным
Jerry, в моём алгоритме деревьев вообще нет. Разобрался с деревьями - молодец, но ИМХО отсортировать одномерный массив проще чем обходить бинарное дерево. Алгоритмов сортировки море - от банальной пузырьковой до Кнут-Морриса-Пратта (время сортировки линейно зависит от количества сортируемых символов).
Интересно, к какому набору символов не подходит мой алгоритм? Я составил его после вдумчивого прочтения главы о методе Хаффмана в указанной мной книге, там традиционно - обход деревьев. Подметил свойства формируемой последовательности битов и решил ими воспользоваться.
Составь по своему алгоритму дерево для символов со следующими вероятностями:
А - 25%
Б - 25%
В - 12,5%
Г - 12,5%
Д - 12,5%
Е - 12,5%
По порядку:
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 посмотреть в сторону арифметического кодирования, которое даёт более близкий к идеалу результат.
Потому и предложил jerri посмотреть в сторону арифметического кодирования, которое даёт более близкий к идеалу результат.
ты ведь про арифметическое кодирование на спекки пошутил?
И вот с этой последовательностью символов ("КТОАЙ-_ЕС") и работает мой алгоритм.
Не увиливай от ответа. alco тебя спросил про конкретный пример- набор букв и их относительные частоты (можешь множить на 100 и получить абсолютные частоты для какого-то абстрактного текста). Вот распиши сколько бит на каждый символ потребуется после работы твоего алгоритма и какие это будут битовые цепочки.
5) Vitamin По поводу 1/(2^N) А как ты ещё представляеш себе "алгоритм Хаффмана приближает относительные частоты появления символов в потоке частотами, кратными степени двойки"? (Указанная мною книга, с 35).
Я в курсе, что иногда результат работы по методу Хаффмана бывает далёк от идеала, предписываемого теоремой Шеннона.
Это означает, что разница между реальной энтропией в исходных данных и оценкой по методу Хаффмана не будет превышать 1 бита на каждый символ- отсюда и степени двойки (вероятности 1/2, 1/4, 1/8 и т.п.). Для арифметического кодирования погрешность не превышает 1 бита на все сообщение.
ты ведь про арифметическое кодирование на спекки пошутил?
Я его реализовывал в свое время:) Ну оооочень медленно работает...
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 ----------
Я его реализовывал в свое время:) Ну оооочень медленно работает...
а осталось чтонибудь? в виде исходников
а осталось чтонибудь? в виде исходников
Оригинал найти не смог, вот оптимизированный вариант от alco.
Я его реализовывал в свое время Ну оооочень медленно работает...
я как бы на это и намекал :)
Там медленнее всего процедура ISCUC, которая инкрементирует кумулятивные частоты ВСЕХ литералов, начиная от текущего. Может, есть какой-то другой метод быстрее.
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot