Алгоритмы сжатия: Алгоритмы сжатия данных без потерь, часть 2 / Хабр

Алгоритмы сжатия данных без потерь, часть 2 / Хабр

Часть 1

Техники сжатия данных

Для сжатия данных придумано множество техник. Большинство из них комбинируют несколько принципов сжатия для создания полноценного алгоритма. Даже хорошие принципы, будучи скомбинированы вместе, дают лучший результат. Большинство техник используют принцип энтропийного кодирования, но часто встречаются и другие – кодирование длин серий (Run-Length Encoding) и преобразование Барроуза-Уилера (Burrows-Wheeler Transform).

Кодирование длин серий (RLE)

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

Простой пример:

На входе: AAABBCCCCDEEEEEEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

На выходе: 3A2B4C1D6E38A

Преобразование Барроуза-Уилера (BWT)

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

Алгоритм:

— создаём массив строк

— создаём все возможные преобразования входящей строки данных, каждое из которых сохраняем в массиве

— сортируем массив

— возвращаем последний столбец

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

Благодаря чередованию одинаковых символов, вывод алгоритма оптимален для сжатия RLE, которое даёт «3H&3A». Но на реальных данных, к сожалению, настолько оптимальных результатов обычно не получается.

Энтропийное кодирование

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

Алгоритм Шеннона — Фано

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

Код для символа получается поиском по дереву, и добавлением 0 или 1, в зависимости от того, идём мы налево или направо. К примеру, путь к “А” – две ветки налево и одна направо, его код будет «110». Алгоритм не всегда даёт оптимальные коды из-за методики построения дерева снизу вверх. Поэтому сейчас используется алгоритм Хаффмана, подходящий для любых входных данных.

1. парсим ввод, считаем количество вхождений всех символов

2. определяем вероятность появления каждого из них

3. сортируем символы по вероятности появления

4. делим список пополам так, чтобы сумма вероятностей в левой ветке примерно равнялось сумме в правой

5. добавляем 0 или 1 для левых и правых узлов соответственно

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

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

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

1. Парсим ввод, считаем количество повторений символов

2. Определяем вероятность появления каждого символа

3. Сортируем список по вероятностям (самые частые вначале)

4. Создаём листы для каждого символа, и добавляем их в очередь

5. пока очередь состоит более, чем из одного символа:

— берём из очереди два листа с наименьшими вероятностями

— к коду первой прибавляем 0, к коду второй – 1

— создаём узел с вероятностью, равной сумме вероятностей двух нод

— первую ноду вешаем на левую сторону, вторую – на правую

— добавляем полученный узел в очередь

6. Последняя нода в очереди будет корнем двоичного дерева.

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

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

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

В общем алгоритм таков:

1. считаем количество уникальных символов на входе. Это количество будет представлять основание для счисления b (b=2 – двоичное, и т.п.).

2. подсчитываем общую длину входа

3. назначаем «коды» от 0 до b каждому из уникальных символов в порядке их появления

4. заменяем символы кодами, получая число в системе счисления с основанием b

5. преобразуем полученное число в двоичную систему

Пример. На входе строка «ABCDAABD»

1. 4 уникальных символа, основание = 4, длина данных = 8

2. назначаем коды: A=0, B=1, C=2, D=3

3. получаем число “0.01230013”

4. преобразуем «0.01231123» из четверичной в двоичную систему: 0.01101100000111

Если мы положим, что имеем дело с восьмибитными символами, то на входе у нас 8х8=64 бита, а на выходе – 15, то есть степень сжатия 24%.

Классификация алгоритмов

Алгоритмы, применяющие метод «скользящего окна»

Всё началось с алгоритма LZ77 (1977 год), который представил новую концепцию «скользящего окна», позволившую значительно улучшить сжатие данных. LZ77 использует словарь, содержащий тройки данных – смещение, длина серии и символ расхождения. Смещение – как далеко от начала файла находится фраза. Длина серии – сколько символов, считая от смещения, принадлежат фразе. Символ расхождения показывает, что найдена новая фраза, похожая на ту, что обозначена смещением и длиной, за исключением этого символа. Словарь меняется по мере парсинга файла при помощи скользящего окна. К примеру, размер окна может быть 64Мб, тогда словарь будет содержать данные из последних 64 мегабайт входных данных.

К примеру, для входных данных «abbadabba» результат будет «abb(0,1,’d’)(0,3,’a’)»

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

LZR

Модификация алгоритма LZ77, предложенная Майклом Роуде в 1981 году. В отличие от LZ77 работает за линейное время, однако требует большего объёма памяти. Обычно проигрывает LZ78 в сжатии.

DEFLATE

Придуман Филом Кацем в 1993 году, и используется в большинстве современных архиваторов. Является комбинацией LZ77 или LZSS с кодированием Хаффмана.

DEFLATE64

Патентованная вариация DEFLATE с увеличением словаря до 64 Кб. Сжимает лучше и быстрее, но не используется повсеместно, т.к. не является открытым.

LZSS

Алгоритм Лемпеля-Зива-Сторера-Цимански был представлен в 1982 году. Улучшенная версия LZ77, которая просчитывает, не увеличит ли размер результата замена исходных данных кодированными.

До сих пор используется в популярных архиваторах, например RAR. Иногда – для сжатия данных при передаче по сети.

LZH

Был разработан в 1987 году, расшифровывается как «Лемпель-Зив-Хаффман». Вариация LZSS, использует кодирование Хаффмана для сжатия указателей. Сжимает чуть лучше, но ощутимо медленнее.

LZB

Разработан в 1987 году Тимоти Беллом, как вариант LZSS. Как и LZH, LZB уменьшает результирующий размер файлов, эффективно кодируя указатели. Достигается это путём постепенного увеличения размера указателей при увеличении размера скользящего окна. Сжатие получается выше, чем у LZSS и LZH, но скорость значительно меньше.

ROLZ

Расшифровывается как «Лемпель-Зив с уменьшенным смещением», улучшает алгоритм LZ77, уменьшая смещение, чтобы уменьшить количество данных, необходимого для кодирования пары смещение-длина. Впервые был представлен в 1991 году в алгоритме LZRW4 от Росса Вильямса. Другие вариации — BALZ, QUAD, и RZM. Хорошо оптимизированный ROLZ достигает почти таких же степеней сжатия, как и LZMA – но популярности он не снискал.

LZP

«Лемпель-Зив с предсказанием». Вариация ROLZ со смещением = 1. Есть несколько вариантов, одни направлены на скорость сжатия, другие – на степень. В алгоритме LZW4 используется арифметическое кодирование для наилучшего сжатия.

LZRW1

Алгоритм от Рона Вильямса 1991 года, где он впервые ввёл концепцию уменьшения смещения. Достигает высоких степеней сжатия при приличной скорости. Потом Вильямс сделал вариации LZRW1-A, 2, 3, 3-A, и 4

LZJB

Вариант от Джеффа Бонвика (отсюда “JB”) от 1998 года, для использования в файловой системе Solaris Z File System (ZFS). Вариант алгоритма LZRW1, переработанный для высоких скоростей, как этого требует использование в файловой системе и скорость дисковых операций.

LZS

Lempel-Ziv-Stac, разработан в Stac Electronics в 1994 для использования в программах сжатия дисков. Модификация LZ77, различающая символы и пары длина-смещение, в дополнение к удалению следующего встреченного символа. Очень похож на LZSS.

LZX

Был разработан в 1995 году Дж. Форбсом и Т.Потаненом для Амиги. Форбс продал алгоритм компании Microsoft в 1996, и устроился туда работать над ним, в результате чего улучшенная его версия стала использоваться в файлах CAB, CHM, WIM и Xbox Live Avatars.

LZO

Разработан в 1996 Маркусом Оберхьюмером с прицелом на скорость сжатия и распаковки. Позволяет настраивать уровни компрессии, потребляет очень мало памяти. Похож на LZSS.

LZMA

“Lempel-Ziv Markov chain Algorithm”, появился в 1998 году в архиваторе 7-zip, который демонстрировал сжатие лучше практически всех архиваторов. Алгоритм использует цепочку методов сжатия для достижения наилучшего результата. Вначале слегка изменённый LZ77, работающий на уровне битов (в отличие от обычного метода работы с байтами), парсит данные. Его вывод подвергается арифметическому кодированию. Затем могут быть применены другие алгоритмы. В результате получается наилучшая компрессия среди всех архиваторов.

LZMA2

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

Статистический алгоритм Лемпеля-Зива

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

Алгоритмы с использованием словаря

LZ78

Алгоритм 1978 года, авторы – Лемпель и Зив. Вместо использования скользящего окна для создания словаря, словарь составляется при парсинге данных из файла. Объём словаря обычно измеряется в нескольких мегабайтах. Отличия в вариантах этого алгоритма строятся на том, что делать, когда словарь заполнен.

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

Входные данные «abbadabbaabaad» на выходе дадут «(0,a)(0,b)(2,a)(0,d)(1,b)(3,a)(6,d)»

An input such as «abbadabbaabaad» would generate the output «(0,a)(0,b)(2,a)(0,d)(1,b)(3,a)(6,d)». You can see how this was derived in the following example:

LZW

Лемпель-Зив-Велч, 1984 год. Самый популярный вариант LZ78, несмотря на запатентованность. Алгоритм избавляется от лишних символов на выходе и данные состоят только из указателей. Также он сохраняет все символы словаря перед сжатием и использует другие трюки, позволяющие улучшать сжатие – к примеру, кодирование последнего символа предыдущей фразы в качестве первого символа следующей. Используется в GIF, ранних версиях ZIP и других специальных приложениях. Очень быстр, но проигрывает в сжатии более новым алгоритмам.

LZC

Компрессия Лемпеля-Зива. Модификация LZW, использующаяся в утилитах UNIX. Следит за степенью сжатия, и как только она превышает заданный предел – словарь переделывается заново.

LZT

Лемпель-Зив-Тищер. Когда словарь заполняется, удаляет фразы, использовавшиеся реже всех, и заменяет их новыми. Не получил популярности.

LZMW

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

LZAP

Джеймс Сторер, 1988 год. Модификация LZMW. “AP” означает «все префиксы» — вместо того, чтобы сохранять при каждой итерации одну фразу, в словаре сохраняется каждое изменение. К примеру, если последняя фраза была “last”, а текущая – «next”, тогда в словаре сохраняются „lastn“, „lastne“, „lastnex“, „lastnext“.

LZWL

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

LZJ

1985 год, Матти Якобсон. Один из немногих вариантов LZ78, отличающихся от LZW. Сохраняет каждую уникальную строку в уже обработанных входных данных, и всем им назначает уникальные коды. При заполнении словаря из него удаляются единичные вхождения.

Алгоритмы, не использующие словарь

PPM

Предсказание по частичному совпадению – использует уже обработанные данные, чтобы предсказать, какой символ будет в последовательности следующим, таким образом уменьшая энтропию выходных данных. Обычно комбинируется с арифметическим кодировщиком или адаптивным кодированием Хаффмана. Вариация PPMd используется в RAR и 7-zip

bzip2

Реализация BWT с открытым исходным кодом. При простоте реализации достигает хорошего компромисса между скоростью и степенью сжатия, в связи с чем популярен в UNIX. Сначала данные обрабатываются при помощи RLE, затем BWT, потом данные особым образом сортируются, чтобы получить длинные последовательности одинаковых символов, после чего к ним снова применяется RLE. И, наконец, кодировщик Хаффмана завершает процесс.

PAQ

Мэтт Махоуни, 2002 год. Улучшение PPM(d). Улучшает их при помощи интересной техники под названием „перемешивание контекста“ (context mixing). В этой технике несколько предсказательных алгоритмов комбинируются, чтобы улучшить предсказание следующего символа. Сейчас это один из самых многообещающих алгоритмов. С его первой реализации было создано уже два десятка вариантов, некоторые из которых ставят рекорды сжатия. Минус – маленькая скорость из-за необходимости использования нескольких моделей. Вариант под названием PAQ80 поддерживает 64 бита и показывает серьёзное улучшение в скорости работы (используется, в частности, в программе PeaZip для Windows).

Алгоритмы сжатия данных без потерь / Хабр

Часть первая – историческая.

Введение

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

История

Иерархия алгоритмов:

Хотя сжатие данных получило широкое распространение вместе с интернетом и после изобретения алгоритмов Лемпелем и Зивом (алгоритмы LZ), можно привести несколько более ранних примеров сжатия. Морзе, изобретая свой код в 1838 году, разумно назначил самым часто используемым буквам в английском языке, “e” и “t”, самые короткие последовательности (точка и тире соотв.). Вскоре после появления мейнфреймов в 1949 году был придуман алгоритм Шеннона — Фано, который назначал символам в блоке данных коды, основываясь на вероятности их появления в блоке. Вероятность появления символа в блоке была обратно пропорциональна длине кода, что позволяло сжать представление данных.

Дэвид Хаффман был студентом в классе у Роберта Фано и в качестве учебной работы выбрал поиск улучшенного метода бинарного кодирования данных. В результате ему удалось улучшить алгоритм Шеннона-Фано.

Ранние версии алгоритмов Шеннона-Фано и Хаффмана использовали заранее определённые коды. Позже для этого стали использовать коды, созданные динамически на основе данных, предназначаемых для сжатия. В 1977 году Лемпель и Зив опубликовали свой алгоритм LZ77, основанный на использования динамически создаваемого словаря (его ещё называют «скользящим окном»). В 78 году они опубликовали алгоритм LZ78, который сначала парсит данные и создаёт словарь, вместо того, чтобы создавать его динамически.

Проблемы с правами

Алгоритмы LZ77 и LZ78 получили большую популярность и вызвали волну улучшателей, из которых до наших дней дожили DEFLATE, LZMA и LZX. Большинство популярных алгоритмов основаны на LZ77, потому что производный от LZ78 алгоритм LZW был запатентован компанией Unisys в 1984 году, после чего они начали троллить всех и каждого, включая даже случаи использования изображений в формате GIF. В это время на UNIX использовали вариацию алгоритма LZW под названием LZC, и из-за проблем с правами их использование пришлось сворачивать. Предпочтение отдали алгоритму DEFLATE (gzip) и преобразованию Барроуза — Уилера, BWT (bzip2). Что было и к лучшему, так как эти алгоритмы почти всегда превосходят по сжатию LZW.
К 2003 году срок патента истёк, но поезд уже ушёл и алгоритм LZW сохранился, пожалуй, только в файлах GIF. Доминирующими являются алгоритмы на основе LZ77.
В 1993 году была ещё одна битва патентов – когда компания Stac Electronics обнаружила, что разработанный ею алгоритм LZS используется компанией Microsoft в программе для сжатия дисков, поставлявшейся с MS-DOS 6.0. Stac Electronics подала в суд и им удалось выиграть дело, в результате чего они получили более $100 миллионов.

Рост популярности Deflate

Большие корпорации использовали алгоритмы сжатия для хранения всё увеличивавшихся массивов данных, но истинное распространение алгоритмов произошло с рождением интернета в конце 80-х. Пропускная способность каналов была чрезвычайно узкой. Для сжатия данных, передаваемых по сети, были придуманы форматы ZIP, GIF и PNG.
Том Хендерсон придумал и выпустил первый коммерчески успешный архиватор ARC в 1985 году (компания System Enhancement Associates). ARC была популярной среди пользователей BBS, т.к. она одна из первых могла сжимать несколько файлов в архив, к тому же исходники её были открыты. ARC использовала модифицированный алгоритм LZW.
Фил Катц, вдохновлённый популярностью ARC, выпустил программу PKARC в формате shareware, в которой улучшил алгоритмы сжатия, переписав их на Ассемблере. Однако, был засужен Хендерсоном и был признан виновным. PKARC настолько открыто копировала ARC, что иногда даже повторялись опечатки в комментариях к исходному коду.
Но Фил Катц не растерялся, и в 1989 году сильно изменил архиватор и выпустил PKZIP. После того, как его атаковали уже в связи с патентом на алгоритм LZW, он изменил и базовый алгоритм на новый, под названием IMPLODE. Вновь формат был заменён в 1993 году с выходом PKZIP 2.0, и заменой стал DEFLATE. Среди новых возможностей была функция разбиения архива на тома. Эта версия до сих пор повсеместно используется, несмотря на почтенный возраст.
Формат изображений GIF (Graphics Interchange Format) был создан компанией CompuServe в 1987. Как известно, формат поддерживает сжатие изображения без потерь, и ограничен палитрой в 256 цветов. Несмотря на все потуги Unisys, ей не удалось остановить распространение этого формата. Он до сих пор популярен, особенно в связи с поддержкой анимации.
Слегка взволнованная патентными проблемами, компания CompuServe в 1994 году выпустила формат Portable Network Graphics (PNG). Как и ZIP, она использовала новый модный алгоритм DEFLATE. Хотя DEFLATE был запатентован Катцем, он не стал предъявлять никаких претензий.
Сейчас это самый популярный алгоритм сжатия. Кроме PNG и ZIP он используется в gzip, HTTP, SSL и других технологиях передачи данных.

К сожалению Фил Катц не дожил до триумфа DEFLATE, он умер от алкоголизма в 2000 году в возрасте 37 лет. Граждане – чрезмерное употребление алкоголя опасно для вашего здоровья! Вы можете не дожить до своего триумфа!

Современные архиваторы

ZIP царствовал безраздельно до середины 90-х, однако в 1993 году простой русский гений Евгений Рошал придумал свой формат и алгоритм RAR. Последние его версии основаны на алгоритмах PPM и LZSS. Сейчас ZIP, пожалуй, самый распространённый из форматов, RAR – до недавнего времени был стандартом для распространения различного малолегального контента через интернет (благодаря увеличению пропускной способности всё чаще файлы распространяются без архивации), а 7zip используется как формат с наилучшим сжатием при приемлемом времени работы. В мире UNIX используется связка tar + gzip (gzip — архиватор, а tar объединяет несколько файлов в один, т.к. gzip этого не умеет).

Прим. перев. Лично я, кроме перечисленных, сталкивался ещё с архиватором ARJ (Archived by Robert Jung), который был популярен в 90-х в эру BBS. Он поддерживал многотомные архивы, и так же, как после него RAR, использовался для распространения игр и прочего вареза. Ещё был архиватор HA от Harri Hirvola, который использовал сжатие HSC (не нашёл внятных объяснений — только «модель ограниченного контекста и арифметическое кодирование»), который хорошо справлялся со сжатием длинных текстовых файлов.

В 1996 году появился вариант алгоритма BWT с открытыми исходниками bzip2, и быстро приобрёл популярность. В 1999 году появилась программа 7-zip с форматом 7z. По сжатию она соперничает с RAR, её преимуществом является открытость, а также возможность выбора между алгоритмами bzip2, LZMA, LZMA2 и PPMd.

В 2002 году появился ещё один архиватор, PAQ. Автор Мэтт Махоуни использовал улучшенную версию алгоритма PPM с использованием техники под названием «контекстное смешивание». Она позволяет использовать больше одной статистической модели, чтобы улучшить предсказание по частоте появления символов.

Будущее алгоритмов сжатия

Конечно, бог его знает, но судя по всему, алгоритм PAQ набирает популярность благодаря очень хорошей степени сжатия (хотя и работает он очень медленно). Но благодаря увеличению быстродействия компьютеров скорость работы становится менее критичной.
С другой стороны, алгоритм Лемпеля-Зива –Маркова LZMA представляет собой компромисс между скоростью и степенью сжатия и может породить много интересных ответвлений.
Ещё одна интересная технология «substring enumeration» или CSE, которая пока мало используется в программах.

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

Алгоритмы сжатия: описание, основные приемы, характеристики

Сжатие является частным случаем кодирования, основной характеристикой которого является то, что результирующий код меньше исходного. Процесс основан на поиске повторений в информационных рядах и последующем сохранении только одного рядом с количеством повторений. Таким образом, например, если последовательность появляется в файле, как «AAAAAA», занимая 6 байтов, он будет сохранен, как «6A», который занимает только 2 байта, в алгоритме сжатия RLE.

История возникновения процесса

Азбука Морзе, изобретенная в 1838 году — первый известный случай сжатия данных. Позже, когда в 1949 году мейнфрейм-компьютеры начали завоевывать популярность, Клод Шеннон и Роберт Фано изобрели кодирование, названного в честь авторов — Шеннона-Фано. Это шифрование присваивает коды символам в массиве данных по теории вероятности.

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

В 1977 году, Авраам Лемпель и Джейкоб Зив издали свой инновационный метод LZ77, использующий более модернизированный словарь. В 1978 году, та же команда авторов, издала усовершенствованный алгоритм сжатия LZ78. Который использует новый словарь, анализирующий входные данные и генерирующий статический словарь, а не динамический, как у 77 версии.

Формы исполнения компрессии

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

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

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

Преимущество алгоритмов сжатия:

