Код "почти-Хаффмана" (как назвать вещи своими именами) :) А) Есть поток величин, меняющихся в широком диапазоне, но в основном танцующих вокруг некоего наиболее частого значения. Соответственно, 95% величин принимают одно из нескольких десятков возможных значений, а 5% -- одно из оставшихся нескольких тысяч.
Б) Если мы используем код Хаффмана, он хорошо пожмет частые значения, а вот дерево и длины кодов для редких (которых бывают тысячи вариантов) вырастет до монструозных размеров.
В) Мы можем объединить редкие значения в один Хаффманов код, а чтобы их различать, после этого кода (и только после него) писать несколько бит, указывающих, какое именно значение (из набора "редких") у нас пришло.
Я не прошу мне помочь -- это написать немногим сложнее, чем написать этот пост :) Я прошу сказать мне, как называется такой код в литературе :)
--------------------------------
ЗЫ. Если некоторые величины сильно коррелируют (скажем, после 0 очень часто идет еще один 0, ну или там после 5 часто идет 4), то такой "парочке" можно присвоить свой отдельный код Хаффмана. В частности, в JPEG таким образом присвоены отдельные коды для последовательностей нулей: там в таблице фигурируют коды "семь нулей и за ними такая-то циферка", "двенадцать нулей и за ними такая-то циферка" и так далее. Это называется "RLE+Huffman" или я ошибаюсь?
-
- ... POV(290 знак., 07.07.2007 17:10, )