Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации icon

Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации




Скачати 337.87 Kb.
НазваГосударственный университет информационно-коммуникационных технологий кафедра систем защиты информации
Дата конвертації24.11.2012
Розмір337.87 Kb.
ТипЛекция
1. /Модуль 2/ЛЗ4-5.doc
2. /Модуль 2/ЛЗ6 центр безопасности.doc
3. /Модуль 2/Лекция 05.doc
4. /Модуль 2/Лекция 06.doc
План введение Цель и содержание работы
Лабораторная работа Центр обеспечения безопасности (Windows Security Center) в операционной системе Windows xp sp2
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации



ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННО-КОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ


Кафедра систем защиты информации


Н.Н. Блавацкая


СИСТЕМЫ РЕЗЕРВНОГО КОПИРОВАНИЯ


(Лекция № 6 для студентов )


(Время - 2 часа)


Форма обучения: дневная


Лекция рассмотрена и одобрена

на заседании кафедры систем защиты информации.

Протокол № ___ от «___» ___________ 2009 года


Киев – 2009


Тема лекции:

«Системы резервного копирования»


ПЛАН

Введение

  1. Этапы развития методов оптимального представления информации

  2. Определения, аббревиатуры и классификации методов сжатия

  3. Методы сжатия без потерь

ЛИТЕРАТУРА

  1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В.Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2003. - 384 с.



Введение


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

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

В настоящее время информационные компьютерные системы проникают во все сферы деятельности человека. Системы цифровой связи (ISDN, цифровая сотовая связь, цифровое телевидение и пр.) также получили всеобщее признание и прогрессируют очень быстро. Информационная инфраструктура разрастается и усложняется. Ценность хранимой информации весьма велика, поэтому применяются различные методы ее защиты. Одним из самых распространенных является резервное копирование, применение которого еще более увеличивает объем хранимой информации. Все это обуславливает лавинообразное увеличение количества хранимой, передаваемой и обрабатываемой информации. Рост количественных и качественных характеристик современных технических средств передачи и хранения информации не успевает за потребностями человечества в таких средствах. Ввод в действие новых высокопроизводительных коммуникационных систем обходится достаточно дорого.

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

Теоретической основой сжатия данных служит теория информации, в первую очередь – такой ее раздел, как теория кодирования. Родоначальником теории информации является К.Шеннон, который, в частности, определил как рассчитывается количество информации через понятия априорной и апостериорной энтропии и обосновал пропускную способность канала связи.

1. ЭТАПЫ РАЗВИТИЯ МЕТОДОВ ОПТИМАЛЬНОГО ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ


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

В XIX веке в связи с появлением новых средств связи возникла необходимость перекодирования сообщений на естественных языках в удобный для передачи вид. Для этого С. Морзе в 1838 г. предложил код, пригодный для передачи по любым каналам с двумя состояниями. Длины кодовых последовательностей для букв Морзе выбрал исходя из частоты встречаемости в языке соответствующих букв. Подобный прием характерен для всех статистических методов сжатия информации. В 1877 году, Ж. Бодо предложил для применения в телеграфии другой код. В отличии от кода Морзе код Бодо является равномерным (каждая буква в нем кодируется пятью сигналами).

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

Почти одновременно с работой Шеннона вышла монография Н. Винера, положившая начало кибернетике. В этой работе Винер (независимо от Шеннона) также вводит понятие информации и энтропии, причем таким же методом, что и Шеннон.

В середине 50-х годов XX в. появилось множество работ по теории информации.

Успехи в теоретических исследованиях процессов передачи информации и не конструктивность многих теорем в теории информации обусловили необходимость развития прикладных аспектов передачи и хранения информации. Эти исследования составили предмет отдельного раздела математики – теории кодирования.

Различают два основных направления исследований по теории кодирования:

    • помехоустойчивое (корректирующее) кодирование;

    • оптимальное кодирование.

Мы рассмотрим методы оптимального кодирования в данной лекции.

