Контекстные префиксные коды (к вопросу об оптимальности кода Хаффмана)


	Сайт о сжатии >> Новинки \| О сервере (Compression Catalog! \| ENGLISH) Книга "Методы сжатия данных" >> Без потерь \| Изображений \| Видео Разделы >> Cтатьи \| Видео \| Arctest \| Ссылки \| Ru.compress \| Форум Проекты >> Д.Ватолина \| А.Ратушняка \| М.Смирнова \| В.Юкина \| Е.Шелвина \| Д.Шкарина

Контекстные префиксные коды, которые,
на самом деле, вовсе не префиксные
(к вопросу об оптимальности кода Хаффмана)

Историческая справка
Цель данной работы
Процесс
Терминология и определения
Дополнительные видеоэффекты
О "физическом смысле"
Long live Huffman! - новая идея
Тестовая реализация (см. примеры использования)
Вопросы
Примеры эффекта от использования не-префиксного кода
Расчет максимальной высоты дерева Хаффмана
К вопросу о доказательстве алгоритма Хаффмана
Библиография

1. Историческая справка

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

Тем не менее, к своему немалому удивлению, единственный дельный факт нашелся только в "Modeling for the text compression" Белла, Виттена и Клири. Там написано (в библиографии, впрочем, отнюдь не в тексте :), что классической работой по хаффмановскому коду является статья "A method for the construction of minimum redundancy codes", опубликованная неким Huffman'ом D.A. в 1952'ом году в каком-то ежегодном сборнике. Кроме того, в той же библиографии удалось обнаружить, что Шеннон занимался своими ужасными экспериментами над людьми где-то в 1948-1952'ом годах. Судя по датам публикаций, по крайней мере.

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

Такое впечатление, что самым содержательным источником должно быть "Искусство программирования" Кнута, в коем тот не поленился предоставить к каждому разделу достаточно содержательную историческую справку. Впрочем, все равно у меня есть только первый том (хотя про Хаффмана упоминается именно там, в разделе, где Кнут считает деревья :), да и тот теоретически - дал почитать. Ну еще есть третий, но в TeX'е. Да и, в любом случае, это чудо является русским переводом 1972 года, что не есть хорошо, учитывая, что после того была еще парочка американских изданий. (Кстати, Кнут утверждает, что он Канут, но так мы ему и поверили).

В общем, ладно. Все равно мне скучно копаться в библиографиях, ни одной книжки из которых мне никогда не увидеть (да и не очень и хотелось), а, кроме того, еще и не вполне понятно, что, собственно, относится к делу, так что мне сказать больше нечего, а если кто чего знает, так пусть не молчит.

2. Цель работы

К сожалению, причина, побудившая меня к исследованию префиксных кодов, в моей дырявой памяти не удержалась. Но вероятно, что это все-таки было чье-то глубокомысленное заявление очередному чайнику о том, что у того код получился непрефиксный, поэтому ничего работать не будет, и вообще код Хаффмана - оптимальный и использовать нужно только его, а лучше - арифметическое кодирование, которое вообще идеальный вариант и лучше не бывает. Честно признаюсь, я тоже никогда особенно не любил читать всяческие доказательства. Обычно хватало факта их наличия, подтверждающего верность некоторого утверждения.

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

Кроме того, всякий раз, когда я писал лексический анализатор, определенные детали его работы вызывали непонятные ассоциации. Действительно, алгоритмы лексического и синтаксического анализа имеют большое сходство с алгоритмами сжатия. Но есть и некоторые отличия. Например, при разборе текстов программ на популярных языках программирования обычно приходится искать _самый длинный_ идентификатор, имеющийся в словаре.

Вот я и подумал: а нельзя ли подобные принципы применить для оптимизации "оптимального" кода Хаффмана?

3. Процесс

Идея была простая: возьмем некоторый текст, посчитаем для него хаффмановский код и закодируем. Логично, что (по крайней мере, не сложно специально создать такой пример) в тексте могут встречаться далеко не все комбинации символов, обычно можно найти даже не все возможные их пары. Но, следовательно, некоторый префикс суммарного кода для отсутствующей пары символов можно использовать в качестве нового кода! И если его назначить символу с достаточно малой частотой, то уже получим возможность закодировать текст лучше, чем кодом Хаффмана, пусть и всего на несколько бит. Разве что, потребуется немного переделать распаковщик, чтобы заставить его искать не первый попавшийся код, а самый длинный. Ну и, кроме того, вероятно нужно будет изменить структуру данных, используемую распаковщиком для поиска символов по битовому коду. Если для префиксного кода достаточно бинарного дерева, так как для каждого его префикса есть максимум два варианта продолжения, то теперь столь же хорошо подойдет тернарное - в каждом узле дерева будем хранить указатели на символ с текущим кодом и на узлы, описывающие два возможных продолжения этого кода.

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

Так вот, сначала я умудрился додуматься до совершенно "гениальной" вещи - завел в структуре-дескрипторе каждого символа по полю размером 8k, представляющему собой последовательность битовых "масок" для суффиксов символа длиной до шестнадцати бит. То есть, сам-то способ представления встречающихся суффиксов оказался неожиданно удобен поиск кратчайшего неиспользованного осуществляется путем сканирования маски _двойными словами_ в поисках отличного от нуля значения (я выбрал "инверсную" кодировку - 0 = есть такой суффикс; 1 = нет), а далее помогает полезная команда BSR. При этом, поскольку маски для суффиксов разной длины располагаются в памяти последовательно, то сразу удается обнаружить именно то, что нужно. Тем не менее, учитывая изначальный расчет на размер алфавита до 64k символов такой расход памяти я посчитал несколько... э-э... неприемлемым. Кроме того, при такой системе необходимо было обшаривать маски всех символов в поисках минимальной суммарной длины кода символа и свободного суффикса. Единственная польза - что сразу становилось известно, с кодом какого символа будет "пересекаться" новый код. Но что делать с этой информацией, я так до сих пор и не придумал.

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

Вот, собственно, и вся основная часть идеи. Впрочем, достаточное количество полезной информации удалось получить и впоследствии, пытаясь заставить _правильно_ распаковываться последовательность кодов, полученных многократным повторением вышеописанной схемы. Например, изначально алгоритм декодирования просто запоминал последний встреченный при обходе дерева кодов символ и, когда идти больше было некуда, записывал именно его. Но вдруг, после произведения нескольких замен кодов, начали попадаться неоднозначности распаковки, например такие:

"!" '"' <13> <10>                000.00101 1.01110 1.11111 1.11110
"7" "c" <13> "n"               000.00101.1 01110.1 11111.1 11110

#10 "`" "A" "b" "o"          111110 01.010010.1 10.10110.0 0100.01 1001
"2" "," " " "s" "y" "g"     111110.01 010010 1.10 10110 0.0100 01.1001

(верхняя строка правильная, нижняя получена после замены кодов '"' и "`" соответственно). Я пытался придумать, как с этим бороться, и у меня возникла очередная, достаточно неожиданная, ассоциация с лексическим анализатором и отчего-то показалось, что тут может помочь _стек_ последних символов. Действительно, если предположить, что выход из дерева без определения очередного символа произойдет не сразу, то таким образом можно спасти ситуацию. И ее даже и на самом деле удалось спасти, как ни странно... пока, еще через несколько итераций на том же тестовом файле, не возникли более сложные коллизии, которые так побороть не удалось. Вот тогда-то я и додумался до причины возникновения подобных недоразумений. Все очень просто - заменяя код символа, нужно проверять не только правильность декодирования того, что за ним будет следовать, но и что префикс нового кода не составит с _предыдущим_ символом некий существующий код.

Честно признаюсь, каким образом учитывать еще и это, я не продумывал. Очевидно, необходимо завести еще один масочный буфер, в котором отмечать последовательности битов, отсчитываемые от текущего символа в _обратную_ сторону. Казалось бы, дополнительно необходимо еще и проверять возможность правильного декодирования последовательности символов с заменяемым кодом (накопленных масок тут недостаточно, они считались при другой кодировке), но сам способ генерации новых кодов позволяет этого не делать. Тем не менее, в таком случае не помешало бы не устанавливать масок в случае, если следующий символ равен текущему, чего в данный момент я не делаю, и что, возможно, разрешило бы использовать еще несколько кодов (проверил; что получилось, не понял; финальный размер кода выходит тот же, зато ошибок при работе вываливается на порядок больше; загадочно).

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

4. Терминология и определения

_код_ = последовательность битов.

_префикс_ = последовательность битов, из которой данный код получается приписыванием другого кода, называемого _суффиксом_.

_дерево символов/кодов_ = бинарное дерево, с некоторыми узлами которого связаны символы.

_путь по дереву_ = последовательность выборов одной из двух ветвей узлов дерева, начиная от выделенного узла, называемого _корнем дерева_.

_префиксный код_ = код символа, ни один из префиксов которого не является кодом другого символа.

_контекстно-префиксный код_ = код, позволяющий однозначно определить символ, при условии, что он встречается в заданном множестве кон текстов.

_код выхода_ = код, соответствующий такому пути по дереву символов, что ни одному проходимому узлу не сопоставлен символ (в стеке декодера не остается ни одного символа).

_глубина кода выхода_ = количество элементов символьного стека, используемых при прохождении дерева по коду выхода.

Символу _b_ может быть сопоставлен код _AB_, составленный из суффикса _B_ и кода _A_, соответствующего символу _a_ в том случае, если для всех вхождений символа _a_ в текст будет выполняться:

(контекстно-префиксный код глубины 0)

а) ни одного контекста, в котором за _a_ следует(ют) символы, составляющие код _B_ в тексте нет.

(контекстно-префиксный код глубины 1)

б) ABCDE -> A.BC.DE

1. _BC_ является кодом следующего за _a_ символа, то бишь, существующим кодом.

2. разбиение _ABCDE -> AB.CDE_ невозможно, так как _CD_ является кодом выхода.

(контекстно-префиксный код глубины n)

в) ABCDEFG... -> A.BC.DE.FG...

1. _BC_ является кодом следующего за _a_ символа, то бишь, существующим кодом.

2. _CDEFG..._ является кодом выхода глубины _n-1_.

5. Дополнительные видеоэффекты

Как ни странно, но до того, чтобы проверить тупой алгоритм, описанный где-то в п.3 руки у меня дошли, несмотря ни на какую лень (см. nonpref.exe). А позже, поскольку улучшения, вносимые в алгоритм оптимизации через некоторое время перестали приводить к уменьшению размера сжатого файла, генерируемого на последнем проходе, мне пришлось заняться косметическими изменениями. Например, захотелось хотя бы приблизительно проверить следующую идею: очевидно, что можно биты, составляющие хаффмановские коды символов не сразу записывать в выходной файл, а подавать на вход арифметическому кодировщику и при этом размер результата должен получиться примерно такой же, как для обычного ari (не считая потерь округления, если они есть). (Предполагается, правда, что счетчики частот для ari ассоциированы с каждым узлом дерева Хаффмана.)

На самом деле, возможно, в этом даже есть какой-то высший смысл. В таком случае можно реализовать весьма специфический бинарный вариант арифметического кодировщика, что может позволить увеличить скорость работы, например. Или те самые потери на округление, опять же. Но если код Хаффмана можно заменить "более лучшим" контекстно-префиксным, то почему бы и его не попробовать допаковать арифметикой аналогичным образом? Вот я и попробовал. Результаты получаются достаточно парадоксальные. С одной стороны, вроде бы действительно наблюдается увеличение сжатия и, вроде бы, это и логично - уменьшилось количество битов в потоке, подаваемом на вход ari. С другой - код Хаффмана можно построить по одной таблице частот, анализа последовательностей символов абсолютно не требуется. А в случае с дожиманием ari оптимизированного битового кода мы приходим к необходимости кодировать каким-то образом "лишнюю" информацию о нем, которую невозможно получить из таблицы частот. Остается, например, записывать отличия от дерева Хаффмана... или еще что-нибудь этакое устроить.

А по поводу парадоксальности - я как-то попробовал прогнать свой тест по уже заархивированному файлу (он был маленький, и я предполагал, что там встречаются не все возможные четверки символов и это можно использовать). Получилось очень забавно - моя программа напечатала размер арифметического кода для этого файла (размером порядка 10k) - получилось около сорока байт. Вот тут-то я задумался над тем, сколько информации содержится в структуре дерева контекстно-префиксного кода... Тем не менее, можно предположить, что результаты все же должны выходить лучшие, чем при обычном ari. Не худшие, по крайней мере.

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

...Воспользуюсь случаем, и заодно опишу тут принцип изменения этих самых частот. При помощи всяческой комбинаторики получается, что файлов, подходящих к данной таблице частот f[0]...f[n-1] будет ровно

L (f[0]+...+f[n-1])!
2 = ---------------------
f[0]!*...*f[n-1]!

Поскольку характеристики ari (статического) зависят исключительно от таблицы частот, получаем, что в идеальном случае мы должны закодировать файл ровно в L бит. И что замечательно, так это простота метода, позволяющего этого идеала достичь - просто нужно уменьшать счетчик/частоту символа после его кодирования.

Все это излагалось, собственно, для того, чтобы продемонстрировать печальный факт бесполезности очередной "гениальной" идеи. А как хорошо звучало - "код, лучший, чем оптимальный код Хаффмана". Только вот с применениями как-то туговато получается. Динамическое построение контекстно-префиксного кода по уже обработанной части файла требует совершенно нереального расхода времени, причем, что особенно ценно, практически то же время потребуется и для раскодирования :). Правда, может, если бы удалось изобрести алгоритм, требующий ресурсов порядка алгоритма Хаффмана... А пока остается радоваться хотя бы возможности применения метода в упаковщиках запускаемых файлов.

Впрочем, была еще одна, вовсе завиральная, задумка. Логично, что, раз достаточно архиваторов до сих пор использует кодирование Хаффмана, то можно было бы уменьшить размеры сжатых файлов, применив оптимизированный код. Так вот, а что если попробовать на основе входного файла построить префиксный код, позволяющий его получить, оптимизировать его, и закодировать снова, да еще и, для полного счастья, применяя арифметическое дожатие. Получается, что таким образом можно попробовать уменьшать размер упакованных файлов, даже не зная алгоритма работы соответствующих архиваторов. Это могло бы помочь подсократить сетевой трафик, например...

6. О "физическом смысле"

Ладно. Раз уж не выходит у меня ничего придумать по части поиска правильного алгоритма генерации контекстно-префиксных кодов, можно тогда обсудить принцип действия и возможные обобщения. Для которых, надо сказать простор открылся весьма немалый. Такой, например, вариант: возможно контекстно-префиксные коды представляют собой хорошее дискретное приближение ко все тому же ari. Скажем, главная вещь, которая не реализуема при помощи префиксного кода - невозможно правильно обработать символы, с вероятностью “встречания” большей, чем 1/2. Такие символы должны занимать дробную часть бита, а минимальная длины битового кода, естественно равна единице. Так вот, подобные случаи прекрасно обходятся путем использования кодов выхода. И правда, остается ведь "потерянное" кодовое пространство, позволяющее (теоретически), скажем, добиться ситуации, когда в стеке декодера не останется ни одного символа, а обход дерева согласно входной битовой последовательности, тем не менее, приведет к выходу. Вот что делать в таком случае? А вот если его ассоциировать с символом, имеющим слишком большую частоту, то получится как раз то, что нужно. И я даже придумал (вычитал, на самом деле :), что делать в такой ситуации после выдачи на выход соответствующего символа. В стек-то ничего нового не попало. И последовательность следующих битов все та же. А вот если инвертировать первый бит входного потока и попробовать декодировать так, то может что и получится (естественно, если строить систему кодов соответственно). На самом деле, может быть достаточно много способов приближения Хаффмана к ari, даже не затрагивающих префиксность. Почему бы, скажем, не использовать для представления одного и того же символа _несколько_ кодов, возможно, даже имеющих различную длину.

Но, все же, к вопросу о расширениях и обобщениях. Что если переделать арифметический распаковщик по тому же возвратно-поступательному принципу, который был применен для битового? То есть, разрешить сопоставлять символам пересекающиеся и включающиеся друг в друга интервалы и искать самый узкий, содержащий кодовое слово. Правда интересно? И, главное, не нужно никакого битового кода первым слоем.

Теперь о том, откуда получается выигрыш в сжатии при использовании не-префиксных кодов. Тут все достаточно ясно - какие-то слова/контексты в файле не встречаются, следовательно нет необходимости оставлять для них кодовое пространство, что происходит при применении стандартных методов. Как с этим бороться стандартными методами? Например, можно для каждого символа учитывать предшествующий контекст, разбираться, что может встречаться после него и не оставлять места для того, что появиться не может. Короче, получится какой-нибудь PPM :).

Вот. А контекстно-префиксные коды в данном случае интересны тем, что (кажется) предоставляют возможность учитывать такие вещи заранее - сделать нечто вроде статического PPM'а. Строишь код один раз, анализируя контексты, а потом, даже уже при сжатии можно контекст вовсе и не учитывать. Сам учтётся, если код построен правильно. А распаковщик, соответственно, должен прочитать кодовую таблицу, а дальше - спокойно распаковывать файл посимвольно, не учитывая больше _ничего_. Забавно. И не нужен никакой моделировщик при распаковке...

Такие вот тихие радости. Осталось только взять и изобрести способ построения этой-самой кодовой таблицы. В общем, начать и... Н-да :)

7. Long live Huffman! - новая идея

Тяжелый случай, однако. И никто-то уже не любит старика Хаффмана. Так, по привычке и ради поддержки совместимости пользуются старыми исходниками, или доказывают, что работа с кодом Хаффмана быстрее, в глубине души понимая, что ari лучше все равно. И действительно, видимо расход времени при арифметическом кодировании и на самом деле больше, раз и до сих пор проводится такое количество исследований в поисках более удачной его реализации, не говоря уж о тех десятках патентов, которые уже получены.

А идея простая. Что, если интервал ari разбить на несколько подинтервалов, имеющих длины, равные степеням двойки? Для этого достаточно иметь возможность оперировать двоичным представлением нормализованной длины этого интервала (сумма нормализованных длин интервалов равна 1.0), что крайне просто. А теперь, во-первых достаточно легко, по сравнению со строительством дерева Хаффмана, найти двоичные коды, соответствующие всем этим интервалам, а во-вторых - не нужен никакой ari. Если закодировать нужное число вхождений символа кодом первого подинтервала, следующие - кодом второго и т.д., то мы получим как раз тот же размер сжатого файла, что и при помощи арифметического кодирования. Впрочем, есть еще одна проблема - символы, имеющие вероятность, большую, чем 1/2 не могут, таким образом, быть закодированы меньше, чем в один бит, что, как бы, не есть хорошо. Но это тоже решаемо - такой символ, на самом деле, может быть только один на весь алфавит, следовательно можно с этим справиться за счет дальнейшего расширения алфавита - добавить символы, обозначающие пары слишком вероятного символа с другим и, возможно несколько, соответствующих тиражам этого символа некоторой длины. Таким образом, можно получить алфавит немалого размера, но зато на скорость кодирования это все равно не повлияет. Кроме того, поскольку никто сейчас уже не применяет алгоритмы частотного кодирования непосредственно, а только в качестве очередного уровня, то такая проблема, скорее всего, даже и не возникнет, ведь если какой-то символ имеет вероятность большую, чем 1/2, то это говорит уже о плохом качестве применяемого контекстного анализа.

Вот. А размер выходного файла при применении такого метода, вообще говоря, будет _меньше_, чем при использовании реализаций арифметического кодирования - ведь тут потери округления практически отсутствуют, а те, которые есть легко контролируемы и зависят от разрядности, применяемой для кодирования длины интервала.

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

Заморочено, конечно. Все же, ari, в идеале, - алгоритм гораздо более красивый. Но адаптивные арифметические схемы, да еще оптимизированные по скорости вряд ли проще.

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

Впрочем, увы, название раздела не удалось - данный алгоритм к Хаффману, все же, отношения, вроде бы, не имеет. Впрочем, какая разница...

Кстати, Хаффман еще жив? Кнут-то вряд ли младше...

9. Вопросы

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

? Оптимальный алгоритм/СД для построения дерева Хаффмана по таблице частот.

? Количество узлов в дереве не-префиксного кода.

? Алгоритм построения не-префиксных кодов, однозначно декодирующихся в данном контексте (без проверок).

? Из-за первоначально ошибки в реализации алгоритма Хаффмана удалось установить, что получаемый сейчас код оптимальный ни в коем случае не является. Как получить действительно оптимальный?

? Как паковать непрефиксное кодовое дерево? Собственно, это не вполне понятно и для обычного-то дерева Хаффмана...

? Арифметический код будет (по идее) тем оптимальнее, чем меньшее количество узлов будет в кодовом дереве. Точнее, чем большим будет их повторное использование. Возможно, стоит попробовать оптимизировать код именно с этой точки зрения?

? Если придумать алгоритм _разбиения_ данного файла на поток префиксных кодов, оптимизирующихся в контекстно-префиксные наилучшим образом, то это позволит дожимать файлы, уже пожатые, по крайней мере, архиваторами, использующими Хаффмана вторым слоем. Единственная проблема адаптивное кодирование. Задача состоит в определении некоего "исходного текста", который бы лучше сжимался другими методами. Как же разбирать на префиксные коды файлы, система кодов в которых постоянно меняется? Рассчитывать на некие стандартные способы адаптации?

? Аналогично, можно попробовать найти такой алгоритм разбиения и для результата арифметического кодирования, скажем, если воспользоваться двухуровневой схемой ari-поверх-хаффмана в качестве базовой. В этом может быть смысл?

10. Примеры эффекта от использования не-префиксного кода

Вот примеры обработки нескольких файлов различного происхождения моей тестовой программой. К сожалению, большая часть экспериментов производилась _до_ обнаружения чудной ошибки в алгоритме построения кода Хаффмана, так что данные для примеров, которые были пересчитаны уже после исправления этой ошибки отмечены фразой "correct huffman implementation".

Некоторые пояснения: поскольку тестовая программа работает с файлами, как с последовательностями 16-тибитных символов, появляется возможность попробовать не расширять разрядность символов обычных файлов, а использовать их как есть - считая пары байт, находящиеся в четных позициях за символы. Часть тестовых файлов представляет собой результат действия maxrep - моего аналога алгоритма sequitur, как выяснилось совсем недавно. Они, в частности, обладают ценным свойством - ни одна пара символов не повторяется в них два раза.

tasm.txt        1,481,083 - любимый файл: русское руководство по тасму
huff0000       884,624 - чистый обычный хаффман
huff0001       864,076 - после оптимизации кодов
;correct huffman implementation
huff0000       884,245
huff0001       864,641

more.com     10,503 - more из русского Win95OSR
more #c        3,446 - пожатый maxrep'ом (без словаря)
huff0000       1,894
huff0001       1,861

more_bit #b 4,508 - пожатый maxrep'ом как поток битов (без словаря)
huff0000       2,433
huff0001       2,381

ark1.doc       44,444 - ark1.doc :)
huff0000       28,852
huff0001       28,384

ark1 #m        17,892 - ark1 пожатый maxrep'ом (без словаря)
huff0000       12,125
huff0001       11,980
; correct huffman implementation
huff0000       12,060
huff0001       12,003

huffman zzz 4,522 - модуль от nonpref, как поток _пар символов_
huff0000       2,119
huff0001       2,061

huffman wrd 4,522 - то же, но как поток символов
huff0000       3,088
huff0001       2,817

book1           768,771 - book1 из Calgary Corpus
huff0000       486,068
huff0001       472,624
; correct huffman implementation
huff0000       438,374
huff0001       435,971

acid.com       76,012 - посимвольно
huff0000 #c   65,914
huff0001 #c   65,834
; correct huffman implementation
huff0000        65,886
huff0001        65,810

acid #w           6,012 - парами символов
huff0000 #w   54,597
huff0001 #w   53,253

Далее предлагается отредактированный протокол обработки файла book1 из Calgary Corpus. Ниже следуют таблицы кода Хаффмана и оптимизированного не-префиксного кода для символов, а также данные о размерах файла, закодированного различными способами.

"e" - 000
"s" - 0010
"i" - 0011
"h" - 0100
"n" - 0101
"," - 011000
""" - 01100100
"+" - 0110010100
"P" - 0110010101
"B" - 011001011
"v" - 0110011
"l" - 01101
"o" - 0111
"a" - 1000
"y" - 100100
"f" - 100101
"g" - 100110
"I" - 10011100
"W" - 1001110100
"3" - 100111010100
"(" - 10011101010100
"K" - 10011101010101
"5" - 1001110101011
"2" - 100111010110
"0" - 1001110101110
"U" - 1001110101111
"?" - 1001110110
";" - 1001110111
"'" - 1001111
"t" - 1010
"d" - 10110
"c" - 101110
"m" - 101111
" " - 110
"w" - 111000
"F" - 11100100000
"L" - 11100100001
"!" - 1110010001
"S" - 1110010010
"O" - 1110010011
"Y" - 11100101000
"E" - 11100101001
"x" - 1110010101
":" - 111001011000
"1" - 111001011001
"j" - 11100101101
"A" - 1110010111
"." - 1110011
"u" - 111010
$000A - 111011
"r" - 11110
"T" - 111110000
"H" - 1111100010
"<" - 11111000110
">" - 11111000111
"-" - 11111001
"b" - 1111101
"p" - 1111110
"R" - 111111100000
"J" - 111111100001
"N" - 11111110001
"q" - 11111110010
"z" - 111111100110
"D" - 111111100111
"M" - 11111110100
"G" - 11111110101
"C" - 11111110110
"V" - 11111110111000
"X" - 11111110111001000
$0000 - 11111110111001001000
$001A - 11111110111001001001
"&" - 11111110111001001010
"*" - 11111110111001001011
"=" - 111111101110010011
"Q" - 1111111011100101
")" - 111111101110011
"4" - 1111111011101
"9" - 11111110111100
"7" - 11111110111101
"8" - 11111110111110
"6" - 11111110111111
"k" - 11111111

"e" - 000
"D" - 0000000000
"U" - 0000011110
"<" - 0000111000
"0" - 0000111110
"s" - 0010
"i" - 0011
"*" - 0011010011
"N" - 0011110000
"7" - 0011110110
"1" - 0011111000
"h" - 0100
"q" - 010001001
"K" - 0100010101
"6" - 0100100110
"E" - 0100101100
"n" - 0101
"," - 011000
"C" - 011000000
")" - 0110000101
$001A - 0110000111
"&" - 0110001011
""" - 01100100
"+" - 0110010100
"P" - 0110010101
"B" - 011001011
"v" - 0110011
"L" - 0110011010
"l" - 01101
"V" - 0110101001
"o" - 0111
"J" - 0111010000
"a" - 1000
"z" - 1000000000
"j" - 1000000100
":" - 1000011100
"5" - 1000100001
"=" - 1000100011
"y" - 100100
"f" - 100101
"(" - 1001010101
"g" - 100110
"I" - 10011100
"W" - 1001110100
"Q" - 1001110101
"?" - 1001110110
";" - 1001110111
"'" - 1001111
"t" - 1010
"M" - 101010110
"d" - 10110
"c" - 101110
"m" - 101111
" " - 110
">" - 1100011000
"8" - 1100100110
"Y" - 1100101010
"9" - 1100101110
"R" - 1100111000
"G" - 110110000
"w" - 111000
"2" - 1110010000
"!" - 1110010001
"S" - 1110010010
"X" - 1110010011
"O" - 111001010
"x" - 111001011
"." - 1110011
"F" - 1110011010
"u" - 111010
"4" - 1110100100
$000A - 111011
"r" - 11110
"T" - 111110000
"A" - 111110001
"-" - 11111001
"b" - 1111101
"p" - 1111110
"H" - 111111100
"3" - 1111111010
$0000 - 1111111011
"k" - 11111111

Bitcode Dynamic Ari: 3480301 bits = 435038 bytes.
Bitcode Static Ari: 3480341 bits = 435043 bytes.
Pure Static Bitcode: 3506988 bits = 438374 bytes.

Bitcode Dynamic Ari: 3421430 bits = 427679 bytes.
Bitcode Static Ari: 3421464 bits = 427683 bytes.
Normal Dynamic Ari: 3479843 bits = 434981 bytes.
Normal Static Ari: 3480341 bits = 435043 bytes.
Pure Static Bitcode: 3487768 bits = 435971 bytes.

Желающие знать, что обозначают загадочные названия методов, могут посмотреть объяснение этого, находящееся в файле usage в исходных текстах тестовой программы (не размещена на сайте). По непонятной для меня причине, этот файл был написан по-английски и в настоящий момент никакого желания его переводить почему-то в наличие не имеется.

11. Расчет максимальной высоты дерева Хаффмана

На самом деле "высота дерева" - не совсем то, о чем я хотел сказать. Просто, чтобы избежать тавтологии в оглавлении пришлось переформулировать заголовок :). На самом же деле вопрос состоял несколько в другом: сколько же места в памяти следует отводить для хранения кодов Хаффмана, если предположить, что файлы размером более четырех гигабайт обрабатываться не будут :). Когда в дескрипторе каждого символа все еще находились маски размером по восемь килобайт, я нисколько не колебался, отводя под поле кода 256 бит, то бишь, 32 байта. Но вот когда маски оттуда исчезли... Короче, захотелось мне выяснить теоретически, какова же будет длина самого-самого длинного кода в самом худшем случае.

Рассуждение было следующим: коды назначаются только символам, которые встречались в файле хотя бы раз. А для того, чтобы соорудить самый что ни на есть длинный код, следует добиться, чтобы на каждой итерации строительства дерева Хаффмана обязательно выбирался узел, являющийся потомком одного и того же символа. Логично, что этого можно ожидать в том случае, когда вес этого узла (суммарная частота) всегда оказывается одним из двух минимальных. Также, логично, что следует начать с наименьшей возможной частоты - то есть, 1. Рисуем такое дерево:

#0:1      #1:1      #2:? ...
   ¦        ¦
  0L   #a:2 -1

Теперь необходимо подобрать следующие частоты так, чтобы узел #a остался среди двух минимальных. Поскольку нам необходимо минимизировать сумму частот (чтобы набить больше в тот же объем :), то в данном случае можно позволить себе еще один символ с частотой 1, если все остальные равны, как минимум, двум.

#0:1   #1:1   #2:1   #3:? ...
  |      |      |
 0L #a:2 -1     |
      ¦         |
     1L-  #b:3 --0

А вот дальше мы себе такое позволить не можем: если бы встречался еще хотя бы один символ с частотой 1, именно он и использовался бы вместо #a. А вот частота 2 вполне приемлема.

#0:1   #1:1   #2:1   #3:2   #4:? ...
  ¦      ¦      ¦      ¦
 0L #a:2 -1     ¦      ¦
      ¦         ¦      ¦
     1L- #b:3  --0     ¦
           ¦           ¦
           L-  #c:5  ---

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

В общем, таким образом это все и продолжается, начиная все сильнее и сильнее напоминать нечто до боли знакомое. А! Фибоначчи...

Такое вот дело. Приходим в выводу, что минимальный размер файла, требуемый для того, чтобы получить код Хаффмана длиной _n_, равен

L[n] = 1 + Sum[ f[i], {i,1,n} ]

К некоторому моему удивлению, этот ряд удалось просуммировать абсолютно без всяких проблем даже при моем уровне знания математики. Просто исходя из стандартной формулы для элемента последовательности Фибоначчи

f1 = (1+Sqrt[5])/2
f2 = (1-Sqrt[5])/2
F[x] = (f1^n-f2^n)/Sqrt[5]

и применив формулу суммирования геометрической прогрессии, я пришел к весьма удачному результату:

Sum[ F[i], {i,1,n} ] = F[n+2]-1

из которого следует, что искомая длина файла L[n] равна 1+F[n+2]-1, то есть просто F[n+2].

Таким образом, для того, чтобы узнать максимальную длину кода, возможную при размере файла до 4G необходимо решить неравенство

(f1^(n+2)-f2^(n+2))/Sqrt[5] <= 2^32

К сожалению непосредственно в таком виде его не удалось решить ни мне лично, ни с помощью алгебраической системы "Математика", но особой необходимости в этом, на самом деле, в общем-то и нет, так как при возрастании _n_ член f2^(n+2) весьма быстро стремится к нулю. Следовательно, можно записать асимптотическую, но при этом дающую точные результаты, формулу

f1^(n+2) = L*Sqrt[5]
(n+2)*Log[f1] = Log[L]+Log[5]/2
n = Floor[ (Log[L]+Log[5]/2)/Log[f1] - 2 ]

Таким образом, удалось выяснить, что максимальная длина кода Хаффмана для файла размером до 4G - 45 бит.

В результате чего я и сократил размер кодового поля в дескрипторах символов с 256 до 64-х бит - в целях выравнивания на двойное слово. Кроме того получилась достаточно простая и полезная формула, позволяющая сэкономить некоторое количество памяти, зная характеристики входного файла. (Как можно заметить, основание логарифма в формуле значения не имеет).

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

Такие дела.

12. К вопросу о доказательстве алгоритма Хаффмана

Кто бы мне его рассказал? :) Просто я считаю осмысленным способом доказательства только такой, из которого можно вывести _другой_ алгоритм получения оптимального префиксного кода. А такого мне, увы, изобрести пока не удалось.

13. Библиография

Timothy Bell, Ian H. Witten, John G. Cleary "Modeling for text compression" modeling.txt, anywhere :)
M. Crochemore, F. Mignosi, A. Restivo, S. Salemi "Text Compression Using Antidictionaries"
http://www-igm.univ-mlv.fr/~mac/DCA.html
Mark Nelson "Data Compression Book"
http://lib.inorg.chem.msu.ru:8000/cs-books/programming/compression.tar.gz
Maxim Zakharov "Yet Another Realization of Multiplication Free Arithmetic Code"
http://bbs.ogo.ru/ADEVCOMP/MFARC.RAR
http://www.tnet.sochi.ru/~maxime
comp.compression FAQ
ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/

Евгений Шелвин

Контекстные префиксные коды, которые, на самом деле, вовсе не префиксные (к вопросу об оптимальности кода Хаффмана)