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

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

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

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

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

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

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

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

Алгоритм RLE

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

Например, для последовательности: 0; 0; 0; 127; 127; 0; 255; 255; 255; 255 (всего 10 байтов) образуется следующий вектор:

При записи в строку он имеет вид:

0; 3; 127; 2; 0; 1; 255; 4 (всего 8 байтов)

В данном примере коэффициент сжатия равен 8/10=0,8=80%

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

Алгоритм KWE

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

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

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

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

 

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

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

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

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

 

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

 

 

 

Рис. 1. Пример побуквенного кодирования русского алфавита по алгоритму Хафмана.

 

Как видно из схемы, представленной на рис.1, используя 16 бит, можно закодировать до 256 различных символов. Однако ничто не мешает использовать и последовательность длиной до 20 бит – тогда можно закодировать до 1024 лексических единиц (это могут быть не символы, а группы символов, слоги и даже слова).

В связи с тем, что к каждому архиву необходимо прикладывать таблицу соответствия, на файлах малых размеров алгоритм Хафмана мало эффективен. Практика также показывает, что его эффективность зависит от заданной предельной длины кода (размера словаря). В среднем наиболее эффективными являются архивы с размером словаря от 512 до 1024 единиц (длина кода до 18-20 бит).

 

Синтетические алгоритмы

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