Использование алгоритма расширяющегося префикса для кодирования и схожих пpоцессов

Если окончание текста источника может быть обнаружено из его контекста, то коды исходного алфавита все находятся в интервале codetype, а максимально возможное в этом тексте значение кода будет maxchar. В противном случае, интервал codetype должен быть расширен на один код для описания специального символа "конец файла". Это означает, что maxchar будет на 1 больше значения максимального кода символа исходного текста. Следующая процедура инициализирует дерево кодов. Здесь строится сбалансированное дерево кодов, но на самом деле, каждое начальное дерево будет удовлетворительным до тех пор, пока оно же используется и для сжатия и для развертывания.

procedure initialize;
var
 i: downindex;
 j: upindex;
begin
 for i := 2 to twicemax do
  up[i] := i div 2;
 for j := 1 to maxchar do begin
  left[j] := 2 * j;
  right[j] := 2 * j + 1;
 end
end { initialize };
После того, как каждая буква сжата ( развернута ) с помощью текущей версии дерева кодов, оно должно быть расширено вокруг кода этой буквы. Реализация этой операции показана в следующей процедуре, использующей расширение снизувверх:
procedure splay( plain: codetype );
var
 c, d: upindex { пары узлов для полуобоpота };
 a, b: downindex { вpащаемые наследники узлов };
begin
 a := plain + succmax;
 repeat  { обход снизу вверх получередуемого дерева }
  c := up[a];
  if c # root then begin { оставляемая пара }
  d := up[c];
  { перемена местами наследников пары }
  b := left[d];
  if c = b then begin b := right[d];
  right[d] := a;
  end else  left[d] := a;
  if a = left[c] then left[c] := b;
  else  right[c] := b;
  up[a] := d;
  up[b] := c;
  a := d;
  end else a := c { управление в конце нечетным узлом };
 until a = root;
end { splay };

Чтобы сжать букву исходного текста ее нужно закодировать, используя дерево кодов, а затем передать. Поскольку процесс кодирования производится при обходе дерева от листа к корню, то биты кода записываются в обpатном порядке. Для изменения порядка следования битов процедура compress пpименяет свой стек, биты из которого достаются по одному и передаются процедуре transmit.

procedure compress( plain: codetype );

var

 a: downindex;

 sp: 1..succmax;

 stack: array[upindex] of bit;

begin

 { кодирование }

 a := plain + succmax;

 sp := 1;

 repeat { обход снизу вверх дерева и помещение в стек битов }

  stack[sp] := ord( right[up[a]] = a );

  sp := sp + 1;

  a := up[a];

 until a = root;

 repeat { transmit }

  sp := sp - 1;

  transmit( stack[sp] );

 until sp = 1;

 splay( plain );

end { compress };

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

var

 a: downindex;

begin

 a := root;

 repeat { один раз для каждого бита на маршруте }

  if receive = 0 then a := left[a]

  else  a := rignt[a];

 until a > maxchar;

 splay( a - succmax );

 expand := a - succmax;

end { expand };

