Статистические методы сжатия

⇐ ПредыдущаяСтр 4 из 5Следующая ⇒

Статистические методы используют вероятностные характеристики символов применяемого алфавита для построения стратегии сжатия. Среди этих методов наиболее известны метод Шеннона –Фано (Shannon – Fano) и метод Хаффмана (Huffman). Кратко рассмотрим особенности их применения.

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

Процесс генерации бинарных кодов должен отвечать двум основным требованиям, налагаемым на вид конечных кодовых комбинаций:

1) все комбинации должны быть различны;

2) любая комбинация меньшей длины не может быть началом любой комбинации большей длины (свойство префикса).

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

4.3.1. Метод Шеннона – Фано. Отсортированные в последовательности от максимального до минимального вероятности появления всех символов алфавита (можно использовать вероятности, полученные при изучении энтропийных свойств алфавита) в тексте делят на две части в такой пропорции, чтобы сумма вероятностей в каждой из частей была максимально близка к 0, 5. Символам верхней части приписывается старший символ бинарного кода – 1, нижней части – 0. Далее каждая из двух частей в свою очередь делится также на две части в такой пропорции, чтобы сумма вероятностей появления символов алфавита, составляющих каждую из частей, характеризовалась наименьшей разностью. Символам верхней из полученных частей приписывается второй символ кода – 1, нижней – также второй символ, но 0.

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

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

Объединение символов, таким образом, создает ветви и узлы дерева. Каждая из ветвей должна быть обозначена бинарным символом (в паре одному соответствует 1, другому – 0). Последние из объединенных символов образуют корень дерева.

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

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

КРИПТОГРАФИЧЕСКИЕ

МЕТОДЫ ПРЕОБРАЗОВАНИЯ ИНФОРМАЦИИ

Криптография является одной из двух ветвей общего научного направления – криптологии. Второй ветвью криптологии является криптоанализ. Цели криптографии и криптоанализа прямо противоположны.

В проблематике современной криптографии можно выделить следующие три типа основных задач:

1) обеспечение конфиденциальности (секретности);

2) создание условий для анонимности (неотслеживаемости);

3) обеспечение аутентификации информации и источника сообщения.

Конфиденциальность – свойство информации быть известной только допущенным и прошедшим авторизацию субъектам системы (пользователям, программам, процессам).

Авторизация – предоставление субъектам доступа к объектам системы.

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

Криптографическое преобразование, как и вышерассмотренные типы (помехоустойчивое кодирование и сжатие), состоит из двух этапов: прямого и обратного. Прямое преобразование называют шифрованием (в соответствии со стандартом ISO 7492-2 – зашифрованием, encrypt), обратное – дешифрованием (расшифрованием, decrypt). Процесс передачи зашифрованных сообщений иллюстрирует рис. 5.1.

Рис. 5.1. Зашифрование и расшифрование информации

Исходное сообщение называется открытым текстом (М от англ. message). Зашифрованное сообщение – шифртекстом, или шифрограммой (С от англ. cipfer). После обратного преобразования получаем исходный (или приближенный к нему) документ (М′ ). Оба преобразования осуществляются на основе ключей (K₁и K₂).

Ключ – секретный параметр, управляющий ходом преобразования. Ключ определяет конкретный вариант преобразования.

Если значения ключей K₁и K₂полностью совпадают, то такие криптосистемы называют симметричными, в противном случае – асимметричными.

Если пользоваться символьными обозначениями, введенными нами ранее (Х_k – данные до прямого преобразования, Х_n – данные после прямого преобразования), т. е. положить, что и то сравнительной характеристикой криптографических методов будет равенство . Это означает, что длина открытого и зашифрованного сообщений не меняется (исключение составляют методы шифрования с использованием электронной цифровой подписи).

Интруз – физическое лицо или процесс, которые реализуют неразрешенный, или несанкционированный, доступ к информации (атаку на систему).

⇐ Предыдущая 1 2 345 Следующая ⇒