Informatika_v_sisteme_nauk_33__33__33__33_ekz

Классические алгоритмы сжатия данных. Диспетчеры архивов. Их функции.

Существует достаточно много алгоритмов сжатия данных, однако все они теоретически основаны на трех способах уменьшения их избыточности: изменение содержания данных; изменение их структуры; изменение содержания данных и их структуры. Изменение содержания данных при их сжатии делает метод сжатия необратимым и полное восстановление информации невозможно. Такие методы называются методами сжатия с регулярной потерей информации. Они применимы для данных, где формальная утрата части содержания не приводит к значительному снижению потребительских свойств. Сюда относятся мультимедийные данные: звукозаписи, рисунки и др. (форматы сжатия: .JPG для графических данных, .MP3 для звуковых данных, .MPG для видеоданных). Эти методы, обладая более высокой степенью сжатия, чем обратимые методы, неприменимы к текстовым документам, базам данных, программному коду.

В основе алгоритмов RLE лежит принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указывается код данных и коэффициент повтора. Например, для последовательности 0, 0, 0, 12, 12, 0, 23, 23, 23, 23 (10 байтов) образуется следующий вектор: 0, 3, 12, 2, 0, 1, 23, 4 (8 байтов) – здесь подчеркнуты коэффициенты повтора. В данном примере коэффициент сжатия равен 8/10 (80%). Алгоритмы RLE отличаются простотой, высокой скоростью работы, но недостаточным сжатием. Для текстовых данных эти методы неэффективны.В основу алгоритмов KWE (по ключевым словам) положено кодирование лексических единиц (пример лексической единицы: слово – последовательность символов, ограниченная с обеих сторон пробелами или символами конца абзаца) исходного документа группами байтов фиксированной длины. Результат кодирования сводится в таблицу, которая прикладывается к результирующему коду и представляет собой словарь. Пары байтов, получаемых при кодировке слов, называются токенами. Эффективность метода зависит от длины документа: прикладываемый словарь значительно увеличивает длину кратких документов. Алгоритм эффективен для англоязычных текстовых документов и файлов баз данных.В основе алгоритма Хаффмана лежит кодирование не байтами, а битовыми группами. Перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого встречаемого символа. Чем чаще встречается символ, тем меньшим числом битов он кодируется. Образующаяся в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия

Изменение структуры данных при их сжатии делает метод сжатия обратимым. Исходные данные восстанавливаются путем применения обратного метода. Обратимые методы применимы для сжатия любых типов данных (примеры форматов сжатия без потери информации: .GIF, .TIF, .PCX – для графических данных; .АVI – для видеоданных, .ZIP, .ARJ, .RAR, .LZH – для любых типов).

Теоремы (примем без доказательства):

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

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

Содержание