Называется по фамилиям создателей: Lempel, Ziv, Welch. Известен тем, что используется в различных библиотеках сжатия и в частности в формате GIF. Был запатентован, и жадная компания Unisys стала требовать денег за создание гифок. Но как известно, если ты плюнешь в коллектив, то коллектив утрётся. А если коллектив плюнет в тебя... Так появился свободный формат PNG (Portable Network Graphics, или PNG's Not GIF).
В 2003 году срок действия патента истёк, и мы можем невозбранно использовать LZW для своих целей.
Я использовал его... лет 25 назад, для сжатия данных в игрушках и демках. Получается, это было незаконно. И был он написан на ассемблере. У меня есть исходник, но мне там лень разбираться, и также знаю, что реализация была так себе, поэтому хочу освежить память и переписать его заново.
Как работает
Алгоритм находит и устраняет повторяющиеся последовательности в сообщении, перемещая их в словарь. То есть последовательность хранится в словаре в единственном экземпляре, а в результат попадает только её код (порядковый номер в словаре).
В обычном случае словарь сразу содержит 256 кодов, которые соответствуют значениям 0..255. Это все возможные последовательности длиной в 1 символ (байт).
Возьмём такое исходное сообщение:
ABCABCABC
Будем считывать из него по одному символу и накапливать последовательность, пока она есть в словаре.
A: есть в словаре, накапливаем
B: получили последовательность AB, нет в словаре
Теперь внимание: когда мы получили последовательность, которой нет, она всегда состоит из предыдущей, которая есть (т.к. мы её накопили до этого), и ещё одного символа, который мы только что прочитали, и который дополнил существующую последовательность до несуществующей.
Поэтому мы выдаём в результат код существующей последовательности (A), затем добавляем в словарь новую последовательность AB, и продолжаем накапливать, начиная с последнего символа B. Всё с начала:
A: есть, накапливаем
B: получили AB, нет, выдали A, словарь +{AB}, осталось B
С: получили BC, нет, выдали B, словарь +{BC}, осталось C
A: получили CA, нет, выдали C, словарь +{CA}, осталось A
B: получили AB, есть, накапливаем
C: получили ABC, нет, выдали {AB}, словарь +{ABC}, осталось C
A: получили CA, есть, накапливаем
B: получили CAB, нет, выдали {CA}, словарь +{CAB}, осталось B
C: получили BC, есть, накапливаем
конец: выдаём накопленное: {BC}
Сжатое сообщение получилось такое:
ABC{AB}{CA}{BC}
Последовательности вроде {AB} я пишу в скобках, так как это не два кода, а один, из словаря, который обозначает эту последовательность.
Если A = 65, B = 66 и C = 67, а AB, BC и CA хранятся в словаре с кодами 256, 257 и 258, то сжатое сообщение будет в реальности выглядеть так:
65, 66, 67, 256, 258, 257
Если продолжать повторять ABC в сообщении, цепочки в словаре будут становиться всё длиннее и длиннее, и чем больше повторений будет, тем сильнее сожмутся данные.
В этом выпуске рассмотрим только сжатие, так как есть много нюансов.
Работа со словарём
Кодер составляет последовательности и ищет их в словаре. Чтобы найти в словаре последовательность за приемлемое время, нужен хэшмап с ключами в виде последовательностей и со значениями в виде их кодов.
В примерах, которые написаны на С++ и Питоне, натурально используется хэшмап с банальными строками-ключами. В чистом C нет библиотечного хэшмапа, но можно прикрутить его стороннюю реализацию.
Однако я хочу попробовать сделать свой вариант хэшмапа и посмотреть, что из этого выйдет. Я потом сравню скорости выполнения.
Что есть последовательность? Изначально это просто индекс в словаре. Добавив к нему второй индекс, мы обнаружим, что последовательность, независимо от её длины, всегда выглядит как
{индекс, который уже есть в словаре}{дополнительный индекс}
где {дополнительный индекс} это всегда 0..255.
Для хранения последовательности выделим стуктуру из двух полей: индекс-голова и индекс-хвост.
У начальных последовательностей из одного символа нет хвоста, поэтому он будет заполнен специальным значением.
Для хранения последовательностей выделим массив типа Sequence[]. Что делать с его размером, рассмотрим дальше.
Далее, для поиска последовательности нужна хэш-таблица. Ключом является значение последовательности "голова+хвост", которое можно представить одним 64-битным числом (считая, что голова и хвост 32-битные, об этом также поговорим потом). Значением, хранящимся по ключу, является индекс в массиве хранения.
Как будем рассчитывать хэш? Примем во внимание наш специфический случай. Каждая новая последовательность в словаре будет получать последовательный индекс+1, и другие последовательности будут скорее всего использовать предыдущие последовательности, так что все имеющиеся индексы будут использованы в хэшах. Значит, заполнение таблицы будет происходить плотно, и для расчёта хэша сгодится наивный вариант с взятием остатка от деления на размер таблицы. (Так это или нет, проверим потом.)
К примеру, делаем хэш-таблицу на 1024 записи. Для расчёта хэша будем использовать только голову последовательности. Тогда голова 0 даст хэш 0, голова 1 хэш 1 и т.д. Голова 1024 попадёт снова на 0 и создаст коллизию. Голова 0, но с другим хвостом, попадёт опять на 0 и создаст ещё одну коллизию, но всего "хвостовых" коллизий не может быть более 256.
Коллизии мы разрешаем так: предположим, что у нас значение головы 1024, которое даёт хэш 0. В хэш-таблице по индексу 0 уже хранится индекс, который указывает на какую-то последовательность в массиве хранения. Мы берём в массиве следующий свободный индекс для сохранения новой последовательности, и перезаписываем его в хэш-таблицу. Но чтобы старая последовательность с тем же хэшем не потерялась, в новой мы сохраняем её индекс, то есть делаем связный список, где каждый следующий элемент знает о предыдущем. Хэш-таблица, таким образом, показывает на последний элемент связного списка.
Структура для хранения последовательности в общем массиве, она же словарная запись, выглядит так:
Собственно, индекс предыдущей коллизии и сама последовательность.
Создание словаря (я сэкономил на иллюстрации структуры Dict, так как она наглядно присутствует здесь):
Поле hash это массив под хэш-таблицу, mem это массив хранения последовательностей, cnt это количество записей, hash_size это размер хэш-таблицы, dict_size это размер словаря, т.е. максимальное количество записей. Отдельно надо пояснить поле hash_mask – оно используется в качестве битовой маски для расчёта остатка от деления на hash_size (при этом hash_size должен быть степенью двойки), dict_offset – размер первой части словаря, заполненной по умолчанию, и none – специальное обозначение несуществующего индекса, которое равно размеру словаря и нужно скорее для удобства.
Первичная инициализация словаря:
Обнуляем всю хэш-таблицу и заносим хэши первых элементов. Попутно создаём в хранилище первичные 1-символьные последовательности. У таких записей индексы предыдущих равны none, потому что они самые первые. И хэш-таблица сейчас ссылается именно на эти записи.
Добавление последовательности в словарь:
Обратите внимание, сейчас нет проверки на превышение размера словаря, чтобы не отвлекаться. Вычисляется хэш последовательности. Из хэш-таблицы по этому хэшу берётся индекс последней записи и формируется новая запись, где этот индекс назначается предыдущим. Новая запись сохраняется под новым индексом (следующий свободный) и этот новый индекс перезаписывается в хэш-таблицу.
Поиск последовательности в словаре:
Вычисляем хэш последовательности и ищем последнюю запись с таким хэшем. Если она совпала с искомой (тут сравниваются отдельно head_code и tail_code, хотя можно было сравнить как одно длинное число), то возвращаем её индекс, если же нет, тогда переходим на предыдущую запись и повторяем.
Далее, я сделал структуру ReadBuffer и методы для загрузки контента из файла в память и затем посимвольного чтения, но так как это не имеет отношения к сжатию, то описание опущу. Всё есть в исходнике, если надо.
Можно начинать сжатие.
- Создаём словарь с заданным размером хэш-таблицы (1024), количеством записей (4096) и количеством заранее подготовленных записей (256)
- Открываем файл на чтение
- Оформляем первую последовательность из одного символа. Её искать не надо, так как один символ в словаре всегда есть. Для ранее рассмотренного текста ABCABCABC это будет A.
Далее в цикле читаем следующий символ – скажем, B, и помещаем его в хвост текущей последовательности. Получается AB. Ищем в словаре. Если нашли, то у такой последовательности есть код. Этот код делаем головой в текущей последовательности. Как видим, работа со строками, с их складыванием, здесь не нужна. Оперируем только двумя числами, индексом головы и индексом хвоста.
Ну а если не нашли, то добавляем новую последовательность в словарь и выводим ту, которую успели найти, то есть голову. После чего хвост становится новой головой.
Я пока не вывожу ничего конкретно в "результат", а просто печатаю коды в консоль для наглядности. Для примера ABCABCABC, который мы ранее рассчитали руками, получился такой вывод:
Который совпадает с рассчитанным.
Что делать с размером словаря?
У словаря фиксированный размер, и значит он может содержать ограниченное количество последовательностей. Ну а если на вход подаётся очень большой файл?
Существует на удивление много решений этой проблемы.
Самое простое – ничего не делать. Как только словарь заполнился, новые последовательности в него не добавляются, и значит будут находиться только старые. Такая стратегия вполне может работать. Например, если начало книги заняло весь словарь, то остаток может обходиться теми последовательностями, которые уже есть, так как скорее всего в нём будут те же повторы, что и в начале.
Другой вариант это очищать словарь и начинать всё заново. С пустым словарём нужно некоторое время, чтобы цепочки повторений снова выросли и вышли на проектную мощность, но зато нет зависимости от предыдущих частей, всё делается оптимально именно для текущего кодируемого куска. Этот вариант теоретически подходит для контента, состоящего из непохожих друг на друга кусков.
Третий вариант это удалять из словаря наименее используемую последовательность... Короче, мы так далеко зайдём.
Я добавлю проверку на переполнение, и чтобы словарь ничего больше не делал:
В качестве входного сообщения возьму текст Уильяма нашего Гибсона "Нейромант":
Его размер – 451934 байта. Я также добавлю счётчик выведенных кодов, так можно будет оценить эффективность сжатия:
Поехали. Результат: 154900 кодов на выходе.
Теперь я сделаю очистку словаря при переполнении:
И результат: 178215. Сжатие хуже! Откатываем назад.
А что, если я увеличу размер словаря с 4К до 64К записей? Результат: 100054. Сжатие стало гораздо лучше, но и выполнение программы на долю секунды замедлилось (раньше было практически мгновенно). Это из-за возросшего числа коллизий в хэш-таблице. Попробую увеличить и размер хэш-таблицы до 16 килобайт. И да, сжатие осталось тем же, но теперь выполняется так же быстро, как и раньше.
В общем, данную версию хэш-таблицы надо будет ещё детально проанализировать, и также сравнить быстродействие с std::unordered_map или вроде того в С++.
Пока же разберём вот что.
Коды переменной длины
Если размер исходного сообщения 451934 байта, а мы получили в сжатом виде 100054 кодов, то с виду мы добились сжатия в 4.5 раза. Но это не так. В исходном сообщении у нас байты, а каждый выдаваемый код это int, то есть 4 байта, то есть надо обратно умножить на 4, и сжатие сходит практически на нет.
Но если быть точнее, кодам не нужно быть 32-битными. При размере словаря в 64 килобайта им хватит 16 бит. Значит, умножаем всего лишь на 2, и мы добились сжатия в 2.2 раза.
Нетрудно представить, что очень много кодов кодируют одиночный символ 8 бит, но всё равно имеют размер 16 бит.
Так что встаёт вопрос балансировки. Чем длиннее код, тем длиннее последовательность, которую он кодирует. Но в то же время последовательности с более короткими кодами вынуждены существовать в том же пространстве, напрасно расходуя биты.
Для алгоритма LZW принято считать коды 12-битными и ограничивать словарь размером 4096 записей. В первых тестах наш словарь был как раз такого размера, поэтому полученный результат 154900 надо привести к 12-битным кодам. Получим увеличение в 1.5 раза, или 232350. Таков реальный размер сжатых данных в байтах. Результат 100054 для 16-битных кодов умножим на 2, и получим 200108. Чуть меньше, но словарь больше в 16 раз, и хэш-таблицу желательно иметь больше, если не хотим тормозов. Получается, что выигрыш в сжатии незначителен, но зато существенно повышает требования к ресурсам.
Нельзя делать однозначные выводы по одному примеру. Входные данные могут быть разные, результаты тоже будут разные. Но видимо, 12 бит выбраны неспроста.
Так а что насчёт кодов переменной длины?
Словарь может управлять длиной кода при добавлении. Например, в него уже добавлено 256 кодов, значит длина следующего кода будет 9 бит. Так как коды добавляются последовательно друг за другом, длина 9 бит будет сохраняться до кода 511, а начиная с 512 станет 10 бит. Таким образом можно отправлять коды в выходной поток, отсчитывая ровно столько бит, сколько нужно.
Я пока не буду этого делать, чтобы упростить различные эксперименты. Плюс надо ещё написать распаковщик, где возникнет интересный вопрос – а как мы будем считывать обратно коды переменной длины, если они не префиксные, как у Хаффмана?
Читайте дальше: