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

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 бита на узел. Можно и ещё компактнее.

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