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

Введение.

Сжатие уменьшает объем места, тpебуемого для хранения файлов в ЭВМ, и

количество времени, нужного для передачи инфы по каналу установленной

ширины пропускания. Это есть форма кодировки. Другими целями кодировки

являются поиск и исправление ошибок, также шифрование. Процесс поиска и

исправления ошибок противоположен сжатию - он наращивает избыточность данных,

когда их Сжатие данных - реферат не надо представлять в комфортной для восприятия человеком форме. Удаляя

из текста избыточность, сжатие содействует шифpованию, что затpудняет поиск

шифpа легкодоступным для взломщика статистическим способом.

Рассмотpим обратимое сжатие либо сжатие без наличия помех, где начальный

текст может быть в точности восстановлен из сжатого состояния. Необратимое либо

ущербное сжатие употребляется для Сжатие данных - реферат цифровой записи аналоговых сигналов, таких как

людская речь либо картинки. Обратимое сжатие в особенности принципиально для текстов,

записанных на естественных и на искусственных языках, так как в данном случае

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

рассматриваемых способов есть сжатие текстов, что отpажает и наша терминология,

но Сжатие данных - реферат, эта техника может отыскать применение и в других случаях, включая обратимое

кодирование последовательностей дискретных данных.

Существует много весомых обстоятельств выделять ресурсы ЭВМ в pасчете на сжатое

представление, т.к. более стремительная передача данных и сокpащение пpостpанства для

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

характеристики ЭВМ. Сжатие возможно Сжатие данных - реферат будет оставаться в сфере внимания из-за все

растущих объемов хранимых и передаваемых в ЭВМ данных, не считая того его можно

использовать для преодоления некотоpых физических ограничений, таких как,

напpимеp, сравнимо низкая шиpину пpопускания телефонных каналов.

ПРИМЕНЕНИЕ РАСШИРЯЮЩИХСЯ ДЕРЕВЬЕВ ДЛЯ СЖАТИЯ ДАННЫХ.

Методы сжатия могут увеличивать эффективность хранения и передачи Сжатие данных - реферат данных

средством сокращения количества их избыточности. Метод сжатия берет в

качестве входа текст источника и производит соответственный ему сжатый текст,

когда как разворачивающий метод имеет на входе сжатый текст и получает из

него на выходе начальный текст источника. Большая часть алгоритмов сжатия

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

начального текста.

Избыточность в представлении строчки S есть L(S) - H(S), где L(S) есть длина

представления в битах, а H(S) - энтропия - мера содержания инфы, также

выраженная в битах. Алгоритмов, которые могли бы без утраты инфы сжать

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

начального текста извлекать по одной буковке некого случайного набоpа,

использующего алфавит А, то энтропия находится по формуле:

--¬ 1

H(S) = C(S) p(c) log ---- ,

c A p(c)

где C(S) есть количество букв в строке, p(c) есть статическая Сжатие данных - реферат возможность

возникновения некой буковкы C. Если для оценки p(c) применена частота возникновения

каждой буковкы c в строке S, то H(C) именуется самоэнтропией строчки S. В этой

статье H (S) будет употребляться для обозначения самоэнтропии строчки, взятой из

статичного источника.

Расширяющиеся деревья обычно обрисовывают формы словарной упорядоченности

деpевьев двоичного поиска, но Сжатие данных - реферат деревья, применяемые при сжатии данных могут не

иметь неизменной упорядоченности. Устранение упорядоченности приводит к

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

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

pасширение приводит к локально приспособленному методу сжатия, котоpый

замечательно прост и резв, хотя Сжатие данных - реферат и не позволяет добиться рационального сжатия.

Когда он применяется к арифметическим кодам, то итог сжатия близок к

хорошему и примерно оптимален по времени.

КОДЫ ПРЕФИКСОВ.

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

Хаффмана. В коде Хаффмана любая буковка начального текста представляется в архиве

кодом переменной длины Сжатие данных - реферат. Более нередкие буковкы представляются маленькими кодами,

наименее нередкие - длинноватыми. Коды, применяемые в сжатом тексте должны подчиняться

свойствам префикса, а конкретно: код, использованный в сжатом тексте не может быть

префиксом хоть какого другого кода.

Коды префикса могут быть найдены средством дерева, в каком каждый лист

соответствует одной буковке алфавита источника. Hа Сжатие данных - реферат pисунке 1 показано дерево кода

префикса для алфавита из 4 букв. Код префикса для буковкы может быть прочитан при

обходе деpева от корня к этой буковке, где 0 соответствует выбору левой его ветки,

а 1 - правой. Дерево кода Хаффмана есть дерево с выравненным весом, где каждый

лист имеет вес, равный частоте встречаемости буковкы в начальном Сжатие данных - реферат тексте, а

внутренние узлы собственного веса не имеют. Дерево в примере будет хорошим, если

частоты букв A, B, C и D будут 0.125, 0.125, 0.25 и 0.5 соответственно.

Обыденные коды Хаффмана требуют подготовительной инфы о частоте встречаемости

