Оглавление

• Обзор

• Сжатие 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)

Этапы кодирования будут выполняться следующим образом:

Обратите внимание, что после считывания последнего символа, "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 соответственно. Начинается процесс кодирования:

Итак, кодированный выход начинается с 0,1,2,4,... . Когда мы начинаем пытаться декодировать, возникает проблема (в приведенной ниже таблице следует помнить, что текущая строка — это просто подстрока, которая была декодирована/переведена в последнем проходе цикла. Кроме того, новая словарная запись создается путем конкатенации текущей строки с первым символом нового преобразования словаря):

Как видите, декодер сталкивается с индексом 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 "Числа Фибоначчи"». На первом мастер-классе мы узнаем, какие бывают сложности алгоритмов, напишем функции возведения числа в целую степень и поиска чисел Фибоначчи. Сделаем это различными способами, изменяя сложность алгоритмов от экспоненциальной до логарифмической.
>> РЕГИСТРАЦИЯ