2014-02-12
1004
Что такое эффективное кодирование
Эффективное кодирование
Измерение информации не имело бы никакого смысла, если бы на практике было невозможно записать информацию в указанное формулой Шенона (1) число бит. Но для этого необходимо кодирование информации, т.е. преобразование ее к другой — краткой форме записи.
Раздел «эффективное кодирование» как раз изучает способы генерации кодовых таблиц для краткой записи информации при условии возможности восстановить информацию в исходном виде без искажений.
Один из самых простых алгоритмов сжатия —алгоритм Running или RLE (Run Length Encoding). Пусть имеется сообщение из одинаковых символов. Налицо явная избыточность информации. По Шенону, кстати, количество информации в таком сообщения и вовсе равно нулю. Эффективное кодирование осуществляется следующим образом:
1) подсчитываем количество одинаковых символов в цепочке;
2) вместо цепочки одинаковых символов записываем, символ и число — сколько раз повторяется этот символ.
|
|
|
Например, строка из 40 «А»: «АААААААААААААААААААААААААААААААААААААААА». Записываем: «А40». Строка длиной 40 символов сжимается до трех символов.
Алгоритм феноменально прост, но малоэффективен. Существует информация, которая содержит повторяющиеся символы, но не может быть сжата этим алгоритмом. Например, когда повторяется не символ, а последовательность символов. Например: «АБАБАБАБАБАБ». Повторяющихся символов нет, и сжать нельзя. Можно, конечно, воспользоваться расширенным алгоритмом:
1) ищем не повторяющиеся символы, а повторяющиеся последовательности символов (в данном случае это «аб»);
2) подсчитываем, сколько раз повторяется эта последовательность;
3) записываем количество повторяющихся фрагментов (в нашем случае 6), и сам фрагмент (в нашем случае «АБ»): «6,АБ».
Но и это не предел. Могут существовать одинаковые фрагменты информации, располагающиеся в разных местах файла. Можно найти эти фрагменты. Записать в кодовую таблицу и приписать каждому определенное значение — код. После этого можно заменит все фрагменты этим кодом-ссылкой.
Несмотря на простоту идеи — реализация такого алгоритма — весьма непростая задача.
Существуют особые ситуации, когда поиск повторяющихся фрагментов может быть ускорен. Например, при передаче видеоизображения данные представляют собой последовательность кадров-картинок, состоящих из массива точек. Эти картинки имеют одинаковый размер и часто предыдущая картинка слабо отличаются от последующей (простейший пример, снимается неподвижный объект). В этом случае реализация Running-подобного алгоритма проста — записывать для каждого следующего кадра только его отличия от предыдущего и можно добиться существенного сжатия данных для медленно меняющихся изображений.
Алгоритмы, подобные RLE, называют алгоритмами корреляционного анализа — эти алгоритмы ищут зависимости (корреляции) между отдельными участками информации и заменяют найденное ссылкой на предыдущее (первое) вхождение подобного участка. К этим алгоритмам мы еще вернемся.
Существуют алгоритмы и другой природы.
