Как было сказано выше, одной из важных задач предварительной подготовки данных к шифрованию является уменьшение их избыточности и выравнивание статистических закономерностей применяемого языка. Частичное устранение избыточности достигается путём сжатия данных.
Сжатие информации представляет собой процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается размер сообщения . Алгоритмы, предназначенные для сжатия информации, можно разделить на две большие группы: реализующие сжатие без потерь (обратимое сжатие) и реализующие сжатие с потерями (необратимое сжатие).
Обратимое сжатие подразумевает абсолютно точное восстановление данных после декодирования и может применяться для сжатия любой информации. Оно всегда приводит к снижению объема выходного потока информации без изменения его информативности, то есть без потери информационной структуры. Более того, из выходного потока, при помощи восстанавливающего или декомпрессирующего алгоритма, можно получить входной , а процесс восстановления называется декомпрессией или распаковкой и только после процесса распаковки данные пригодны для обработки в соответствии с их внутренним форматом. Сжатие без потерь применяется для текстов, исполняемых файлов, высококачественного звука и графики.
Необратимое сжатие имеет обычно гораздо более высокую степень сжатия, чем кодирование без потерь, но допускает некоторые отклонения декодированных данных от исходных. На практике существует широкий круг практических задач, в которых соблюдение требования точного восстановления исходной информации после декомпрессии не является обязательным. Это, в частности, относится к сжатию мультимедийной информации: звука, фото- или видеоизображений. Так, например, широко применяются форматы мультимедийной информации JPEG и MPEG , в которых используется необратимое сжатие. Необратимое сжатие обычно не используется совместно с криптографическим шифрованием, так как основным требованием к криптосистеме является идентичность расшифрованных данных исходным. Однако при использовании мультимедиа-технологий данные, представленные в цифровом виде, часто подвергаются необратимой компрессии перед подачей в криптографическую систему для шифрования. После передачи информации потребителю и расшифрования мультимедиа-файлы используются в сжатом виде (то есть не восстанавливаются).
Рассмотрим подробнее некоторые из наиболее распространённых способов обратимого сжатия данных.
Наиболее известный простой подход и алгоритм сжатия информации обратимым путем – это кодирование серий последовательностей (Run Length Encoding – RLE ). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов на один кодирующий байт -заполнитель и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других, – не кодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток вначале кодированных цепочек. Такими метками могут быть характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже – с малым числом повторяющихся байтов в сериях.
При равномерном кодировании информации на сообщение отводится одно и то же число бит , независимо от вероятности его появления. Вместе с тем логично предположить, что общая длина передаваемых сообщений уменьшится, если часто встречающиеся сообщения кодировать короткими кодовыми словами, а редко встречающиеся – более длинными. Возникающие при этом проблемы связаны с необходимостью использования кодов с переменной длиной кодового слова . Существует множество подходов к построению подобных кодов.
Одними из широко используемых на практике являются словарные методы, к основным представителям которых относятся алгоритмы семейства Зива и Лемпела. Их основная идея заключается в том, что фрагменты входного потока («фразы») заменяются указателем на то место , где они в тексте уже ранее появлялись. В литературе подобные алгоритмы обозначаются как алгоритмы LZ сжатия .
Подобный метод быстро приспосабливается к структуре текста и может кодировать короткие функциональные слова, так как они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов. Декодирование сжатого текста осуществляется напрямую, – происходит простая замена указателя готовой фразой из словаря, на которую тот указывает. На практике LZ-метод добивается хорошего сжатия, его важным свойством является очень быстрая работа декодера.
Другим подходом к сжатию информации является код Хаффмана , кодер и декодер которого имеют достаточно простую аппаратную реализацию. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды, тогда как реже встречающимся символам – более длинные. За счет этого достигается сокращение средней длины кодового слова и большая эффективность сжатия. Коды Хаффмана имеют уникальный префикс (начало кодового слова), что и позволяет однозначно их декодировать, несмотря на их переменную длину.
Процедура синтеза классического кода Хаффмана предполагает наличие априорной информации о статистических характеристиках источника сообщений. Иначе говоря, разработчику должны быть известны вероятности возникновения тех или иных символов, из которых образуются сообщения. Рассмотрим синтез кода Хаффмана на простом примере.
p(S 1)=0,2, p(S 2)=0,15, p(S 3)=0,55, p(S 4)=0,1
