Сжатие данных без потерь.

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

Другим примером метода сжатия без потерь является метод RLE (Run- Length Encoding). В основу методов RLE положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указывается код данных и коэффициент повтора. Например, последовательность 0, 0, 0, 0, 0, 127,127, 127, 0; 255; 255; 255: 255, 255 объемом 14 байт можно записать в виде последовательности 0, 5, 127, 3, 0, 1, 255, 5, которая имеет объем 8 байт. В данном случае коэффициент сжатия составит 1,75.

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

На практике рассмотренные выше методы не применяются в чистом виде, так как их эффективность сильно зависит от начальных условий. В связи с этим, в современных методах сжатия данных используют более сложные методы, основанные на комбинации нескольких теоретических методов. Общим для таких комбинированных методов является предварительный просмотр и анализ исходных данных для индивидуальной настройки метода на особенности обрабатываемого материала. Примерами других методов сжатия без потерь являются метод арифметического кодирования, метод скользящего окна LZ77, LZ78, LZW и т.д.

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

2.3.3.