Алгоритмы сжатия данных в файлах неизвестного формата

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

Компрессия способом кодирования серий  
Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Смысл методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. Задача всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную последовательность от других - некодированных последовательностей байтов. Решение задачи достигается обычно простановкой меток в начале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной последовательности, значения первого байта кодированной последовательности и т.п. Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в последовательностьх.

Компрессия без применения метода RLE 
Процесс сжатия данных без применения метода RLE можно разбить на два этапа: моделирование (modelling) и, собственно, кодирование (encoding). Эти процессы и их реализующие алгоритмы достаточно независимы и разноплановы.

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

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

Второй метод - метод адаптивного  кодирования (adaptive coder method). Его общий принцип состоит в том, чтобы менять схему кодирования в зависимости от характера изменений входного потока. Такой подход имеет однопроходный алгоритм и не требует сохранения информации об использованном кодировании в явном виде. Адаптивное кодирование может дать большую степень сжатия, по сравнению со статическим, поскольку более полно учитываются изменения частот входного потока. Данный метод известен как динамическое кодирование Хаффмена. В статическом кодировании Хаффмена входным символам (цепочкам битов различной длины) ставятся в соответствие цепочки битов, также, переменной длины - их коды. Длина кода каждого символа берется пропорциональной двоичному логарифму его частоты, взятому с обратным знаком. А общий набор всех встретившихся различных символов составляет алфавит потока. Это кодирование является префиксным, что позволяет легко его декодировать результативный поток, т.к., при префиксном кодировании, код любого символа не является префиксом кода никакого другого символа - алфавит уникален.

Заключение

При сжатии данных используются две группы режимов: статический и динамический; различают физическое и логическое компрессия; симметричное и асимметричное компрессия; адаптивное, полуадаптивное и неадаптивное кодирование; компрессия без потерь, с потерями и минимизацией потерь. Существуют следующие виды сжатия данных: 
Статическое компрессия данных — используется для длительного хранения и архивации; выполняется при помощи специальных сервисных программ-архиваторов, например ARJ, PKZIP/PKUNZIP. После декомпрессии исходная запись восстанавливается, динамическое компрессия (в реальном времени;) — предназначено для сокращения занимаемой области дисковой памяти данными, требующими оперативного доступа и вывода на внешние устройства ЭВМ (в том числе на экран монитора). Динамическое компрессия данных и их восстановление производится специальными программными средствами автоматически и «мгновенно». 
Физическое компрессия — методология сжатия, при которой данные перестраиваются в более компактную форму «формально», то есть без учета характера содержащейся в них информации. 
Логическое компрессия — методология, в соответствии с которой один набор алфавитных, цифровых или двоичных символов заменяется другим, при этом смысловое значение исходных данных сохраняется. Примером может служить замена словосочетания его аббревиатурой. Логическое компрессия производится на символьном или более высоком уровне и основано исключительно на содержании исходных данных. Логическое компрессия не применяется для изображений. 
Симметричное компрессия — методология сжатия, в соответствии с которой принципы построения алгоритмов упаковки и распаковки данных близки или тесно взаимосвязаны. При использовании симметричного сжатия время, затрачиваемое на компрессия и распаковку данных, соизмеримо. В программах обмена данными обычно используется симметричное компрессия. 
Асимметричное компрессия — методология, в соответствии с которой при выполнении работ «в одном направлении» времени затрачивается больше, чем при выполнении работ в другом направлении. На компрессия изображений обычно затрачивается намного больше времени и системных ресурсов, чем на их распаковку, эффективность этого подхода определяется тем, что компрессия изображений может производиться только один раз, а распаковываться с целью их отображения – многократно. Алгоритмы асимметричные «в обратном направлении» (на компрессия данных затрачивается меньше времени, чем на распаковку) используется при выполнении резервного копирования данных. 
Адаптивное кодирование — методология кодирования при сжатии данных, которая заранее не настраивается на определенный вид данных. Программы, использующие адаптивное кодирование, настраиваются на любой тип сжимаемых данных, добиваясь максимального сокращения их объема.  
Неадаптивное кодирование  — методология кодирования, ориентированная на компрессия определенного типа или типов данных. Кодировщики, построенные по этому принципу, имеют в своем составе статические словари «предопределенных подстрок», о которых известно, что они часто появляются в кодируемых данных. Примером может служить метод сжатия Хаффмена. 
Полуадаптивное кодирование — методология кодирования при сжатии данных, которая использует элементы адаптивного и неадаптивного кодирования. Принцип действия полуадаптивного кодирования заключается в том, что кодировщик выполняет две группы операций: вначале — просмотр массива кодируемых данных и построение для них словаря, а затем — собственно кодирование. 
Компрессия без потерь — методология сжатия, при которой ранее закодированная порция данных восстанавливается после их распаковки полностью без внесения изменений. 
Компрессия с потерями — методология, при которой для обеспечения максимальной степени сжатия исходного массива часть содержащихся в нем данных отбрасывается. Для текстовых, числовых и табличных данных использование программ, реализующих подобные методы сжатия, является неприемлемой. Однако для программ, работающих с графикой, это часто бывает целесообразно. Качество восстановленного изображения зависит от характера графического материала и корректности реализованного в программе алгоритма сжатия. Существует ряд алгоритмов сжатия, учитывающих допустимые уровни потерь исходного графического образа в конкретных вариантах использования его восстановленного изображения, например, путем просмотра его на экране монитора, распечатки принтером, в полиграфии. Эти методы являются методами сжатия с минимизацией потерь.  
Компрессия графического изображения — технический прием или метод сокращения объема (размеров) записи графических изображений (рисунков, чертежей, схем) на информационном носителе (например, на магнитном диске, магнитной ленте). По существу, оно является разновидностью динамического сжатия, для его реализации используются различные способы кодирования данных, которые ориентированы на элементы графики, составляющие изображение, включая и движущиеся объекты. Применяется также при передаче факсимильной информации по каналам связи, в системах мультимедиа, видео. 

Литература

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. "Методы сжатия данных" - 2003г.
2. Балашов К.Ю. "Компрессия информации: анализ методов и подходов" - Минск, 2000г.
3. Мастрюков Д. "Алгоритмы сжатия информации"
4. Потапов В.Н. "Арифметическое кодирование вероятностных источников"
5. Потапов В.Н "Обзор методов неискажающего кодирования дискретных источников"
6. Семенова Ю.А. "Телекоммуникационные технологии"
7. Шелвин Е. "Алгоритм арифметического кодирования"
8. Фомин А.А. "Основы сжатия информации" - Санкт-Петербург, 1998г.
9. А.С.Климов “Форматы графических файлов”. // С.-Петербург, Изд. “ДиаСофт” 1995.
10. Д.С.Ватолин “Компрессия статических изображений” // Открытые системы сегодня. Номер 8 (29) Апрель 1995
11. Д.С.Ватолин “MPEG - стандарт ISO на видео в системах мультимедиа” // Открытые системы. Номер 2. Лето 1995
12. Д.С.Ватолин “Применение фракталов в машинной графике” // ComputerWorld-Россия. Номер 15. 12 декабря 1995
13. Д.С.Ватолин “Тенденции развития алгоритмов архивации графики” // Открытые системы. Номер 4. Зима 1995
14. Д.С.Ватолин “Фрактальное компрессия изображений” // ComputerWorld-Россия. Номер 6 (23). 20 февраля 1996
15. Д.С.Ватолин “Использование графики в WWW” // ComputerWorld-Россия. Номер 15 (32). 23 апреля 1996
16. http://loveisgame.ru/vtoechru-vtir22/%D0%A1%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85
17. http://kunegin.narod.ru/ref1/code/7.htm
18. http://www.compression.ru/arctest/descript/methods.htm
19. http://www.structur.h1.ru/arch.htm
20. http://www.polyset.ru/glossary/%D1%E6%E0%F2%E8%E5_%E4%E0%ED%ED%FB%F5:_%E0%EB%E3%EE%F0%E8%F2%EC%FB_%E8_%F4%EE%F0%EC%E0%F2%FB.php
21. http://lib.ru/TECHBOOKS/ALGO/VATOLIN/algcomp.htm
22. http://rfc2.ru/1951.rfc
23. http://www.infocity.kiev.ua/prog/other/content/progother023.phtml
24. http://habrahabr.ru/post/105652/
25. http://ru.wikipedia.org/wiki/%D1%E6%E0%F2%E8%E5_%E4%E0%ED%ED%FB%F5
26. http://algolist.manual.ru/compress/image/fractal/main.php