|
При декодировании кодовая таблица не нужна, поскольку первоначально инициируется словарь в соответствии с таблицей 8.1. По мере поступления кодов комбинаций исходных отсчетов, в процессе декодирования составляется кодовая таблица, идентичная той, что была составлена кодером.
Алгоритм
Прочитать код сжатых данных в буфер Code.
Далее в цикле до конца потока выполняются следующие операции:
Если Code равен коду очистки, то
Инициализировать таблицу кодов.
Прочитать следующий код сжатых данных.
Найти последовательность байтов в кодовой таблице, соответствующую коду Code и записать ее в файл изображения.
Скопировать Code в буфер OldCode.
Если Code равен коду конца записи, то завершить работу.
Иначе:
Если Code находится в таблице, то
вывести соответствующую ему декодированную последовательность отсчетов в файл;
последовательность отсчетов, соответствующую OldCode + первый байт последовательности, соответствующей Code, добавить в кодовую таблицу;
cкопировать Code в буфер, где хранится OldCode.
Иначе, если Code не находится в таблице, необходимо:
сформировать последовательность, соответствующую OldCode + первый байт последовательности OldCode и вывести значения декодированного кода в файл изображения;
добавить в таблицу полученную последовательность байтов;
скопировать Code в буфер, где хранится OldCode.
Прочитать код Code из входного потока. Перейти на начало цикла.
Для приведенного примера процесс декодирования выполняется в соответствии с таблицей 8.3.
Таблица 8.3. Пример декодирования по алгоритму LZW
Чтение кода
№
|
Код, вводимый
из потока
|
Последовательность байтов, выводимых
в файл изображения
|
Содержимое таблицы кодов
|
OldCode
|
0
|
256
|
|
|
|
1
|
7
|
7
|
Инициализировать таблицу
|
7
|
2
|
258
|
7,7
|
258 7,7
|
258
|
3
|
10
|
10
|
259 7,7,10
|
10
|
4
|
10
|
10
|
260 10,10
|
10
|
5
|
258
|
7,7
|
261 10,7
|
258
|
6
|
5
|
5
|
262 7,7,5
|
5
|
7
|
5
|
5
|
263 5,5
|
5
|
8
|
257
|
|
|
5
|
В результате декодирования исходная последовательность байтов восстановлена без потери информации.
Метод сжатия LZW может быть применен не только для кодирования восьмиразрядных данных, но и для кодирования данных произвольной разрядности. В этом случае кодовые размерности объединяются в группы из восьми разрядов. Например, в четырехразрядных данных два отсчета объединяются в один, а при 16-разрядном представлении один отсчет разбивается на 2 группы. Коэффициент сжатия при использовании этого метода равен обычно 2-3.
Метод кодирования Хаффмана
Метод кодирования Хаффмана [55] относится к группе методов сжатия данных без потерь информации. Этот метод используется для поддержки факсимильной связи и представления документов. Применяется также при записи графических изображений в файлы и является компонентом алгоритмов сжатия данных JPEG и MPEG - 2. Метод предложен Дэвидом Хаффманом в 1952 г. Особенностью метода является использование кодов переменной длины, при этом наиболее
вероятным символам присваиваются наиболее короткие кодовые слова, а менее вероятным – длинные. Благодаря такой стратегии, код Хаффмана дает минимальную среднюю длину кодовой последовательности, приближающуюся к энтропии источника сообщения. Рассмотрим построение кодовой таблицы на примере. Пусть кодируется 13 символов упорядоченных по невозрастанию вероятности их появления: {А1, A2,…,
А13}. Пусть вероятности появления Ai обозначаются
pi и составляют {0,2;
0,18; 0,1; 0,1; 0,1; 0,06; 0,06; 0,04; 0,04; 0,04; 0,04; 0,03; 0,01}
соответственно. Алгоритм можно описать следующим образом.
Объединяются два символа с наименьшими вероятностями в узел кодового дерева, этому узлу приписывается вероятность, равная сумме вероятностей появления символов, составляющих узел. В примере минимальную вероятность имеют символы А12 и А13, суммарная вероятность которых равна 0,04. Далее объединяются символы или узлы с минимальными вероятностями, образуя следующий узел, которому присваивается вероятность, равная сумме вероятностей составляющих.
Процесс повторяется до тех пор, пока не сойдется в один узел, расположенный в вершине. После этого левые и правые ветви дерева обозначаются «0» и «1» соответственно (или наоборот, «1» и «0»). Значение кодового слова формируется в виде последовательности кодов ветвей по пути от вершины кодового дерева к узлу. Кодовое дерево для приведенного примера представлено на рисунке 8.5. В результате кодирования по методу Хаффмана получены коды, приведенные в таблице
8.4. В таблице 8.4 Li
- длина кодового слова i-го символа (в количестве
разрядов). Код Хаффмана является префиксным кодом, то есть таким, что ни одно кодовое слово не является префиксом (началом) другого кодового слова. Префиксные коды декодируются однозначно, но обратное утверждение не выполняется. Например, код {0, 01, 010, 0,0101, …,} не является префиксным, хотя декодируется однозначно.
Таблица 8.4 Таблица кодов для последовательности {A1,...,A13}
Имя
|
Код
|
Li
|
pi
|
Имя
|
Код
|
Li
|
pi
|
A 1
|
00
|
2
|
0,2
|
A8
|
10101
|
5
|
0,04
|
A2
|
100
|
3
|
0,18
|
A9
|
10110
|
5
|
0,04
|
A3
|
110
|
3
|
0,1
|
A10
|
10111
|
5
|
0,04
|
A4
|
010
|
3
|
0,1
|
A11
|
11110
|
5
|
0,04
|
A5
|
011
|
3
|
0,1
|
A12
|
111110
|
6
|
0,03
|
A6
|
1110
|
4
|
0,06
|
A13
|
111111
|
6
|
0,01
|
A7
|
10100
|
5
|
0,06
|
|
|
|
|
Lср
Средняя длина кода может быть получена в соответствии с формулой:
N
pi Li . (8.2)
i 1
Для рассмотренной последовательности средняя длина кода составляет
3,42 разряда.
A1 p1=0,2
A2 p2=0,18
A3 p3=0,1
A4 p4=0,1
A5 p5=0,1
A6 p6=0,06
A7 p7=0,06
A8 p8=0,04
A9 p9=0,04
В приведенном примере таблица кодов построена в соответствии с частотой появления символов во входной последовательности.
A10 p10=0,04
A11 p11=0,04
A12 p12=0,03
A13 p13=0,01
1
Рисунок 8.5 Формирование кодового дерева по методу Хаффмана.
Процедура кодирования в этом случае выполняется в два этапа. Вначале оцениваются частоты появления символов в последовательности, строится кодовая таблица, а затем, на втором этапе, производится собственно кодирование.
Для декодирования необходимо передать с потоком кодовую таблицу, содержащую алфавит (все символы от A1 до A13) и соответствующие им коды. На практике часто используют модифицированный алгоритм Хаффмана, при котором применяется заранее составленная на основании статистических данных кодовая таблица. Именно так выполняется кодирование в формате JPEG.
Do'stlaringiz bilan baham: |
