Алгоритмы обратимых методов.

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

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

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

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

Пример. Допустим, входной текст состоит только из десятичной записи целых чисел и знаков «минус», разделенных пробелами (например, «280 - 1296 48 40 365 - 159 13 777»). Множество символов, встречающихся в таком тексте, состоит всего из 12 символов (цифры от «0» до «9», знак «-» (минус) и пробел). Для кодирования такого количества символов достаточно всего четырех бит, целого байта для этого много. Если упаковать коды данных символов в 4 бита (например, так: «0» как «0000», «1» как «0001»,... «9» как «1001», «-» как «1110», пробел как «1111»), то можно будет кодировать по два символа входного текста одним байтом в выходном массиве. В результате получим двукратное сжатие данных. Формат записи чисел, при котором число записывается в десятичной системе, а цифры числа кодируются 4-битовыми кодами, называется BCD-форматом (Binary Coded Decimal, или двоично-десятичная запись). BCD-формат нередко используется в программировании для хранения целых чисел, например в базах данных.

Пример. Входной текст «КОЛ_ОКОЛО_КОЛОКОЛА» содержит всего 5 различных символов («К», «О», «Л», «А» и «_»), следовательно, каждый символ может быть закодирован тремя битами. Всего в исходном тексте 18 символов, так что потребуется 18 × 3 = 54 бита. Округлив это значение с избытком до целого числа байт, получим размер сжатого массива — всего 7 байт. Коэффициент сжатия равен 18/7 = 2,(571428) ≈ 2,6.

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

• номер байта, в котором начинается код символа, вычисляется так: L = [M-N/8];

• номер первого бита кода (в пределах этого байта) К равен остатку от деления M-N на 8.

Метод упаковки дает хорошие результаты, только если множество используемых символов невелико. Например, если в тексте используются только прописные русские буквы и знаки препинания, то текст может быть сжат всего на 25%: 33 русские буквы плюс пробел и знаки препинания — итого около 40 символов. Для их кодирования достаточно 6 бит. При упаковке текст уменьшится до 3/4 от первоначального объема.

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

Улучшения степени сжатия можно достичь, кодируя часто встречающиеся символы короткими кодами, а редко встречающиеся — более длинными. Именно такова идея метода, опубликованного Д. Хаффманом (Huffman) в 1952 г.

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

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

Вычисление частот встречаемости — тривиальная задача. Разберем построение дерева кодирования Хаффмана.

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

3. Создается их узел-«родитель» с весом, равным сумме их весов, он соединяется с «детьми» дугами.

4. Одной дуге, выходящей из «родителя», ставится в соответствие бит 1, другой — бит 0.

5. «Родитель» добавляется в список свободных узлов, а двое его «детей» удаляются из этого списка.

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

Пример. Построение дерева Хаффмана и префиксных кодов для текста «KOJI_OKOJIO_KOJIOKOJIA»:

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

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

После того как коды символов построены, остается сгенерировать сжатый массив данных, для чего надо снова прочесть входные данные и каждый символ заменить на соответствующий код. В нашем случае непосредственно код текста будет занимать 39 бит, или 5 байт. Коэффициент сжатия равен 18/5 = 3,6. Для восстановления сжатых данных необходимо снова воспользоваться деревом Хаффмана, так как код каждого символа представляет собой путь в дереве Хаффмана от вершины до конечного узда дерева, соответствующего данному символу. Общая схема процесса восстановления такова: специальный маркер устанавливается в вершину дерева Хаффмана, и сжатый массив данных читается побитово. Если читаемый бит равен О, то маркер перемещается из вершины по верхнему ребру, если 1, то по нижнему. Затем читается следующий бит, и маркер снова перемещается, и т. д., пока маркер не попадет в один из конечных узлов дерева. В восстанавливаемый массив записывается символ, которому соответствует этот конечный узел, маркер снова помещается в вершину дерева, и процесс повторяется.

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