букв в начальном тексте, что ведет к необходимости его двойного просмотра - один

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

следующем, значения этих частот необходимо соединять воединыжды с самим сжатым текстом, чтоб

в предстоящем сделать вероятным его развертывание. Адаптивное сжатие производится

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

на частотах всех других кpоме нее букв Сжатие данных - реферат алфавита. Базы для действенной

реализации адаптивного кода Хаффмана были заложены Галлагером, Кнут опубликовал

практическую версию такового метода, а Уиттер его pазвил.

Лучший приспособленный код Уиттера всегда лежит в границах 1-го бита на

буковку источника по отношению к хорошему статичному коду Хаффмана, что обычно

составляет несколько процентов от H Сжатие данных - реферат . К тому же, статичные коды Хаффмана всегда

лежат в границах 1-го бита на буковку начального текста от H ( они добиваются этот

предел только когда для всех букв p(C) = 2 ). Есть методы сжатия

которые могут преодолевать эти ограничения. Метод Зива-Лемпелла, к примеру,

присваивает слова из аpхива фиксированной длины Сжатие данных - реферат строчкам начального текста

пеpеменной длины, а арифметическое сжатие может использовать для кодировки

букв источника даже толики бита.

Применение расширения к кодам префикса.

Расширяющиеся деревья были в первый раз описаны в 1983 году и поболее подpобно

рассмотрены в 1985. Сначало они понимались как вид самосбалансиpованных

деpевьев двоичного поиска, и было также показано, что они позволяют Сжатие данных - реферат выполнить

самую резвую реализацию приоритетных очередей. Если узел расширяющегося дерева

доступен, то оно является расширенным. Это означает, что доступный узел становится

корнем, все узлы слева от него образуют новое левое поддерево, узлы справа -

новое правое поддерево. Расширение достигается при обходе дерева от старенького

корня к мотивированному узлу Сжатие данных - реферат и совершении пpи этом локальных конфигураций, потому стоимость

расширения пропорциональна длине пройденного пути.

Тарьян и Слейтон проявили, что расширяющиеся деревья статично оптимальны.

Другими словами, если коды доступных узлов взяты согласно статичному

рассредотачиванию вероятности, то скорости доступа к расширяющемуся дереву и

статично равновесному, оптимизированному этим рассредотачиванием, будут

отличаться друг Сжатие данных - реферат от друга на неизменный коэффициент, приметный при довольно

длинноватых сериях доступов. Так как дерево Хаффмана представляет собой пример

статично равновесного дерева, то пpи использовании расширения для сжатия

данных, pазмер сжатого текста будет лежать в границах некого коэффициента от

размера архива, приобретенного при использовании кода Хаффмана.

Как было сначало описано, расширение применяется Сжатие данных - реферат к деревьям, хранящим

данные во внутренних узлах, а не в листьях. Деревья же кодов префикса несут все

свои данные исключительно в листьях. Существует, но, вариант расширения, именуемый

полурасширением, который применим для дерева кодов префикса. При нем мотивированной

узел не перемещается в корень и модификация его наследников не делается,

взамен путь Сжатие данных - реферат от корня до цели просто миниатюризируется в два раза. Полурасширение добивается

тех же теоретических границ в границах неизменного коэффициента, что и

расширение.

В случае извилистого обхода словарного дерева, проведение как

расширения, так и полурасширения усложняется, в отличие от прямого маршрута по

левому либо правому краю дерева к Сжатие данных - реферат мотивированному узлу . Этот обычной случай показан на

рисунке 2. Воздействие полурасширения на маршруте от корня ( узел w ) до листа

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

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

2 раза. В процессе полурасширения узлы каждой Сжатие данных - реферат пары, более дальние от корня,

врубаются в новый путь ( узлы x и z ), а более близкие из него

исключаются ( узлы w и y ).

Сохранение операцией полурасширения словарного порядка в деревьях кода

префикса не является неотклонимым. Единственно принципиальным в операциях с кодом

префикса является четкое соответствие дерева, применяемого процедурой Сжатие данных - реферат сжатия

дереву, применяемому процедурой развертывания. Хоть какое его изменение, допущенное

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

обе процедуры производят однообразные конфигурации в схожем порядке.

Hенужность поддержки словарного порядка существенно упрощает проведение

операции полурасширения за счет исключения варианта зигзага. Это может быть

изготовлено проверкой узлов на Сжатие данных - реферат пути от корня к мотивированному листу и переменой местами

правых наследников с их братьями. Назовем это ПОВОРОТОМ дерева. Тепеpь новый код

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

самым левым листом. На рисунке 3 дерево было повернуто вокруг листа C. Эта

операция не нарушает Сжатие данных - реферат никаких ограничений представления полурасширения.

2-ое упрощение появляется, когда мы обнаруживаем, что можем по желанию поменять

меж собой не только лишь наследников 1-го узла, да и все внутренние узлы дерева

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

поменять применяемую в полурасширении операцию обоpота на операцию, требующую

обмена Сжатие данных - реферат только меж 2-мя звеньями в цепи, которую будем именовать ПОЛУОБОРОТОМ.

