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

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

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

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

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

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

11.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

алгоритмы Хаффмана, но соответствующее значение n зависит от частоты изменения

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

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

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

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

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