Алгоритмы Сжатия Данных Без Потерь, Часть 2

Большинство из них объединяют несколько принципов сжатия для создания законченного алгоритма.

Даже хорошие принципы, объединенные вместе, дают лучшие результаты.

Большинство методов используют принцип энтропийного кодирования, но распространены и другие — кодирование по длине и преобразование Берроуза-Уилера.

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

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

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

Пример работы с подходящим массивом данных (& обозначает конец файла)



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

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

Простой ЭK сочетает в себе статистическую модель и сам кодировщик.

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

).

Создает двоичное дерево для представления вероятностей появления каждого символа.

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

Например, путь к «А» — это две ветки влево и одна вправо, ее код будет «110».

Алгоритм не всегда выдает оптимальные коды из-за метода построения дерева снизу вверх.

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

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

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

1. Разбираем ввод, подсчитываем количество повторений символов 2. Определить вероятность появления каждого символа.

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

5. пока очередь состоит из более чем одного символа: — взять два листа из очереди с наименьшими вероятностями — прибавляем 0 к коду первого, 1 к коду второго — создать узел с вероятностью, равной сумме вероятностей двух узлов — первый узел вешаем слева, второй справа — добавляем полученный узел в очередь 6. Последний узел в очереди будет корнем бинарного дерева.

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

Вместо разделения вероятностей на дерево алгоритм преобразует входные данные в одно рациональное число от 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 использует словарь, содержащий тройки данных — смещение, длину пробега и символ расхождения.

Смещение – насколько далеко от начала файла находится фраза.

Длина серии — сколько символов, считая от смещения, принадлежит фразе.

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

Словарь изменяется по мере анализа файла с использованием скользящего окна.

Например, размер окна может составлять 64 МБ, тогда словарь будет содержать данные из последних 64 МБ входных данных.

Например, для ввода «abbadabba» результатом будет «abb(0,1,'d')(0,3,'a')».

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

ЛЗР Модификация алгоритма LZ77, предложенная Майклом Роде в 1981 году.

В отличие от LZ77, он работает за линейное время, но требует больше памяти.

Обычно LZ78 проигрывает в компрессии.

СДУТЬ Изобретенный Филом Кацем в 1993 году, он используется в большинстве современных архиваторов.

Представляет собой комбинацию LZ77 или LZSS с кодировкой Хаффмана.

СДУТЬ64 Запатентованная вариация DEFLATE с увеличением словаря до 64 КБ.

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

не открыт. ЛЗСС Алгоритм Лемпеля-Зива-Сторера-Цимански был представлен в 1982 году.

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

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

ЛЖ Он был разработан в 1987 году и расшифровывается как Лемпель-Зив-Хаффман.

Вариант LZSS, он использует кодирование Хаффмана для сжатия указателей.

Сжимает немного лучше, но заметно медленнее.

ЛЗБ Разработан в 1987 году Тимоти Беллом как вариант LZSS. Как и LZH, LZB уменьшает размер получаемого файла за счет эффективного кодирования указателей.

Это достигается за счет постепенного увеличения размера указателей по мере увеличения размера скользящего окна.

Сжатие выше, чем у ЛЗСС и ЛЖ, но скорость значительно ниже.

РОЛЗ Аббревиатура «Лемпель-Зив с уменьшенным смещением» улучшает алгоритм LZ77 за счет уменьшения смещения, чтобы уменьшить объем данных, необходимых для кодирования пары «смещение-длина».

Впервые он был представлен в 1991 году в алгоритме LZRW4 Росса Уильямса.

Другие варианты: BALZ, QUAD и RZM. Хорошо оптимизированный РОЛЗ достигает почти тех же степеней сжатия, что и ЛЗМА – но популярности он не завоевал.

ЛЗП «Лемпель-Зив с предсказанием».

Вариация РОЛЗ со смещением = 1. Есть несколько вариаций, одни направлены на скорость сжатия, другие на степень.

Алгоритм LZW4 использует арифметическое кодирование для лучшего сжатия.

ЛЗРВ1 Алгоритм Рона Уильямса в 1991 году, где он впервые представил концепцию уменьшения систематической ошибки.

Достигает высокой степени сжатия на приличных скоростях.

Затем Уильямс сделал вариации LZRW1-A, 2, 3, 3-A и 4. ЛЗЖБ Вариант Джеффа Бонвика (отсюда и «JB») 1998 года для использования в файловой системе Solaris Z (ZFS).

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

