Коэффициент сжатия может быть как постоянным (некоторые алгоритмы сжатия звука, изображения и т. п., например А-закон, μ-закон, ADPCM, усечённое блочное кодирование), так и переменным. Во втором случае он может быть определён либо для каждого конкретного сообщения, либо оценён по некоторым критериям:

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

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

Допустимость потерь

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

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

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

Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых они реализованы:

• оперативной памяти (под промежуточные данные);
• постоянной памяти (под код программы и константы);
• процессорного времени.

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

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

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

Компрессия данных

Компрессия (сжатие) данных применяется для сокращения времени их передачи по сети. Так как на компрессию и декомпрессию тратится дополнительное время, то выгоды от сокращения времени на передачу ощутимы только на низкоскоростных каналах связи (где скорости не более 64 Кбит/с).

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

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

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

Объем продаж программных продуктов сжатия данных до последнего времени значительно отставал от объема продаж аппаратных средств, однако, по мере широкого распространения таких популярных программ, как, например, DoubleSpace, Stacker, а также утилит серии PkZip, Arc, Arj и др., на этом сегменте рынка начался настоящий бум. В связи с этим аналитики предсказывают существенный рост объемов продаж программных средств сжатия данных.

В то же время, программные продукты сжатия данных используются в основном для экономии места на магнитных носителях и не пригодны для работы в сети в режиме on-line. Такое программное обеспечение используется в режиме off-line — по кабельным линиям передаются уже предварительно сжатые данные.

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

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

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

Для сжатия аудиосигнала, например, компания Gandalf разработала высокоэффективный алгоритм CELP (Codebook Excited Linear Prediction), являющийся комбинацией волновых (waveform) методов и методов кодирования источника (source coding). Суть волновых методов состоит в цифровом кодировании амплитуды аналогового сигнала, а кодирование источника заключается в использовании двух типов генераторов звуковых сигналов и меняющегося во времени фильтра. Звуковой сигнал разбивается на блоки, для каждого из которых определяется набор параметров: установки фильтра, амплитуда и т.д. Являясь достаточно эффективным с точки зрения степени сжатия, кодирование источника в то же время обеспечивает худшее качество сигнала по сравнению с волновыми методами. Алгоритм CLEP, объединяя возможности обоих методов, позволяет достичь высокой производительности при сохранении хорошего качества сигнала. В технологии CLEP применяется также таблица образцов звуковых сигналов (codebook), записанных в цифровом виде, которые сравниваются с входящим звуковым сигналом. Наиболее подходящий образец сигнала затем и пересылается на удаленный узел сети.

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

Простым языком о том, как работает сжатие файлов

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

Что такое сжатие?

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

Сжатие с потерями

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

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

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

Чем сильнее вы сжимаете файл, тем заметнее становится снижение качества. Вы, вероятно, замечали такое, слушая некачественную музыку в формате MP3, загруженную на YouTube. Например, сравните музыкальный трек высокого качества с сильно сжатой версией той же песни.

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

При сохранении в формате с потерями, вы зачастую можете установить уровень качества. Например, у многих графических редакторов есть ползунок для выбора качества JPEG от 0 до 100. Экономия на уровне 90 или 80 процентов приводит к небольшому уменьшению размера файла с незначительной визуальной разницей. Но сохранение в плохом качестве или повторное сохранение одного и того же файла в формате с потерями ухудшит его.

Посмотрите на этот пример.

Оригинальное изображение, загруженное с Pixabay в формате JPEG. 874 КБ:

Результат сохранения в формате JPEG с 50-процентным качеством. Выглядит не так уж плохо. Вы можете заметить артефакты по краям коробок только при увеличении. 310 КБ:

Исходное изображение, сохранённое в формате JPEG с 10-процентным качеством. Выглядит ужасно. 100 КБ:

Где используется сжатие с потерями

Как мы уже упоминали, сжатие с потерями отлично подходит для большинства медиафайлов. Это крайне важно для таких компаний как Spotify и Netflix, которые постоянно транслируют большие объёмы информации. Максимальное уменьшение размера файла при сохранении качества делает их работу более эффективной.

Сжатие без потерь

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

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

Это простая иллюстрация того, как осуществить сжатие без потерь. Та же информация сохраняется более эффективным способом. Рассмотрим реальный файл: mmmmmuuuuuuuoooooooooooo. Его можно сжать до гораздо более короткой формы: m5u7o12. Это позволяет использовать 7 символов вместо 24 для представления одних и тех же данных.

Где используется сжатие без потерь

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

Другие распространённые форматы без потерь — PNG для изображений и FLAC для аудио. Форматы видео без потерь встречаются редко, потому что они занимают много места.

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

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

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

Позже вы, возможно, захотите загрузить музыку на телефон или старый MP3-плеер. Здесь не так важно, чтобы музыка была в идеальном качестве, поэтому вы можете конвертировать файлы FLAC в MP3. Это даст вам аудиофайл, который по-прежнему достаточно хорош для прослушивания, но не занимает много места на мобильном устройстве. Качество MP3, преобразованного из FLAC, будет таким же, как если бы вы создали сжатый MP3 с оригинального CD.

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

Проблемы во время сжатия файлов

Бесполезно конвертировать формат с потерями в формат без потерь. Это пустая трата пространства. Скажем, у вас есть MP3-файл весом в 3 МБ. Преобразование его в FLAC может привести к увеличению размера до 30 МБ. Но эти 30 МБ содержат только те звуки, которые имел уже сжатый MP3. Качество звука от этого не улучшится, но объём станет больше.

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

Заключение

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

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

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

Это очень простой алгоритм. Он заменяет серии из двух или более одинаковых символов числом, обозначающим длину серии, за которым идёт сам символ. Полезен для сильно избыточных данных, типа картинок с большим количеством одинаковых пикселей, или в комбинации с алгоритмами типа 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’)»

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

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

DEFLATE

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

DEFLATE64

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

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

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

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

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

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

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

LZRW1

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

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

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

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

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

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

LZMA2

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

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

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

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

Алгоритм 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:

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

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

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

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

Джеймс Сторер, 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. И, наконец, кодировщик Хаффмана завершает процесс.