1. Значительно уменьшает объем памяти. При степени сжатия 2:1 файл в 20 мегабайт (МБ) займет 10 МБ пространства. В результате администраторы сети тратят меньше денег и времени на хранение баз данных.
2. Оптимизирует производительность резервного копирования.
3. Важный метод сокращения данных.
4. Практически любой файл может быть сжат, но важно выбрать нужную технологию под конкретный тип файла. Иначе файлы могут быть «уменьшены», но при этом общий размер не изменится.

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

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

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

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

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

Порядок создания алгоритмы сжатия данных:

1. Просчитывают, сколько раз каждый символ повторяется в файле для «уменьшения».
2. Создают связанный список с информацией о символах и частотах.
3. Выполняют сортировку списка от наименьшего к наибольшему в зависимости от частоты.
4. Преобразуют каждый элемент в списке в дерево.
5. Объединяют деревья в одно, при этом первые два образуют новое.
6. Добавляют частоты каждой ветви в новый элемент дерева.
7. Вставляют новое в нужное место в списке, в соответствии с суммой полученных частот.
8. Назначают новый двоичный код каждого символа. Если берется нулевая ветвь, к коду добавляется ноль, а если первая ветвь, добавляется единица.
9. Файл перекодируется в соответствии с новыми кодами.
10. Например характеристики алгоритмов сжатия для короткого текста:»ata la jaca a la estaca»
11. Подсчитывают, сколько раз появляется каждый символ и составляют связанный список:» (5), a (9), c (2), e (1), j (1), l (2), s (1), t (2)
12. Заказывают по частоте от низшей к высшей: e (1), j (1), s (1), c (2), l (2), t (2), » (5), a (9)

Как видно, корневой узел дерева создан, далее назначаются коды.

И осталось только упаковать биты в группы по восемь, то есть в байты:

Всего восемь байтов, а исходный текст был 23.

Демонстрация библиотеки LZ77

Алгоритм LZ77 рассмотрим на примере текста«howtogeek». Если повторить его три раза, то он изменит его следующим образом.

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

Это идеальный пример, когда большая часть текста сжимается с помощью нескольких символов. Например, слово «это» будет сжато, даже если оно встречается в таких словах, как «этом», «их» и «этого». С повторяющимися словами можно получить огромные коэффициенты сжатия. Например, текст со словом «howtogeek», повторенным 100 раз имеет размер три килобайта, при компрессии займет всего 158 байт, то есть с 95% «уменьшением».

Это, конечно, довольно экстремальный пример, но наглядно демонстрирует свойства алгоритмов сжатия. В общей практике он составляет 30-40% с текстовым форматом ZIP. Алгоритм LZ77, применяется ко всем двоичным данным, а не только к тексту, хотя последний легче сжать из-за повторяющихся слов.

Дискретное косинусное преобразование изображений

Сжатие видео и аудио работает совсем по-другому. В отличие от текста, где выполняют алгоритмы сжатия без потерь, и данные не будут потеряны, с изображениями выполняют «уменьшение» с потерями, и чем больше %, тем больше потерь. Это приводит к тем ужасно выглядящим JPEG-файлам, которые люди загружали, обменивали и делали скриншоты по несколько раз.

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

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

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

Сжатие аудио работает очень похоже на сжатие текста и изображений. Если JPEG удаляет детали из изображения, которое не видны человеческим глазом, сжатие звука делает, то же самое для звуков. MP3 использует битрейт, в диапазоне от нижнего уровня 48 и 96 кбит/с (нижний предел) до 128 и 240 кбит/с (довольно хороший) до 320 кбит/с (высококачественный звук), и услышать разницу можно только с исключительно хорошими наушниками. Существуют кодеки сжатия без потерь для звука, основным из которых является FLAC и использует кодирование LZ77 для передачи звука без потерь.

Форматы «уменьшения» текста

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

Прогоны значений кодируются, как символ, за которым следует длина прогона. Можно правильно восстановить оригинальный поток. Если длина серии<= 2 символа, имеет смысл просто оставить их без изменения, например, как в конце потока с «bb».

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

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

Схемы HTTP: DEFLATE и GZIP

Сегодня в интернете используют два широко используемых алгоритмов сжатия текста HTTP: DEFLATE и GZIP.

DEFLATE — обычно объединяющий данные, с применением LZ77, кодирования Хаффмана. GZIP – файла использует DEFLATE внутри, наряду с некоторыми интересными блокировками, эвристикой фильтрации, заголовком и контрольной суммой. В целом, дополнительная блокировка и эвристика, использующие GZIP, дают качественные коэффициенты сжатия, чем просто один DEFLATE.

Протоколы данных следующего поколения — SPDY и HTTP2.0, поддерживают сжатие заголовков с помощью GZIP, поэтому большая часть веб-стека будет использовать его и в будущем.

Большинство разработчиков просто загружают несжатый контент и полагаются на веб-сервер для «уменьшения» данных на лету. Это дает отличные результаты и простой в использовании алгоритм сжатия графических изображений. По умолчанию на многих серверах установлен GZIP с уровнем 6, наибольший уровень которого равен 9. Это сделано преднамеренно, что позволяет серверам компрессировать данные быстрее за счет большего выходного файла.

Форматы BZIP2 и LZMA, создающие более компактные формы чем GZIP, которые при этом распаковываются быстрее.

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

Предварительная обработка документа

Для качественного сжатия выполняют двухэтапный процесс:

• этап минимизации;
• этап без потерь.

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

Есть много программ, которые выполняют основные алгоритмы сжатия, среди них:

1. Winzip — это формат хранения без потерь, широко используемый для документов, изображений или приложений. Это довольно простая программа, которая сжимает каждый из файлов в отдельности, что позволяет восстанавливать каждый без необходимости читать остальные. Тем самым повышая производительность процесса.
2. 7zip — Бесплатный менеджер для очень мощного и простейшего алгоритма сжатия информации. Благодаря формату файлов 7z, который улучшает стандарт ZIP на 50%. Он поддерживает другие наиболее распространенные форматы, такие как RAR, ZIP, CAB, GZIP и ARJ, поэтому не создает проблем для использования с любым сжатым файлом и интегрируется с контекстным меню в Windows.
3. GZIP — это один из самых известных компрессоров, предназначенных для Linux. Учитывая успех на этой платформе, его доработали для Windows. Одним из основных преимуществ gzip является то, что он использует алгоритм DEFLATE (комбинация кодирования LZ77 и Хаффмана).
4. WinRAR — Компрессорная программа и многофункциональный декомпрессор данных. Это незаменимый инструмент для экономии места на диске и времени передачи при отправке и получении файлов через интернет или при резервном копировании. Он служит для сжатия всех типов документов или программ, чтобы они занимали меньше места на диске и могли быстрее сохраняться или передаваться по сети. Это первый компрессор, который реализует 64-битное управление файлами, что позволяет обрабатывать большие объемы, ограниченные только операционной системой.

Минификаторы CSS

Существует много минификаторов CSS. Некоторые из доступных вариантов включают:

• онлайн CSS Minifier;
• freeformatter.com/css-minifier;
• cleancss.com/css-minify;
• cnvyr.io;
• minifier.org;
• css-minifier.com.

Основное различие между этими инструментами зависит от того, насколько глубоки их процессы минификации. Так, упрощенная оптимизация фильтрует текст, чтобы убрать ненужные пробелы и массивы. Развитая оптимизация предусматривает замену «AntiqueWhite» на « # FAEBD7 », поскольку шестнадцатеричная форма в файле короче, и принудительное использование символа нижнего GZIP-регистра.

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

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

Плюсы и минусы сжатия

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

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

Основным недостатком компрессии является влияние на производительность в результате использования ресурсов ЦП и памяти для процесса и, последующей распаковки.

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

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

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

С экспоненциальным увеличением аппаратной скорости в соответствии с законом Мура, процессы смешивания контекста, вероятно, будут процветать. Так как затраты на скорость преодолеваются за счет быстрого оборудования из-за высокой степени сжатия. Алгоритм, который PAQ стремился улучшить, называется «Прогнозирование путей частичного сопоставления». Или PPM.

Наконец, цепной алгоритм Лемпеля-Зива-Маркова (LZMA) неизменно демонстрирует превосходный компромисс между скоростью и высокой степенью сжатия и, вероятно, создаст больше новых вариантов в будущем. Он будет лидировать, поскольку уже принят во многих конкурирующих форматах сжатия, например, в программе 7-Zip.

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

Алгоритмы используемые при сжатии данных / Хабр

Вступление

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

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

Коды или Алгоритм Хаффмана (Huffman codes) — широко распространенный и очень эффективный метод сжатия данных, который, в зависимости от характеристик этих данных, обычно позволяет сэкономить от 20% до 90% объема.
Рассматриваются данные, представляющие собой последовательность символов. В жадном алгоритме Хаффмана используется таблица, содержащая частоты появления тех или иных символов. С помощью этой таблицы определяется оптимальное представление каждого символа в виде бинарной строки.

Построение кода

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

Обрабатываем b и c

Следующим шагом будет построение дерева, где вершины — «символы», а пути до них соответствуют их префиксным кодам. Для этого на каждом шаге будем брать два символа с минимальной частотой вхождения, и объединять их в новые так называемые символы с частотой равной сумме частот тех, которые мы объединяли, а также соединять их рёбрами, образуя таким образом дерево(см. рисунок). Выбирать минимальные два символа будем из всех символов, исключая те, которые мы уже выбирали. В примере мы объединим символы b и с в символ bc с частотой 3. Далее объединим a и bc в символ abc, получив тем самым дерево. Теперь пути от корня (abc) до листьев и есть Коды Хаффмана(каждому ребру соответствует либо 1 либо 0)

Получившееся дерево

Преобразование MTF

Преобразование MTF (move-to-front, движение к началу) — алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения производительности последующего кодирования.

Построение кода

Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.
Современные алгоритмы (например, bzip2) перед алгоритмом MTF используют алгоритм BWT, поэтому в качестве примера рассмотрим строку s=«BCABAAA», полученную из строки «ABACABA» в результате преобразования Барроуза-Уиллера (о нем далее). Первый символ строки s=’B’ является вторым элементом алфавита «ABC», поэтому на вывод подаётся 1. После перемещения ‘B’ в начало алфавита тот принимает вид «BAC». Дальнейшая работа алгоритма:

• Символ Список Вывод
• B ABC 1
• C BAC 2
• A CBA 2
• B ACB 2
• A BAC 1
• A ABC 0
• A ABC 0

Таким образом, результат работы алгоритма MTF(s):«1222100».

Обратное преобразование

Пусть даны строка s= «1222100» и исходный алфавит «ABC». Символ с номером 1 в алфавите — это ‘B’. На вывод подаётся ‘B’, и этот символ перемещается в начало алфавита. Символ с номером 2 в алфавите — это ‘A’, поэтому ‘A’ подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.

• Символ Список Вывод
• 1 ABC B
• 2 BAC C
• 2 CBA A
• 2 ACB B
• 1 BAC A
• 0 ABC A
• 0 ABC A

Значит, исходная строка s = «BCABAAA».

Преобразование Барроуза-Уиллера

Преобразование Барроуза — Уилера (Burrows-Wheeler transform, BWT) — это алгоритм, используемый в техниках сжатия данных для преобразования исходных данных.
Bzip2 использует преобразование Барроуза-Уилера для превращения последовательностей многократно чередующихся символов в строки одинаковых символов, затем применяет преобразование MTF, и в конце кодирование Хаффмана.

Работа алгоритма

Преобразование выполняется в три этапа. На первом этапе составляется таблица всех циклических сдвигов входной строки. На втором этапе производится лексикографическая (в алфавитном порядке) сортировка строк таблицы. На третьем этапе в качестве выходной строки выбирается последний столбец таблицы преобразования. Следующий пример иллюстрирует описанный алгоритм:
Пусть нам дана исходная строка s=«ABACABA».

Результат вкратце запишем так: BWT(s)=(«BCABAAA», 3), где 3 — это номер исходной строки в отсортированной матрице, так как он может понадобиться для обратного преобразования.
Следует заметить, что иногда в исходной строке приводится так называемый символ конца строки $, который в преобразовании будет считаться последним символом, тогда сохранение номера исходной строки не требуется. При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки и будет исходной («ABACABA$»). При этом при сортировке матрицы данный символ будет рассматриваться как самый последний после всех символов алфавита. Тогда результат можно записать так BWT(s)=»$CBBAAAA». Он будет эквивалентен первому, так как также содержит все символы исходной строки.

Обратное преобразование

Пусть нам дано: BWT(s)=(«BCABAAA», 3). Тогда выпишем в столбик нашу преобразованную последовательность символов «BCABAAA». Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза — Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно отсортируем матрицу, затем в предыдущий столбец запишем «BCABAAA». Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических перестановок строки, которую нам надо найти. Выстроив полный отсортированный список перестановок, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку. Алгоритм обратного преобразования описан в таблице ниже:

Следует также заметить, что если нам было бы дано BWT(s)=»$CBBAAAA», то мы также получили бы нашу исходную строку, только с символом конца строки $ на конце: ABACABA$.

Заключение

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

Сжатие информации без потерь. Часть первая / Хабр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если вероятность появления элемента s_i равна p(s_i), то наиболее выгодно будет представить этот элемент — log₂p(s_i) битами. Если при кодировании удается добиться того, что длина всех элементов будет приведена к log₂p(s_i) битам, то и длина всей кодируемой последовательности будет минимальной для всех возможных методов кодирования. При этом, если распределение вероятностей всех элементов F = {p(s_i)} неизменно, и вероятности элементов взаимно независимы, то средняя длина кодов может быть рассчитана как

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

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

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

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

Где P_k — вероятность нахождения источника в состоянии k.

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

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

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

Пусть задан некоторый алфавит , состоящий из некоторого (конечного) числа букв. Назовем каждую конечную последовательность символов из этого алфавита (A=a₁, a₂,… ,a_n) словом, а число n — длиной этого слова.

