Сжатие данных
Теоретические основы сжатия данных
Обратимость сжатия
Алгоритмы сжатия данных.
Программные средства сжатия данных
Базовые требования к диспетчерам архивов
Теоретические основы сжатия данных
Характерной особенностью большинства типов данных, является избыточность.
Степень избыточности зависит от типа данных. У видеоданных степень избыточности в несколько раз больше, чем у графических, а степень избыточности графических данных в несколько раз больше, чем текстовых. Степень избыточности данных зависит от принятой системы кодирования.
При обработке информации избыточность также играет важную роль. Так, например, при преобразовании информации избыточность используют для повышения ее качества (актуальности, адекватности и т. п.).
Объекты сжатия
В зависимости от того, в каком объекте размещены данные, подвергаемые сжатию, различают:
• уплотнение(архивацию) файлов;
• уплотнение (архивацию) папок;
• уплотнение дисков.
• Уплотнение файлов применяют для уменьшения их размеров при подготовке к передаче по каналам электронных сетей или к транспортировке на внешнем носителе малой емкости
• Уплотнение папок используют как средство архивации данных перед длительным хранением, в частности при резервном копировании.
• Уплотнение дисков служит для повышения эффективности использования их рабочего пространства.
Обратимость сжатия
Существует три способа сжатия данных.
Это изменение содержания данных, изменение их структуры, либо и то и другое вместе.
Если при сжатии данных происходит изменение их содержания, метод сжатия необратим и при восстановлении данных из сжатого файла не происходит полного восстановления исходной последовательности. Такие методы называют методами сжатия с регулируемой потерей информации. Они применимы только для типов данных, для которых формальная утрата части содержания не приводит к значительному снижению потребительских свойств. Это относится к мультимедийным данным: видеорядам, музыкальным записям, звукозаписям и рисункам.
Методы сжатия с потерей информации обеспечивают более высокую степень сжатия, чем обратимые методы, но их нельзя применять к текстовым документам, базам данных и, к программному коду.
Характерными форматами сжатия с потерей информации являются:
.JPG для графических данных;
.MPG для видеоданных;
МРЗ для звуковых данных.
Если при сжатии данных происходит только изменение их структуры, то метод сжатия обратим.
Из результирующего кода можно восстановить исходный массив путем применения обратного метода. Обратимые методы применяют для сжатия любых типов данных.
Характерными форматами сжатия без потери информации являются:
•.GIF,.TIP,.PCX и многие другие для графических данных;
•.AVI для видеоданных;
•.ZIP,.ARJ,.RAR,.LZH,.LH,.CAB и многие другие для любых типов данных.
Алгоритмы обратимых методов
При исследовании методов сжатия данных следует иметь в виду существование следующих доказанных теорем.
• Для любой последовательности данных существует теоретический предел сжатия, который не может быть превышен без потери части информации.
• Для любого алгоритма сжатия можно указать такую последовательность данных, для которой он обеспечит лучшую степень сжатия, чем другие методы.
• Для любого алгоритма сжатия можно указать такую последовательность данных, для которой данный алгоритм вообще не позволит получить сжатия.
Существует достаточно много обратимых методов сжатия данных, однако в их основе лежит сравнительно небольшое количество теоретических алгоритмов, представленных в таблице 1.
Алгоритмы сжатия данных.
Алгоритм RLE.
В основу алгоритмов RLE положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указывается код данных и коэффициент повтора.
Например, для последовательности: 0; 0; 0; 127; 127; 0; 255; 255; 255; 255 (всего 10 байтов) образуется следующий вектор:
При записи в строку он имеет вид:
Всего 8 байтов).
В данном примере коэффициент сжатия равен 8/10 (экономия объема составляет 20%).
Программные реализации алгоритмов RLE отличаются простотой, высокой скоростью работы, но обеспечивают недостаточное сжатие. Наилучшими объектами для данного алгоритма являются графические файлы, в которых большие одноцветные участки изображения кодируются длинными последовательностями одинаковых байтов. Этот метод также может давать заметный выигрыш на некоторых типах файлов баз данных, имеющих таблицы с фиксированной длиной полей. Для текстовых данных методы RLE не эффективны.
Алгоритм KWE
В основу алгоритмов кодирования по ключевым словам (Keyword Encoding) положено кодирование лексических единиц исходного документа группами байтов фиксированной длины. Лексическая единица - слово (последовательность символов, справа и слева ограниченная пробелами или символами конца абзаца). Результат кодирования сводится в таблицу, которая прикладывается к результирующему коду и представляет собой словарь. Для англоязычных текстов используется двухбайтная кодировка слов. Образующиеся при этом пары байтов называют токенами.
Алгоритм эффективен для англоязычных текстовых документов и файлов баз данных. Для русскоязычных документов, отличающихся увеличенной длиной слов и большим количеством приставок, суффиксов и окончаний, не удается ограничиться двухбайтными токенами, и эффективность метода снижается.
Алгоритм Хаффмана
В основе этого алгоритма лежит кодирование не байтами, а битовыми группами.
• Перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов.
• Чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется (соответственно, чем реже встречается символ, тем длиннее его кодовая битовая последовательность).
• Образующаяся в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия.
Пример кодирования символов русского алфавита представлен на рис. 1. Как видно из схемы, представленной на рисунке, используя 16 бит, можно закодировать до 256 различных символов. Однако ничто не мешает использовать и последовательности длиной до 20 бит — тогда можно закодировать до 1024 лексических единиц (это могут быть не символы, а группы символов, слоги и даже слова).
В связи с тем, что к сжатому архиву необходимо прикладывать таблицу соответствия, на файлах малых размеров алгоритм Хаффмана малоэффективен. Эффективность алгоритма зависит и от заданной предельной длины кода (размера словаря). Наиболее эффективными оказываются архивы с размером словаря от 512 до 1024 единиц (длина кода до 18-20 бит).