Алгоритмы методов сжатия

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

Таблица 8.1

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

Алгоритм	Выходная структура	Сфера применения	Примечание
RLE (Run-length Encoding)	Список (вектор данных)	Графические данные	Эффективность алгоритма не зависит от объема данных
KWE (Keyword Encoding)	Таблица данных (словарь)	Текстовые данные	Эффективен для массивов большого объема
Алгоритм Хаффмана	Иерархическая структура (дерево кодировки)	Любые данные	Эффективен для массивов большого объема

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

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

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

Дата добавления: 2015-10-21