Составители:
30
вола, имеющих минимальные вероятности, причем данной верши&
не приписывается суммарная вероятность ее ветвей. В результате
все вершины сходятся к одной корневой вершине, которая долж&
на получить вероятность 1. После построения дерева ветвям при&
сваиваются значения 1 или 0 в зависимости от того, в какую сто&
рону они расходятся от текущей вершины. Код каждого символа
можно получить, записав последовательность нулей и единиц,
которыми обозначены ветви на пути от вершины к данному симво&
лу. В выходной файл вначале записывается кодовая таблица, а
далее – поток битов переменной длины. Следует отметить, что иног&
да применяется заранее сформированная, т. е. стандартная, таб&
лица кодировки, как, например, в формате TIFF. Основное огра&
ничение данного метода – необходимость существенных различий
вероятности появления различных символов.
В методе LZW&кодирования использован другой подход, который
не требует предварительно создавать и хранить вместе с закодиро&
ванным файлом таблицу кодов. Метод основан на поиске в сжимае&
мой информации повторяющихся сочетаний различных кодов, кото&
рые, в свою очередь, кодируются более короткой последовательнос&
тью нулей и единиц. Сначала часть информации записывается без
сжатия, а далее следуют либо другие несжатые последовательности
кодов, либо данные, которые указывают, где можно найти требуе&
мую последовательность кодов в уже записанной информации. Та&
кие широко известные программы сжатия без потерь как PKZIP, RAR,
ARC используют различные модификации LZW&метода, который
иногда называется «методом на основе словаря», так как в процессе
Рис. 3.5. Дерево кодов Хаффмана
доK000101011001101110111111111
ловмиСABCDEFGH
ьтсонтяореВ52.012.091.051.080.070.030.020.0
Страницы
- « первая
- ‹ предыдущая
- …
- 28
- 29
- 30
- 31
- 32
- …
- следующая ›
- последняя »