Процедуры, управляющие сжатием и развертыванием, просты и представляют собой вызов процедуры initialize, за которым следует вызов либо compress, либо expand для каждой обрабатываемой буквы.
Характеристика алгоритма расширяемого префикса
На практике, расширяемые деревья, на которых основываются коды префикса, хоть и не являются оптимальными, но обладают некоторыми полезными качествами. Прежде всего это скорость выполнения, простой программный код и компактные структуры данных. Для алгоритма расширяемого префикса требуется только 3 массива, в то время как для Л-алгоритма Уитерса, вычисляющего оптимальный адаптированный код префикса, - 11 массивов [10]. Предположим, что для обозначения множества символов исходного текста используется 8 бит на символ, а конец файла определяется символом, находящимся вне 8-битового предела, maxchar = 256, и все элементы массива могут содержать от 9 до 10 битов ( 2 байта на большинстве машин)(3). Неизменные запросы памяти у алгоритма расширяемого префикса составляют приблизительно 9.7К битов (2К байтов на большинстве машин). Подобный подход к хранению массивов в Л-алгоритме требует около 57К битов (10К байтов на большинстве машин ).
Другие широко применяемые алгоритмы сжатия требуют еще большего пространства, например, Уэлч советует для реализации метода Зива-Лемпела [11] использовать хеш-таблицу из 4096 элементов по 20 битов каждый, что в итоге составляет уже 82К битов ( 12К байтов на большинстве машин ). Широко используемая команда сжатия в системе ЮНИКС Беркли применяет код Зива-Лемпела, основанный на таблице в 64К элементов по крайней мере в 24 бита каждый, что в итоге дает 1572К битов ( 196К байтов на большинстве машин ).
В таблица I показано как Л-алгоритм Уиттера и алгоритм расширяющегося префикса характеризуются на множестве разнообразных тестовых данных. Во всех случаях был применен алфавит из 256 отдельных символов, расширенный дополнительным знаком конца файла. Для всех файлов, результат работы Л-алгоритма находится в пределах 5% от H и обычно составляет 2% от H . Результат работы алгоритма расширяющегося префикса никогда не превышает H больше, чем на 20%, а иногда бывает много меньше H .
Тестовые данные включают программу на Си (файл 1), две программы на Паскале (файлы 2 и 3) и раннюю редакцию данной статьи (файл 4). Все 4 текстовые файлы используют множество символов кода ASCII с табуляцией, заменяющей группы из 8 пробелов в начале, и все пробелы в конце строк. Для всех этих файлов Лалгоритм достигает результатов, составляющих примерно 60% от размеров исходного текста, а алгоритм расширения - 70%. Это самый худший случай сжатия, наблюдаемый при сравнении алгоритмов.
Два объектых файла М68000 были сжаты ( файлы 5 и 6 ) также хорошо, как и файлы вывода TEX в формате .DVI ( файл 7 ). Они имеют меньшую избыточность, чем текстовые файлы, и поэтому ни один метод сжатия не может сократить их размер достаточно эффективно. Тем не менее, обоим алгоритмам удается успешно сжать данные, причем алгоритм расширения дает результаты, большие результатов работы Л-алгоритма приблизительно на 10%.
Были сжаты три графических файла, содержащие изображения человеческих лиц ( файлы 8, 9 и 10 ). Они содержат различное число точек и реализованы через 16 оттенков серого цвета, причем каждый хранимый байт описывал 1 графическую точку. Для этих файлов результат работы Л-алгоритма составлял приблизительно 40% от первоначального размера файла, когда как алгоритма расширения - только 25% или 60% от H . На первый взгляд это выглядит невозможным, поскольку H есть теоретический информационный минимум, но алгоритм расширения преодолевает его за счет использования марковских характеристик источников.
Последние 3 файла были искусственно созданы для изучения класса источников, где алгоритм расширяемого префикса превосходит ( файлы 11, 12 и 13 ) все остальные. Все они содержат одинаковое количество каждого из 256 кодов символов, поэтому H одинакова для всех 3-х файлов и равна длине строки в битах. Файл 11, где полное множество символов повторяется 64 раза, алгоритм расширения префикса преобразует незначительно лучше по сравнению с H . В файле 12 множество символов повторяется 64 раза, но биты каждого символа обращены, что препятствует расширению совершенствоваться относительно H . Ключевое отличие между этими двумя случаями состоит в том, что в файле 11 следующие друг за другом символы вероятно исходят из одного поддерева кодов, в то время как в файле 12 это маловероятно. В файле 13 множество символов повторяется 7 раз, причем последовательность, образуемая каждым символом после второго повторения множества, увеличивается вдвое. Получается, что файл заканчивается группой из 32 символов "a", за которой следуют 32 символа "b" и т.д. В этом случае алгоритм расширяемого префикса принимает во внимание длинные последовательности повторяющихся символов, поэтому результат был всего 25% от H , когда как Л-алгоритм никогда не выделял символ, вдвое более распространенный в тексте относительно других, поэтому на всем протяжении кодирования он использовал коды одинаковой длины.
Когда символ является повторяющимся алгоритм расширяемого префикса последовательно назначает ему код все меньшей длины: после по крайней мере 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 |
Ј||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Таблица: Результаты тестирования Л-алгоритма и алгоритма расширяемого префикса
Среди графических данных редко когда бывает, чтобы несколько последовательных точек одной графической линии имели одинаковую цветовую интенсивность, но в пределах любой области с однородной структурой изображения, может быть применено свое распределение статичной вероятности. При сжатии последовательных точек графической линии, происходит присвоение коротких кодов тем точкам, цвета которых наиболее распространены в текущей области. Когда алгоритм переходит от области с одной структурой к области с другой структурой, то короткие коды быстро передаются цветам, более распространенным в новой области, когда как коды уже не используемых цветов постепенно становятся длиннее. Исходя из характера такого поведения, алгоритм расширяемого префикса можно назвать ЛОКАЛЬНО АДАПТИВНЫМ. Подобные локально адаптивные алгоритмы способны достигать приемлимых результатов п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. Оба алгоритма были реализованы на Паскале, сходным по описанию с представленным здесь языком.

Отправить комментарий

Проверка
Антиспам проверка
Image CAPTCHA
...