В основу алгоритмов RLE (англ. Run-Length Encoding — кодирование путем учета числа повторений) положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой: повторяющимся фрагментом и коэффициентом повторения.

Рассмотрим идею сжатия данных по методу RLE (это не метод, а идея):

Ограничения – длина обрабатываемого фрагмента не должна превосходить 127 байтов.

Пример. Надо упаковать методом RLE следующую последовательность

Таким образом, 12 байт упаковали в 8 байт, и значит, коэффициент сжатия равен 2/3, т.е. 66 процентов.

Различные реализации данного метода используются в графических файлах форматов PCX, BMP, при факсимильной передаче информации. Для текстовой информации метод RLE неэффективен.

В конце 70-х годов прошлого века израильские ученые Яков Зив и Абрахам Лемпель предложили алгоритмы сжатия LZ77 и LZ78. Оригинальность алгоритмов состоит в том, что сжимаются здесь не только относительно буквы но и слова.

Общая схема алгоритма LZ77 такова (это не точное описание алгоритма):

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

• для цепочки первых байтов непрочитанной части ищется наиболее длинное совпадение в прочитанной части. Если совпадение найдено, то составляется комбинация {смещение, длина}, где смещение указывает, на сколько байтов надо сместиться назад от текущей позиции, чтобы найти совпадение, а длина — это длина совпадения;

• если запись комбинации {смещение, длина} короче совпадения, то она записывается в выходной массив, а текущая позиция перемещается вперед (на длину совпадающей части);

• если совпадение не обнаружено или оно короче записи комбинации {смещение, длина}, то в выходной массив копируется текущий байт, текущая позиция перемещается вперед на 1, и анализ повторяется.

Пример. Фраза КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ зако- дируется алгоритмом LZ77 как КО ЛО(-4,3)_(- 5,4)0_(-14,7)ЬНИ.

Общая схема алгоритма LZ78 такова (это не точное описание алгоритма):

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

• для цепочки первых байтов непрочитанной части ищется наиболее длинное совпадение в словаре. Код совпадения записывается в выходной массив, туда же заносится первый несовпавший символ, и текущая позиция перемещается вперед на длину совпадения + 1;

• в словарь добавляется новое слово: «совпадение» + + «несовпавший символ», и процесс повторяется до тех пор, пока не будет сжат весь входной массив.

Алгоритмы Лемпеля - Зива тем лучше сжимают текст, чем больше размер входного массива. Характерной особенностью обратных алгоритмов LZ77 и LZ78 является то, что, кроме самих сжатых данных, никакой дополнительной информации им не требуется! Начав работать, эти алгоритмы по уже распакованной части восстанавливают информацию, необходимую для распаковки следующих частей сжатых данных. Для сравнения: в алгоритме Хаффмана вместе со сжатыми данными требуется сохранять дерево Хаффмана, иначе распаковка будет невозможна.

Поучительна история развития алгоритмов Лемпеля - Зива. Зив и Лемпель придумали плодотворные идеи сжатия, построили алгоритмы и провели теоретическое исследование их эффективности. Но поскольку опубликованные алгоритмы были очень неэффективно реализованы (т. е. запрограммированы), долгое время они не использовались на практике. Только спустя 6 лет, в 1984 году Терри Велч (Terry Welch) сумел существенно улучшить алгоритм LZ78. Эта модификация алгоритма получила название LZW, она широко используется в программах сжатия данных. Алгоритм LZ77 ждал своего часа целых десять лет — только в 1987 году появилась его высокоэффективная версия, которая работала в сотни (!) раз быстрее оригинального алгоритма. В настоящее время существует около полусотни модификаций обоих алгоритмов. Обобщенно все они называются методами сжатия со словарем. Эти алгоритмы оказались настолько быстры и эффективны, что сейчас занимают лидирующее место среди используемых на практике алгоритмов сжатия.

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: