Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информатика 2015

3.4. Методы сжатия информации без потерь

Нужно писать так, чтобы словам было тесно, а мыслям просторно.

Чехов А.П.

Несмотря на то, что объемы внешней памяти ЭВМ постоянно растут, потребность в архивации не уменьшается. Это объясняется гем, что сжатие информации необходимо не только для экономии места в памяти, но и для быстрой передачи информации но сети на другие ЭВМ. Кроме того, возможность отказа магнитных, оптических и электронных носителей информации, разрушающее действие вирусов заставляют пользователей делать резервное копирование ценной информации на другие (запасные) носители информации. Очевидно, что разумнее информацию хранить сжатой.

Сжатие информации без потерь (архивация) — это такое преобразование информации, при котором объем файла уменьшается, а количество информации, содержащейся в архиве, остается прежним.

Процесс записи файла в архивный файл называется архивированием (упаковкой, сжатием), а извлечение файла из архива — разархивированием (распаковкой, извлечением). Упакованный (сжатый) файл называется архивом.

Степень сжатия информации зависит от содержимого файла и формата файла, а также от выбранного метода архивации. Степень (качество) сжатия файлов характеризуется коэффициентом сжатия Кс, который определяется как отношение объема исходного файла У0 к объему сжатого файла Ус:

Чем больше величина Кс, тем выше степень сжатия информации.

Заметим, что в некоторых литературных источниках встречается определение коэффициента сжатия, обратное приведенному отношению.

Все существующие методы сжатия информации можно разделить на два класса: сжатие без потерь информации (обратимый алгоритм) и сжатие с потерей информации (необратимый алгоритм). В первом случае исходную информацию можно полностью извлечь из архива. Во взором случае распакованное сообщение будет отличаться от исходного сообщения.

В настоящее время разработано много методов архивации без потерь. Рассмотрим две наиболее известные идеи.

Первая идея, основанная на учете частот появления символов в тексте, была разработана Клодом Шеииопом и независимо от него Робертом Фано, а затем в 1952 г. развита Дэвидом Хаффманом - аспирантом Массачусетского технологического института при написании им курсовой работы. Идея базируется на том факте, что в обычном тексте частоты появления различных символов неодинаковые. По этой причине для сжатия нужно использовать кодовые комбинации различной длины.

При кодировании символов в ЭВМ используют кодовые таблицы. При этом каждый символ кодируется либо одним байтом (СР-1251, КОИ-8), либо двумя байтами (Unicode). Кодовые таблицы стандартизируют процедуру кодирования. Однако для передачи информации но каналу связи (или для долговременного хранения на вешнем носителе) можно использовать более сложную процедуру кодирования. При данном методе архивации стандартные кодовые таблицы не используются, а создаются собственные. При этом вид кодовой таблицы каждый раз изменяется и зависит от содержимого архивируемого документа.

Задачу экономного кодирования сообщений источника, имеющего отличное от равномерного распределения вероятностей появления символов его алфавита, позволяют решить неравномерные префиксные коды.

Рассмотрим принцип построения кода методом Шеннона-Фано [2, 7, 8]. Построение кода основываются на статистических свойствах источника сообщений. При этом часто встречающимся символам алфавита ставят в соответствие короткие кодовые комбинации. Из-за того, что разным символам алфавита соответствуют кодовые комбинации разной длины, такие коды называют неравномерными.

В качестве примера сжатия методом Шеннона-Фано рассмотрим процедуру архивации сообщения «ИНН 637322757237». Данный текст содержит избыточность, которая определяется но формуле:

где Я - энтропия сообщения;

п - длина кодовой комбинации при равномерном кодировании.

Энтропия сообщения вычисляется по формуле:

где N - число символов в алфавите источника;

р, - относительная частота (вероятность) появления символа в сообщении.

Относительная частота встречаемости символа определяется как отношение абсолютной частоты появления символа в сообщении к общей длине сообщения (числу символов в сообщении):

