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

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

Л-алгоритма приблизительно на 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 , когда как Л-алгоритм никогда не выделял символ,

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

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

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