Оглавление
Обзор
Сжатие LZW
Распаковка LZW
Советы по программированию
Обзор
Если бы вы взглянули почти на любой файл данных в компьютере, просматривая символ за символом, то наверняка обратили бы внимание на множество повторяющихся элементов. LZW — это метод сжатия данных, который воспользовался этим повторением. Оригинальная версия метода была создана Лемпелем и Зивом в 1978 году (LZ78) и доработана Уэлчем в 1984 году, отсюда и аббревиатура LZW (Lempel, Ziv and Welch). Как и в любом адаптивном/динамическом методе сжатия, идея заключается в том, чтобы (1) начать с исходной модели, (2) читать данные по частям, (3) обновлять модель и кодировать данные по мере продвижения. LZW — алгоритм сжатия на основе "словаря". Это означает, что вместо сведения в таблицу количества символов и построения деревьев (как при кодировании по Хаффману), LZW кодирует данные, обращаясь к словарю. Таким образом, чтобы закодировать подстроку, в выходной файл нужно записать только одно кодовое число, соответствующее индексу этой подстроки в словаре. Хотя LZW часто рассматривается в контексте сжатия текстовых файлов, его можно использовать для любого типа файлов. Однако, как правило, он лучше всего справляется с файлами где есть повторяющиеся подстроки, например, с текстовыми файлами.
Сжатие
LZW начинает со словаря из 256 символов (в случае 8 бит) и использует их в качестве "стандартного" набора символов. Затем он считывает данные по 8 бит за раз (например, 't', 'r' и т.д.) и кодирует их в виде числа, которое представляет собой индекс в словаре. Всякий раз, встречая новую подстроку (скажем, "tr"), он добавляет ее в словарь; каждый раз, когда ему попадается подстрока, которая ранее уже встречалась, он просто считывает новый символ и выполняет его конкатенацию с текущей строкой, чтобы получить новую подстроку. В следующий раз, когда LZW вновь обратится к подстроке, она будет закодирована с помощью одного числа. Обычно для словаря задается максимальное количество записей (скажем, 4096), чтобы процесс не исчерпал память. Таким образом, коды, занимающие место подстрок в данном примере, имеют длину 12 бит (2^12 = 4096). Это необходимо, чтобы коды были длиннее в битах, чем символы (12 против 8 бит), но поскольку вместо большого количества часто встречающихся подстрок будет использоваться только один код, в конечном итоге достигается сжатие.
Вот как это может выглядеть в псевдокоде:
string s;
char ch;
...
s = empty string;
while (there is still data to be read)
{
ch = read a character;
if (dictionary contains s+ch)
{
s = s+ch;
}
else
{
encode s to output file;
add s+ch to dictionary;
s = ch;
}
}
encode s to output file;
Теперь предположим, что наш входной поток, который мы хотим сжать, это "banana_bandana", и при этом используется только начальный словарь:
Index Entry
0 a
1 b
2 d
3 n
4 _ (space)
Этапы кодирования будут выполняться следующим образом:
Вход |
Текущая строка |
Видели это раньше? |
Кодированный выход |
Новая словарная запись/индекс |
b |
b |
да |
ничего |
никакой |
ba |
ba |
нет |
1 |
ba / 5 |
ban |
an |
нет |
1,0 |
an / 6 |
bana |
na |
нет |
1,0,3 |
na / 7 |
banan |
an |
да |
без изменений |
никакой |
banana |
ana |
нет |
1,0,3,6 |
ana / 8 |
banana_ |
a_ |
нет |
1,0,3,6,0 |
a_ / 9 |
banana_b |
_b |
нет |
1,0,3,6,0,4 |
_b / 10 |
banana_ba |
ba |
да |
без изменений |
никакой |
banana_ban |
ban |
нет |
1,0,3,6,0,4,5 |
ban / 11 |
banana_band |
nd |
нет |
1,0,3,6,0,4,5,3 |
nd / 12 |
banana_banda |
da |
нет |
1,0,3,6,0,4,5,3,2 |
da / 13 |
banana_bandan |
an |
да |
без изменений |
никакой |
banana_bandana |
ana |
да |
1,0,3,6,0,4,5,3,2,8 |
никакой |
Обратите внимание, что после считывания последнего символа, "a", должна быть выведена последняя подстрока, "ana".
Распаковка
Процесс декомпрессии (распаковки) для LZW также прост. Кроме того, он имеет преимущество перед статическими методами сжатия, поскольку для алгоритма декодирования не требуется словарь или другая дополнительная информация - в процессе работы словарь, идентичный тому, который был создан во время сжатия, восстанавливается. Программы кодирования и декодирования должны начинаться с одного и того же начального словаря, в данном случае со всех 256 символов ASCII.
Вот как это работает. Декодер LZW сначала считывает индекс (целое число), ищет этот индекс в словаре и выводит подстроку, связанную с этим индексом. Первый символ этой подстроки конкатенируется с текущей рабочей строкой. Эта новая конкатенация добавляется в словарь (подобно тому, как подстроки были добавлены во время сжатия). Затем декодированная строка становится текущей рабочей строкой (текущий индекс, т.е. подстрока, запоминается), и процесс повторяется.
Еще раз, вот как это может выглядеть:
string entry;
char ch;
int prevcode, currcode;
...
prevcode = read in a code;
decode/output prevcode;
while (there is still data to read)
{
currcode = read in a code;
entry = translation of currcode from dictionary;
output entry;
ch = first char of entry;
add ((translation of prevcode)+ch) to dictionary;
prevcode = currcode;
}
Есть исключение, когда алгоритм не работает; это происходит, когда код вызывает индекс, который еще не был введен (например, вызов индекса 31, когда индекс 31 в настоящее время обрабатывается и поэтому его еще нет в словаре). Пример из Sayood поможет проиллюстрировать этот момент. Предположим, у вас есть строка ababababab..... и начальный словарь, состоящий только из a и b с индексами 0 и 1 соответственно. Начинается процесс кодирования:
Вход |
Текущая строка |
Видели это раньше? |
Кодированный выход |
Новая словарная запись/индекс |
a |
a |
да |
ничего |
никакой |
ab |
ab |
нет |
0 |
ab / 2 |
aba |
ba |
нет |
0,1 |
ba / 3 |
abab |
ab |
да |
без изменений |
никакой |
ababa |
aba |
нет |
0,1,2 |
aba / 4 |
ababab |
ab |
да |
без изменений |
никакой |
abababa |
aba |
да |
без изменений |
никакой |
abababab |
abab |
нет |
0,1,2,4 |
abab / 5 |
... |
... |
... |
... |
… |
Итак, кодированный выход начинается с 0,1,2,4,... . Когда мы начинаем пытаться декодировать, возникает проблема (в приведенной ниже таблице следует помнить, что текущая строка — это просто подстрока, которая была декодирована/переведена в последнем проходе цикла. Кроме того, новая словарная запись создается путем конкатенации текущей строки с первым символом нового преобразования словаря):
Кодированный вход |
Преобразование словаря |
Декодированный выход |
Текущая строка |
Новая словарная запись/индекс |
0 |
0 = a |
a |
никакая |
никакая |
0,1 |
1 = b |
ab |
a |
ab / 2 |
0,1,2 |
2 = ab |
abab |
b |
ba / 3 |
0,1,2,4 |
4 = ??? |
abab??? |
ab |
??? |
Как видите, декодер сталкивается с индексом 4, в то время как принадлежащая ему запись в данный момент обрабатывается. Чтобы понять, почему это происходит, взгляните на таблицу кодирования. Сразу же после того, как "aba" (с индексом 4) заносится в словарь, следующей кодируемой подстрокой является "aba" (т.е. следующим кодом, записанным в кодированный выходной файл, будет 4). Таким образом, этот особый сценарий может возникнуть только в том случае, если подстрока начинается и заканчивается одним и тем же символом ("aba" имеет вид <char><string><char>. <знак><строка><знак>). Поэтому, чтобы справиться с этим исключением, вы просто берете подстроку, которую уже получили, "ab", и конкатенируете ее первый символ с самим собой, "ab "+"a" = "aba", вместо того, чтобы следовать процедуре как обычно. Поэтому приведенный выше псевдокод должен быть немного изменен, чтобы справиться со всеми случаями.
Практическое задание для понимания: Расшифруйте закодированные данные для первого примера и посмотрите, сможете ли вы вернуть "banana_bandana". Помните, что вы должны начать с того же начального словаря (т.е. каждый символ находится в том же индексном слоте, что и раньше). Для облегчения работы составьте таблицу декодирования, как показано выше. Проверьте свой ответ здесь
Советы по программированию
Здесь приведены некоторые подсказки и советы, которые могут помочь при программировании LZW.
Структура данных. Программы кодирования и декодирования обращаются к словарю бесчисленное количество раз в ходе работы алгоритма. Структура данных с использованием сложности поиска 0(1) была бы очень удобна. Однако обеим программам не обязательно нужна одна и та же структура данных. Кодер ищет индексы в словаре с помощью строк (какая структура может подойти для этого?), а декодер ищет строки с помощью индексов (произвольный доступ с помощью индексов? как это звучит?)
Псевдо-EOF. В кодировании Хаффмана псевдо-EOF (End Of File) выводится в конце вывода, чтобы декодер знал, когда достигается конец закодированного вывода. Хотя LZW, как правило, не требует псевдо-eof (обычно он читает данные до тех пор, пока не сможет прочитать больше), его использование является хорошей идеей. В частности, если вы хотите расширить свою программу для сжатия нескольких файлов, вам понадобится средство для обозначения того, где заканчиваются закодированные данные одного файла и начинаются данные другого. Вероятно, самый простой способ сделать это — зарезервировать место в словаре (скажем, последний индекс) для псевдо-eof (на самом деле там ничего не хранится). Когда вы закончите кодирование, просто запишите индекс псевдо-eof. Само собой разумеется, что программа декодирования также должна зарезервировать этот индекс для сигнала псевдо-eof.
Flush Character. Это тоже необязательная функция. И снова нужно зарезервировать еще один слот в словаре. Когда программа распаковки прочитает индекс для символа flush, она вернет словарь в исходное состояние. Видите ли, когда словарь становится полным, он перестает быть динамическим и, следовательно, перестает отражать локальные характеристики. Однако, используя символ flush, вы можете следить за коэффициентом сжатия и очищать словарь всякий раз, когда этот коэффициент падает ниже определенного порога. Попробуйте поэкспериментировать с этим, и в вашем распоряжении окажется неплохая программа сжатия.
Материал подготовлен в рамках курса «Алгоритмы и структуры данных».
Всех желающих приглашаем на открытый урок «Сложность алгебраических алгоритмов. Часть-1 "Числа Фибоначчи"». На первом мастер-классе мы узнаем, какие бывают сложности алгоритмов, напишем функции возведения числа в целую степень и поиска чисел Фибоначчи. Сделаем это различными способами, изменяя сложность алгоритмов от экспоненциальной до логарифмической.
>> РЕГИСТРАЦИЯ
eandr_67
И ни слова о том, как именно должны кодироваться / декодироваться индексы в сжатом файле. В какой момент кодировщик увеличивает разрядность записи индекса и как декодер определяет момент, в который происходит увеличение разрядности? А ведь это не менее важно, чем схема добавления / распаковки индексов.
blueboar2
А вот, кстати, объясните, если вы в курсе. Допустим, разрядность индекса у нас - 12 бит, и последний индекс - 100000000011 (только что записанный). Декодер читает - видит первый бит - "1". Он понимает - "О! Раз первый бит 1 - то мы можем получить 100000000000, 100000000001, 100000000010 или 100000000011". В любом случае мы получим после единицы девять нулей. И кодер, и декодер это знают. Так почему бы не посылать их? Если и кодер и декодер знают, что идет далее, это ведь можно не посылать?
Тем не менее, например в GIF (использующем LZW), да и в других LZW-архиваторах - шлется весь индекс, независимо ни от чего. Почему?
dkosolobov
Я думаю, что это сделано для простоты реализации. LZW - очень простой но при этом эффективный алгоритм, который каждый может реализовать без мудрствований. Но если продолжать вашу мысль и довести её до идеала, то оптимально было бы применять для каждой фразы LZW адаптивное интервальное кодирование или что-то в этом духе. Тогда вся последовательность из z фраз LZW будет занимать всего log2(256) + log2(257) + ... + log2(255 + z) + 1 битов, ну или log2(256) + log2(257) + ... + log2(d) + log2(d) + ... + log2(d) + 1 битов, если размер словаря ограничен d фразами (например, d = 2^16, как обычно полагают). В стандартных реализациях LZW (типа LZC) тоже есть механизмы уменьшения размера кодов для первых фраз (хоть и не такие оптимальные): обычно первые фразы занимают последовательно 9, 10, ..., 16 битов, а потом словарь перестаёт расти. Вполне возможно, что на реальных датасетах этот простой трюк не намного хуже более хитрого оптимального кодирования. Вообще, если нужно сжатие по-лучше, то лучше сразу обращаться к LZMA, а не пытаться тюнить LZW.
tbl
LZ + опциональный Huffman + арифметическое кодирование дают больший прирост в скорости декодирования чем lzma при сравнимо той же степени сжатия
dkosolobov
Бегло прошёлся по бенчмаркам в интернете и, судя по всему, LZMA и его производные даже против deflate (это LZ77 с Хаффманов) дают в 1.5 - 2 раза лучшее сжатие. А против LZW они будут ещё лучше (LZW проигрывает deflate по сжатию, но не так драматически). По-моему это не "сравнимая" степень сжатия. Зависит от сжимаемых данных, конечно, но эти бенчмарки часто довольно репрезентативны. Недавно, кстати, на хабре была хорошая статья на близкую тему: https://habr.com/ru/post/570694/ (там же есть ссылка на один хороший бенчмарк; ещё можно посмотреть http://www.mattmahoney.net/dc/text.html). Много раз уже сталкивался с похожим мнением, что сжатие не важно и важнее скорость. Согласен, есть такие приложения, где это так. Но даже в таком случае LZW далеко не лучший выбор и методы на основе LZ77 (не обязательно LZMA) работаю лучше. Например, zstd с флагом "level 2" (или около того), судя по бенчмаркам, так же эффективен по степени сжатия, как deflate с наилучшим сжатием, но раз в 5 быстрее декодирует. Я уверен, что LZW с Хаффманом/арифметиком декодирует медленнее, чем deflate (LZW для декодирования использует более сложного вида словарь, а deflate просто копирует уже декодированные куски); в интернете пишут, что LZW в 2 раза медленнее декодирует, чем deflate, в некоторых реализациях. Без Хаффмана LZW точно по-быстрее будет, но тоже не факт, что быстрее чем deflate. Так что zstd явно гораздо лучше в этом отношении и чем LZW, и чем deflate.