Алгоритмы обратимых методов

При исследовании методов сжатия данных следует иметь в виду существование следующих теорем:

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

2. Для любого алгоритма сжатия можно указать такую последовательность данных, для которой он обеспечит лучшую степень сжатия, чем другие методы.

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

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

Свойства алгоритмов сжатия

Алгоритм RLE

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

Например, для последовательности: 0;0;0;127;127;0;255;255;255;255 (всего 10 байтов) образуется следующий вектор: 0;3;127;2;0;1;0255;4 (всего 8 байтов). Коэффициент сжатия равен 8/10 (80 %).

Программы реализации алгоритмов RLE отличаются простотой, высокой скоростью работы, но обеспечивают недостаточное сжатие. Лучше всего данным алгоритмом сжимаются графические данные, в которых большие одноцветные участки кодируются длинными последовательностями одинаковых байтов. Для текстовых данных методы RLE неэффективны.

Алгоритм KWE

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

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

Данный алгоритм наиболее эффективен для англоязычных текстов, баз данных.

Алгоритм Хафмана

В основе этого алгоритма лежит кодирование не байтами, а битовыми группами.

· Перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов.

· Чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется.

· Образующаяся в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия.

Пример кодирования русского алфавита:

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