Самый эффективный способ сжатия файлов

Выбираем лучший архиватор для сжатия файлов и распаковки архивов

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

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

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

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

Замечания по тестированию

• В испытании использовались настройки по умолчанию, потому что большинство пользователей используют стандартные настройки. Единственное изменение, которое могло вноситься — это переключение на формат ZIP, если по умолчанию предлагался другой тип архива. Вы можете добиться более высокой производительности, если измените размер слова и словаря, уровень сжатия или количество потоков ЦПУ.
• Тестирование сжатия выполнялось два раза для каждой программы: один раз с настройками по умолчанию и один раз с максимально возможным уровнем сжатия.
• Платные программы WinRAR и WinZIP также принимали участие в тестировании.
• WinZip по умолчанию настроен на максимальное сжатие при выборе формата ZIP.

Протестированные архиваторы

Тестовые образцы

• Тест на сжатие №1: папка с 11 вложенными папками и 100 файлами, общим размером 949 мегабайт.
• Тест на сжатие №2: 180 файлов, общим размером 3,46 гигабайт. Среди тестовых файлов были документы, изображения, видеофайлы и файлы других типов.
• Тест на разархивацию №1: архив ZIP размером 1,36 гигабайт.
• Тест на разархивацию №2: 10 ZIP архивов, размером от 13 мегабайт до 1,36 гигабайт. Всего содержали более 20000 файлов, общим размером 4,09 гигабайт.

Результаты: сжатие

Архиватор	Файл #1		Файл #1 Max		Файл #2		Файл #2 Max
Время	Размер	Время	Размер	Время	Размер	Время	Размер
7-Zip	19 с	108002KB	101 с	106781KB	47 с	3555024KB	473 с	3550401KB
Bandizip	5 с	111813KB	11 с	110791KB	45 с	3554068KB	46 с	3553130KB
PeaZip	21 с	108002KB	101 с	106781KB	51 с	3555024KB	484 с	3550401KB
WinRAR	13 с	111438KB	23 с	110978KB	93 с	3551997KB	94 с	3551604KB
WinZip	39 с	107234KB	116 с	3551667KB

Результаты: разархивация

Архиватор	Файл #1		Файл #2
Время	Время
7-Zip	12 с	70 с
Bandizip	8 с	117 с
PeaZip	12 с	69 с
WinRAR	13 с	94 с
WinZip	12 с	480 с

Анализ и выводы

Некоторые результаты были неожиданными. Bandizip хорошо показал себя во всех задачах сжатия. Программа оказалась лидером во всех тестах и часто опережала ближайшего преследователя с огромным отрывом. Создание первого архива с помощью Bandizip заняло всего 5 и 11 секунд соответственно, в то время как WinRAR выполнил эти же операции за 13 и 23 секунды.

Bandizip быстрее всех справился со вторым тестом на сжатие. Программе понадобилось 45 и 46 секунд для создания гигабайтного архива со стандартным и максимальным уровнем сжатия соответственно. 7-Zip также неплохо справился с тестом на сжатие со стандартными настройками и лишь 2 секунды уступил Bandizip. При переключении на максимальное сжатие, результаты были гораздо хуже — 7-Zip потребовалось в 10 раз больше времени для создания архива, чем Bandizip.

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

В тесте на распаковку готовых архивов программы были очень близки по результатам. Bandizip показал наилучшие результаты в первом тесте — для извлечения первого тестового архива потребовалось всего 8 секунд. Второе место разделяют 7-Zip, PeaZip, и WinZIP, которые выполнили эту задачу за 12 секунд. Третье место досталось WinRAR, который выполнил разархивацию за 13 секунд.

Во втором испытании на распаковку архивов ситуация заметно изменилась. PeaZip выбился в лидеры с результатом в 69 секунд. Ближайшим преследователем стал 7-Zip — ему потребовалось на секунду больше. Bandizip, который показал хорошие результаты в других испытаниях, на этот раз отработал не лучшим образом — 117 секунд. Замыкает таблицу WinZip с результатом в 480 секунд.

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

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

На основе полученных результатов можно дать следующие рекомендации. Если вам часто приходится создавать архивы, то рассмотрите бесплатную программу Bandizip, которая продемонстрировала высокую эффективность. Если в приоритете размер сжатия, то попробуйте 7-Zip или PeaZip. WinRAR может стать подходящим вариантом, если вы предпочитаете RAR-архивы. Дополнительным бонусом является то, что вы можете использовать PAR инструментарий (MultiPar, QuickPar) для создания файлов восстановления.

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

Какими архиваторами пользуетесь вы? Почему вы выбрали именно их?

Источник

Тест архивов. Какой формат выбрать?

Эта тема будет посвящена сравнению алгоритмов сжатия. Для владельцев Медленного и Лимитного Интернета будет полезно, да и не только им.

Для сжатия использовался ZArchiver 0.9.5 для Android, настройки всех форматов на Ультра. Указаны Размер и Процент от Размера Оригинала. Для 7Z включён LZMA2 (В настройках ZArchiver)

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

Внимание! Много Картинок!

Есть 7 папок, под разные категории

Теперь начнём же сравнение!

1: Образ Windows 3.10

2: Война и мир, FB2

3: Jeanne d’Arc, Rus, PSP

4: 459 игр для NES aka Денди, Rus

5: Исходный код Той Самой Игры — DOOM

6: Прошивка Navitel C500

7: Субтитры для Наруто: Ураганные Хроники! Кто помнит Акацуки и Мадару?

Вот и комментарии

Категория 1: Образ Windows 3.10

Оригинал: 11.25 МБ

Форматы типа «Как у всех» (Далее будет указан как «Тип 1»)

ZIP: 8.89 МБ / 79% // Слабовато.

7Z: 8.05 МБ / 71% // Что и следовало ожидать от 7Z.

Форматы типа «Найди их — тот ещё квест». Кроме TAR.XZ. (Далее будет указан как «Тип 2»)

TAR.LZ4: 9.48 МБ / 84% // Слился от ZIP. Что ещё ожидать от формата, заточенного на скорость. Хотя.

TAR.ZST: 8.38 МБ / 74% // Очень быстрое сжатие и распаковка, размеры в основном между ZIP и 7Z, хотя возможны варианты. Известен как ZStandard или ZSTD

TAR.XZ: 7.70 МБ / 68% // Тот случай, когда 7Z — не самый крутой в области сжатия!

Категория 2: Война и мир, в формате FB2

Оригинал: 9.07 МБ

ZIP: 3.37 МБ / 37% // Перфекционисты могут быть довольны — 37 же!

7Z: 2.96 МБ / 32% // Классика жанра

TAR.LZ4: 4.57 МБ / 50% // LZ4 снова слился.

TAR.ZST: 3.31 МБ / 36% // И снова победа над ZIP!

TAR.XZ: 2.96 МБ / 32% // Тут 7Z и XZ равны.

Категория 3: Игра для PSP — Jeanne d’Arc, русская версия!

Оригинал: 1.16 ГБ

ZIP: 640.14 МБ / 53% // Почти в два раза. Но всё равно — размеры ого-го!

7Z: 459.80 МБ / 38% // Вот это адекватные размеры!

TAR.LZ4: 701.92 МБ / 59% // Такой архив весит многовато.

TAR.ZST: 601.44 МБ / 50% // Архив меньше на

40 МБ, но скорость распаковки. Вы удивитесь, когда начнёте тесты на файлах больше 1 ГБ!

TAR.XZ: 459.80 МБ / 38% // Снова они равны!

Категория 4: Сборник из 459 игр для NES / Денди на русском языке!

Оригинал: 76.44 МБ

ZIP: 38.30 МБ / 50% // Чётко и поровну!

7Z: 34.82 МБ / 45% // 5 Процентов разницы для кого-то могут значит.

TAR.LZ4: 46.15 МБ / 60% // Как всегда.

TAR.ZST: 33.80 МБ / 44% // 7Z гнут даже скоростные форматы!

TAR.XZ: 27.83 МБ / 36% // 7Z уложили на лопатки!

Категория 5: Исходный код Той Самой Игры — DOOM!

Оригинал: 1.36 МБ

ZIP: 440.01 КБ / 31% // Классике всегда будет место!

7Z: 400.31 КБ / 28% // Немного лучше.

TAR.LZ4: 492.36 КБ / 35% // Не удивляйтесь!

TAR.ZST: 323.63 КБ / 23% // И снова 7Z пои. Победили, вот!

TAR.XZ: 273.11 КБ / 19% // Fatality!

Категория 6: Прошивка Navitel C500

Оригинал: 64.93 МБ

ZIP: 47.39 МБ / 72% // Норм

7Z: 40.56 МБ / 62% //Вот так лучше!

TAR.LZ4: 51.56 МБ / 79% // ОК.

TAR.ZST: 44.89 МБ / 69% // Скорость — ваше всё! (Соник согласится)

TAR.XZ: 40.51 МБ / 62% // Тут разница некритична.

Категория 7: Субтитры для Наруто: Ураганные Хроники! Кто помнит Акацуки, Мадару?

Оригинал: 134.00 МБ

ZIP: 32.67 МБ / 24% // Тексты всегда сжимаются на ура!

7Z: 28.46 МБ / 21% // Кто-то сэкономит траффик.

TAR.LZ4: 39.68 МБ / 29% // Даже тексты. Сжимает хуже всего!

TAR.ZST: 19.53 МБ / 14% // 7Z нагибают аж от души!

TAR.XZ: 11.68 МБ / 8% // Ну. у 7Z нет шансов!

Вывод

ZIP средний во всём, кроме сжатия — тут он занимает предпоследнее место!

7Z имеет высокое сжатие и низкую скорость сжатия / распаковки, но иногда его нагибают скоростные форматы, не говоря уже об XZ!

LZ4 до появления ZStandard мог быть пригоден благодаря скорости сжатия / распаковки, но после появления ZStandart его стоит использовать разве то для совместимости.

ZStandard имеет сжатие в основном между ZIP и 7Z, ОЧЕНЬ высокую скорость сжатия / распаковки, а иногда он по сжатию превосходит 7Z!

XZ имеет самое лучшее сжатие и низкую скорость сжатия / распаковки. Шикарный вариант для медленного и лимитного интернета.

Делайте свои выводы.

Спасибо за чтение!

Upd: сделал дополнительные тесты и узнал, что:

1: LZ4 иногда сжимает ЛУЧШЕ, чем ZIP, притом НАМНОГО быстрее даже на ультра настройках!

2: По скорости сжатия / распаковки 1 место занимает LZ4 (Скорость пригодна для Оперативной Памяти), а второе — ZStandard. Учитивая то, что формат создал автор LZ4 для замены алгоритмов на основе Deflate (ZIP, GZIP и т.д.), по скорости и степени сжатия он круче ZIP по всём! Игра для PSP, которую ZIP на Ультрах сжимает десятки минут, ZStandard на тех же настройках делает это за несколько секунд, давая меньший размер! И да, образ Windows XP SP3 особо не сжимается — я пытался. Ещё раз спасибо за чтение!

Источник

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

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

Кодирование длин серий (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’)»

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

Модификация алгоритма 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. И, наконец, кодировщик Хаффмана завершает процесс.

Источник