Способы сжатия информации

Сжатие данных можно разделить на два основных типа:

• 1) Сжатие без потерь или полностью обратимое;
• 2) Сжатие с потерями, когда несущественная часть данных утрачивается и полное восстановление невозможно.

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

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

сжатие информация лемпель зива.

Алгоритмы сжатия без потерь

Обзор алгоритмов

В настоящее время существует несколько алгоритмов сжатия без потерь, частично это открытые алгоритмы, частично коммерческие алгоритмы. Открытые алгоритмы обычно рассматривают только саму идею, не останавливаясь на проблемах ее реализации в виде программы или реализованы в виде «демонстрационной» (не очень эффективной) программы. Коммерческий алгоритм обычно включает в себя не только идею алгоритма сжатия, но и эффективную реализацию алгоритма в виде программы. Коммерческие алгоритмы не публикуются и познакомится с ними невозможно, за исключением ознакомления с результатами работы программ на базе этих алгоритмов. Соответствующие программы (ZIP, ARJ, RAR, ACE и др.) достаточно известны и с ними можно познакомиться самостоятельно.

Алгоритмы обратимого сжатия данных можно разделить на две группы:

• 1) Алгоритмы частотного анализа для подсчета частоты различных символов в данных и преобразование кодов символов с соответствии с их частотой.
• 2) Алгоритмы корреляционного анализа для поиска корреляций (в простейшем случае точных повторов) между различными участками данных и замена коррелирующих данных на код (ы), позволяющая восстановить данные на основе предшествующих данных. В простейшем случае точных повторов, кодом является ссылка на начало предыдущего вхождения этой последовательности символов в данных и длина последовательности.

Можно отметить следующие алгоритмы обратимого сжатия данных из первой группы [1]:

• 1) Метод Хаффмана — замена кода равной длины для символов на коды неравной длины в соответствии с частотой появления символов в данных. Коды минимальной длины присваиваются наиболее часто встречающимся символам. Если частоты появления символов являются степенью двойки (2ⁿ), то этот метод достигает теоретической энтропийной границы эффективности сжатия для методов такого типа.
• 2) Метод Шеннона-Фано — сходен с методом Хаффмана, но использует другой алгоритм генерации кодов и не всегда дает оптимальные коды (оптимальный код — код дающий наибольшее сжатие данных из всех возможных для данного типа преобразования).
• 3) Арифметическое кодирование — усовершенствование метода Хаффмана, позволяющее получать оптимальные коды для данных, где частоты появления символов не являются степенью двойки (2ⁿ). Этот метод достигает теоретической энтропийной границы эффективности сжатия этого типа для любого источника.

Для второй группы можно назвать следующие алгоритмы [1]:

• 1) Метод Running (или RLE) — заменяет цепочки повторяющихся символов на код символа и число повторов. Это пример элементарного и очень понятного метода сжатия, но, к сожалению, он не обладает достаточной эффективностью.
• 2) Методы Лемпеля-Зива — это группа алгоритмов сжатия объединенная общей идеей: поиск повторов фрагментов текста в данных и замена повторов ссылкой (кодом) на первое (или предыдущее) вхождение этого фрагмента в данные. Отличаются друг от друга методом поиска фрагментов и методом генерации ссылок (кодов).

В настоящее время, в различных модификациях и сочетаниях, два алгоритма — метод Хаффмана (или арифметическое кодирование) и метод Лемпеля-Зива — составляют основу всех коммерческих алгоритмов и программ.

Далее будут подробно рассмотрены несколько вариантов алгоритма сжатия Лемпеля-Зива и на основе модификации этого алгоритма Терри Уэлчем разработана действующая программа для архивирования и разархивирования файлов.