Современные методы хранения информации в сжатом виде(методы неискажающего сжатия и восстановления информации)

 

Министерство транспорта Российской Федерации

Омский государственный  университет путей сообщения 

Кафедра «Автоматика и  Системы управления»

 

 

 

 

 

 

 

 

 

Тематический реферат

по дисциплине «ИСВВТ»

 

 

Современные методы хранения информации в сжатом виде(методы неискажающего сжатия и восстановления информации)

ИНМВ.801000.000 Д

 

 

 

 

 

 

 

                                               Студент гр. 29 З

____________К.А. Аненков

                                                        «__»________2012 г.

 

 

                                                                     Руководитель – преподаватель

                                            кафедры АиСУ

____________Н.Ю.Афоничев

                                                      «__»________2012 г.

 

 

 

 

 

 

 

Омск  2012 

Содержание

Введение 4

1 Классификация  методов сжатия 5

2 Критерии  оценки методов сжатия 6

3 Надежность  программ и сложность алгоритмов 7

4 Современные  методы сжатия 8

4.1 Алгоритмы  статистического моделирования 8

4.2 Алгоритмы  словарного сжатия 8

4.3 Алгоритмы  сжатия сортировкой блоков 9

4.4 Методы  энтропийного кодирования 9

4.5 Префиксные  коды 9

4.6 Арифметические  коды 10

5 Обзор алгоритмов  сжатия без потерь 11

5.1 RLE 11

5.2 Алгоритмы  семейства LZ 12

5.3 Алгоритм LZ77 13

5.4 Алгоритм  LZSS 15

5.5 Алгоритм LZ78 17

5.6 Алгоритм  LZW 19

5.7 Алгоритм  LZM 25

5.8 Алгоритм  LZB 27

5.9 Алгоритм  LZH 28

5.10 Алгоритм  LZC 28

5.11 Алгоритм  LZT 28

5.12 Алгоритм  LZMV 29

5.13 Алгоритм  LZJ 29

5.14 Алгоритм  LZFG 29

5.15 Унарное  кодирование 30

5.16 Метод  Хафмана 31

5.16.1 Идея  метода 31

5.16.2 Алгоритм 31

5.16.3 Кодирование  Хаффмана 32

5.16.4 Адаптивное  сжатие Хаффмана 33

5.16.5 Адаптивное  кодирование Хаффмана 34

5.16.6 Проблемы  адаптивного кодирования 35

5.16.7 Фиксированный  алгоритм Хаффмана 36

5.16.8 Алгоритм  стопки книг 36

5.17 Арифметическое  кодирование 37

5.18 Вероятностное  сжатие 39

Заключение 40

Библиографический список 41

 

 

Введение

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

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

 

1 Классификация методов сжатия

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

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

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

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

Кроме того, можно выделить:

• методы сжатия общего назначения (general-purpose), которые не зависят от физической природы входных данных и, как правило, ориентированы на сжатие текстов, исполняемых программ, объектных модулей и библиотек и т. д., т. е. данных, которые в основном и хранятся в ЭВМ;
• специальные (special) методы сжатия, которые ориентированы на сжатие данных известной природы, например, звука, изображений и т. д. И за счет знания специфических особенностей сжимаемых данных достигают существенно лучшего качества и/или скорости сжатия, чем при использовании методов общего назначения.

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

 

     

 

2 Критерии оценки методов сжатия

Основными свойствами какого-либо алгоритма  сжатия данных являются:

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

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

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

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

 

3 Надежность программ и сложность алгоритмов

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

Наилучшие по качеству сжатия алгоритмы статистического моделирования источников Маркова семейств PPM (от англ. Prediction by Partial Matching), DMC (от англ. Dynamic Markov Compression), ACB (от англ. Associative Coding by Buyanovski) предсказывают вероятность появления следующего символа на основе анализа частоты появления различных последовательностей символов в ранее закодированной части сообщения.

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

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

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

4.2 Алгоритмы словарного сжатия

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

Обычно для ускорения поиска совпадающих подстрок и ограничения  объема требуемой памяти область  поиска ограничивается определенным количеством  последних символов закодированной части: такая модификация LZ77 называется LZ77 со скользящим окном (LZ77 with sliding window).

Алгоритмы семейства LZ в 1.3-1.7 раза уступают методам статистического моделирования по качеству сжатия, однако обладают очень высокой скоростью кодирования при сравнительно небольшом объеме требуемой памяти.

Огромное преимущество алгоритмов семейства LZ – чрезвычайно высокая скорость декодирования. Это позволяет применять их в тех случаях, когда декодирование осуществляется гораздо чаще кодирования или скорость декодирования очень важна (например, при хранении данных на CD-ROM, в файловых системах со сжатием и т. д.).

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

4.3 Алгоритмы сжатия сортировкой блоков

Алгоритмы сжатия сортировкой блоков семейства BWT/BS, разработанные в 1994г. Барроузом и Уилером, разбивают кодируемую последовательность на блоки символов, представляют (обратимым образом) символы каждого блока так, что появляется много повторений одного и того же символа, а затем сжимают преобразованные данные каким-либо достаточно простым способом.

По качеству сжатия они приближаются к методам статистического моделирования (уступая им в 1.2-1.3 раза), а по скорости – к алгоритмам семейства LZ, при меньшем по сравнению с методами статистического моделирования объеме требуемой памяти; скорость декодирования также достаточно высока.

4.4 Методы энтропийного кодирования

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

Такие методы кодирования известны с конца 40-х гг. и хорошо изучены. Их можно разбить на два больших  класса: префиксные (методы Хаффмана, Шеннона, Шеннона-Фано) и арифметические.

4.5 Префиксные коды

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

Известно много способов построения префиксных кодов: коды Шеннона и  Шеннона-Фано почти идеальны, а код Хаффмана – оптимален среди префиксных кодов.

Так как длина каждого кодового слова выражается целым числом битов, то префиксные коды неэффективны на алфавитах  малой мощности (2-8 символов) или  при наличии символов с очень  большой (более 30-50%) вероятностью появления  и по качеству сжатия могут уступать арифметическим.