небольшой вопрос по алгоритму сжатия Хоффмана

привет.

написал вот реализацию алгоритма Хоффмана для сжатия данных, а при расжатии столкнулся с одной заковыркой: допустим, буква "a" была закодирована по алгоритму Хоффмана в 000. при записи в файл я в самом начале файла сохраняю сопоставление этих кодов буквам, т.е. для "a" в файле будет записано "0". теперь же, если попробовать разжать эти данные, то, эти три нуля вырождаются в один нуль, что неверно, т.к. одному нулю уже будет соответствовать совсем другой символ. как же быть? может я что-то упустил...

 

лол
ошибка в коде
на этом мои телепатические способности ичерпались.

 

посмотри в гугле готовую реализацию алгоса. пару дней назад сам искал.

 

если у тебя a закодирован как 000, то 1 ноль уже ничему не может соответстовать.
тебе нужно кодировать все дерево. а не соответствия. например 10 != 010, ну или если все таки хочешь записывать кода, то введи для каждого символа поле длина битовйо последовательности. лучше конечно строить каноническое дерево Хаффмана. тогда можно сохранять только длины для символов.

 

скажем 000b = 'a', а 11b = 'б' стало быть если существует такой вектор: 0000001111000000 (03 С0), то у нас закодировано здесь aaббaa. Не понимаю, что здесь не так? Рассматривай выходную последовательность как поток битов(stream), а не как отдельные последовательности бит.

 

все это понятно. мне непонятно другое - как мне при считывании моего хидера с инфой о кодах на все символы определять - это "001" или "01" или же "1".
букву "a" мой алгос закодировал как "001". но при записи в хидер этих данных идет просто '1". как я теперь при считывании этой инфы с хидера распознаю, что там 001 а не 1?
вот я о чем спрашиваю.

 

Ну во-первых, если в файле закодирован 1 символ 'a' с шифром прохода по дереву равном 001, то в файл должно записаться 00100000b, т.е. 20h. А во-вторых, ты обязан сохранять дерево, а при распаковке работать с ним, только в обратно направлении.

 

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

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

 

зачем? Сбрасываешь биты по мере их накопления.
Например, если a=000, b=001, c=01, то тогда aabcaabcaabc будет сброшено в байты:
00000000 10100000 00010100 00000010 1xxxxxxx, где 'x' - еще не заполненные биты.
Для расшифровки нужно лишь иметь дерево. Начинаем вынимать биты и проходим по дереву. Либо можно иметь таблицу, как ты сделал. Тогда тоже расшифровка будет однозначной, т.к. не может быть так, чтобы были буквы с кодами 000 и 00 или 001 и 0010. Нафига сохранять длину?

 

щас обмозгую что ты сказал , погодь ))

 

все сделал.
но теперь у меня непонятная вещь происходит: если кодирую неочень длинные исходные данные, то декодируется ок. например, данный текст кодируется и декодируется ок:

но стоит лишь добавить к нему еще хотя бы один символ, и при декодировании часть букв путается.
хотя фраза "1234567890"x100 раз декодируется нормально.
ищу, где напортачил...

 

varnie
кстати я пару месяцев назад ради интереса писал на Сишниге реализацию Хаффмана, у меня похожая трабла была =)
Я не помню разобрался или нет..

 

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

 

Странно у вас как-то получается. Судя по всему вы вообще не понимаете как работает эта вся кухня. Объясняю на пальцах:

Пусть у нас есть двоичное дерево, у которого листья - это символы, которые нужно закодировать. Для кодирования\декодирования символа требуется просмотр дерева от корня к требуемому листу. Приймем, что если мы просматриваем ЛЕВОЕ поддерево то это соответстует биту "0", а если ПРАВОЕ - то бит "1".

Итак для кодирования:
1) Начинаем просмотр дерева от вершины к требуемому листу (то есть к символу-который нужно закодировать).
2) Если на текущем этапе выбирается ЛЕВОЕ поддерево - эначит записывем в выходной поток бит "0", иначе записываем в выходной поток бит "1".
3) Повторять пункт 2 пока не дойдем до требуемого листа дерева.
4) В результате - символ закодирован, а выходном потоке содержится его БИТОВАЯ последовательность.

Для декодирования:
1) Начинаем просмотр дерева от вершины.
2) Читаем бит из входного потока. Если это бит "0" - то выбираем ЛЕВОЕ поддерево, если это бит "1" выбираем ПРАВОЕ поддерево.
3) Повторять пункт 2 пока мы не достигнем листа дерева - это и есть символ, закодированный раннее
4) В результате - мы раскодировали символ и из потока прочитана битовая последовательность, соответствующая этому символу.

ЗЫ - Кстати, если это все вкурить, то плучается, что любой символ кодируется ЦЕЛЫМ кличеством бит. А если представить, например, что часть пердыдущего кода, содержит часть следующего кода - то мы получаем арифметическое кодирование. Результат - для более крутого сжатия пользуйтесь другим алгоритмом

 

Ultrin Faern,
я именно так и вкуриваю. именно так и получается, что после кодирования некоторые байты содержат в себе сразу биты на текущий символ и на последущий, или же его часть. тут всё понятно.

 

Ultrin Faern

Ну все правильно, так и есть. Как будто мы не знали?
При чем тут целое число бит? Ты о чем вообще

 

Varnie - хватит курить - я бро БАЙТЫ вообще ничего не говорил. Только про биты. То есть часть последнего БИТА последовательности (именно ЧАСТЬ) является началом следующей последовательности

Great - курить дальше - желательно про арифметическое сжатие )

 

мне это вообще не нужно вопрос задавал топикстартер

 

Ultrin Faern,
окей, босс.

 

Для страждущих - описание + исходники на C арифметического сжатия. Плюс там все объясняется, как тако может быть "мньше бита".

http://rapidshare.com/files/62547457/ARITHM.TXT.html