ЛЗС Lempel-Ziv-Stac, разработанный Stac Electronics в 1994 году для использования в программах сжатия дисков.

Модификация LZ77, которая различает символы и пары смещений длины, а также удаляет следующий встреченный символ.

Очень похоже на ЛЗСС.

ЛЗХ Он был разработан в 1995 году Дж.

Форбсом и Т.

Потаненом для Amiga. Forbes продал алгоритм Microsoft в 1996 году и приступил к работе над ним, в результате чего его улучшенная версия стала использоваться в файлах CAB, CHM, WIM и аватарах Xbox Live. ЛЗО Разработан в 1996 году Маркусом Оберхумером с учетом скорости сжатия и декомпрессии.

Позволяет настраивать уровни сжатия и потребляет очень мало памяти.

Аналог ЛЗСС.

ЛЗМА «Алгоритм цепочки Маркова Лемпеля-Зива» появился в 1998 году в архиваторе 7-zip, который продемонстрировал лучшее сжатие, чем почти все архиваторы.

Алгоритм использует цепочку методов сжатия для достижения наилучшего результата.

Сначала данные анализирует слегка модифицированный LZ77, работающий на битовом уровне (в отличие от обычного байтового метода).

Его вывод подлежит арифметическому кодированию.

Затем могут быть применены другие алгоритмы.

Результат — лучшее сжатие среди всех архиваторов.

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

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

, авторы: Лемпель и Зив.

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

Размер словаря обычно измеряется несколькими мегабайтами.

Различия вариантов этого алгоритма основаны на том, что делать, когда словарь полон.

При разборе файла алгоритм добавляет в словарь каждый новый символ или комбинацию символов.

Для каждого входного символа на выходе создается словарная форма (индекс + неизвестный символ).

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

Данные, на которые указывает индекс, добавляются к последнему символу неизвестной подстроки.

Если текущий символ не найден, индекс устанавливается в 0, указывая, что это один символ в словаре.

Записи образуют связанный список.

Входные данные «abbadabbaabaad» выведут «(0,a)(0,b)(2,a)(0,d)(1,b)(3,a)(6,d)» Входные данные, такие как «abbadabbaabaad», будут генерировать выходные данные «(0,a)(0,b)(2,a)(0,d)(1,b)(3,a)(6,d)».

Вы можете увидеть, как это было получено, в следующем примере:



ЛЗВ Лемпель-Зив-Велч, 1984 г.

Самая популярная версия LZ78, несмотря на запатентованность.

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

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

Используется в GIF, ранних версиях ZIP и других специальных приложениях.

Очень быстрый, но проигрывает по сжатию более новым алгоритмам.

ЛЗК Компрессия Лемпеля-Зива.

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

ЛЗТ Лемпель-Зив-Тишер.

Когда словарь заполнен, он удаляет наименее используемые фразы и заменяет их новыми.

Не приобрел популярности.

ЛЗМВ Виктор Миллер и Марк Вегман, 1984. Действует как ЛЗТ, но связывает не похожие данные в словаре, а две последние фразы.

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

Также непопулярен.

ЛЗАП Джеймс Сторер, 1988 г.

Модификация LZMW. «AP» означает «все префиксы» — вместо сохранения одной фразы на каждой итерации словарь сохраняет каждое изменение.

Например, если последняя фраза была «last», а текущая — «next», то в словаре сохраняются «lastn», «lastne», «lastnex», «lastnext».

ЛЗВЛ Вариант LZW 2006 года, который работает с комбинациями символов, а не с отдельными символами.

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

ЛЗДЖ 1985, Матти Джейкобсон.

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

Когда словарь заполнен, из него удаляются отдельные записи.

Обычно сочетается с арифметическим кодировщиком или адаптивным кодированием Хаффмана.

Вариант PPMd используется в RAR и 7-zip. bzip2 Реализация BWT с открытым исходным кодом.

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

PAQ Мэтт Махони, 2002 г.

, улучшенная PPM(d).

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

В этом методе несколько алгоритмов прогнозирования объединяются для улучшения прогнозирования следующего символа.

На данный момент это один из самых многообещающих алгоритмов.

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

Минусом является низкая скорость из-за необходимости использования нескольких моделей.

Вариант под названием PAQ80 поддерживает 64 бита и показывает серьёзное улучшение скорости работы (используется, в частности, в программе PeaZip для Windows).