Пусть задан также другой алфавит. Аналогично, обозначим слово в этом алфавите как B.

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

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

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

a₁ <-> B₁

a₂ <-> B₂

…

a_n <-> B_n

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

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

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

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

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

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

Итак, мы разобрались с основными определениями. Так как же происходит само кодирование без памяти?

Оно происходит в три этапа.

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

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

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

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

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

1. Все буквы входного алфавита упорядочиваются в порядке убывания вероятностей. Все слова из алфавита выходного потока (то есть то, чем мы будем кодировать) изначально считаются пустыми (напомню, что алфавит выходного потока состоит только из символов {0,1}).
2. Два символа a_j-1 и a_j входного потока, имеющие наименьшие вероятности появления, объединяются в один «псевдосимвол» с вероятностью p равной сумме вероятностей входящих в него символов. Затем мы дописываем 0 в начало слова B_j-1, и 1 в начало слова B_j, которые будут впоследствии являться кодами символов a_j-1 и a_j соответственно.
3. Удаляем эти символы из алфавита исходного сообщения, но добавляем в этот алфавит сформированный псевдосимвол (естественно, он должен быть вставлен в алфавит на нужное место, с учетом его вероятности).

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

Для лучшей иллюстрации, рассмотрим небольшой пример.

Пусть у нас есть алфавит, состоящий из всего четырех символов — { a₁, a₂, a₃, a₄}. Предположим также, что вероятности появления этих символов равны соответственно p₁=0.5; p₂=0.24; p₃=0.15; p₄=0.11 (сумма всех вероятностей, очевидно, равна единице).

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

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

Если сделать иллюстрацию этого процесса, получится примерно следующее:

Как вы видите, при каждом объединении мы присваиваем объединяемым символам коды 0 и 1.

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

a₁ = 0

a₂ = 11

a₃ = 100

a₄ = 101

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

Итак, мы добились того, что самый частый символ кодируется самым коротким кодом, и наоборот.

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

Пусть на входу у нас была строка из 1000 символов, в которой символ a₁ встречался 500 раз, a₂ — 240, a₃ — 150, и a₄ — 110 раз.

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

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

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

Заключение

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

Литература

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

Алгоритмы сжатия изображений / Хабр

Легко подсчитать, что несжатое полноцветное изображение, размером 2000*1000 пикселов будет иметь размер около 6 мегабайт. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений.
Все существующие алгоритмы можно разделить на два больших класса:

• Алгоритмы сжатия без потерь;
• Алгоритмы сжатия с потерями.

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

Алгоритмы сжатия без потерь

Алгоритм RLE

Все алгоритмы серии RLE основаны на очень простой идее: повторяющиеся группы элементов заменяются на пару (количество повторов, повторяющийся элемент). Рассмотрим этот алгоритм на примере последовательности бит. В этой последовательности будут чередовать группы нулей и единиц. Причём в группах зачастую будет более одного элемента. Тогда последовательности 11111 000000 11111111 00 будет соответствовать следующий набор чисел 5 6 8 2. Эти числа обозначают количество повторений (отсчёт начинается с единиц), но эти числа тоже необходимо кодировать. Будем считать, что число повторений лежит в пределах от 0 до 7 (т.е. нам хватит 3 бит для кодирования числа повторов). Тогда рассмотренная выше последовательность кодируется следующей последовательностью чисел 5 6 7 0 1 2. Легко подсчитать, что для кодирования исходной последовательности требуется 21 бит, а в сжатом по методу RLE виде эта последовательность занимает 18 бит.
Хоть этот алгоритм и очень прост, но эффективность его сравнительно низка. Более того, в некоторых случаях применение этого алгоритма приводит не к уменьшению, а к увеличению длины последовательности. Для примера рассмотрим следующую последовательность 111 0000 11111111 00. Соответствующая ей RL-последовательность выглядит так: 3 4 7 0 1 2. Длина исходной последовательности – 17 бит, длина сжатой последовательности – 18 бит.
Этот алгоритм наиболее эффективен для чёрно-белых изображений. Также он часто используется, как один из промежуточных этапов сжатия более сложных алгоритмов.

Словарные алгоритмы

Идея, лежащая в основе словарных алгоритмов, заключается в том, что происходит кодирование цепочек элементов исходной последовательности. При этом кодировании используется специальный словарь, который получается на основе исходной последовательности.
Существует целое семейство словарных алгоритмов, но мы рассмотрим наиболее распространённый алгоритм LZW, названный в честь его разработчиков Лепеля, Зива и Уэлча.
Словарь в этом алгоритме представляет собой таблицу, которая заполняется цепочками кодирования по мере работы алгоритма. При декодировании сжатого кода словарь восстанавливается автоматически, поэтому нет необходимости передавать словарь вместе с сжатым кодом.
Словарь инициализируется всеми одноэлементными цепочками, т.е. первые строки словаря представляют собой алфавит, в котором мы производим кодирование. При сжатии происходит поиск наиболее длинной цепочки уже записанной в словарь. Каждый раз, когда встречается цепочка, ещё не записанная в словарь, она добавляется туда, при этом выводится сжатый код, соответствующий уже записанной в словаре цепочки. В теории на размер словаря не накладывается никаких ограничений, но на практике есть смысл этот размер ограничивать, так как со временем начинаются встречаться цепочки, которые больше в тексте не встречаются. Кроме того, при увеличении размеры таблицы вдвое мы должны выделять лишний бит для хранения сжатых кодов. Для того чтобы не допускать таких ситуаций, вводится специальный код, символизирующий инициализацию таблицы всеми одноэлементными цепочками.
Рассмотрим пример сжатия алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Предположим, что словарь будет вмещать 32 позиции, а значит, каждый его код будет занимать 5 бит. Изначально словарь заполнен следующим образом:

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

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

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

Строку, добавленную в словарь на i-ом шаге мы можем полностью определить только на i+1. Очевидно, что i-ая строка должна заканчиваться на первый символ i+1 строки. Т.о. мы только что разобрались, как можно восстанавливать словарь. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c — это один символ, а S — строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.

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

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

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

Алгоритм Хаффмана позволяет строить префиксные коды. Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну соответствует 0 в коде, а к правому сыну – 1. Если мы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева.
Опишем алгоритм построения дерева Хаффмана и получения кодов Хаффмана.

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа
2. Выбираются два свободных узла дерева с наименьшими весами
3. Создается их родитель с весом, равным их суммарному весу
4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

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

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

Алгоритмы арифметического кодирования кодируют цепочки элементов в дробь. При этом учитывается распределение частот элементов. На данный момент алгоритмы арифметического кодирования защищены патентами, поэтому мы рассмотрим только основную идею.
Пусть наш алфавит состоит из N символов a1,…,aN, а частоты их появления p1,…,pN соответственно. Разобьем полуинтервал [0;1) на N непересекающихся полуинтервалов. Каждый полуинтервал соответствует элементам ai, при этом длина полуинтервала пропорциональна частоте pi.
Кодирующая дробь строится следующим образом: строится система вложенных интервалов так, чтобы каждый последующий полуинтервал занимал в предыдущем место, соответствующее положению элемента в исходном разбиении. После того, как все интервалы вложены друг в друга можно взять любое число из получившегося полуинтервала. Запись этого числа в двоичном коде и будет представлять собой сжатый код.
Декодирование – расшифровка дроби по известному распределению вероятностей. Очевидно, что для декодирования необходимо хранить таблицу частот.
Арифметическое кодирование чрезвычайно эффективно. Коды, получаемые с его помощью, приближаются к теоретическому пределу. Это позволяет утверждать, что по мере истечения сроков патентов, арифметическое кодирование будет становиться всё более и более популярным.

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

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

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

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

Перевод в цветовое пространство YCbCr

В цветовой модели YCbCr мы представляем изображение в виде яркостной компоненты (Y) и двух цветоразностных компонент (Cb,Cr). Человеческий глаз более восприимчив к яркости, а не к цвету, поэтому алгоритм JPEG вносит по возможности минимальные изменения в яркостную компоненту (Y), а в цветоразностные компоненты могут вноситься значительные изменения. Перевод осуществляется по следующей формуле:

Выбор Kr и Kb зависит от оборудования. Обычно берётся Kb=0.114;Kr=0.299. В последнее время также используется Kb=0.0722;Kr=0.2126, что лучше отражает характеристики современных устройств отображения.

Субдискретизация компонент цветности

После перевода в цветовое пространство YCbCr выполняется дискретизация. Возможен один из трёх способов дискретизации:
4

• :4:4 – отсутствует субдискретизация;
• 4:2:2 – компоненты цветности меняются через одну по горизонтали;
• 4:2:0 – компоненты цветности меняются через одну строку по горизонтали, при этом по вертикали они меняются через строку.

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

Дискретное косинусное преобразование

Изображение разбивается на компоненты 8*8 пикселов, к каждой компоненте применятся ДКП. Это приводит к уплотнению энергии в коде. Преобразования применяются к компонентам независимо.

Квантование

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

Зигзаг-обход матриц

Зигзаг-обход матрицы – это специальное направление обхода, представленное на рисунке:

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

RLE- кодировние

Используется особый вид RLE-кодирования: выводятся пары чисел, причём первое число в паре кодирует количество нулей, а второе – значение после последовательности нулей. Т.е. код для последовательности 0 0 15 42 0 0 0 44 будет следующим (2;15)(0;42)(3;44).

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

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

Фрактальное сжатие

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

1. Разделение изображения на неперекрывающиеся области (домены). Набор доменов должен покрывать всё изображение полностью.
2. Выбор ранговых областей. Ранговые области могут перекрываться и не покрывать целиком всё изображение.
3. Фрактальное преобразование: для каждого домена подбирается такая ранговая область, которая после аффинного преобразования наиболее точно аппроксимирует домен.
4. Сжатие и сохранение параметров аффинного преобразования. В файл записывается информация о расположении доменов и ранговых областей, а также сжатые коэффициенты аффинных преобразований.

Этапы восстановления изображения:

1. Создание двух изображений одинакового размера A и B. Размер и содержание областей не имеют значения.
2. Изображение B делится на домены так же, как и на первой стадии процесса сжатия. Для каждого домена области B проводится соответствующее аффинное преобразование ранговых областей изображения A, описанное коэффициентами из сжатого файла. Результат помещается в область B. После преобразования получается совершенно новое изображение.
3. Преобразование данных из области B в область A. Этот шаг повторяет шаг 3, только изображения A и B поменялись местами.
4. Шаги 3 и 4 повторяются до тех пор, пока изображения A и B не станут неразличимыми.

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

RLE и LZ77 / Хабр

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

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

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

Алгоритм RLE является, наверное, самым простейшим из всех: суть его заключается в кодировании повторов. Другими словами, мы берём последовательности одинаковых элементов, и «схлопываем» их в пары «количество/значение». Например, строка вида «AAAAAAAABCCCC» может быть преобразована в запись вроде «8×A, B, 4×C». Это, в общем-то, всё, что надо знать об алгоритме.

Пример реализации

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

unsigned char data[] = {
	0,   0,   0,   0,   0,   0,   4,   2,   0,   4,   4,   4,   4,   4,   4,   4,
	80,  80,  80,  80,  0,   2,   2,   2,   2,   255, 255, 255, 255, 255, 0,   0
};

Для многих гораздо привычней будет видеть эти данные в виде hex-дампа:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF FF 00 00

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

Закодируем наши данные, используя свежеполученные знания: 6×0, 4, 2, 0, 7×4, 4×80, 0, 4×2, 5×255, 2×0.

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

Есть как минимум два выхода из этой ситуации:

1. В качестве индикатора сжатой цепочки выделить одно значение байта, а в случае коллизии с реальными данными экранировать их. Например, если использовать в «служебных» целях значение 255, то при встрече этого значения во входных данных мы вынуждены будем писать «255, 255» и после индикатора использовать максимум 254.
2. Структурировать закодированные данные, указывая количество не только для повторяемых, но и последующих далее одиночных элементов. Тогда мы будем заранее знать, где какие данные.

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

Итак, теперь у нас имеется два вида последовательностей: цепочки одиночных элементов (вроде «4, 2, 0») и цепочки одинаковых элементов (вроде «0, 0, 0, 0, 0, 0»). Выделим в «служебных» байтах один бит под тип последовательности: 0 — одиночные элементы, 1 — одинаковые. Возьмём для этого, скажем, старший бит байта.

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

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

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

Второе, что можно заметить — не бывает последовательностей одинаковых элементов единичной длины. Поэтому, от значения длины таких последовательностей при кодировании мы будем отнимать ещё единичку, увеличив тем самым их максимальную длину до 129 (максимальная длина цепочки одиночных элементов по-прежнему равна 128). Т.е. цепочки одинаковых элементов у нас могут иметь длину от 2 до 129.

Закодируем наши данные снова, но теперь уже и в понятном для компьютера виде. Будем записывать служебные байты как [T|L], где T — тип последовательности, а L — длина. Будем сразу учитывать, что длины мы записываем в изменённом виде: при T=0 отнимаем от L единицу, при T=1 — двойку.

[1|4], 0, [0|2], 4, 2, 0, [1|5], 4, [1|2], 80, [0|0], 0, [1|2], 2, [1|3], 255, [1|0], 0

Попробуем декодировать наш результат:

• [1|4]. T=1, значит следующий байт будет повторяться L+2 (4+2) раз: 0, 0, 0, 0, 0, 0.
• [0|2]. T=0, значит просто читаем L+1 (2+1) байт: 4, 2, 0.
• [1|5]. T=1, повторяем следующий байт 5+2 раз: 4, 4, 4, 4, 4, 4, 4.
• [1|2]. T=1, повторяем следующий байт 2+2 раз: 80, 80, 80, 80.
• [0|0]. T=0, читаем 0+1 байт: 0.
• [1|2]. T=1, повторяем байт 2+2 раз: 2, 2, 2, 2.
• [1|3]. T=1, повторяем байт 3+2 раз: 255, 255, 255, 255, 255.
• [1|0]. T=1, повторяем байт 0+2 раз: 0, 0.

А теперь последний шаг: сохраним полученный результат как массив байт. Например, пара [1|4], упакованная в байт, будет выглядеть вот так:

В итоге получаем следующее:

0000: 84 00 02 04 02 00 85 04 82 80 00 00 82 02 83 FF

0010: 80 00

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

Возможные улучшения

Эффективность алгоритма зависит не только от собственно алгоритма, но и от способа его реализации. Поэтому, для разных данных можно разрабатывать разные вариации кодирования и представления закодированных данных. Например, при кодировании изображений можно сделать цепочки переменной длины: выделить один бит под индикацию длинной цепочки, и если он выставлен в единицу, то хранить длину и в следующем байте тоже. Так мы жертвуем длиной коротких цепочек (65 элементов вместо 129), но зато даём возможность всего тремя байтами закодировать цепочки длиною до 16385 элементов (2¹⁴ + 2)!

Дополнительная эффективность может быть достигнута путём использования эвристических методов кодирования. Например, закодируем нашим способом следующую цепочку: «ABBA». Мы получим «[0|0], A, [1|0], B, [0|0], A» — т.е. 4 байта мы превратили в 6, раздули исходные данные аж в полтора раза! И чем больше таких коротких чередующихся разнотипных последовательностей, тем больше избыточных данных. Если это учесть, то можно было бы закодировать результат как «[0|3], A, B, B, A» — мы бы потратили всего один лишний байт.

LZ77 — один из наиболее простых и известных алгоритмов в семействе LZ. Назван так в честь своих создателей: Абрахама Лемпеля (Abraham Lempel) и Якоба Зива (Jacob Ziv). Цифры 77 в названии означают 1977 год, в котором была опубликована статья с описанием этого алгоритма.

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

Как и остальные алгоритмы этого семейства семейства, LZ77 использует словарь, в котором хранятся встречаемые ранее последовательности. Для этого он применяет принцип т.н. «скользящего окна»: области, всегда находящейся перед текущей позицией кодирования, в рамках которой мы можем адресовать ссылки. Это окно и является динамическим словарём для данного алгоритма — каждому элементу в нём соответствует два атрибута: позиция в окне и длина. Хотя в физическом смысле это просто участок памяти, который мы уже закодировали.

Пример реализации

Попробуем теперь что-нибудь закодировать. Сгенерируем для этого какую-нибудь подходящую строку (заранее извиняюсь за её нелепость):

«The compression and the decompression leave an impression. Hahahahaha!»

Вот как она будет выглядеть в памяти (кодировка ANSI):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20   The compression
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65   and the decompre
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69   ssion leave an i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68   mpression. Hahah
0040: 61 68 61 68 61 21                                 ahaha!

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

«The compression and t[he ]de[compression ]leave[ an] i[mpression]. Hah[ahahaha]!»

Для пущей наглядности посмотрим на схему, где видны соответствия повторяемых последовательностей и их первых вхождений:

Пожалуй, единственным неясным моментом здесь будет последовательность «Hahahahaha!», ведь цепочке символов «ahahaha» соответствует короткая цепочка «ah». Но здесь нет ничего необычного, мы использовали кое-какой приём, позволяющий алгоритму иногда работать как описанный ранее RLE.

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

С этим разобрались. Теперь заменим найденные повторы на ссылки в словарь. Будем записывать ссылку в формате [P|L], где P — позиция первого вхождения цепочки в строке, L — её длина.

«The compression and t[22|3]de[5|12]leave[16|3] i[8|7]. Hah[61|7]!»

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

«The compression and t[20|3]de[22|12]leave[28|3] i[42|7]. Hah[2|7]!»

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

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

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

По опыту с RLE мы знаем, что не всякие значения могут быть использованы. Очевидно, что ссылка может иметь минимальное значение 1, поэтому, чтобы адресовать назад в диапазоне 1..4096, мы должны при кодировании отнимать от ссылки единицу, а при декодировании прибавлять обратно. То же самое с длинами последовательностей: вместо 0..15 будем использовать диапазон 2..17, поскольку с нулевыми длинами мы не работаем, а отдельные символы последовательностями не являются.

Итак, представим наш закодированный текст с учётом этих поправок:

«The compression and t[19|1]de[21|10]leave[27|1] i[41|5]. Hah[1|5]!»

Теперь, опять же, нам надо как-то отделить сжатые цепочки от остальных данных. Самый распространённый способ — снова использовать структуру и прямо указывать, где сжатые данные, а где нет. Для этого мы разделим закодированные данные на группы по восемь элементов (символов или ссылок), а перед каждой из таких групп будем вставлять байт, где каждый бит соответствует типу элемента: 0 для символа и 1 для ссылки.

Разделяем на группы:

• «The comp»
• «ression »
• «and t[19|1]de»
• «[21|10]leave[27|1] »
• «i[41|5]. Hah[2|5]»
• «!»

Компонуем группы:

«{0,0,0,0,0,0,0,0}The comp{0,0,0,0,0,0,0,0}ression {0,0,0,0,0,1,0,0}and t[19|1]de{1,0,0,0,0,0,1,0}[21|10]leave[27|1] {0,1,0,0,0,0,0,1}i[41|5]. Hah[1|5]{0}!»

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

Теперь нам остаётся только сгруппировать результат в массив байтов. Условимся, что мы используем биты и байты в порядке от старшего к младшему. Посмотрим, как пакуются в байты ссылки на примере [19|1]:

В итоге наш сжатый поток будет выглядеть так:

0000: 00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f   #The comp#ressio

0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c   n #and t##de###l

0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68   eave## #i##. Hah

0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00   ###!

Возможные улучшения

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

«The long goooooong. The loooooower bound.»

Найдём последовательности только для слова «loooooower»:

«The long goooooong. The [lo][ooooo]wer bound.»

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

«The long goooooong. The l[oooooo]wer bound.»

Тогда мы потратили бы на один байт меньше.

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

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

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

Облегченный алгоритм сжатия (де) для встроенного использования

Переполнение стека

1. Около

2. Продукты

3. Для команд

1. Переполнение стека
   Общественные вопросы и ответы

2. Переполнение стека для команд
   Где разработчики и технологи делятся частными знаниями с коллегами

3. Вакансии
   Программирование и связанные с ним технические возможности карьерного роста

4. Талант
   Нанимайте технических специалистов и создавайте свой бренд работодателя

5. Реклама
   Обратитесь к разработчикам и технологам со всего мира

6. О компании

.

Кто-нибудь может предложить алгоритм двоичного сжатия?

Переполнение стека

1. Около

2. Продукты

3. Для команд

1. Переполнение стека
   Общественные вопросы и ответы

2. Переполнение стека для команд
   Где разработчики и технологи делятся частными знаниями с коллегами

3. Вакансии
   Программирование и связанные с ним технические возможности карьерного роста

4. Талант
   Нанимайте технических специалистов и создавайте свой бренд работодателя

5. Реклама
   Обратитесь к разработчикам и технологам со всего мира

6. О компании

.