LINUX.ORG.RU

Сжатие данных при помощи lzw

 ,


0

1

Здравствуй, лор. Из айтишных форумов я посещаю только тебя, поэтому спросить мне больше негде.

Пытаюсь закодить LZW. Как работает сам алгоритм, понял хорошо. Возникают проблемы с его реализацией. Сразу оговорюсь, что в качестве яп — java.

Ограничим размер самого длинного кода в словаре 12-ю битами. Допустим, я считал какой-то блок данных (используя жабий FileInputStream), корректно обработал его и получил для него список кодов (пусть он хранится в ArrayList). Теперь передо мной стоит задача: как сохранить этот набор кодов (в файл) так, чтобы можно было бы потом корректно его считать. Т.е. если все коды имеют переменную длину, то как при декодировании один код отличить от другого в непрерывном потоке байт?

UPD: вот тут - LZW.jar, BinaryStdOut.jar делается по-наивному. Как я понял, все коды просто приводятся к длине в 12 бит, поэтому проблем при декодировании не возникнет. Но это неоптимально по сжатию.

Сначала ты написал

получил для него список кодов (пусть он хранится в ArrayList)

а потом

как сохранить этот набор кодов так, чтобы можно было бы потом корректно его считать.

Если он уже сохранен как список, зачем его опять сохранять?

hotpil ★★★★ ()
Последнее исправление: hotpil (всего исправлений: 1)
Ответ на: комментарий от hotpil

Видимо камрад имеет ввиду как потом пройти по этому префиксному дереву в поисках нужного значения.

Но вообще ,если ты все правильно сделал, то у тебя не должно быть проблем. Первае совпавшая последовательность из словаря должно быть валидной.

хм .. яж правильно помню, что это в lzw строится битовый trie? или это другой алгоритм?

anonymous ()
Ответ на: комментарий от anonymous

хм .. яж правильно помню, что это в lzw строится битовый trie? или это другой алгоритм?

Не,это Хаффман)

DaniilA ()
Ответ на: комментарий от hotpil

Я имел ввиду записать его (этот ArrayList с кодами) в файл.

DaniilA ()

Размер групп фиксированный. Алгоритм в заатаченых реализациях просто соответсвует определнию LZW.

Вы, кстати, не первый кто посчитал это не оптимальным (stack).

UnknownNPC ()

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

iliyap ★★★★★ ()
Последнее исправление: iliyap (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.