Она показано на рисунке 4. Эта операция оказывает такое же воздействие на длину пути

от каждого листа до корня, как и полный обоpот, но уничтожает словарный

порядок, выполняя в нашем примере отсечение и пересадку всего 2-ух веток на

дереве, в Сжатие данных - реферат то время как полный обоpот производит отсечение и пересадку 4

веток.

Истинной необходимости поворачивать дерево перед операцией полурасширения нет.

Заместо этого полурасширение может быть использовано к маршруту от корня к мотивированной

верхушке как к самому левому пути. К примеру, дерево на рисунке 3 может быть

расширено впрямую как показано на Сжатие данных - реферат рисунке 5. В этом примере дерево

полурасширяется вокруг листа C, используя полуобоpот для каждой пары внутренних

узлов на пути от C к корню. Необходимо направить внимание на то, что в итоге этой

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

бы деpево было поначалу повернуто так, что C был Сжатие данных - реферат самым левым листом, а потом

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

внутренних узлов и переменой местами наследников неких из их.

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

различающиеся меж собой четной либо нечетной длиной пути от корня к листу. В

случае нечетной Сжатие данных - реферат длины узел на этом пути не имеет пары для роли в обоpоте либо

полуобоpоте. Потому, если пары строятся снизу ввысь, то будет пропущен корень,

если напротив, то последний внутренний узел. Представленная тут реализация

нацелена на подход сверху-вниз.

Метод расширяемого префикса.

Представленная тут программка написана по правилам языка Паскаль с выражениями Сжатие данных - реферат,

имеющими неизменное значение и подставляемыми в качестве констант для увеличения

читаемости программки. Структуры данных, применяемые в примере, реализованы на

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

использовании записей и ссылок. Это соответствует форме представления из ранешних

работ по этой же теме [5,10], также Сжатие данных - реферат позволяет производить и обычное

решение в более старенькых, но обширно применяемых языках, таких как Фортран, и

малогабаритное представление указателей. Каждый внутренний узел в дереве кодов

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

метод для этого - использовать для каждого узла 3 указателя: на лево, на право и

ввысь Сжатие данных - реферат. Такое представление, обсуждаемое в [9] было реализовано только с помощью

2-ух указателей на узел(2), но при всем этом малогабаритное хранение их в памяти будет

возмещено возрастанием продолжительности выполнения программки и запутанностью ее

кода. Нам потребуются последующие главные структуры данных:

const

maxchar = ... { наибольший код знака начального текста };

succmax = maxchar Сжатие данных - реферат + 1;

twicemax = 2 * maxchar + 1;

root = 1;

type

codetype = 0..maxchar { кодовый интервал для знаков начального текста };

bit = 0..1;

upindex = 1..maxchar;

downindex = 1..twicemax;

var

left,right: array[upindex] of downindex;

up: array[downindex] of upindex;

Типы upindex и downindex употребляются для указателей ввысь и вниз по дерева

кодов. Указатели вниз обязаны иметь возможность указывать и на листья Сжатие данных - реферат, и на

внутренние узлы, в то время как ссылки ввысь указывают лишь на внутренние

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

меж 1 и maxchar включительно будут использованы для обозначения ссылок на

внутренние узлы, когда как значения индексов меж maxchar + 1 и 2 * maxchar + 1

включительно - ссылок на листья. Заметим что Сжатие данных - реферат корень дерева всегда находится в

1-ой ячейке и имеет неопределенного родителя. Cоотвествующая листу буковка может

быть найдена вычитанием maxchar + 1 из его индекса.

Если окончание текста источника может быть найдено из его контекста, то коды

начального алфавита все находятся в интервале 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 массивов . Представим, что для обозначения огромного количества знаков

начального текста употребляется 8 бит на знак, а конец файла определяется

эмблемой, находящимся Сжатие данных - реферат вне 8-битового предела, maxchar = 256, и все элементы

массива могут содержать от 9 до 10 битов ( 2 б на большинстве машин)(3).

Постоянные запросы памяти у метода расширяемого префикса составляют

примерно 9.7К битов (2К байтов на большинстве машин). Схожий подход к

хранению массивов в Л-алгоритме просит около 57К битов (10К байтов на

большинстве Сжатие данных - реферат машин ).

Другие обширно используемые методы сжатия требуют еще большего места,

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

хеш-таблицу из 4096 частей по 20 битов каждый, что в конечном итоге составляет уже82К

битов ( 12К байтов на большинстве машин ). Обширно применяемая команда сжатия в

системе ЮНИКС Сжатие данных - реферат Беркли применяет код Зива-Лемпела, основанный на таблице в 64К

частей по последней мере в 24 бита каждый, что в конечном итоге дает 1572К битов ( 196К

байтов на большинстве машин ).

В таблице I показано как Л-алгоритм Уиттера и метод расширяющегося префикса

характеризуются на огромном количестве различных тестовых данных. Во Сжатие данных - реферат всех случаях был

использован алфавит из 256 отдельных знаков, расширенный дополнительным знаком

конца файла. Для всех файлов, итог работы Л-алгоритма находится в границах

5% от H и обычно составляет 2% от H . Итог работы метода расширяющегося

префикса никогда не превосходит H больше, чем на 20%, а время от времени бывает много меньше Сжатие данных - реферат

H .

Тестовые данные включают программку на Си (файл 1), две программки на Паскале

(файлы 2 и 3) и случайный текстовый файл (файл 4). Все текстовые файлы

употребляют огромное количество знаков кода ASCII с табуляцией, заменяющей группы из 8

пробелов сначала, и все пробелы в конце строк. Для всех этих файлов Лалгоритм

добивается результатов, составляющих приблизительно 60% от Сжатие данных - реферат размеров начального текста, а

метод расширения - 70%. Это самый худший случай сжатия, наблюдаемый при

сопоставлении алгоритмов.

Два объектых файла М68000 были сжаты ( файлы 5 и 6 ) также отлично, как и файлы

вывода TEX в формате .DVI ( файл 7 ). Они имеют наименьшую избыточность, чем

текстовые файлы, и потому ни один способ Сжатие данных - реферат сжатия не может уменьшить их размер

довольно отлично. Все же, обоим методам удается удачно сжать

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

Л-алгоритма примерно на 10%.

Были сжаты три графических файла, содержащие изображения человечьих лиц (

файлы 8, 9 и 10 ). Они содержат различное число точек и реализованы через 16

цветов сероватого цвета, при Сжатие данных - реферат этом каждый хранимый б описывал 1 графическую точку.

Для этих файлов итог работы Л-алгоритма составлял примерно 40% от

начального размера файла, когда как метода расширения - только 25% либо

60% от H . На 1-ый взор это смотрится неосуществимым, так как H есть

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

счет использования Сжатие данных - реферат марковских черт источников.

Последние 3 файла были искусственно предназначены для исследования класса источников, где

метод расширяемого префикса превосходит ( файлы 11, 12 и 13 ) все другие.

Они все содержат однообразное количество каждого из 256 кодов знаков, потому H

схожа для всех 3-х файлов и равна длине строчки в битах. Файл 11, где полное Сжатие данных - реферат

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

некординально лучше по сопоставлению с H . В файле 12 огромное количество знаков повторяется

64 раза, но биты каждого знака обращены, что препятствует расширению

совершенствоваться относительно H . Ключевое отличие меж этими 2-мя вариантами

заключается в том, что в файле 11 последующие вереницей знаки возможно исходят Сжатие данных - реферат

из 1-го поддерева кодов, в то время как в файле 12 это маловероятно. В файле

13 огромное количество знаков повторяется 7 раз, при этом последовательность, образуемая

каждым эмблемой после второго повторения огромного количества, возрастает в два раза.

Выходит, что файл завершается группой из 32 знаков "a", за которой

следуют 32 знака "b" и Сжатие данных - реферат т.д. В данном случае метод расширяемого префикса

воспринимает во внимание длинноватые последовательности циклических знаков, потому

итог был всего 25% от H , когда как Л-алгоритм никогда не выделял знак,

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

протяжении кодировки он использовал коды схожей длины.

Когда знак является циклическим Сжатие данных - реферат метод расширяемого префикса

поочередно назначает ему код все наименьшей длины: после по последней мере log n

повторений хоть какой буковкы n-буквенного алфавита, ей будет соответствовать код

длиной всего только в 1 бит. Это разъясняет блестящий итог внедрения

метода расширения к файлу 13. Более того, если буковкы из 1-го Сжатие данных - реферат поддерева

дерева кодов имеют повторяющиеся ссылки, метод уменьшит длину кода сходу для

всех букв поддерева. Это разъясняет, почему метод отлично отработал для файла

11.

Посреди графических данных изредка когда бывает, чтоб несколько поочередных

точек одной графической полосы имели схожую цветовую интенсивность, но в

границах хоть какой области с однородной Сжатие данных - реферат структурой изображения, может быть использовано

свое рассредотачивание статичной вероятности. При сжатии поочередных точек

графической полосы, происходит присвоение маленьких кодов тем точкам, цвета

которых более всераспространены в текущей области. Когда метод перебегает от

области с одной структурой к области с другой структурой, то недлинные коды

стремительно передаются цветам, более всераспространенным в Сжатие данных - реферат новейшей области, когда как коды

уже не применяемых цветов равномерно становятся длиннее. Исходя из нрава

такового поведения, метод расширяемого префикса можно именовать ЛОКАЛЬНО

АДАПТИВНЫМ. Подобные локально адаптивные методы могут достигать приемлимых

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

имеет достаточную длину, чтоб метод приспособился к Сжатие данных - реферат этому состоянию.

Другие локально приспособленные методы сжатия данных были предложены Кнутом и

Бентли . Кнут предложил локально приспособленный метод Хаффмана, в каком

код, применяемый для очередной буковкы определяется n последними знаками. Таковой

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

методы Хаффмана, но соответственное значение n находится в Сжатие данных - реферат зависимости от частоты конфигурации

состояний источника. Бентли предлагает использовать эвристическую технику

перемещения в начало ( move-to-front ) для организации перечня последних

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

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

для кодировки количества пробелов в перечне. Этот код Хаффмана включает

периодическое уменьшение Сжатие данных - реферат весов всех букв дерева средством умножения их на

неизменное число, меньше 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 состояниями были наименее эффективны, чем обычная статичная модель Сжатие данных - реферат,

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

с 3 состояниями. Это вышло по той причине, что внедрение модели Маркова

служит помехой локально приспособленному поведению метода расширяемого

префикса.

Оба метода, Л- и расширяемого префикса, производятся по времени прямо

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

варианте имеет длину O(H ), т.о. оба должны производиться в худшем случае за время

O(H ). Неизменные коэффициенты отличаются, так как метод расширяемого

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

выходе больше битов. Для 13 файлов, представленных в таблице I, Лалгоритм Сжатие данных - реферат

выводит в среднем 2К битов за секунду, когда как метод расширяемого префикса -

более 4К битов за секунду, т.о. 2-ой метод всегда намного резвее. Эти

характеристики были получены на рабочей станции М68000, серии 200 9836CU Хьюлет

Паккард, имеющей OC HP-UX. Оба метода были реализованы на Паскале, схожим по

описанию с представленным тут Сжатие данных - реферат языком.

АРИФМЕТИЧЕСКИЕ КОДЫ.

Tекст, приобретенный при сжатии арифметических данных, рассматривается в качестве

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

открытого справа интервала [0,1). Текст источника можно рассматривать как

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

буковка в алфавите употребляется в качестве числа, а интервал значений, связанных Сжатие данных - реферат с

ней находится в зависимости от частоты встречаемости этой буковкы. 1-ая буковка сжатого текста

(самая "означающая" цифра) может быть декодирована нахождением буковкы, полуинтеpвал

которой включает значение пpедставляющей текст дроби. После определения

очередной буковкы начального текста, дробь пересчитывается для нахождения

последующей. Это осуществляется вычитанием из дроби базы связанной с Сжатие данных - реферат отысканной

буковкой подобласти, и делением результата на ширину ее полуинтервала. После

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

В качестве примера арифметического кодировки разглядим алфавит из 4-х букв

(A, B, C, D) с вероятностями ( 0.125, 0.125, 0.25, 0.5 ). Интервал [ 0,1) может

быть разбит последующим образом:

A = [ 0, 0.125 ), B = [ 0.125, 0.25 ), C = [ 0.25, 0.5 ), D = [ 0.5, 1 ).

Деление интервала просто осуществляется Сжатие данных - реферат средством скопления вероятностей

каждой буковкы алфавита и ее предшественников. Дан сжатый текст 0.6 (

представленный в виде десятичной дроби ), тогда первой его буковкой должна быть D,

так как это число лежит в интервале [ 0.5, 1 ). Пересчет дает итог:

( 0.6 - 0.5 ) / 0.5 = 0.2

2-ой буковкой будет B, т.к. новенькая дробь лежит в интервале [ 0.125, 0.25 ).

Пересчет дает:

( 0.2 - 0.125 ) / 0.125 = 0.6.

Это означает, что 3-я Сжатие данных - реферат буковка есть D, и начальный текст при отсутствии инфы о

его длине, будет циклической строчкой DBDBDB ...

Первоочередной неувязкой тут является высочайшая точность математики для

осознания и опеpиpования со сплошным битовым потоком, каковым смотрится сжатый

текст, рассматриваемый в качестве числа. Эта неувязка была решена в 1979 году.

Эффективность сжатия способом статичного арифметического Сжатие данных - реферат кодировки будет равна

H , только при использовании математики неограниченной точности. Да и

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

очень не плохое сжатие. Целых переменных длиной 16 битов, 32-битовых произведений

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

нескольких процентах от предела и был чуть Сжатие данных - реферат ли не всегда малость лучше, чем у

рационального приспособленного кода Хаффмана, предложенного Уитером.

Как и в случае кодов Хаффмана, статичные арифметические коды требуют 2-ух

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

коды требуют действенного метода для поддержания и конфигурации инфы о

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

этого - завести счетчик для каждой буковкы, увеличивающий свое значение на единицу

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

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

числом ее возникновений и числом возникновений ее предшественников Сжатие данных - реферат. Этот обычной подход

может востребовать O(n) операций над буковкой n-арного алфавита. В реализованном на

Си Уиттеном, Нейлом и Клири методе сжатия арифметических данных, среднее

значение было усовершенствовано средством использования дисциплины move-to-front, что

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

обрабатывается буковка.

Предстоящее улучшение организации рассредотачивания скопленной Сжатие данных - реферат частоты просит

коренного отхода от обычных СД. Требования, которым должна отвечать эта СД лучше

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

операциями: initialize, update, findletter, findrange и maxrange. Операция

инициализации устанавливает частоту всех букв в 1, и хоть какое не равное нулю

значение Сжатие данных - реферат будет действовать до того времени, пока метод кодировки и

раскодирования употребляют схожие исходные частоты. Изначальное значение

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

т.о. предупреждая его от передачи либо получения.

Операция update(c) наращивает частоту буковкы с. Функции findletter и findrange

обратны друг дружке, и update может делать Сжатие данных - реферат хоть какое изменение порядка алфавита,

пока сохраняется эта оборотная связь. В хоть какой момент времени findletter ( f, c,

min, max ) будет возвращать буковку c и связанный с нею накапливаемый частотный

интервал [ min, max ), где f [ min, max ). Оборотная функция findrange( c, min,

max ) будет возвращать значения min Сжатие данных - реферат и max для данной буковкы c.

Функция maxrange возвращает сумму всех частот всех букв алфавита, она нужна

для перечисления скопленных частот в интервале [ 0, 1 ).

Применение расширения к арифметическим кодам.

Ключом к реализации СД, накапливающей значение частот и в худшем случае

требующей для каждой буковкы наименее, чем O(n) операций для n-буквенного алфавита Сжатие данных - реферат,

является представление букв алфавита в качестве листьев дерева. Каждый лист

дерева имеет вес, равный частоте встречаемой буковкы, вес каждого узла

представляет собой сумму весов его наследников. Набросок 7 показывает такое

дерево для 4-х-буквенного алфавита ( A, B, C, D ) с вероятностями ( 0.125,

0.125, 0.25, 0.5 ) и частотами ( 1, 1, 2, 4 ). Функция maxrange на таком дереве Сжатие данных - реферат

рассчитывается тривиально - она просто возвращает вес корня. Функции update и

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

findletter - от корня к листу.

СД для представления дерева накапливаемых частот по существу такие же, как

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

массива, хранящего Сжатие данных - реферат частоты каждого узла.

const

maxchar = ... { maximum source character code };

succmax = maxchar + 1;

twicemax = 2 * maxchar + 1;

root = 1;

type

codetype = 0..maxchar { source character code range };

bit = 0..1;

upindex = 1..maxchar;

downindex = 1..twicemax;

var

up: array[downindex] of upindex;

freq: array[downindex] of integer;

left,right: array[upindex] of downindex;

Инициализация этой структуры содержит в себе не только лишь построение древовидной Сжатие данных - реферат

СД, да и инициализацию частот каждого листа и узла последующим образом:

procedure initialize;

var

u: upindex;

d: downindex;

begin

for d := succmax to twicemax do freq[d] := 1;

for u := maxchar downto 1 do begin

left[u] := 2 * u;

right[u] := ( 2 * u ) + 1;

freq[u] := freq[left[u]] + freq[right[u]];

up[left Сжатие данных - реферат[u]] := u;

up[right[u]] := u;

end;

end { initialize };

Для того, чтоб найти буковку и соответственный ей интервал скопленной

частоты, когда известна отдельная скопленная частота, нужно обойти дерево

начиная с корня по направлению к буковке, производя беглое вычисление интервала

частот, соответственного текущей ветке дерева. Интервал, соответственный корню,

есть [0, freq[root]], он Сжатие данных - реферат должен содержать f. Если отдельный узел деpева i связан

с интервалом [a, b), где a - b = freq[i], то интервалами, связанными с 2-мя

поддеревьями будут интервалы [a, a+freq[left[i]] ) и [a+freq[left[i]], b). Они

не пересекаются, потому путь вниз по дереву будет таким, что f Сжатие данных - реферат содержится в

подинтервале, связанном с каждым узлом на этом пути. Это показано в

последующей процедуре:

procedure findsymbol( f: integer; var c: codetype; var a, b: integer );

var

i: downindex;

t: integer;

begin

a := 0;

i := root;

b := freq[root];

repeat

t := a + freq[left[i]];

if f < t then begin { повоpот влево Сжатие данных - реферат }

i := left[i];

b := t;

end else begin { повоpот напpаво }

i := right[i];

a := t;

end;

until i > maxchar;

c := i - succmax;

end { findsymbol };

Чтоб отыскать связанный с буковкой частотный интервал, процесс, описанный в

findsymbol должен происходить в оборотном направлении. Сначало единственной

информацией, известной о буковке узла дерева i Сжатие данных - реферат, есть частота этой буковкы freq[i].

Это значит, что интервал [0, freq[i]) будет соответствовать какойлибо буковке,

если весь алфавит состоит из нее одной. Дано: интервал [a, b) связан с неким

листом поддерева с корнем в узле i, тогда может быть вычислен интервал,

связанный с этим листом в поддереве up[i Сжатие данных - реферат]. Если i - левый наследник, то это

просто интервал [ a, b ), если правый, то - [ a + d, b + d ), где

d = freq[up[i]] - freq[i], либо, что одно и то же: d = freq[left[up[i]]].

procedure findrange( c: codetype; var a, b: integer );

var

i: downindex;

d: integer;

begin

a := 0;

i := c + succmax Сжатие данных - реферат;

b := freq[i];

repeat

if right[up[i]] = i then begin { i is right child }

d := freq[left[up[i]]];

a := a + d;

b := b + d;

end;

i := up[i];

until i = root;

end { findrange };

Если неувязка сохранения сбалансированности в дереве накапливаемых частот не

стоит, то функция update будет Сжатие данных - реферат очевидной, состоящей из обхода дерева от

изменяемого листа до корня, сопровождающегося повышением значения каждого

встреченного узла на единицу. В неприятном случае время, затраченное на операции

findletter, findrange и update при сначало равновесном дереве будет в

сpеднем O(log n) на одну буковку для n-буквенного алфавита. Это лучше, чем худший

вариант Сжатие данных - реферат O(n), достигаемый средством внедрения линейной СД (с организацией

move-to-front либо без нее ), но может быть усовершенствовано еще.

Заметьте, что любая буковка, сжатая арифметическим способом просит воззвания к

процедуре findrange, за которым следует вызов update. Т.о. путь от корня к буковке

в дереве накапливаемых частот Сжатие данных - реферат будет проделан два раза во время сжатия и два раза во

время развертывания. Минимизация общего времени сжатия либо развертывания

сообщения просит минимизации общей длины всех путей, пройденных в дереве. Если

частоты букв известны заблаговременно, то статичное дерево Хаффмана будет минимизировать

длину этого маршрута! Длина пути для сообщения S будет ограничена Сжатие данных - реферат значением

2(Hs(S) + C(S)), где C(S) - количество букв в строке, а множитель 2 отражает тот

факт, что каждый маршрут проходится два раза.

Нет смысла в использовании дерева накапливаемых частот, если все вероятности

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

нахождения вероятностей. Если они Сжатие данных - реферат неопознаны, то лучший Л-алгоритм Уиттера

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

при этом длина пути обхода дерева, имеющая место во время сжатия либо развертывания

не будет превосходить значение 2( H (S) + C(S) ). Аналогично можно использовать

метод расширяющегося префикса, дающего ограничение O(H (S)) для длины пути,

но при Сжатие данных - реферат большем неизменном множителе. Ранее пpиведенные бывалые результаты

демонстрируют, что эти неизменные множители более чем компенсируются простотой

метода расширяющегося префикса.

В согласовании с этим методом операции расширения не надо затрагивать

инфы внутренних узлов дерева. Когда расширение производится как часть

операции update, любая операция полувpащения должна защищать инвариацию

регулирования Сжатие данных - реферат весов узлов дерева. На рисунке 8 дерево полувpащается вокруг А,

имея результатом то, что вес Х сокращается весом А и нарастает весом С. В то

же время, так как это есть часть повторного пути от А к корню, вес А

возрастает. Итоговый код будет:

procedure update( c: codetype );

var

c, d: upindex { пара полувpащаемых Сжатие данных - реферат узлов };

a, b: downindex { наследники полувpащемых узлов };

begin

a := c + 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;

freq[c] := ( freq[c] - freq[a] ) + freq[b];

freq[a] := freq[a] + 1;

a := d;

end else begin { помещение непарного ( нечетного ) узла в конец пути }

freq[a] := freq Сжатие данных - реферат[a] + 1;

a := up[a];

end;

until a = root;

freq[root] := freq[root] + 1;

end { update };

Программка игнорирует делему переполнения счетчиков частот. Арифметическое

сжатие данных повсевременно производит вычисление по формуле a * b / c, и предел

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

промежным произведениям и делимым, а не самим Сжатие данных - реферат целочисленным перемен ным.

Многие 32-битные машины накладывают 32-битовое ограничение на произведения и

делимые, и т.о. по сути устанавливают 16-битовый предел на представление

целых чисел a, b и c в вышеуказанном выражении. Когда это ограничение передается

коду самой программке архиватора, то незапятнанный итог имеет ограничение в 16383

для наибольшего значения Сжатие данных - реферат, возвращаемого функцией maxrange либо значения

freq[root]. Потому, если сжатый файл имеет длину более 16383 байтов, нужно

временами пересчитывать все частоты в СД, чтоб втиснуть их в этот интервал.

Обычной путь для этого - поделить значения всех частот на небольшую константу,

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

Значения листьев в дереве Сжатие данных - реферат накапливаемых частот просто могут быть пересчитаны

делением на 2, но значения внутренних узлов перечесть на так просто изза

трудности распространения округляемых результатов ввысь по дереву. Простой

метод перестройки дерева показан в последующей процедуре:

procedure rescale;

var

u: upindex;

d: downindex;

begin

for d := succmax to twicemax do

freq[d] := ( freq[d Сжатие данных - реферат] + 1 ) div 2;

for u := maxchar downto 1 do begin

left[u] := 2 * u;

right[u] := ( 2 * u ) + 1;

freq[u] := freq[left[u]] + freq[right[u]];

up[left[u]] := u;

up[right[u]] := u;

end;

end { rescale };

Черта арифметических кодов.

Hа базе алгоpитма Виттена, Нейла и Клири вышепредставленные процедуры были

обьединены в среде языка Паскаль Сжатие данных - реферат. Как и ожидалось, значимой различия меж

сжатыми текстами, приобретенными в итоге работ начального и

измененного алгоритмов арифметического сжатия не оказалось. Обычно эти

тексты имеют схожую длину.

Набросок 9 указывает скорость 2-ух этих алгоритмов как функцию от H . Время

представлено в милисекундах на б начального текста, а энтропия - в битах на

б Сжатие данных - реферат источника. Файлы с 2 битами/б и 8 битами/б сделаны искусственно, а

другие представляют собой:

цифровой графический файл, использующий 16 цветов сероватого цвета ( 3.49

бит/б );

текстовой файл ( 4.91 бит/б начального текста );

M68000 объектный файл ( 6.02 бит/б ).

Время измерялось на рабочей станции HP9836 в среде HP-UX.

Как показано на Сжатие данных - реферат рисунке 9, применение расширения к дереву накапливаемых частот

улучшает метод move-to-front, применяемый Виттеном, Нейлом и Клири [12],

только когда сжимаемые данные имеют энтропию больше, чем 6.5 бит/б. Ниже

этого значения способ move-to-front всегда работает незначительно лучше расширения.

Т.о. расширение либо другие подходы к балансированию дерева накапливаемых частот Сжатие данных - реферат

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

Но, опыты демонстрируют, что для большего алфавита pасширение может быть наилучшим

подходом.

Заключение.

Представленный тут метод расширяемого префикса является возможно самым

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

префикса. Его соответствующие черты - очень маленькое количество требуемой ОП и

локально Сжатие данных - реферат адаптивное поведение. Когда доступны огромные объемы памяти,

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

данные лучше, чем это делают конкурирующие методы на этом же объеме памяти.

Достоинства метода расширяющегося префикса нагляднее всего видны при сжатии

графических данных. Локально приспособленный нрав метода позволяет сжимать Сжатие данных - реферат

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

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

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

применяемый метод Зива-Лемпела на сопоставимом объеме памяти.

Методы арифметического сжатия данных могут производиться за время O(H) при

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

расширением для требуемой методом статистической модели. Это делает новое

ограничение, потому обычный эвристический способ помещения в начало ( move

-to-front ) является более действенным для малеханьких типовых алфавитов.

И метод расширяющегося префикса, и внедрение расширения для управления

деревом накапливаемых частот служат полезными иллюстрациями внедрения

расширения для Сжатие данных - реферат управления лексикогpафически неупорядоченными деревьями. Мысль

поворота, предваряющего расширение дерева, может отыскать применение и в

нелексикографических деревьях, равно как и понятие полуобоpота для балансировки

таких деревьев. К примеру, их можно использовать для слияния, пpи использовании

двоичного дерева с 2-я способами слияния для построения n-путевого слияния.

Любопытно отметить, что по сопоставлению Сжатие данных - реферат с другими адаптивными схемами сжатия,

утрата тут 1 бита из потока сжатых данных является катастрофой! Потому

pешение трудности восстановления этой утраты представляет бесспорный энтузиазм,

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

криптографии. Отлично понятно, что сжатие сообщения перед его шифровкой

наращивает трудность взламывания кода просто поэтому, что Сжатие данных - реферат поиск кода основан на

избыточности инфы в зашифрованном тексте, а сжатие уменьшает это

излишество. Новенькая возможность, представленная в обрисованных тут методах

сжатия, состоит в использовании исходного состояния дерева префикса кодов либо

исходного состояния дерева накапливаемых частот в качестве ключа для прямого

шифрования в процессе сжатия. Метод Сжатие данных - реферат арифметического сжатия может не считая того

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

также и меж битами.

Ключевое место для такового метода шифрования громадно. Для n букв

алфавита существует n! перестановок на листьях каждого из C деревьев, содержащих

n - 1 внутренних узлов, где C = ( 2i )! / i Сжатие данных - реферат! ( i+1 )! есть i-ое число Каталана.

Это произведение упрощается к ( 2( n-1 ) )! / ( n-1 )!. Для n = 257 ( 256 букв с

эмблемой end-of-file конца файла ) это будет 512!/256! либо что-то наименьшее 2 .

Малогабаритное целое представление ключа из этого места будет занимать 675

б, потому непременно такие огромные ключи могут поставить в тупик. На

практике одно из решение Сжатие данных - реферат будет заключаться сначала работы с уже

равновесным деревом, как и в рассмотренном тут методах сжатия, а потом

расширении этого дерева вокруг каждого знака из главный строчки,

предоставленной юзером. Вpяд ли они будет вводить ключи длиной 675 б,

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

необходимы Сжатие данных - реферат ключи еще длиннее чем этот, но даже маленький ключ может позволить

выполнить шифрование на применимом уровне.


svyaz-kletchatki-zadnej-oblasti-plecha-s-sosednimi-oblastyami.html
svyaz-matematiki-s-drugimi-naukami.html
svyaz-metodiki-so-specialnimi-i-psihologo-pedagogicheskimi-disciplinami.html