Метод повторяющихся последовательностей

 

Метод повторяющихся последовательностей (Run-Length Encoding - RLE) является наиболее простым из известных алгоритмов сжатия информации и используется в основном для сжатия графических файлов. Классический вариант этого метода предусматривает замену последовательности повторяющихся символов на строку, содержащую сам этот символ, и число повторов этого символа.

Пример 4.1: Строка АААББББВВВВВГГ будет записана в виде: 3А4Б5В2Г. Здесь содержится 14 символов. Как известно, для представления одного символа требуется 1 Байт, или 8 бит. Для представления всей последовательности требуется 14*8=112 бит, а после сжатия нужно лишь 8*8=64 бита, т. е. даже на таком маленьком массиве данных объем уменьшается почти вдвое. В то же время применение этого метода для сжатия текстовых или исполняемых (EXE, COM) файлов оказывается неэффективным, а общим недостатком RLE

является достаточно низкая степень сжатия.

Вероятностные методы

 

К ним относятся алгоритмы Шеннона-Фено и Хаффмана. В их основе лежит идея построения дерева, на ветвях которого положение каждого символа определяется частотой его появления в файле. Каждому символу присваивается код, длина которого обратно пропорциональна частоте появления символа в файле.

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

Пример 4.2: Имеется строка символов, в которой используются 6 первых букв русского алфавита: А, Б, В, Г, Д и Е. На первом этапе она разбивается на две части так, чтобы суммы частот появления символов в них были приблизительно равны: А(8)-Б(2)-В(3) и Г(4)-Д(1)-Е(6). Для левого подмножества каждому символу приписывается "0", для правого - "1". Затем каждое из этих двух подмножеств делится пополам, и процедура повторяется для каждого из подмножеств. В конечном итоге в каждом подмножестве останется по одному символу.

В результате каждый из символов получает свой код ("А" - 00, "Б" - 011, "В" - 010 и т. д.), по которому к нему можно добраться с вершины дерева. При этом, чем чаще встречается символ в файле, тем ближе он к вершине дерева и тем короче его адресный код.

Метод Хаффмана очень похож на метод Шеннона-Фено, но создание дерева в нем начинается не с вершины, а с корня. Это метод сжатия, который уменьшает среднюю длину кода для символов.

Код Хаффмана может быть построен по следующему алгоритму. Сначала выписываются в строку все символы алфавита в порядке возрастания или убывания частоты (вероятности) их появления в сообщении. Для нашего примера это будет последовательность: А(8)-Е(6)-Г(4)-В(3)-Б(2)-Д(1).

Последовательно объединяются два символа с наименьшими частотами появления (в данном случае "Б" и "Д") в новый составной символ, вероятность появления которого полагается равной сумме частот составляющих его символов. Присваивая ветвям дерева "0" и "1", так же, как и в предыдущем методе, поднимаемся к вершине, получая код для каждого символа. В результате формируется дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него. Затем отcлеживается путь к каждой ветви и помечает направление к каждому узлу (например, направо - "1", налево - "0").

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

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

Арифметические алгоритмы

 

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

Пpи аpифметическом кодиpовании текст пpедставляется вещественными числами в интеpвале [0; 1]. По меpе кодиpования текста, отобpажающий его интеpвал уменьшается, а количество бит для его пpедставления возpастает. Последующие символы текста сокpащают величину интеpвала исходя из значений их веpоятностей. Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, добавляют меньше бит к pезультату.

Пример 4.3: Рассмотрим кодирование двух символов "А" и "Б" с вероятностями 0,666 и 0,333. Кодируя сообщение, для символа "А" выбираем интервал [0; 0,666], для символа "Б" - [0,666; 1]. Для двух символов получим: "АА" - [0; 0,444], "АБ" - [0,444; 0,666], "БА" - [0,666; 0,888] и для "ББ" - [0,888; 1].

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

Метод словарей

 

Этот алгоритм был впервые описан в работах Абрахама Лемпеля и Якоба Зива (двухступенчатое кодирование). На сегодняшний день этот алгоритм, известный как LZ-алгоритм, и его модификации получили наиболее широкое распространение по сравнению с другими алгоритмами сжатия. В его основе лежит идея замены наиболее часто встречающихся последовательностей символов (строк) в файле ссылками на образцы, хранящиеся в специально создаваемом словаре. Так, создав словарь, содержащий 65 536 наиболее употребительных слов, можно представить текстовые файлы в виде последовательности

16-битовых ссылок на место данного слова в словаре.

Пример 4.4: Если программа сжатия уже имеет в словаре последовательность "АБВ" и обнаружит последовательность "АБВА", то она вначале занесет в выходной файл код из словаря для "АБВ", затем для символа "A", после чего последовательность "АБВА" будет добавлена в словарь. Если же она позже встретит "АБВАБ", то выведет код для "АБВА", затем код для символа "Б" и

добавит "АБВАБ" в словарь. Когда программа встречает последовательность из словаря, она выдает код и добавляет новую запись, которая на один байт длиннее. То есть каждый раз при повторении последовательности словарь будет расти за счет включения продолжения этой последовательности.

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

Упомянем и об алгоритме Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW), который отличают невысокие требования к памяти и более низкая степень сжатия по сравнению со схемой двухступенчатого кодирования. Этот алгоритм просматривает входной поток, разбивая его на подстроки и добавляя новые коды в конец словаря. Он преобразует поток символов на входе в поток индексов ячеек словаря на выходе.

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

 

Список рекомендуемой литературы

1.Цуприков А.А. Основы баз данных. Учебное пособие для студентов спец. 351400.-Прикладная информатика в экономике. -Краснодар: Внутр. кафедр. изд., 2004. –40 с.:ил.

2. Цуприков А.А., Бычков А.В.Базы данных. Лабораторный практикум. Методические указания по выполнению лабораторных работ для студентов спец. 351400.-Прикладная информатика в экономике. -Краснодар: Внутр. кафедр. изд., 2004. –100 с.:ил.

3. Цуприков А.А., Кузнецова Л.М.Базы данных. Методические указания по выполнению курсовой работы для студентов спец. 351400.-Прикладная информатика в экономике заочной формы обучения.. -Краснодар: Внутр. кафедр. изд., 2004. –28 с.: ил

4. Костюк А.И. Базы данных и знаний. Курс лекций. -Таганрог, Изд-во ТРГУ, -1999. -172 с.

5. Малыхина М.П. Базы данных / Учебное пособие.-Краснодар: Изд-во КубГТУ, 1999. -143 с.

6. Мейер Д. Теория реляционных баз данных. –М.: Мир, 1987. -608 с.

7. Морозов А.Д. Введение в теорию фракталов. Учебное пособие. –Нижний Новгород: Изд-во НГУ, 1999. 140 с.