Сжатие информации с потерями — в помощь студенту

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

alt

Узнай стоимость своей работы

Бесплатная оценка заказа!

Оценим за полчаса!

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

Сжатие. Нужно ли оно в наше время?

Разумеется, да. Конечно, все мы понимаем, что сейчас нам доступны и носители информации большого объема, и высокоскоростные каналы передачи данных. Однако, одновременно с этим растут и объемы передаваемой информации. Если несколько лет назад мы смотрели 700-мегабайтные фильмы, умещающиеся на одну болванку, то сегодня фильмы в HD-качестве могут занимать десятки гигабайт.

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

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

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

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

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

alt

Узнай стоимость своей работы

Бесплатная оценка заказа!
Читайте также:  Затраты, расходы, издержки - в помощь студенту

Оценим за полчаса!
Сжатие с потерями
Лучшие степени сжатия, при сохранении «достаточно хорошего» качества данных. Применяются в основном для сжатия аналоговых данных — звука, изображений. В таких случаях распакованный файл может очень сильно отличаться от оригинала на уровне сравнения «бит в бит», но практически неотличим для человеческого уха или глаза в большинстве практических применений.
Сжатие без потерь
Данные восстанавливаются с точностью до бита, что не приводит к каким-либо потерям информации. Однако, сжатие без потерь показывает обычно худшие степени сжатия.

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

Универсальные методы сжатия без потерь

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

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

При этом не вычисляется никаких вероятностей, кодирование символов осуществляется только на основе тех данных, которые уже были обработаны, как например в LZ – методах (названных по имени Абрахама Лемпеля и Якоба Зива).

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

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

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

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

При этом некоторые методы, особенно основанные на перестановке блоков, могут не приводить к существенному (или вообще какому-либо) уменьшению объема данных.

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

Общие принципы, на которых основано сжатие данных

Все методы сжатия данных основаны на простом логическом принципе.

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

