Алгоритм LZW: Сравнение производительности и распаковщик

В предыдущей части был написан упаковщик LZW:

Если порыться в сети, то большинство реализаций LZW будут опираться на использование хэшмапа с ключами-строками. Почему? Потому что это самое очевидное, что приходит в голову.

Но я сделал свою версию хэш-таблицы для реализации словаря. Без ключей-строк и вообще очень примитивную.

Я измерил время выполнения своей программы на файле "Neuromancer", упомянутом в предыдущей части. Оно составило около 0.05 секунды.

Потом я решил вывести статистику заполнения своей кустарной хэш-таблицы и обнаружил, что количество коллизий на некоторых индексах доходит до 44, хотя в подавляющем большинстве случаев оно меньше 6.

Тогда я решил немного доработать вычисление хэша. Напомню, что моя последовательность состоит из головного и хвостового кода, и хэш я считал просто как головной_код % HASH_SIZE, наибанальнейшим способом. В результате я добавил в хэш операцию XOR с хвостовым кодом, умноженным на простое число. Делал я это от балды,

и к примеру, операция "+" вместо XOR или какие-то другие простые числа ничего радикально не изменили, но в результате максимальное количество коллизий сократилось до 12.

Время работы программы теперь составило 0.025 секунды.

Далее я адаптировал и запустил программу на C++, которую нашёл в гугле. Она использует строки-ключи в хэшмапе и выполняется в ДЕСЯТЬ раз медленнее, чем мой первоначальный вариант: около 0.4 секунды. Я переделал её, чтобы ключами были не строки, которые постоянно складываются с выделением-освобожденим памяти, а целочисленные коды, как у меня. Стало работать быстрее, но всё равно 0.3 секунды, что в ДЕСЯТЬ раз медленнее моего финального варианта.

Далее я запустил аналогичную программу из гугла на Питоне, и она работает примерно с той же скоростью, что и программа на C++. Представляете? Питон такой такой же быстрый, как C++!

Конечно, нет. Просто внутренняя реализация словаря у Питона написана на C, а кроме действий со словарём, в программе ничего особо и нет.

Память

Я также измерил, сколько памяти требуется для выполнения программы. Делал это в Linux следующим способом: ограничивал с помощью команды ulimit доступную память и запускал программу. Если программа работала, то уменьшал память до тех пор, пока программа не отказывалась работать.

Моя программа работала с памятью в 5 мегабайт. Для программы на C++ потребовалось уже 9 мегабайт, и наконец для программы на Питоне – 37 (тридцать семь) мегабайт.

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

Таким образом, вы можете прикинуть масштаб бедствия, когда вам рассказывают, что на Питоне что-то можно написать в одну строчку.

Распаковщик

Что ж, выводы, надеюсь, понятны.

Перейдём к реализации распаковщика.

В качестве исходных условий я взял словарь размером 4096, который при переполнении просто перестаёт добавлять элементы (эта стратегия в прошлой части была отмечена как более выгодная по сравнению с очисткой словаря). А размер кода я сделал 16 бит, чтобы было проще читать, не заморачиваясь с 12 битами или переменным размером.

Пока не нужно усложнять то, что ещё не проверено. На данный момент требуется проверить, правильно ли работал упаковщик, и соответственно правильно ли работает распаковщик. Когда мы получим утвердительные ответы, можно уже будет баловаться с очисткой словаря и кодами переменной длины.

Работа распаковщика напоминает сюжет с бароном Мюнхгаузеном, который вытаскивал себя вместе с лошадью из болота за собственные волосы.

Упаковщик шёл по тексту и строил словарь. Распаковщик будет строить текст, и одновременно строить точно такой же словарь по уже построенному тексту.

Словарь сильно упрощён. В нём уже не надо ничего искать по значению строки, поэтому не нужна и хэш-таблица. Нужный элемент достаётся просто по индексу. Таким образом, словарь будет обычным массивом, состоящим из последовательностей.

Порядок распаковки:

1. Рабочая последовательность пустая
2. Прочитать код последовательности
3. Вывести последовательность из словаря, которая соответствует прочитанному коду
4. Добавить в словарь новую последовательность, которая состоит из рабочей + первый символ прочитанной
5. Рабочая последовательность = прочитанная
6. Повторить с пункта 2

Простой алгоритм, но он заставил меня довольно долго медитировать на него, прежде чем что-то стало понятно. Попробуем разобраться по ходу повествования.

Последовательности я по-прежнему храню в структуре из двух кодов:

Словарь теперь это простой массив последовательностей и служебные поля:

Заполняем словарь первыми последовательностями по умолчанию:

Замечу, что конкретно здесь заполнение head_code или tail_code не так уж принципиально, так как при коде < 256 и так понятно, что это одиночный символ, и не надо вообще искать такую последовательность.

Добавление новой последовательности в словарь:

Ну и пока можно перейти к основному алгоритму:

Самый первый прочитанный код всегда будет меньше 256, поэтому я сразу его вывожу и делаю текущей последовательностью. Всё, что будет читаться далее, будет цепляться уже к существующей последовательности.

Например, первый прочитанный символ это A с кодом 65, а второй это B с кодом 66. В соответствии с алгоритмом в словарь добавляется последовательность AB, которая состоит из кодов { 65, 66 }, но сама последовательность при этом получает код 256, так как записывается в следующую свободную позицию словаря. Затем, когда мы считываем код 256, то находим последовательность по индексу 256, которая равна { 65, 66 }, и...

Чтобы вывести такую последовательность, придётся действовать с конца. Последний её символ это 66 (B), а предыдущий это A (65). Это простейший случай, где A уже финальный символ, но в более длинных последовательностях предыдущие будут ссылаться на другие последовательности и т.д. То есть нужно все символы начиная с конца записывать в какой-то буфер тоже с конца, и двигаться вверх по предыдущим, пока не дойдём до самого первого символа. Затем то, что записано в буфере, можно уже вывести в прямом порядке.

Я состряпал вот такую функцию для вывода, но это лишь временная мера:

Задача, как я и говорил, проверить правильность упаковки-распаковки, не обращая внимания на детали реализации.

Есть ещё один момент, связанный с получением первого символа последовательности. Его тоже пока не получить иначе, чем через движение от последнего:

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

Но я изначально закладываюсь на то, что алгоритм может работать в потоковом режиме. Распаковщик может делать вывод сразу в какое-нибудь сетевое соединение, не сохраняя у себя текст, стало быть и метки начала/конца последовательностей будет ставить негде.

В общем, к этому вопросу ещё вернёмся. Пока работает и так, и несмотря на обходы цепочек связного списка, работает очень быстро, так что даже не знаю, есть ли нужда что-то улучшать.

Важно сейчас другое. Рассмотрим вариант с кодированием текста ABABABAB.

• A: копим
• B: накопили AB, в словаре нет, добавили AB (256), вывели A (65), осталось B
• A: накопили BA, в словаре нет, добавили BA (257), вывели B (66), осталось A
• B: накопили AB, в словаре есть, копим
• A: накопили ABA, в словаре нет, добавили ABA (258), вывели AB (256), осталось A
• B: накопили AB, в словаре есть, копим
• A: накопили ABA, в словаре есть, копим
• B: накопили ABAB, в словаре нет, добавили ABAB (259), вывели ABA (258), осталось B
• вывели остаток: B (66)

Итого в кодированном виде: 65, 66, 256, 258, 66

Теперь раскодируем:

• 65: вывели A, текущая последовательность: A
• 66: вывели B, добавили в словарь A + B[0] = AB (256), текущая последовательность: B
• 256: вывели из словаря AB, добавили в словарь B + AB[0] = BA (257), текущая последовательность: AB
• 258: ...

Тут мы обнаруживаем, что не можем вывести последовательность 258, потому что её нет в словаре. Это происходит потому, что ритмы упаковщика и распаковщика несколько сбиты.

Решение есть: наша текущая последовательность это AB, и мы сейчас должны добавить в словарь новую последовательность AB + X[0], где X это неизвестная последовательность с кодом 258. То, что сейчас мы добавим, и станет последовательностью с кодом 258. А так как то, что мы добавляем, начинается на A, значит мы добавляем к AB первый символ самой себя, т.е. AB + AB[0] = ABA!

Соответственно, вот более точный алгоритм:

1. Рабочая последовательность пустая
2. Прочитать код последовательности
3. Если код последовательности есть в словаре, добавить в словарь новую последовательность, которая состоит из рабочей + первый символ прочитанной, иначе добавить в словарь новую последовательность, которая состоит из рабочей + первый символ рабочей
4. Вывести последовательность из словаря, которая соответствует прочитанному коду
5. Рабочая последовательность = прочитанная
6. Повторить с пункта 2

Ну и вот теперь да, всё работает.

Исходный код программы

В заключительной части рассмотрим различные оптимизации.

Читайте дальше: