Отметим важную характеристику кода Хаффмана - ни один битовый код не начинается с другого битового кода. Это позволяет расшифровать список кодированных значений из файла, используя табл. 15.2 и табл. 15.3. Чтобы продемонстрировать алгоритм декодирования, предположим, что сжатый файл содержит поток битов {100100100 …}. Первое битовое значение в этом файле равно 1, так что оно должно представлять значение 96, поскольку в таблице декодирования есть битовый код 1, и это значение не может быть префиксом ни одного другого кода. Далее имеем битовое значение 0. Других однобитовых кодов, кроме 1, нет, кроме того, нет двухбитовых кодов, поэтому следующий код - 001 или 0010. Проверяя таблицу индексированных кодов, находим файловое значение 210 и код 0010, что означает, что файлового значения с кодом 001 быть не может. На этом этапе декодированы первые два файловых значения 96 и 210. Следующий код в потоке битов должен быть равен 010 или 0100. Файловое значение с кодом 010 существует, поэтому четырехбитового кода с таким префиксом быть не может. Следовательно, третье декодированное файловое значение равно 141. Подобным образом продолжаем анализировать поток битов, пока сжатый файл не будет декодирован полностью.

ТАБЛИЦА 15.2. Коды Хаффмана с индексами для файла-примера

ТАБЛИЦА 15.3. Справочная таблица битовых кодов

Кроме того, можно использовать другие схемы для генерации и распределения битовых кодов Хаффмана. Подсчитав частоту вхождения элементов, каждому файловому значению можно присвоить длину кода. Зная длины кодов и частоту вхождения, для разработки конкретные битовых кодов можно затем использовать алгоритм слияния списков. Кроме того, для присвоения кодов файловым значениям можно применить предопределенный набор кодов. Преимущество этого подхода - не нужно хранить коды в сжатом файле.

АРИФМЕТИЧЕСКОЕ КОДИРОВАНИЕ

В данной схеме сжатия для получения численных кодов последовательностей файловых значений используется частота вхождения элемента в файл. В алгоритме арифметического кодирования вначале вычисляется доля файла, занятая каждым значением. В результате получается набор подынтервалов, принадлежащих единичному интервалу от 0,0 до 1,0. Затем каждая доля файла последовательно отображается в данные подынтервалы, и устанавливаются численные интервалы для различных комбинаций файловых значений. Для кодирования этих комбинаций используются численные границы подынтервалов.

ФОРМАТ ОСНОВНОГО ФАЙЛА

Для представления графических данных с различным содержимым были разработаны сотни форматов файлов для различных систем. Операционные системы, например, в программах системной обработки обычно используют несколько специально разработанных форматов. Помимо этого, существуют отдельные форматы для специфических приложений, например, трехмерное моделирование, анимация, графические пользовательские интерфейсы, программы бегущих лучей, видеозапись, программы научной визуализации и рисования, текстовые редакторы, пакеты табличных вычислений, связь в Internet, телевещание и передача по факсу. Кроме того, комитеты по стандартизации ISO и ANSI предложили несколько форматов и систем сжатия файлов общего пользования.

⇐ вернуться назад | | далее ⇒