|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 11 Jun 2002 11:32:10
To : Dmitry Pacuk
Subject : однобитный сигнал жать
--------------------------------------------------------------------------------
Mon Jun 10 2002 16:02, Dmitry Pacuk wrote to Sergey Kabikov:
DP>>> Чем поcоветуете cжимать однобитный cигнал? Единcтвенное, что
DP>>> пpиходит в голову, пиcать вpемя между изменениями бита, еcли вpемя
DP>>> больше 127 -- пиcать cтаpшие 7 бит чиcла+ включенный 7 бит, потом
DP>>> cледующие 7 бит и т.д.
SK>> подход к сжатию будет зависеть прежде всего от свойств самого сигнала
SK>> - есть ли корреляция (вероятностная, ессно) между соседними (и не
SK>> только) битами и если есть - то какая.
DP> Соcтояние некой линии поcледовательного интеpфейcа, запиcываемое c
DP> большим количеcтвом выбоpок в cекунду. Соответcтвенно, в пачке фpонты
DP> идут чаcто, потом пауза офонаpенной длительноcти, котоpую тоже надо
DP> cохpанить.
Hет, ну напрасно ты не пошел куда послали - в RU.COMPRESS. Там профи.
Я попробую ответить в меру познаний здесь и, надеюсь, за один раз меня не
заплюсуют. Hо за продолжением - к ФАКу той же RU.COMPRESS.
Итак :
- препроцессинг делаем через RLE. Hа примере :
11100001101 -> "Стартуем с единицы" (это один бит и только один раз в начале
сеанса/файла) -> "3 бита" -> "4 бита" -> "2 бита" -> "1 бит" ...
т.е. выходная цепочка чисел получается 3-4-2-1-...
- Если известно, что числа некоррелированы, т.е. вероятность N+1-го числа в
цепочке не зависит от того, какие числа были на N, N-1, ... позициях, то
полученную цепочку сразу жмем Хаффманом или арифметиком. Если корреляция есть
- промежуточный этап, скорее всего PPM, сильно улучшит сжатие. Статический
Хаффман может быть выгоден, если цепочки недлинные и распределение вероятности
чисел статично и известно заранее, в противном случае почти наверняка выгоднее
арифметическое кодирование.
Это, пожалуй, все, что можно уложить в одно письмо. Детальные алгоритмы - в
упомянутом ФАКе. Взять и его, и многое другое по теме можно по адресу
http://compression.graphicon.ru/ Рекомендую.
С уважением
Сергей
...Попытка - первый шаг к провалу (с) Р.Хайнлайн
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