где а>- - абсолютная частота (частость) встречаемости i-oro символа алфавита источника; т - число символов в сообщении.

В данном случае энтропия сообщения равна:

бит/символ

где - относительная частота появления символа «7»;

- относительная частота появления символов «2» и «3»;

- относительная частота появления символа «Н»;

- относительная частота появления символов «5»,

«6», «И», Пробел.

При использовании равномерного кода (например, СР-1251) длина кодовой комбинации определяется так:

[х~| - функция округления аргумента до ближайшего целого значения, не меньшего, чем X .

В данном примере бит.

Избыточность сообщения при кодировании равномерным кодом равна:

На первом этапе построения кода Шеннона-Фано формируется таблица абсолютных частот символов.

Символ

Абсолютная частота щ

Символ

Абсолютная частота щ

7

4

5

1

2

3

6

1

3

3

И

1

Н

2

Пробел

1

Для получения кодовых комбинаций строится кодовое дерево. При формировании кода Шеннона-Фано дерево строится от корня к листьям (в отличие от настоящего дерева здесь корень располагается вверху, а листья - внизу). В качестве корня используется множество всех символов алфавита сообщения, упорядоченное (ранжированное) по частоте встречаемости символов. Число сверху таблицы указывает на количество символов в исходном сообщении (см. следующий рисунок).

Затем множество символов делят на два подмножества так, чтобы новые подмножества имели равные (насколько это возможно) суммарные частоты встречаемости входящих в них символов. Например, вес 11 желательно разделить на два подмножества 5 и 6, деление на подмножества 4 и 7 будет ошибочным. Два новых подмножества соединяются с корнем дерева ветвями, становясь потомками. Левая ветвь дерева обозначается символом 1, а правая ветвь - символом 0.

Полученные подмножества рекурсивно делятся до тех пор, пока не будут сформированы листья дерева - отдельные символы сообщения.

Кодовые комбинации (на предыдущем рисунке они указаны в кавычках под соответствующими листьями) получаются при движении от корня дерева к кодируемому символу-листу путем объединения (конкатенации) бит, присвоенных пройденным ветвям дерева. Запись кодовой комбинации ведут в направлении от старших разрядов к младшим. Например, при кодировании символа «3» сначала следует пройти но правой ветви к множеству {3, Н, 5, 6, И, Пробел}. При этом в кодовую комбинацию нужно записать бит 0. Затем нужно пройти но левой всгви к множеству {3, Н} (к кодовой комбинации добавляется бит 1). Наконец, нужно пройти по левой ветви, чтобы достичь листа «3». Таким образом, получена кодовая комбинация «011».

При декодировании биты считываются из входного потока и используются, как указатели направления движения но кодовому дереву от корня к искомому листу. При достижении листа найденный символ записывается в выходной поток, а движение но кодовому дереву снова начинают от корня. Например, декодирование комбинации «010» происходит следующим образом. Из потока данных считывается бит 0, следовательно, нужно пройти по правой ветви от корня дерева к узлу {3, Н, 5, 6, И, Пробел}. Следующий бит единичный, что требует пройти по левой ветви к множеству {3, Н}. Наконец, следующий бит 0 приводит декодер но правой ветви к листу «Н».

В следующей таблице приведены все разрешенные комбинации полученного кода Шеннона-Фано. Это так называемый словарь сообщения. Он передается на приемную сторону вместе с архивом.

Символ

Кодовая комбинация

Символ

Кодовая комбинация

7

11

5

ООН

2

10

6

0010

3

011

И

0001

Н

010

Пробел

0000

Закодированное сообщение будет иметь вид:

000101001000000010011110111010110011111001111

Общая длина закодированного сообщения составляет 45 бит.

Средняя длина кодовой комбинации равна (напомним, что число символов в сообщении - 16):

Избыточность сообщения после применения кода Шеннона-Фано снизилась до значения:

Несложно убедиться, что применение кода Шеннона-Фано позволило существенно уменьшить избыточность сообщения. При равномерном кодировании рассмотренного сообщения с помощью кодовой таблицы СР-1251 пришлось бы передать не 45 бит, а 128 бит.

Вторая идея архивации состоит в учете того факта, что в файлах часто встречаются несколько подряд идущих одинаковых байтов, а некоторые последовательности байтов повторяются многократно. При архивации такие места файла можно заменить командами вида «повторить данный байт п раз» или «взять часть данных длиной к байтов, которая встречалась т байтов назад». Такой алгоритм архивации носит имя RLE (Run Length Encoding — кодирование путем учета повторений).

Понять идею этою метода упаковки позволяет следующий анекдот.

Один в прошлом известный полководец решил написать достаточно объемные мемуары. Составленные воспоминания звучали примерно так.

«Утром я вскочил на своего коня и помчался в штаб армии. Подковы коня издавали звуки «цок-цок-цок-цок-цок-цок-цок-цок-цок-цок-цок-цок- цок-цок-цок-цок ...». Через двое суток я соскочил с коня и вошел в штаб».

Для увеличения объема литературною произведения словосочетание «цок» было написано «писателем» на двухстах страницах. Очевидно, что информативность «мемуаров» не изменилась бы, если вместо 200 страниц перечисления цокающих звуков было бы указано: «Затем следуют 64 000 раз звуки «цок-цок».

Проиллюстрируем эту же идею другим примером.

Пусть имеется следующее изображение звездного неба: на черном фоне видны редкие белые звезды. При растровом представлении неба информация в ЭВМ будет храниться в таком виде: черное-черное-черное-черное- черное-белое-черное-черное-черное-черное-черное и т. д.

Естественно, что значительно компактнее хранить информацию, указав, сколько раз подряд идут черные пиксели, сколько раз белые и т. д.

Среди известных художественных произведений наибольшему сжатию методом RLE можно подвергнуть «Черный квадрат» Малевича К.С.

Рассмотрим детально основную идею метода архивации RLE.

Упакованная методом RLE последовательность состоит из управляющих байтов, за которыми следуют один или несколько байтов данных. При этом если старший бит управляющего байта равен 1, то следующий за ним байт данных нужно повторить при распаковке столько раз, сколько указано в оставшихся 7 битах управляющего байта.

Например, управляющий байт 10001001 говорит, что следующий за ним байт нужно повторить 9 раз, гак как IOOI2 =9ю.

Если старший бит управляющег о байта равен 0, то при распаковке архива нужно взять несколько следующих байтов без изменений. Число байтов, которые берутся без изменений, указывается в оставшихся 7 битах. Например, управляющий байт 00000011 говорит, что следующие за ним 3 байта нужно взять без изменений.

Рассмотрим пример архивации методом RLE.

Выполним сжатие сообщения «ИНН 22223133333» методом RLE.

Текст

Десятичный код (таблица СР-1251)

Двоичный код

Архив

И

200

11001000

00000001

Н

205

11001101

11001000

н

205

11001101

10000010

Пробел

32

00100000

11001101

2

50

00110010

00000001

2

50

00110010

00100000

2

50

00110010

10000100

2

50

00110010

00110010

3

51

00110011

00000010

1

49

00110001

00110011

3

51

00110011

00110001

3

51

00110011

10000101

3

51

00110011

00110011

3

51

00110011

3

51

00110011

Таким образом, пятнадцать байт исходного текста сжаты до тринадцати байт. Коэффициент сжатия в данном случае составил:

На рисунке показан пользовательский интерфейс одного из наиболее популярных архиваторов — WinZip.

Выделим важные возможности архиваторов:

  • • создание многотомных архивов с возможностью задания произвольного размера тома;
  • • создание самораспа- ковывающихся SFX-архивов;
  • • создание пароля для доступа к архиву.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы