Занимаюсь осмыслением файловой системы для контроллеров.., а Вася решает олимпиадные задачи. Вася задал вопрос, как эффективно находить подстроки. Я вспомнил идею из алгоритма LZJB, и увлекся созерцанием этого алгоритма. LZJB - алгоритм потоковой упаковки данных, был включен в дистрибутива файловой системы ZFS. Найти исходники LZJB можно в дистрибутиве OpenZFS или OpenIllumos, клона OpenSolaris. Алгоритм изначально был предназначен для быстрой записи дампа памяти, в случае краха системы. От него ничего не требуется, кроме скорости записи и простоты чтения. Эффективно дложны паковаться длинные последовательности ноликов и высказывания типа 0xBAADF00D и 0xDEADBEEF - неинициализированная память, остальное не так важно. Подстроки алгоритм ищет через хеш-функцию недоделанную. Не могу сказать, что упаковка данных может оказаться полезной, но с точки зрения проектирования файловой системы, опция упаковки, как в ZFS или как в SquashFS, не помешает. Осмыслить возможность стоит.
Алгоритм простой и в тоже время невероятно криво написан, не глючит каким-то чудом. Когда-то лет десять или более назад, когда открыли исходники OpenSolaris, мне понравились некоторые идеи и в том числе засматривался на алгоритм потокого сжатия LZJB, для применния в своих разработках. Сейчас вижу, кривой, хочу подправить, чтобы не был таким кривым.
Первая проблема- таблица хеш не использует второй уровень сравнения, его просто нет, можно найти подстроку только одного вида, последнюю, которая соответствует хешу.
Вторая - подстроки от вставленных подстрок не считаются, по какой-то причине получается, что часть шаблонов игнорируется.
В алгоритме довольно хорошо подобрана хеш функция, но на нее как раз все и завязано, от эффективности хеш функции сильно зависит результат. Пробовал несколько вариантов других хеш функций, степень сжатия удавалось получить лучше и хуже. Но так не должно быть, результат не должен зависить от размера хеш или от эффективности функции хеширования. Поэтому первым делом начал исправлять хеш таблицы.
Взял за основу хеш таблицы и способ работы со сылками из Elf - формата.
Простая замена в алгоритме хеш таблиц позволяет существенно увеличить степень сжатия. Кроме того, ввел в алгоритм заполнение хеш таблиц от всего потока, а не только от фрагментов некодированных, как в исходном алгоритме.
В основе кодирования LZJB лежит эффективный алгоритм подгрузки и декодирования битовых строк, отвечающих за выбор формата кодирования. Я пробовал заменить его на кодирование подстрок наподобие форматов кодирования LZO. В первом приближении способ работы с флагами "copymap" оказался эффективнее. Флаги выбора типа кодирования дают накладные расходы 1 бит на байт, который не входит в подстроку. Подстрока кодируется двумя байтами: длина последовательности и смещение в буфере от текущей позиции записи. Формат упаковки длины и смещения используется только один:6 бит длина, 10 бит - смещение.
Чтобы понять насколько эффективный при этом получается декодер, предлагаю рассмотреть функцию декодирования в виде шаблона:
// Алгоритм распаковки LZJB.
int lzjb_decompress(...)
{
uint8_t copymap = 0;
int copymask = 0x80;
while (dst < d_end) {
/* выбор типа кодирования */
if ((copymask <<= 1) == 0x100) {
copymask = 1;
copymap = *src++;
}
if (copymap & copymask) {
/* 1:декодирование формата ссылки */
/* 2:копирование подстроки */
} else {
*dst++ = *src++;
}
}
return (0);
}
Декодирование однопроходное, без вложенных циклов и сравнимо по быстродействию с операцией копирования. Предложен интересный способ декодирования формата с подгрузкой битовых строк "copymap". Приведенного алгоритма достаточно чтобы понять как все устроено, не буду приводить код целиком.
Возможно ли из этого алгоритма сделать что-то превосходящее по параметрам. --ДА! Во первых мы можем предложить несколько форматов упаковки подстрок, в частности тут последовательности меньше 3 байт не кодируются, а мы можем, если ввести формат умещающийся в один байт. Исходный алгоритм (LZJB) использует максимальную дистанцию поиска подстрок 1024 байта. Мы можем приспособить для работы с блоками размером 4кБайт, если увеличим эту дистанцию хотя бы до 2кБайт. Проверил, оказалось действительно на блоках размером 4кБайт эффективнее работает дистанция в 2кБайта. Второй формат должен быть скромнее, он должен паковать маленькие последовательности, опытным путем вывел формулу второго формата: 2-бита на длину, 6-бит смещение. Получаем два формата: "2-6" и "5-11" -- их можно сделать параметрическими для случая, когда размер блока флеш памяти меньше 4кБайт. Я пропущу описание дня работы, когда я изучал распределения и эффективность упаковки двумя и более форматами. Для отладки процесса кодирования использовал недоделанный кодировщик, который не заботится о записи, а только высчитывает длины и смещения для выбранного способа кодирования. Для оценки эффективности использовал различные файлы: картинки, тексты программ, бинарники x86 и ARM, форматы XML. Да наибольшая эффективность достигается именно на форматах типа XML, на векторной графике SVG в частности.
Разработка функции декомпрессии
Важно отметить, что разработка алгоритма начинается не с функции сжатия, а со структуры алгоритма распаковки, как он должен выглядить для максимальной производительности. В исследовательских работах есть своя прелесть, нет никакого тех задания пиши, что хочешь. Но какова цель? Ставлю цель, чтобы алгоритм работал быстро, чтобы распаковка была эффективной. Быстро - означает возможность использования векторных инструкций для копирования и сравнения. Идеально было бы избавиться от циклов при поиске подстрок в алгоритме сжатия и от проверок и вложенных циклов в алгоритме распаковки. Чтобы избавиться от циклов при поиске, предлгаю ввести ограничение, длина подстроки не может предвышать 64 или 32 байта, -- этот параметр завязан на формат кодирования. Для формата "6-10" (длина-смещение) подойдет ограничение длины подстроки в 64=2^6 байта, а для формата "5-11" ограничение длины подстроки в 32=2^5 байта. Чтобы можно было переключаться между двумя(тремя) форматами кодирования придумал двухуровневую структуру, на основе исходного алгоритма декодирования.
// Структура алгоритма распаковки.
int my_decompress(...)
{
uint8_t copymap = 0;
int copymask = 0x80;
while (dst < d_end) {
/* выбор типа кодирования */
if ((copymask <<= 1) == 0x100) {
copymask = 1;
copymap = *src++;
}
if (copymap & copymask) {// флаг кодирования
if ((copymask <<= 1) == 0x100) {
copymask = 1;
copymap = *src++;
}
if (copymap & copymask) {// флаг формата
/* 1.1:декодирование формата №1 2-6 */
} else {
/* 1.2:декодирование формата №2 5-11 */
}
/* 2:копирование подстроки */
} else {
*dst++ = *src++;
}
}
return (0);
}
Мой алгоритм декомпрессии использует битовый поток для выбора форматов кодирования. Еще короче структуру алгоритма можно выразить следующим образом.
// Структура алгоритма распаковки.
int my_decompress(...)
{
while (dst < d_end) {
/* выбор типа кодирования */
if (bitstream_get(stream, 1)) {// флаг кодирования
if (bitstream_get(stream, 1)) {// флаг формата
/* 1.1:декодирование формата №1 2-6 */
} else {
/* 1.2:декодирование формата №2 5-11 */
}
/* 2:копирование подстроки */
} else {
*dst++ = *src++;
}
}
return (0);
}
Результат. При сжатии фала SVG получил степень сжатия 0.42 алгоритмом LZJB и степнь сжатия 0.27 моим алгоритмом. Мой алгоритм потокового сжатия около 90 строк, алгоритм распаковки =34 строки. Добавить перцу: в моем алгоритме хеш функция берет первый байт последовательности, обработка не требуется, эффективнее некуда. Приведу функцию заполнения хеш таблицы, остальное следует из описания алгоритма. Хеш таблицы для потокового сжатия не используют динамические данные или списки. Список формируется в массиве "chain".
// Функция заполнения хеш-таблицы
uint16_t _htable_insert(uint16_t *htable, uint8_t key)
{
uint16_t *chain = htable + 256;
uint16_t y = n_chain++;
uint16_t *head = &htable[key];
chain[y] = *head;
*head = y;
return y;
}
При поиске подстроки максимальной длины используется цикл по цепочке "chain", с массивами можно работать, как со списками.
// цикл поиска подстроки с использованием хеш-таблицы
hash = *src;// это моя хеш-функция, копирует байт.
i =_htable_insert(htable, hash);
while ((i = chain[i])!=0)
{// обработка подстрок по цепочке
. . .
}
Исходники на Github
Выбор хеш-функции
Исходно утверждал, что результат не должен зависеть от выбора хеш функции. Однако, это смотря в чем измерять результат. Степень упаковки действительно не должна зависеть от выбора хеш- функции. Однако, выбор влияет на скорость запаковывания, сколько требуется циклов на поиск значения в хеш-таблице. Для сравнения предлагаю несколько вариантов хеш функции. Все они основаны на том, что в алфавтие примерно 32 буквы чего-то значат и часто применяются, в таблице символов используется только половина (7 бит или 6 бит), остальная половина используется для кодирования чего-то другого, другого языка. Эта идея годится для английского языка и ASCII таблиц. Чтобы высчитывать хеш от текстов UTF-8 надо применять знания о кодировании UTF-8. Последовательности кодирования имеют вид 110xxxxx 10xxxxxx .. Видно, что значимыми бывают 5 бит первого байта и 6 бит последующих.
// Функция хеш из LZJB
static uint32_t lzjb_hash(uint8_t* src, int min_len)
{
uint32_t hash;
hash = (src[0] << 8) + src[1];
hash += hash >> 9;
hash += hash >> 5;
return hash;
}
// Функция хеш из GLIB для строк
static uint32_t glib_hash(uint8_t* src, int min_len)
{
uint32_t hash;
hash = (src[0] * 33) + src[1] + 5381;
return hash;
}
// Оптимальная хеш
static uint32_t my_hash(uint8_t* src, int min_len)
{
uint32_t hash;
hash = (src[0] * 66) + src[1];
return hash;
}
// Функция Фибоначчи хеш
static uint32_t lz4_hash(uint8_t* src, int bits)
{
uint32_t val = (uint32_t) src[0] | ((uint32_t) src[1] << 8);
return (val * 2654435761ULL) >> (32-bits);
}
Первый вариант взят из оригинального алгоритма LZJB, адаптирован для двух-байтвых последовательностей. Второй из описания работы хеш функции glib, g_str_hash. Третий подбирал по мотивам двух предыдущих. Кроме того пробовал использовать остатки от деления на простые числа, что тоже благотворно сказывается на равномерности распределение хешей по таблице. Для отладки выводил среднее число циклов при поиске в хеш таблице. Отлаживал Хеш функцию на текстах XML и русскоязычных текстах в кодировке UTF-8. Компромисом оказалась функция my_hash. Почему так, не скажу, числа подбирал исходя из идей кодирования.
Повторюсь, хороший результат получается, для функций содержащих остаток от деления на простое число. Функция хеширования может быть составлена из комбинации сдвигов, побитовой операции XOR и умножения на некоторое обратное число. Остаток от деления на простое число можно представить операцией умножения на обратное число. Пример такой хеш функции нашел в реализации алгоритма сжатия LZ4. Использование lz4_hash с параметром bits=16 дает сравнимый результат.
Сравнение методов кодирования форматов
Изучив несколько вариантов фукнций сжатия на потоке, среди которых LZ4, LZO, LZF, пришел к выводу: все они одинаковые по сути, различаются только методы кодирования последовательностей (litterаl/RLE-run length encode) литерал/длина последовательности копирования. В моем варианте алгоритма выбор формата RLE - это битовые последовательности, а применяется всего два формата кодирования. В остальных рассматриваемых форматах LZO, LZF, LZ4 методы кодирования схожи, но используют первый байт кодового блока для выбора метода кодирования, включая выбор последовательности литарал или RLE. Алгоритм компрессии можно разложить на два этапа: 1) составление таблицы, включающий три поля для кодирования (длина литерала, длина последовательности, смещение в выходном буфере), и 2) функция кодирования по выбору.
Степень сжатия при одинаковой функции поиска повторяющихся фрагментов определяется исключительно эффективностью формата кодирования. Наш метод кодирования оказался самым эффективным. Для доказательства этого утверждения я использовал расчет кодовых длин для каждого из форматов, на всех тестовых. Например, исходный формат кодирования LZJB не позволяет кодировать бвухбайтовые последовательности - это существенно снижает его эффективность и напрямую влияет на степень сжатия, используется всего один вариант формата кодирования. В LZO содержится много вариантов кодирования. В LZF - два варианта кодирования, в LZ4 - несколько, за счет расширений, метод расширения не кажется эффективным. Существенно выделяется формат LZJB, потому что для выделения литералов используется не кодовое слово, а отдельный механизм дающий прибавку +1 бит на литерал. Такой подход оказыватеся эффективнее судя по степени сжатия.
При проектировании фукнции сжатия на эффективность влиют несколько факторов: 1) Использование словаря -- мы пока не пытаемся встроить использование словаря, может зря, 2) кодирование последовательностей несколькими форматами, включая двухбайтовые. 3) Особый метод кодирования для снижения накладных расходов при кодировании литералов.
Ниже привожу краткие характеристики форматов кодирования:
LZJB: максимальная дистанция обратного просмотра буфера 1кБайт (10 бит). 1 формат 2 байта.
0|S(8) -- кодирование литералов 1 байт+1бит.
1|L(6)|D(10): length=L+3, distance=D; -- кодирование RLE 2 байта+1бит
LZO: максимальная дистанция 2кБайта (11 бит)
01L DDD SS | H(8) -- копирует L+3 байт (3..4), и S литералов.
1LL DDD SS | H(8) -- копирует L+5 байт (5..8), и S литералов.
LLL DDD SS | H(8) -- копирует L+3 байт (3..10), и S литералов.
. . . есть и другие варианты.
distance = (H << 3) + D + 1
LZF: максимальаня дистанция 8кБайт (13 бит), два формата
T1(3)|T2(5) - токен, первый байт кодового блока
при T1=0, n_literal= T2+1 -- копирование литералов
при T1=7, length = T1+2+L(8), distance = (T2<<8) + D(8)+1; -- кодовый блок 3 байта
length = T1+2, distance = (T2<<8) + D(8)+1; -- кодовый блок 2 байта
LZ4: максимальная дистанция 2кБайта (11 бит)
T1(4)|T2(4) - токен, первый байт кодового блока
при T1=0, n_literal= T2+1 -- копирование литералов
-- кодовый блок 2 байта, расширяемый
LZJB-2, Мой вариант: максимальная дистанция 2кБайта (11 бит).
0| S -- кодирование литералов 1 байт+1бит
10|L(2)|D(6) : length=L+2, distance=D+1; -- кодовый блок 1 байт и 2 бита
11|L(5)|D(11): length=L+3, distance=D+1; -- кодовый блок 2 байта и 2 бита
при L=31 : length=L(8)+34, distance=D+1; -- кодовый блок 3 байта и 2 бита
Коды Хаффмана
Не смог обойти вниманием коды Хаффмана. Основная причина, по которой я привожу кусок кода алгоритма декодирования Defalte [RFC 1951] - не нашел читабельной реализации, чтобы из кода было понятно, как выполняется кодирование. Из текста RFC не сильно понятно, как реализовать таблицы кодирования, хотя расписано все достаточно подробно. Красивой реализации на три строчки кода, чтобы из кода было понятно, как выполняется разбор формата - не нашел. Предлагаю свою реализацию:
// literal/length decode
code = huffman_read_bit(0, stream, 5);
switch (code & 0x1F) {// 5-bit prefix
case 0b00000 ... 0b00101:// 256 - 279
code = huffman_read_bit(code, stream, 2);
code = code - 0b0000000 + 256;
break;
case 0b00110 ... 0b10111:// 0 - 143
code = huffman_read_bit(code, stream, 3);
code = code - 0b00110000 + 0;
break;
case 0b11000 ... 0b11000:// 280 - 287
code = huffman_read_bit(code, stream, 3);
code = code - 0b11000000 + 280;
break;
case 0b11001 ... 0b11111:// 144 - 255
code = huffman_read_bit(code, stream, 4);
code = code - 0b110010000 + 144;
break;
}
Данынй фрагмент написан на языке Си, как ни странно, с использованием бинарных констант и диапазонов case. В отличие от представленных ранее методов кодирования, код Хаффмана не выровнен на байт, а все биты берет из потока. Функция чтения бит из потока, представлена huffman_read_bit() и реализована таким образом, чтобы дополнять кодовые последовательности битами из потока.
Глядя на фиксированную таблицу кодирования Delate, и сравнивая с представленными методами кодирования LZJB-2, понимаю, - мой метод в чем-то лучше кодирует, по одной причине - он использует двухбайтовые последовательности, а метод fixed Delate вообще зря теряет байт на кодировании длины. Метод кодирования LZJB использует два источника: поток бит и поток байт - это выигрышная стратегия. Вероятно выиграть в степени сжатия можно с упаковкой форматов кодирования полей длина-смещение (RLE) в битовый поток.
Данынй фрагмент кода представляет собой кодирование литерала или длины последовательности методом Хаффмана с фиксированной таблицей кодирования. Таблица кодирования может быть задана динамически и представлена, как бинарное дерево, где каждое ветвление выполняется по старшему биту.
