Реферат: Сжатие данных

постоянное число, меньше 1. Похожий подход использован и для арифметических

кодов. Периодическое уменьшение весов всех букв в адаптивном коде Хаффмана или в

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

результатом работы описанного здесь алгоритм расширения.

Компактные структуры данных, требуемые алгоритмом расширяемого префикса,

позволяют реализуемым моделям Маркова иметь дело с относительно большим числом

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

196К памяти, как это сделано в команде сжатия в системе ЮНИКС Беркли.

Предлагаемая здесь программа может быть изменена для модели Маркова посредством

добавления одной переменной state и массива состояний для каждого из 3-х

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

бытьинициированы одинаково, и один оператор необходимо добавить в конец

процедуры splay для изменения состояния на основании анализа предыдущей буквы (

или в более сложных моделях, на основании анализа предыдущей буквы и предыдущего

состояния ).

Для системы с n состояниями, где предыдущей буквой была С, легко использовать

значение С mod n для определения следующего состояния. Такая модель Маркова

слепо переводит каждую n-ю букву алфавита в одно состояние. Для сжатия

текстового, объектного и графического ( файл 8 ) файлов значения n изменялись в

пределах от 1 до 64. Результаты этих опытов показаны на рисунке 6. Для

объектного файла было достаточно модели с 64 состояниями, чтобы добиться

результата, лучшего чем у команды сжатия, основанной на методе Зива-Лемпела, а

модель с 4 состояниями уже перекрывает H . Для текстового файла модель с 64

состояниями уже близка по результату к команде сжатия, а модель с 8 состояниями

достаточна для преодоления барьера H . Для графических данных ( файл 8 ) модели

с 16 состояниями достаточно, чтобы улучшить результат команды сжатия, при этом

все модели по своим результатам великолепно перекрывают H . Модели Маркова более

чем с 8 состояниями были менее эффективны, чем простая статичная модель,

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