|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Goldobin 2:5020/400 12 Apr 2003 12:04:48
To : Vit Arsentyev
Subject : Re: "Стопка книг"
--------------------------------------------------------------------------------
Hi!
> DG> Hасколько я помню, это какая-то разновидность хаффмана с динамическим
> DG> словарем? Длину кода там нельзя заранее определить, просто читаешь
побитно
> DG> и после очередного бита определяешь, считан ли весь код полностью. Hу
> DG> допустим словарь из всего 3 кодов 0,10,11 считав первый бит ты
определяешь
> DG> нужно ли читать следующий для получения полного кода.
> Я несовсем понял.
> Как определить нужен еще один бит или нет?
> Допустим словарь из 255 кодов.
> Самые частые символы кодируются одним битом, самые редкие - восемью.
> Как узнать сколько бит читать для следующего кода?
> В Хаффмане все понятно, там еще хранится дерево (или какая-то таблица?).
> Hо Хаффман не подходит так как требует двух проходов.
Попробовал найти в инете, но нашел только очень общее описание. Если я
правильно понял, то используется одно фиксированное, заранее заданное
дерево, типа хаффмана, но еще дополнительно используется таблица
перекодировки, в которой и происходят все изменения после чтения каждого
кода. То есть строишь допустим дерево, в котором код 0 кодируется четырьмя
битами, а код FF двенадцатью битами. Заполняешь таблицу перекодировки
значениями 0-FF. После чтения очередного кода вытаскиваешь соответствующее
значение из таблицы перекодировки, это значение перемещаешь в начало
таблицы, сдвигая остальные. Допустим у тебя исходный файл забит FF. Первый
код FF закодируется 12 битами, все последующие четырьмя.
Это если я правильно понял описание алгоритма.
Bye.
--- ifmail v.2.15dev4
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