Точная взаимосвязь между частотами появления элементов, и оптимальными длинами кодов описана в так называемой теореме Шеннона о источнике шифрования(Shannon's source coding theorem), которая определяет предел максимального сжатия без потерь и энтропию Шеннона.

Немного математики

Если вероятность появления элемента si равна p(si), то наиболее выгодно будет представить этот элемент — log2p(si) битами. Если при кодировании удается добиться того, что длина всех элементов будет приведена к log2p(si) битам, то и длина всей кодируемой последовательности будет минимальной для всех возможных методов кодирования.

При этом, если распределение вероятностей всех элементов F = {p(si)} неизменно, и вероятности элементов взаимно независимы, то средняя длина кодов может быть рассчитана как Сжатие информации с потерями - в помощь студенту Это значение называют энтропией распределения вероятностей F, или энтропией источника в заданный момент времени.

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

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

Поэтому, учитывая эту поправку, можно выразить среднюю длину кодов какСжатие информации с потерями - в помощь студенту Где Pk — вероятность нахождения источника в состоянии k. Итак, на данном этапе мы знаем, что сжатие основано на замене часто встречающихся элементов короткими кодами, и наоборот, а так же знаем, как определить среднюю длину кодов. Но что же такое код, кодирование, и как оно происходит?

Кодирование без памяти

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

Рассмотрим эту тему чуть более подробно.

Пусть задан некоторый алфавит Сжатие информации с потерями - в помощь студенту, состоящий из некоторого (конечного) числа букв. Назовем каждую конечную последовательность символов из этого алфавита (A=a1, a2,… ,an) словом, а число n — длиной этого слова.

Сжатие информации с потерями - в помощь студенту

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

Пусть также задано отображение F, которое ставит в соответствие каждому слову A из первого алфавита некоторое слово B=F(A) из второго. Тогда слово B будет называться кодом слова A, а переход от исходного слова к его коду будет называться кодированием.

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

a1 B1

a2 B2 …

an Bn

Это соответствие называют схемой, и обозначают ∑.

В этом случае слова B1, B2,…, Bn называют элементарными кодами, а вид кодирования с их помощью — алфавитным кодированием. Конечно, большинство из нас сталкивались с таким видом кодирования, пусть даже и не зная всего того, что я описал выше.

Итак, мы определились с понятиями алфавит, слово, код, и кодирование. Теперь введем понятие префикс.

Пусть слово B имеет вид B=B'B''. Тогда B' называют началом, или префиксом слова B, а B'' — его концом. Это довольно простое определение, но нужно отметить, что для любого слова B, и некое пустое слово ʌ («пробел»), и само слово B, могут считаться и началами и концами.

Итак, мы подошли вплотную к пониманию определения кодов без памяти. Последнее определение, которое нам осталось понять — это префиксное множество. Схема ∑ обладает свойством префикса, если для любых 1≤i, j≤r, i≠j, слово Bi не является префиксом слова Bj.

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

  1. Составляется алфавит Ψ символов исходного сообщения, причем символы алфавита сортируются по убыванию их вероятности появления в сообщении.
  2. Каждому символу ai из алфавита Ψ ставится в соответствие некое слово Bi из префиксного множества Ω.
  3. Осуществляется кодирование каждого символа, с последующим объединением кодов в один поток данных, который будет являться результатам сжатия.

Одним из канонических алгоритмов, которые иллюстрируют данный метод, является алгоритм Хаффмана.

Алгоритм Хаффмана

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

Рассмотрим случай, когда, не зависимо от входного потока, алфавит выходного потока состоит из всего 2 символов – нуля и единицы. В первую очередь при кодировании алгоритмом Хаффмана, нам нужно построить схему ∑. Делается это следующим образом:

  1. Все буквы входного алфавита упорядочиваются в порядке убывания вероятностей.

    Все слова из алфавита выходного потока (то есть то, чем мы будем кодировать) изначально считаются пустыми (напомню, что алфавит выходного потока состоит только из символов {0,1}).

  2. Два символа aj-1 и aj входного потока, имеющие наименьшие вероятности появления, объединяются в один «псевдосимвол» с вероятностью p равной сумме вероятностей входящих в него символов.

    Затем мы дописываем 0 в начало слова Bj-1, и 1 в начало слова Bj, которые будут впоследствии являться кодами символов aj-1 и aj соответственно.

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

Шаги 2 и 3 повторяются до тех пор, пока в алфавите не останется только 1 псевдосимвол, содержащий все изначальные символы алфавита. При этом, поскольку на каждом шаге и для каждого символа происходит изменение соответствующего ему слова Bi (путем добавление единицы или нуля), то после завершения этой процедуры каждому изначальному символу алфавита ai будет соответствовать некий код Bi. Для лучшей иллюстрации, рассмотрим небольшой пример.

Пусть у нас есть алфавит, состоящий из всего четырех символов — { a1, a2, a3, a4}. Предположим также, что вероятности появления этих символов равны соответственно p1=0.5; p2=0.24; p3=0.15; p4=0.11 (сумма всех вероятностей, очевидно, равна единице).

Итак, построим схему для данного алфавита.

  1. Объединяем два символа с наименьшими вероятностями (0.11 и 0.15) в псевдосимвол p'.
  2. Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
  3. Объединяем два символа с наименьшей вероятностью (0.24 и 0.26) в псевдосимвол p''.
  4. Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
  5. Наконец, объединяем оставшиеся два символа, и получаем вершину дерева.

Если сделать иллюстрацию этого процесса, получится примерно следующее: Сжатие информации с потерями - в помощь студенту Как вы видите, при каждом объединении мы присваиваем объединяемым символам коды 0 и 1. Таким образом, когда дерево построено, мы можем легко получить код для каждого символа. В нашем случае коды будут выглядить так:

a1 = 0

a2 = 11 a3 = 100 a4 = 101 Поскольку ни один из данных кодов не является префиксом какого-нибудь другого (то есть, мы получили пресловутое префиксное множество), мы можем однозначно определить каждый код в выходном потоке. Итак, мы добились того, что самый частый символ кодируется самым коротким кодом, и наоборот. Если предположить, что изначально для хранения каждого символа использовался один байт, то можно посчитать, насколько нам удалось уменьшить данные.

Пусть на входу у нас была строка из 1000 символов, в которой символ a1 встречался 500 раз, a2 — 240, a3 — 150, и a4 — 110 раз.

Изначально данная строка занимала 8000 бит. После кодирования мы получим строку длинной в ∑pili = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 бит. Итак, нам удалось сжать данные в 4,54 раза, потратив в среднем 1,76 бита на кодирование каждого символа потока.

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

Заключение

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

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

Литература

  • Ватолин Д., Ратушняк А., Смирнов М. Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео; ISBN 5-86404-170-X; 2003 г.

Источник: https://habr.com/post/142242/

Сжатие информации с потерями и без потерь

Сжатие информации с потерями - в помощь студенту
Сжатие информации с потерями - в помощь студенту

  • Александр Прохоров
  •      Совсем немного теории для непрофессионалов
  • Избыточность естественных языков
  •      Кодирование информации
  •      Сжатие с потерями
  •      Сжатие без потерь
  •      Кодирование Хаффмена
  •      Статическое кодирование
  •      Динамическое кодирование
  •      LZW-сжатие
  • Какой же выбрать архиватор?
  •      Поддержка различных форматов
  •      Умение создавать solid-архивы
  •      Возможность создавать многотомные архивы
  •      Возможность работы в качестве менеджера архивов
  •      Возможность парольной защиты
  •      Удобство в работе
  •      Глоссарий
  •      О сжатии информации
  •      Краткое описание 20 популярных архиваторов

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

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

Однако очевидно, что процесс этот не бесконечен.

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

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

Позволю себе начать эту весьма серьезную тему со старой шутки. Беседуют два пенсионера:

Читайте также:  Отрасли хозяйства - в помощь студенту

— Вы не могли бы сказать мне номер вашего телефона? — говорит один.

— Вы знаете, — признается второй, — я, к сожалению, точно его не помню.

— Какая жалость, — сокрушается первый, — ну скажите хотя бы приблизительно…

Действительно, ответ поражает своей нелепостью. Совершенно очевидно, что в семизначном наборе цифр достаточно ошибиться в одном символе, чтобы остальная информация стала абсолютно бесполезной.

Однако представим себе, что тот же самый телефон написан словами русского языка и, скажем, при передаче этого текста часть букв потеряна — что произойдет в подобном случае? Для наглядности рассмотрим себе конкретный пример: телефонный номер 233 34 44.

Соответственно запись «Двсти трцать три трицть четре сорк чтре», в которой имеется не один, а несколько пропущенных символов, по-прежнему легко читается.

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

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

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

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

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

R = (Hmax — H)/ Hmax

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

Факт избыточности свидетельствует о возможностях перехода на иную систему кодирования, которая уменьшила бы избыточность передаваемого сообщения. Говоря о переходе на коды, которые позволяют уменьшить размер сообщения, вводят понятие «коды сжатия». В принципе, кодирование информации может преследовать различные цели:

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

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

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

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

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

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

Так, из трех фотографий, показанных ниже, первая представлена в TIFF-формате (формат без потерь), вторая сохранена в формате JPEG c минимальным параметром сжатия, а третья с максимальным.

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

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

Например, если в результате сжатия изображения на лице изменится форма родинки (но лицо при этом останется полностью узнаваемо), то эта фотография окажется вполне приемлемой, чтобы послать ее по почте знакомым, однако если пересылается фотоснимок легких на медэкспертизу для анализа формы затемнения — это уже совсем другое дело. Кроме того, в случае машинных методов анализа графической информации результаты кодирования с потерей (незаметные для глаз) могут быть «заметны» для машинного анализатора.

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

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

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

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

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

Наиболее известны два алгоритма сжатия без потерь: это кодирование Хаффмена (Huffman) и LZW-кодирование (по начальным буквам имен создателей Lempel, Ziv, Welch), которые представляют основные подходы при сжатии информации.

Кодирование Хаффмена появилось в начале 50-х; принцип его заключается в уменьшении количества битов, используемых для представления часто встречающихся символов и соответственно в увеличении количества битов, используемых для редко встречающихся символов.

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

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

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

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

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

В том случае, когда вероятности символов входных данных неизвестны, используется динамическое кодирование, при котором данные о вероятности появления тех или иных символов уточняются «на лету» во время чтения входных данных.

Алгоритм LZW [2], предложенный сравнительно недавно (в 1984 году), запатентован и принадлежит фирме Sperry.

LZW-алгоритм основан на идее расширения алфавита, что позволяет использовать дополнительные символы для представления строк обычных символов. Используя, например, вместо 8-битовых ASCII-кодов 9-битовые, вы получаете дополнительные 256 символов.

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

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

Возвращаясь к примеру с телефоном, можно, проведя весьма упрощенную аналогию, сказать, что, сжимая запись 233 34 44 по LZW-методу, мы придем к введению новых строк — 333 и 444 и, выражая их дополнительными символами, сможем уменьшить длину записи.

Наверное, читателю будет интересно узнать, какой же архиватор лучше. Ответ на этот вопрос далеко не однозначен.

Если посмотреть на таблицу, в которой «соревнуются» архиваторы (а сделать это можно как на соответствующем сайте в Интернете [3], так и на нашем CD-ROM), то можно увидеть, что количество программ, принимающих участие в «соревнованиях», превышает сотню. Как же выбрать из этого многообразия необходимый архиватор?

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

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

В связи с этим существуют различные виды специализированных тестов, например на сжатие только текстовых файлов или только графических. Так, в частности, Wave Zip в первую очередь умеет сжимать WAV-файлы, а мультимедийный архиватор ERI лучше всех упаковывает TIFF-файлы.

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

Существует тип архиваторов (так называемые Exepackers), которые служат для сжатия исполняемых модулей COM, EXE или DLL. Файл упаковывается таким образом, что при запуске он сам себя распаковывает в памяти «на лету» и далее работает в обычном режиме.

Одними из лучших в данной категории можно назвать программы ASPACK и Petite. Более подробную информацию о программах данного класса, а также соответствующие рейтинги можно найти по адресу [4].

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

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

Большинство программ поддерживают один или два формата. Однако некоторые, такие, например, как программа WinAce, поддерживают множество форматов, осуществляя компрессию в форматах ACE, ZIP, LHA, MS-CAB, JAVA JAR и декомпрессию в форматах ACE, ZIP, LHA, MS-CAB, RAR, ARC, ARJ, GZip, TAR, ZOO, JAR.

Создание solid-архивов — это архивирование, при котором увеличение сжатия возрастает при наличии большого числа одновременно обрабатываемых коротких файлов. Часть архиваторов, например ACB, всегда создают solid-архивы, другие, такие как RAR или 777, предоставляют возможность их создания, а некоторые, например ARJ, этого делать вообще не умеют.

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

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

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

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

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

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

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

КомпьютерПресс 5'2000

Источник: https://compress.ru/article.aspx?id=10581

Сжатие данных с потерями — это… Что такое Сжатие данных с потерями?

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

Типы сжатия с потерями

Существуют две основных схемы сжатия с потерями:

  • В трансформирующих кодеках фреймы изображений или звука обычно трансформируются в новое базисное пространство и производится квантование. Трансформация может осуществляться либо для всего фрейма целиком (как, например, в схемах на основе wavelet-преобразования), либо поблочно (характерный пример — JPEG). Результат затем сжимается энтропийными методами.
  • В предсказывающих кодеках предыдущие и/или последующие отсчеты данных используются для того, чтобы предсказать текущий отсчет изображения или звука. Ошибка между предсказанными данными и реальными вместе с добавочной информацией, необходимой для производства предсказания, затем квантуется и кодируется.

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

Сжатие с потерями против сжатия без потерь

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

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

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

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

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

Недостатки

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

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

Методы сжатия данных с потерями (примеры)

Компрессия изображений

Компрессия видео

Компрессия звука

Основная статья: Цифровой звук

Источник: https://dic.academic.ru/dic.nsf/ruwiki/35366

Способы сжатия и архивации информации

Проблема, тесно связанная с моделями представления информации, — сжатие информации.

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

Разработаны и применяются два типа алгоритмов сжатия:

  • • сжатие с изменением структуры данных (оно происходит без потери данных);
  • • сжатие с частичной потерей данных.

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

Такой тип сжатия применяется, например, для хранения текстов (наиболее известны алгоритмы Хаффмана и Лемпела—Зива).

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

Читайте также:  Конкуренция, совершенная конкуренция - в помощь студенту

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

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

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

На практике выделяют следующие два вида компрессии данных:

  • 1. Сжатие без потерь (lossless compression) — собственно сжатие в смысле приведенного выше определения.
  • 2. Сжатие с потерями (lossy compression) — процесс, состоящий из двух этапов:
    • • выделение сохраняемой части информации в зависимости от цели сжатия и особенностей приемника и источника;
    • • собственно сжатие без потерь.

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

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

Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника: элемент а., вероятность появления которого равняется р., выгоднее всего представлять —log 1pj бит. Если при кодировании размер элементарных кодов в точности получается равным —log^.

, то длина кода будет минимальной из всех возможных способов алфавитного кодирования и равна энтропии tf = -2>, log2jP|. Сжатие всегда осуществляется за счет устранения статистической избыточности в представлении информации. Компрессор не может сжать любой файл.

Размер некоторых файлов уменьшается, а остальных остается неизменным или увеличивается.

  • Коды Хаффмана (Huffman Coding), или коды с минимальной избыточностью
  • Характеристики: степени сжатия — от 1 до 8, средняя — 1,5; не увеличивает размер файла (не считая таблицы перекодировки).
  • Кодирование длин повторов, Run Length Encoding (RLE)

Один из наиболее старых методов сжатия. Идея метода состоит в замене идущих подряд одинаковых символов (бит или байт) парой (количество, символ). В основном используется для кодирования растровых изображений. Характеристика: степень сжатия от 0,5 до 32.

Алгоритмы Зива-Лемпеля (LZ-методы)

Реализации LZ77, LZ78, LZW и LZH. Относятся к словарным методам сжатия, т. е. сообщение кодируется не побуквенно (алфавитное кодирование), а по словам. Характеристики LZ78: степень сжатия в зависимости отданных, обычно 2—3, алгоритмы универсальны, но лучше всего подходят для сжатия текстов, рисованных картинок или других однородных данных.

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

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

Изначально словарь содержит одно слово с номером 0 — пустое Л.

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

Рассмотрим, например, входную последовательность 010 001 011 001 010 001 101 011 00.

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

На третьем шаге имеем совпадение с непустым словом в словаре 0, в словарь добавляется слово 00, имеющее код (1,0), и т. д. На шестом шаге мы уже закодировали последовательность 010001011, словарь имеет вид {Л, 0, 1, 00, 01, 011}, остался текст 0010100011. Максимальное совпадение с третьим словом словаря «00».

Данная последовательность вместе со следующим символом (здесь 1) кодируется парой чисел (номер совпадающего слова в словаре, следующий символ) (здесь (3,1)) и добавляется в словарь (теперь словарь имеет вид (Л, 0, 1, 00, 01, 011, 001}. На следующем шаге считывается следующий за уже закодированными символ и т. д.

до конца входного текста.

В результате последовательности 010 001 011 001 010 001 101 011 00 соответствует словарь {Л, 0, 1, 00, 01, 011, 001, 010, ООП, 0101, 10}, разбиение последовательности на слова и код (см. табл. 7):

Таблица 7

Номер 0 1 2 3 4 5 б 7 8 9 10
Слово Л 0 1 00 01 011 001 010 ООП 0101 10
Код (0,0) (0,1) (1,0) (1,1) (4,1) (3,1) (4,0) (6,1) (7,1) (2,0)

При декодировании одновременно строится словарь и сжатое сообщение. Применение

LZ-методы: практически все известные архиваторы (программы WinRar, Win- Zip, форматы файлов гаг, zip, arj, cad, асе и т. д.); графические файлы gif, tiff.

  1. RLE: графические файлы jpeg, tiff.
  2. Коды Хаффмана: jpeg, tiff.
  3. Сжатие с потерями

Характеристики: один из самых эффективных методов; степень сжатия от 1 до 8, т. е. не увеличивает размер данных; в худшем случае обеспечивает лучшую степень сжатия, чем алгоритм Хаффмана (в среднем 1—10%). Не является алфавитным кодированием. Весь кодируемый текст представляется в виде дроби из [0; 1).

Дробь строится таким образом, чтобы текст был представлен как можно компактнее. Возьмем начальный интервал [0; 1) и разобьем на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов. Пусть х = математика. Получим таблицу 8.

Таблица 8

Символ Частота Вероятность Диапазон
а 3 0,3 [0; 0,3)
м 2 0,2 [0,3; 0,5)
т 2 0,2 [0,5; 0,7)
е 1 0,1 [0,7; 0,8)
и 1 0,1 [0,8; 0,9)
к 1 0,1 [0,9; 1)

Будем считать, что таблица известна в компрессоре и декомпрессоре. Кодирование заключается в уменьшении рабочего интервала. Для первого символа в качестве рабочего интервала берется [0; 1). Он разбивается на диапазоны в соответствии с заданными частотами символов.

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

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

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

Таблица 9

Текущий символ Рабочий интервал Длина интервала 1/10 длины
[0; 1) 1 0,1
м [0,3; о,5) [0,3; 0,5) 0,2 0,02
а [0; 0,3) [0,3; 0,36) 0,06 0,006
т [0,5; 0,7) [0,33; 0,342) 0,012 0,0012
е [0,7; 0,8) [0,3384; 0,3396) 0,0012 0,00012

Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а его начало зависит от порядка следования символов в потоке. Если обозначить диапазон символа с как [а(с),Ь(с)), а /0 = 0, r0 = 1, i = 0; пока не будет достигнут последний символ слова

В качестве кода берется произвольное число, лежащее в полученном интервале [/,,/;). Для последовательности х = «мате», состоящей из 4 символов, можно взять у = 0,339. Этого числа достаточно для восстановления исходной цепочки, если известна исходная таблица диапазонов и длина цепочки. Дальше это число можно перевести в двоичную дробь и закодировать цифрами после запятой.

Рассмотрим работу алгоритма декомпрессии. Каждый следующий интервал вложен в предыдущий. Это означает, что если есть число 0,339, то первым символом может быть только М, так как только его диапазон включает это число.

В качестве интервала берется диапазон М [0,3; 0,5), разбивается на подинтервалы, среди которых находится содержащий 0,339. Это [0,3; 0,36), соответствующий символу «А».

Дальше разбивается в соответствии с таблицей этот интервал и т. д.

Источник: https://studref.com/400519/informatika/sposoby_szhatiya_arhivatsii_informatsii

Сжатие информации: как это делается

Мы каждый день пользуемся различными архиваторами: zip, rar, ace окружают нас повсюду. Графические и звуковые файлы тоже содержат сжатые данные. Если же нам нужно использовать сжатие в своей проге, то мы используем различные dll'ки, многие из которых платные. Шареварность — это не единственное свойство программных компонентов, мешающих их нормальному использованию. Если, например, сжимать waw или bmp-файл архиватором, то он будет значительно уступать специальному методу для конкретного типа данных, т.е. метод должен учитывать особенности конкретного типа данных. Поэтому полезно уметь реализовывать сжатие самостоятельно. В этой статье я расскажу, как вообще сжимать информацию и рассмотрю один из методов сжатия.

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

Прежде всего, все методы сжатия делятся на сжатие с потерями и сжатие без потерь.

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

После этого дополнительно применяется сжатие без потерь. Сжатие без потерь — это однозначное кодирование, такое что закодированные сообщения в среднем занимают меньше места. Именно такому сжатию посвящена эта статья. Далее под словом «сжатие» мы будем подразумевать сжатие без потерь.

Теория

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

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

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

Словарные методы заключаются в том, чтобы в случае встречи подстроки, которая уже была найдена раньше, кодировать ссылку, которая занимает меньше места, чем сама подстрока. Классическим словарным методом является метод Лемпела-Зива (LZ). Все используемые на сегодняшний день словарные методы являются лишь модификациями LZ.

Статистическое кодирование заключается в том, чтобы кодировать каждый символ, но использовать коды переменной длины. Примером таких методов служит метод Хаффмана (Huffman). Обычно словарные и статистические методы комбинируются, поскольку у каждого свои преимущества. Отметим один момент, который почему-то неочевиден для некоторых «теоретиков».

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

  • Доказано, что наименьший возможный средний размер сжатого сообщения равен энтропии ансамбля возможных сообщений, округленной с избытком. Энтропия вычисляется по формуле:
  • H = -Sum(p[i] * log(p[i]))

где Sum — сумма по i, p[i] — вероятность i-го сообщения, log — логарифм по основанию 2. Энтропия сложного сообщения равна сумме энтропий входящих в него простых сообщений.

Если кодировать каждый символ отдельно, то длина кода каждого сообщения должна быть равна -log(p). Т.е., например, если вероятность символа 0.3, то его код должен иметь длину 1.73 бита, в то время, как реальные длины целые.

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

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

Этот метод в корне отличается от всех рассмотренных ранее методов. Его главное преимущество в том, что достигается теоретический предел сжатия. Рассмотрим этот метод подробно.

Всё сообщение целиком представляется одним числом по следующему правилу. Число должно находиться в интервале от 0 до 1. Этот интервал делится на части, пропорциональные вероятностям значений первого символа.

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

новая_нижняя_граница = нижняя_граница + ширина * S[i] новая_ширина = ширина * p[i]

где p[i] — вероятность i-го символа, S[i] — сумма вероятностей символов с номерами меньше i.

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

Ширина интервала равна произведению вероятностей символов, т.е. вероятности всего сообщения. Т.о., длина кода равна -log(p), т.е. теоретическому пределу.

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

Реализация

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

Класс CMarkovProcessDef обрабатывает данные, сохраненные в ресурсе в специальном формате. Эти данные сгенерированы по результатам обработки большого количества текстов, т. е. текстовые файлы, скорее всего, будут сжиматься хорошо, а если попытаться сжать какой-нибудь бинарник, то размер «сжатого» файла будет больше исходного.

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

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

Запишем его и сдвинем буферы на 1 байт. При распаковке кроме переменных, обрабатываемых так же, как при упаковке, нам понадобится еще одна, где будет информация из файла. Для того, чтобы определить очередной символ, нужно найти символ с наименьшим номером, такой, что S[n] * dwBuf2 >= dwBuf3, т.е. P[n] >= dwBuf3 / dwBuf2.

При работе с целыми числами возникает проблема: мы представляем вероятности (дробные числа от 0 до 1) целочисленными переменными (0x100000000 * p). Для умножения и деления на них нужны особые процедуры: при умножении берем старшее 32-битное слово 64-битного результата, а при делении делим число, умноженное на 2^32.

Компилятор не может, умножитв DWORD на DWORD, поместить результат в 64-битную переменную — это недостаток языка С++. Поэтому пришлось написать специальные процедуры на ассемблере.

void CArithmCompressorDlg::OnBnClickedCompress() { CFileDialog dlg1(TRUE); if (dlg1.DoModal() != IDOK) return; CFileDialog dlg2(FALSE, «compressed», 0, OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT, «*.compressed|*.

compressed|All files|*.*||»); if (dlg2.DoModal() != IDOK) return; CFile file1(dlg1.GetPathName(), CFile::modeRead); CFile file2(dlg2.GetPathName(), CFile::modeCreate | CFile::modeWrite); BYTE b; ULONGLONG fs = file1.

GetLength();

file2.Write(&fs, 8); //

Запишем размер исходного файла

//

m_mpd — это объект класса CMarkovProcessDef  m_mpd.ResetProcess(); // Сбросим данные о предшествующих символах

//

Здесь начинается сжатие // Начальный интервал — от 0x00000000 до 0xFFFFFFFF DWORD dwBuf1 = 0; // Нижняя граница DWORD dwBuf2 = 0xFFFFFFFF; // Ширина DWORD dww; // Временная переменная while (file1.Read(&b, 1)) {

//

Вычисляем новый интервал if (b > 0) dww = MulHigh(m_mpd.GetDistribution(b-1), dwBuf2); else dww = 0; /* m_mpd.GetDistribution(b-1) — Это S[b], т. о. p[b] — это m_mpd.GetDistribution(b) — m_mpd.GetDistribution(b-1)

Замените эту функцию на свою реализацию и получите метод сжатия для вашего типа данных.

*/ dwBuf1 += dww; if (b < 255) dwBuf2 = MulHigh(m_mpd.GetDistribution(b), dwBuf2) - dww; else dwBuf2 -= dww;

while (((dwBuf1 ^ (dwBuf1 + dwBuf2)) & 0xFF000000) == 0) //

Если старший байт буфера определен {

file2.Write(((LPBYTE)&dwBuf1)+3, 1); //

Записываем его dwBuf1 = dwBuf1 = S[m]

//

Поиск методом половинного деления do { m = (l+h)/2;

  1. if (h if (m_mpd.GetDistribution(m) } while (true);
  2. //

Вычисляем новый интервал if (m > 0) dww = MulHigh(m_mpd.GetDistribution(m-1), dwBuf2); else dww = 0; dwBuf1 += dww; dwBuf3 -= dww; if (m < 255) dwBuf2 = MulHigh(m_mpd.GetDistribution(m), dwBuf2) - dww; else dwBuf2 -= dww;

file2.Write(&m, 1); //

Пишем символ m_mpd.PushSymbol(m, 0); 

while (((dwBuf1 ^ (dwBuf1 + dwBuf2)) & 0xFF000000) == 0) //

Если старший байт буфера определен {

dwBuf1 = dwBuf1

Источник: https://xakep.ru/2004/06/22/22811/

Ссылка на основную публикацию