Первый теоретически обоснованный метод оптимального кодирования был предложен в 1949 г. независимо друг от друга Шенноном и Фано . В 1952 г. Д.Хаффман предложил код, основанный на тех же соображениях, но способ построения которого кардинально отличался. Эти коды, соответственно, получили название кодов Шеннона-Фано и Хаффмана.

До конца 70-х годов XX столетия все работы по оптимальному кодированию связаны с исследованием различных вариантов схемы Хаффмана.

Арифметическое кодирование, как метод оптимального кодирования, было предложено в 1976 г. Д. Риссаненом. Оно обладает важными преимуществами перед кодированием Хаффмана, однако в первоначальном виде было неприменимо на практике и представляло лишь теоретический интерес. В 1979 г. было предложено новую методику, позволяющую практически реализовать арифметическое кодирование. С тех пор арифметическое кодирование стало весьма популярным.

Словарные методы кодирования были предложены математиками Дж. Зивом и Э. Лемпелом.

Одним из важных теоретических достижений в теории оптимального кодирования явилась впервые высказанная в 1981 г. идея разделения процесса оптимального кодирования на две части:

    • моделирование, которое служит для построения модели источника и оценивания вероятностей появления символов на основании построенной модели;

    • собственно кодирование.

Это дало толчок к развитию методов моделирования источников, базирующихся на рассмотрении источника как конечного автомата (finite state machine – FSM) с памятью или без памяти. Также были предложены методы моделирования, основанные на марковских моделях состояний случайного процесса, методы контекстуального моделирования источника и некоторые другие методы. Алгоритмы, реализующие эти методы, нетривиальны, используют эмпирически установленные факты, но обеспечивают высокое качество сжатия. Некоторые из них ради получения дополнительного выигрыша по оптимальности сжатия ориентированы только на определенные виды информации.

В последние годы были предложены несколько оригинальных методов сжатия информации, основанных на блочно-сортирующем преобразовании М.Барроуза и Д. Уиллера.

2. ОПРЕДЕЛЕНИЯ, АББРЕВИАТУРЫ И КЛАССИФИКАЦИИ МЕТОДОВ СЖАТИЯ


Базовые определения

Бит- это "атом" цифровой информации: переменная, которая может принимать ровно два различных значения:

  • "1" (единица, да, истина, существует);

  • "0" (нуль, нет, ложь, не существует).

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

Емкость для хранения бита можно представлять себе как небольшой "ящик" где-то в пространстве-времени (в микросхеме, на магнитном/оптическом диске, линии связи) с двумя возможными состояниями: полный - " 1" и пустой - "0".

Данные - информация в цифровом виде.

Объем данных измеряется в битах, но может быть и рациональным числом, а не только целым.

R-битовый элемент - совокупность R битов - имеет 2R возможных значений-состояний. Большинство источников цифровой информации порождает элементы одного размера R. А в большинстве остальных случаев - элементы нескольких размеров: R], R2, R3— (например, 8, 16 и 32).

Байт - это 8-битовый элемент: совокупность 8 битов.

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

Блок - конечная последовательность цифровой информации.

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

Блок - последовательность с произвольным доступом, а поток - с последовательным.

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

Используют и такие пары терминов: компрессия/декомпрессия, кодирование/декодирование, упаковка/распаковка.

Под просто сжатием будем далее понимать сжатие без потерь (lossless compression).

Сжатие с потерями (lossy compression) - это два разных процесса:

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

  2. собственно сжатие, без потерь.

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

Конечную последовательность битов назовем кодом1, а количество битов в коде - длиной кода.

Конечную последовательность элементов назовем словом, а количество элементов в слове - длиной слова. Иногда используются синонимы строка и фраза. В общем случае слово построено из R-битовых элементов, а не 8-битовых. Таким образом, код - это слово из 1-битовых элементов.

Например, в блоке из 14 элементов "кинчотсихыннад" одно слово длиной14 элементов, два слова длиной 13 элементов, и т. д., 13 слов длиной 2 и 14 слов длиной 1. Аналогично в блоке из семи битов "0100110" один код длиной 7 бит, два кода длиной 6 бит, и т. д., семь кодов длиной 1 бит.

Символ - это "атом" некоторого языка (например, буквы, цифры, ноты, символы шахматных фигур, карточных мастей). Во многих случаях под символом имеют в виду R-битовый элемент (обычно байт), однако элементы мультимедийных данных все-таки не стоит называть символами: они содержат количественную, а не качественную информацию.

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

ASCII (American Standard Code for Information Interchange - Американский стандартный код для обмена информацией) каждому значению байта ставит в соответствие символ. Но чтобы построить однозначное соответствие для всех необходимых символов из множества национальных алфавитов народов мира, требуется больше: по крайней мере 16 бит на символ (что и обеспечивает стандарт Unicode).

Множество всех различных символов, порождаемых некоторым источником, называется алфавитом, а количество символов в этом множестве - размером алфавита. Источники данных порождают только элементы, но физические источники информации - символы или элементы.

Размер алфавита таблицы ASCII равен 28=256, a Unicode- 216=65 536. Это две самые распространенные таблицы символов.

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

Можно говорить, что источник без памяти порождает "элементы", а источник данных с памятью - "слова", поскольку во втором случае

  • учет значений соседних элементов (контекста) улучшает сжатие, т. е. имеет смысл трактовать данные как слова;

  • поток данных выглядит как поток слов.

В первом же случае имеем дело с перестановкой элементов и рассматривать данные как слова нет смысла.

Кавычки показывают, что это условные названия способов интерпретации входных данных: "слова", "элементы", "биты".

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

Третья важнейшая применяемая при сжатии данных математическая модель - аналоговый сигнал:

  • данные считаются количественными;

  • источник данных считается источником Маркова 1-го порядка.

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

Еще две важные характеристики алгоритма сжатия - объемы памяти, необходимые для сжатия и для разжатия (для хранения данных, создаваемых и/или используемых алгоритмом).

Названия методов

CM (Context Modeling) - контекстное моделирование.

DMC (Dynamic Markov Compression) - динамическое марковское сжатие (является частным случаем СМ).

PPM (Prediction by Partial Match) - предсказание по частичному совпадению (является частным случаем СМ).

LZ-методы - методы Зива - Лемпела, в том числе LZ77, LZ78, LZH и LZW.

PBS (Parallel Blocks Sorting) - сортировка параллельных блоков.

ST (Sort Transformation) - частичное сортирующее преобразование (является частным случаем PBS).

BWT (Burrows-Wheeler Transform) - преобразование Барроуза - Уилера (является частным случаем ST).

RLE (Run Length Encoding) - кодирование длин повторов.

HUFF (Huffman Coding) - кодирование по методу Хаффмана.

SEM (Separate Exponents and Mantissas) - разделение экспонент и мантисс (представление целых чисел).

UNIC (Universal Coding) - универсальное кодирование (является частным случаем SEM).

ARIC (Arithmetic Coding) - арифметическое кодирование.

RC (Range Coding) - интервальное кодирование (вариант арифметического).

DC (Distance Coding) - кодирование расстояний.

IF (Inversion Frequences) - "обратные частоты" (вариант DC).

MTF (Move To Front) - "сдвиг к вершине", "перемещение стопки книг".

ENUC (Enumerative Coding) - нумерующее кодирование.

FT (Fourier Transform) - преобразование Фурье.

DCT (Discrete Cosine Transform) - дискретное Косинусное Преобразование, ДКП (является частным случаем FT).

DWT (Discrete Wavelet Transform) - дискретное вэйвлетное преобразование, ДВП.

LPC (Linear Prediction Coding) - линейно-предсказывающее кодирование, ЛПК (к нему относятся дельта-кодирование, ADPCM, CELP и MELP).

SC (Subband Coding) - субполосное кодирование.

VQ (Vector Quantization) - векторное квантование.

Каждая группа (ветвь, семейство) содержит множество методов. Исключением является блочно-ориентированный СМ - это относительно мало исследованная область. Авторам не известны другие практические реализации, кроме компрессоров СМ Булата Зиганшина и "pre-conditioned PPMZ" Чарльза Блума.

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

Все поточные методы применимы и к блокам, но обратное неверно.

Блочные методы не применимы к потокам, поскольку не могут начать выполнение, пока не задана длина блока, заполненного данными, подлежащими сжатию.

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

Во второй строке - методы для источников без памяти и аналоговых сигналов. Эти данные при сжатии невыгодно рассматривать как слова.

Не все методы для потоков R-битовых "элементов" применимы к "битам" (только те, которые в третьей строке "карты").

Очевидно, что невыгодно применять методы для "элементов" - к "словам" или "битам". Менее очевидно, что невыгодно и обратное: применять методы для потоков "слов" к данным без значимых вероятностных взаимосвязей, к "элементам" ИЛИ "битам".

Базовые стратегии сжатия

Базовых стратегий сжатия три:

1. Преобразование потока ("Скользящее окно-словарь"). Описание поступающих данных через уже обработанные. Сюда входят LZ-методы для потоков "слов", т. е. когда комбинации поступающих элементов предсказуемы по уже обработанным комбинациям. Преобразование по таблице, RLE, LPC, DC, MTF, VQ, SEM, Subband Coding, Discrete Wavelet Transform - для потоков "элементов", т. е. когда не имеет смысла рассматривать комбинации длиной два и более элемента или запоминать эти комбинации, как в случае Linear Prediction Coding.

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

2. Статистическая стратегия.

а) Адаптивная(поточная). Вычисление вероятностей для поступающих данных на основании статистики по уже обработанным данным. Кодирование с использованием этих вычисленных вероятностей. Семейство РРМ-методов - для потоков "слов", адаптивные варианты методов Хаффмана и Шеннона - Фано, арифметического кодирования - для потоков "элементов". В отличие от первого случая, давно собранная статистика имеет тот же вес, что и недавняя, если метод не борется с этим специально, что гораздо сложнее, чем в случае LZ. Кроме того, считаются вероятными все комбинации, даже те, которые еще не встречались в потоке и скорее всего никогда не встретятся.

б) Блочная. Отдельно кодируется и добавляется к сжатому блоку его статистика. Статические варианты методов Хаффмана, Шеннона – Фано и арифметического кодирования - для потоков "элементов". Статическое СМ - для "слов".

3. Преобразование блока. Входящие данные разбиваются на блоки, которые затем трансформируются целиком, а в случае блока однородных данных лучше брать весь блок, который требуется сжать. Это методы сортировки блоков ("BlockSorting''-методы: ST, BWT, PBS), а также Fourier Transform, Discrete Cosine Transform, фрактальные преобразования, Enumerative Coding.

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

Резюмируя одним предложением: метод сжатия может быть или статистическим, или трансформирующим и обрабатывать данные либо поточно, либо блоками, причем

  • чем больше и однороднее данные и память, тем эффективнее блочные методы;

  • чем меньше и неоднороднее данные и память, тем эффективнее поточные методы;

  • чем сложнее источник, тем сильнее улучшит сжатие оптимальная преобразование;

  • чем проще источник, тем эффективнее прямолинейное статистическое решение (математические модели "источник Бернулли" и "источник Маркова").

3. МЕТОДЫ СЖАТИЯ БЕЗ ПОТЕРЬ


В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые - длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем если бы все элементы представлялись кодами одинаковой длины. Данный факт известен давно: вспомним, например, азбуку Морзе, в которой часто используемым символам поставлены в соответствие короткие последовательности точек и тире, а редко встречающимся - длинные.

Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника, которая гласит, что элемент si вероятность появления которого равняется p(si), выгоднее всего представлять -log2 p(si) битами. Если при кодировании размер кодов всегда в точности получается равным -log2 p(si) битам, то в этом случае длина закодированной последовательности будет минимальной для всех возможных способов кодирования. Если распределение вероятностей F= {p(si)} неизменно, и вероятности появления элементов независимы, то мы можем найти среднюю длину кодов как среднее взвешенное

(1.1)

Это значение также называется энтропией распределения вероятностей F.

Обычно вероятность появления элемента является условной, т. е. зависит от какого-то события. В этом случае при кодировании очередного элемента si распределение вероятностей F принимает одно из возможных значений Fk, т. е. F = Fkи соответственно H= Hk Можно сказать, что источник находится в состоянии k, которому соответствует набор вероятностей генерации всех возможных элементов si. Поэтому среднюю длину кодов можно вычислить по формуле

(1.2)

где Рk - вероятность того, что F примет kзначение, или, иначе, вероятность нахождения источника в состоянии k.

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

Но в подавляющем большинстве случаев истинная структура источника нам неизвестна, поэтому необходимо строить модель источника, которая позволила бы нам в каждой позиции входной последовательности оценить вероятность p(s,) появления каждого элемента .у, алфавита входной последовательности. В этом случае мы оперируем оценкой q(si) вероятности элемента si.

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

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

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

Существует 2n различных файлов длины п бит, где n = 0, 1, 2, ... Если размер каждого такого файла в результате обработки уменьшается хотя бы на 1 бит, то 2 n исходным файлам будет соответствовать самое большее 2n-1 различающихся сжатых файлов. Тогда по крайней мере одному архивному файлу будет соответствовать несколько различающихся исходных, и, следовательно, его декодирование без потерь информации невозможно в принципе.

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

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

Словарные методы сжатия данных


Идея словарных методов

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

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

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

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

Например, рассмотрим количество взаимно различных строк длины от 1 до 5 в тексте на русском языке (роман Ф.М. Достоевского "Бесы", обычный неформатированный текст, размер около 1.3 Мб):

Иначе говоря, размер (мощность) алфавита равен 136 символам, но реально используется только 2536/(136*136)100% ~ 13.7 % от всех возможных двухсимвольных строк и т. д.

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

Классические алгоритмы Зива - Лемпела

Алгоритмы словарного сжатия Зива-Лемпела появились во второй половине 70-х гг. Это были так называемые алгоритмы LZ77 и LZ78, разработанные совместно Зивом (Ziv) и Лемпелом (Lempel). В дальнейшем первоначальные схемы подвергались множественным изменениям, в результате чего мы сегодня имеем десятки достаточно самостоятельных алгоритмов и бессчетное количество модификаций.

LZ77 и LZ78 являются универсальными алгоритмами сжатия, в которых словарь формируется на основании уже обработанной части входного потока, т. е. адаптивно. Принципиальным отличием является лишь способ формирования фраз. В модификациях первоначальных алгоритмов это свойство сохраняется. Поэтому словарные алгоритмы Зива - Лемпела разделяют на два семейства - алгоритмы типа LZ77 и алгоритмы типа LZ78. Иногда также говорят о словарных методах LZ1 и LZ2.

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

С тех пор методы данного семейства неизменно являются самыми популярными среди всех методов сжатия данных, хотя в последнее время ситуация начала меняться в пользу BWT и РРМ, как обеспечивающих лучшее сжатие. Кроме того, практически все реально используемые словарные алгоритмы относятся к семейству Зива - Лемпела.

Необходимо сказать несколько слов о наименованиях алгоритмов и методов. При обозначении семейства общепринятой является аббревиатура LZ, но расшифровываться она должна как Ziv - Lempel, поэтому и алгоритмы Зива - Лемпела, а не Лемпела - Зива. Согласно общепринятому объяснению этого курьеза, Якоб Зив внес больший вклад в открытие соответствующих словарных схем и исследование их свойств и, таким образом, заслужил, чтобы первым стояла его фамилия. Но случайно была допущена ошибка, и прикрепилось сокращение LZ (буквы упорядочены в алфавитном порядке). В дальнейшем, если некий исследователь существенно изменял какой-то алгоритм, относимый к семейству LZ, то в названии полученной модификации к строчке LZ обычно дописывалась первая буква его фамилии, например: алгоритм LZB, автор Белл (Bell).

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

АЛГОРИТМ LZ77

Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 г., но сам алгоритм разработан не позднее 1975 г.

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

Скользящее окно имеет длину N, т. е. в него помещается N символов, и состоит из двух частей:

  • последовательности длины уже закодированных символов, которая и является словарем;

  • упреждающего буфера, или буфера предварительного просмотра ( словарь на порядки больше чем буфер предварительного просмотра).

Идея алгоритма заключается в поиске самого длинного совпадения между строкой буфера, и всеми фразами словаря.

Полученная в результате поиска фраза кодируется с помощью двух чисел:

  1. смещения от начала буфера;

  2. длины соответствия, или совпадения.

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

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

АЛГОРИТМ LZSS

Алгоритм LZSS позволяет достаточно гибко сочетать в выходной последовательности символы и указатели (коды фраз), что до некоторой степени устраняет присущую LZ77 расточительность, проявляющуюся в регулярной передаче одного символа в прямом виде. Эта модификация LZ77 была предложена в 1982 г. Сторером (Storer) и Жимански (Szymanski).

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

  • записывать символы в явном виде, когда соответствующий им код имеет большую длину и, следовательно, словарное кодирование только вредит;

  • обрабатывать ни разу не встреченные до текущего момента символы.

АЛГОРИТМ LZ78

Алгоритм LZ78 был опубликован в 1978 г. и впоследствии стал "отцом" семейства словарных методов LZ78.

Алгоритмы этой группы не используют скользящего окна и в словарь помещают не все встречаемые при кодировании строки, а лишь "перспективные" с точки зрения вероятности последующего использования. На каждом шаге в словарь вставляется новая фраза, которая представляет собой сцепление (конкатенацию) одной из фраз S словаря, имеющей самое длинное совпадение со строкой буфера, и символа s. Символ s является символом, следующим за строкой буфера, для которой найдена совпадающая фраза S. В отличие от семейства

LZ77 в словаре не может быть одинаковых фраз.

Кодер порождает только последовательность кодов фраз. Каждый код состоит из номера (индекса) "родительской" фразы или префикса, и символа.

В начале обработки словарь пуст. Далее, теоретически, словарь может расти бесконечно, т. е. на его рост сам алгоритм не налагает ограничений.

На практике при достижении определенного объема занимаемой памяти словарь должен очищаться полностью или частично.

Методы контекстного моделирования


Применение методов контекстного моделирования для сжатия данных опирается на парадигму сжатия с помощью универсального моделирования и кодирования (universal modelling and coding), предложенную Риссаненом (Rissanen) и Лэнгдоном (Langdon) в 1981 г. В соответствии с данной идеей процесс сжатия состоит из двух самостоятельных частей:

  • моделирования;

  • кодирования.

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




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

Следует заметить, что понятие "кодирование" часто используют в широком смысле для обозначения всего процесса сжатия, т. е. включая моделирование в данном нами определении. Таким образом, необходимо различать понятие кодирования в широком смысле (весь процесс) и в узком (генерация потока кодов на основании информации модели). Понятие "статистическое кодирование" также используется, зачастую с сомнительной корректностью, для обозначения того или иного уровня кодирования. Во избежание путаницы ряд авторов применяет термин "энтропийное кодирование" для кодирования в узком смысле. Это наименование далеко от совершенства и встречает вполне обоснованную критику. Далее в этой главе процесс кодирования в широком смысле будем именовать "кодированием", а в узком смысле - "статистическим кодированием" или "собственно кодированием".

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

Оценка вероятностей символов при моделировании производится на основании известной статистики и, возможно, априорных предположений, поэтому часто говорят о задаче статистического моделирования. Можно сказать, что моделировщик предсказывает вероятность появления каждого символа в каждой позиции входной строки, отсюда еще одно наименование этого компонента - "предсказатель" или "предиктор" (от predictor). На этапе статистического кодирования выполняется замещение символа si с оценкой вероятности появления q(si) кодом длиной -log2 q(si) бит.

Классификация стратегий моделирования


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

  • статическое;

  • полуадаптивное;

  • адаптивное (динамическое);

  • блочно-адаптивное.

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

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

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

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

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

  • большими вычислительными расходами на обновление модели (как пример - в случае адаптивного кодирования по алгоритму Хаффмана);

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

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

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

Контекстное моделирование

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

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

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

Действительно, размер алфавита русского текста превышает 64 знака, но меньше 128 знаков (строчные и заглавные буквы, знаки препинания, пробел), что требует 7-битовых кодов.

Анализ распространенных типов данных, - например, тех же текстов на естественных языках, - выявляет сильную зависимость вероятности появления символов от непосредственно им предшествующих. Иначе говоря, большая часть данных, с которыми мы сталкиваемся, порождается источниками с памятью. Допустим, нам известно, что сжимаемый блок является текстом на русском языке. Если, например, строка из трех только что обработанных символов равна "_цы" (подчеркиванием здесь и далее обозначается пробел), то текущий символ скорее всего входит в следующую группу: "г" ("цыган"), "к" ("цыкать"), "п" ("цыпочки"), "ц" ("цыц"). Или, в случае анализа фазу нескольких слов, если предыдущая строка равна "Вставай,_проклятьем_заклейменный,", то продолжением явно будет "весь_мир_".

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

В первом случае моделируются условные распределения вероятностей символов, зависящие от значения строки из одного непосредственно предшествующего символа, во втором - зависящие от строки из двух предшествующих символов.

Виды контекстного моделирования

Пример обработки строки "абсабвбабс" иллюстрирует сразу две проблемы контекстного моделирования:

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

  • как оценивать вероятность символов, имеющих нулевую частоту (например, "г").

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

Если в модели используются для оценки только KtA(N), то иногда такой подход называют "чистым" (pure) контекстным моделированием порядка N. Из-за вышеуказанного недостатка "чистые" модели представляют обычно только научный интерес.

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

смешиванием (blending). Известно несколько способов выполнения смешивания.

Алгоритмы РРМ

Техника контекстного моделирования Prediction by Partial Matching (предсказание по частичному совпадению), предложенная в 1984 г. Клири (Cleary) и Уиттеном (Witten), является одним из самых известных подходов к сжатию качественных данных и уж точно самым популярным среди контекстных методов. Значимость подхода обусловлена и тем фактом, что алгоритмы, причисляемые к РРМ, неизменно обеспечивают в среднем наилучшее сжатие при кодировании данных различных типов и служат стандартом, "точкой отсчета" при сравнении универсальных алгоритмов сжатия.

Перед собственно рассмотрением алгоритмов РРМ необходимо сделать замечание о корректности используемой терминологии. На протяжении примерно 10 лет - с середины 80-х гг. до середины 90-х - под РРМ понималась группа методов с вполне определенными характеристиками. В последние годы, вероятно из-за резкого увеличения числа всевозможных гибридных схем и активного практического использования статистических моделей для сжатия, произошло смешение понятий и термин "РРМ" часто используется для обозначения контекстных методов вообще.

Ниже будет описан некий обобщенный алгоритм РРМ, а затем особенности конкретных распространенных схем.

Как и в случае многих других контекстных методов, для каждого контекста, встречаемого в обрабатываемой последовательности, создается своя контекстная модель КМ. При этом под контекстом понимается последовательность элементов одного типа - символов, пикселов, чисел, но не набор разнородных объектов. Далее вместо слова "элемент" мы будем использовать слово "символ". Каждая КМ включает в себя счетчики всех символов, встреченных в соответствующем контексте.

РРМ относится к адаптивным методам моделирования. Исходно кодеру и декодеру поставлена в соответствие начальная модель источника данных. Будем считать, что она состоит из КМ(-1), присваивающей одинаковую вероятность всем символам алфавита входной последовательности. После обработки текущего символа кодер и декодер изменяют свои модели одинаковым образом, в частности наращивая величину оценки вероятности рассматриваемого символа. Следующий символ кодируется (декодируется) на основании новой, измененной модели, после чего модель снова модифицируется и т. д. На каждом шаге обеспечивается идентичность модели кодера и декодераза счет применения одинакового механизма ее обновления.

В РРМ используется неявное взвешивание оценок. Попытка оценки символа начинается с KM(N), где N является параметром алгоритма и называется порядком РРМ-модели. В случае нулевой частоты символа в КМ текущего порядка осуществляется переход к КМ меньшего порядка за счет использования механизма уходов (escape strategy).

Фактически, вероятность ухода - это суммарная вероятность всех символов алфавита входного потока, еще ни разу не появлявшихся в контексте.

Любая КМ должна давать отличную от нуля оценку вероятности ухода. Исключения из этого правила возможны только в тех случаях, когда значения всех счетчиков КМ для всех символов алфавита отличны от нуля, т. е. любой символ может быть оценен в рассматриваемом контексте. Оценка вероятности ухода традиционно является одной из основных проблем алгоритмов с неявным взвешиванием, и она будет специально рассмотрена ниже в подразд. "Оценка вероятности ухода".


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

2 Относительная частота элемента X в блоке Z - это количество элементов со значением X, деленное на количество всех элементов в блоке Z.




Схожі:

Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации iconГосударственный университет информационно-коммуникационных технологий кафедра систем защиты информации
Методы противодействия динамическим способам снятия защиты программ от копирования
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации iconИнформационное сообщение Уважаемые коллеги ! Кафедра экономики промышленности и организации производства гвуз «Украинский государственный химико-технологический университет»
Кафедра экономики промышленности и организации производства гвуз «Украинский государственный химико-технологический университет»...
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации iconМеждународной заочной научно-практической конференции (с публикацией в сборнике научных трудов) «Современные тенденции в науке»
...
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации iconРусское географическое общество Администрация Тамбовской области Московский государственный университет имени М. В. Ломоносова Тамбовский государственный университет имени Г. Р. Державина информационное письмо №1
Международная научная школа-конференция, посвященная 150-летию со дня рождения академика В. И. Вернадского
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации iconТема самообразования Применение информационно-коммуникационных технологий (икт) в образовательном процессе для развития творческой инициативы, мотивации учащихся с целью повышения качества обучения
Математика для большинства представляется «обособленным предметом, а умения, развиваемые посредством математики, минимально используются...
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации iconИнформационный менеджмент в деятельности Научно-технических библиотек и служб информации предприятий
Диссертация выполнена на кафедре информационного менеджмента фгоу впо «Санкт-Петербургский государственный университет культуры и...
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации iconОбщие методические подходы к использованию информационных и коммуникационных технологий информатизация общества
Общие методические подходы к использованию информационных и коммуникационных технологий
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации iconФгбоу впо «вятский государственный гуманитарный университет» ул. Красноармейская, д. 26, г. Киров (обл.), 610002 Телефон: (8332) 67-89-75 Факс: (8332) 37-51-69 фгбоу впо «Вятский государственный гуманитарный университет»
Приглашаем вас принять участие в региональной научно-практической конференции «Инновационный потенциал молодежного самоуправления:...
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации iconТамбовский государственный университет имени Г. Р. Державина Кафедра политической экономии и мирового глобального хозяйства
Конференция проводится в целях развития научного потенциала и интеграции экономической науки с исследованием и разрешением проблем...
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации iconКомпьютерные технологии в обучении русскому языку
Общие сведения об информационных технологиях обучения. Характеристика информационных технологий обучения. Необходимость использования...
Государственный университет информационно-коммуникационных технологий кафедра систем защиты информации iconТульский государственный университет
Каждому участнику будет выслан в электронном виде сборник по итогам конференции с присвоением isbn
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи