Когда символ является повторяющимся алгоритм расширяемого префикса после- довательно назначает ему код все меньшей длины: после по крайней мере log n повторений любой буквы n-буквенного алфавита, ей будет соответствовать код длиной всего лишь в 1 бит. Это объясняет блестящий результат применения алго- ритма расширения к файлу 13. Более того, если буквы из одного поддерева дерева кодов имеют повторяющиеся ссылки, алгоритм уменьшит длину кода сразу для всех букв поддерева. Это объясняет, почему алгоритм хорошо отработал для файла 11. +======+========+========+=========+==========+==========+============+ | file | type | bytes | bits | H(s) | bits | splay bits | +======+========+========+=========+==========+==========+============| | 1 | C | 12090 | 96720 | 58880.2 | 60176 | 66344 | | 2 | Pascal | 3632 | 29056 | 16882.0 | 17544 | 19608 | | 3 | Pascal | 9720 | 77760 | 45788.6 | 46704 | 53552 | | 4 | text | 55131 | 441048 | 270814.9 | 274032 | 309496 | | 5 | object | 32207 | 257656 | 193665.3 | 196760 | 206280 | | 6 | object | 41456 | 331648 | 249270.7 | 252312 | 263744 | | 7 | .DVI | 41881 | 335048 | 257542.3 | 260592 | 282304 | | 8 | image | 46187 | 369496 | 147296.7 | 149056 | 94936 | | 9 | image | 60141 | 481128 | 183023.7 | 186032 | 115576 | | 10 | image | 144981 | 1159848 | 506817.1 | 515304 | 262376 | | 11 | test | 16385 | 131080 | 131080.2 | 132552 | 122296 | | 12 | test | 16385 | 131080 | 131080.2 | 132592 | 144544 | | 13 | test | 16385 | 131080 | 131080.2 | 132552 | 32424 | +======+========+========+=========+==========+==========+============+ Таблица I. Результаты тестирования Л-алгоритма и алгоритма расширяемого префикса. Среди графических данных редко когда бывает, чтобы несколько последова- тельных точек одной графической линии имели одинаковую цветовую интенсивность, но в пределах любой области с однородной структурой изображения, может быть применено свое распределение статичной вероятности. При сжатии последователь- ных точек графической линии, происходит присвоение коротких кодов тем точкам, цвета которых наиболее распространены в текущей области. Когда алгоритм пере- ходит от области с одной структурой к области с другой структурой, то короткие коды быстро передаются цветам, более распространенным в новой области, когда как коды уже не используемых цветов постепенно становятся длиннее. Исходя из характера такого поведения, алгоритм расширяемого префикса можно назвать ЛО- КАЛЬНО АДАПТИВНЫМ. Подобные локально адаптивные алгоритмы способны достигать приемлимых результатов пpи сжатии любого источника Маркова, который в каждом состоянии имеет достаточную длину, чтобы алгоритм приспособился к этому состо- янию. Другие локально адаптированные алгоритмы сжатия данных были предложены Кнутом[5] и Бентли et al [1]. Кнут предложил локально адаптированный алгоритм Хаффмана, в котором код, используемый для очередной буквы определяется n пос- ледними буквами. Такой подход с точки зрения вычислений ненамного сложнее, чем простые адаптированные алгоритмы Хаффмана, но соответствующее значение n зави- сит от частоты изменения состояний источника. Бентли et al предлагает исполь- зовать эвристическую технику перемещения в начало ( move-to-front ) для орга- низации списка последних использованных слов ( предполагая, что текст источни- ка имеет лексическую ( словарную ) структуру ) в соединении с локально адапти- рованным кодом Хаффмана для кодирования количества пробелов в списке. Этот код Хаффмана включает периодическое уменьшение весов всех букв дерева посредством умножения их на постоянное число, меньше 1. Похожий подход использован в [12] для арифметических кодов. Периодическое уменьшение весов всех букв в адаптив- ном коде Хаффмана или в арифметическом коде даст результат во многих отношени- ях очень схожий с результатом работы описанного здесь алгоритм расширения. Компактные структуры данных, требуемые алгоритмом расширяемого префикса, позволяют реализуемым моделям Маркова иметь дело с относительно большим числом состояний. Например, модели более чем с 30 состояниями могут быть реализованы в 196К памяти, как это сделано в команде сжатия в системе ЮНИКС Беркли. Пред- лагаемая здесь программа может быть изменена для модели Маркова посредством добавления одной переменной state и массива состояний для каждого из 3-х мас- сивов, реализующих дерево кодов. Деревья кодов для всех состояний могут быть инициированы одинаково, и один оператор необходимо добавить в конец процедуры splay для изменения состояния на основании анализа предыдущей буквы ( или в более сложных моделях, на основании анализа предыдущей буквы и предыдущего со- стояния ). Для системы с n состояниями, где предыдущей буквой была С, легко использо- вать значение С mod n для определения следующего состояния. Такая модель Мар- кова слепо переводит каждую n-ю букву алфавита в одно состояние. Для сжатия текстового, объектного и графического ( файл 8 ) файлов значения n изменялись в пределах от 1 до 64. Результаты этих опытов показаны на рисунке 6. Для объ- ектного файла было достаточно модели с 64 состояниями, чтобы добиться резуль- тата, лучшего чем у команды сжатия, основанной на методе Зива-Лемпела, а мо- дель с 4 состояниями уже перекрывает H . Для текстового файла модель с 64 со- стояниями уже близка по результату к команде сжатия, а модель с 8 состояниями достаточна для преодоления барьера H . Для графических данных ( файл 8 ) моде- ли с 16 состояниями достаточно, чтобы улучшить результат команды сжатия, при этом все модели по своим результатам великолепно перекрывают H . Модели Марко- ва более чем с 8 состояниями были менее эффективны, чем простая статичная мо- дель, применяемая к графическим данным, а самый плохой результат наблюдался для модели с 3 состояниями. Это получилось по той причине, что использование модели Маркова служит помехой локально адаптированному поведению алгоритма ра- сширяемого префикса. +тыс. H Б | и | т 200| сжатие в UNIX ы | | с | ж | а | т 100| о | o---------------o-------------------------------o г | о | o - объектный файл | o - текстовой файл т | o - графический файл е +++-+---+-------+---------------+-------------------------------+ к 2 4 8 16 32 64 с Состояния модели Маркова. т а Рисунок 6. Характеристика алгоритма расширяющегося префикса с марковской моделью. Оба алгоритма, Л- и расширяемого префикса, выполняются по времени прямо пропорционально размеру выходного файла, и в обоих случаях, выход в наихудшем варианте имеет длину O(H ), т.о. оба должны выполняться в худшем случае за время O(H ). Постоянные коэффициенты отличаются, поскольку алгоритм расширяе- мого префикса производит меньше работы на бит вывода, но в худшем случае про- изводя на выходе больше битов. Для 13 файлов, представленных в таблице I, Л- алгоритм выводит в среднем 2К битов в секунду, когда как алгоритм расширяемого префикса - более 4К битов в секунду, т.о. второй алгоритм всегда намного быст- рее. Эти показатели были получены на рабочей станции М68000, серии 200 9836CU Хьюлет Паккард, имеющей OC HP-UX. Оба алгоритма были реализованы на Паскале, сходным по описанию с представленным здесь языком.