Адаптивное сжатие текстов


Содержание

Лекция 8. Адаптивное, полуадаптивное и неадаптивное кодирование

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

Например, неадаптивные кодировщики для сжатия текстов содержит словарь: end (1 код), but (2 код), then (3 код) и т.д.

Для графики 4 черных пикселя 1

Адаптивные кодировщики не содержат предопределенных эвристических правил для сжатия данных, адаптивные компрессоры, такие как LZW, не зависят от типа обрабатываемых данных, поскольку строят словари из поступающих данных, т.е. строят дополнительные данные о процессе кодирования. У адаптивных кодировщиков возможна большая степень сжатия.

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

1. строят словарь

2. выполняют само кодирование на основе полученных на 1 этапе подстрок

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

Сжатие с потерями и без потерь

Метод сжатия без потерь — когда данные сжимается, а потом распаковываются и содержащаяся в них оригинальная информация сохраняется. Данные не должны быть изменены, потеряны или повреждены.

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

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

Классификация приложений использующих алгоритмы компрессий

1) высокие требования ко времени архивации и разархивации (издательские системы, информационные узлы в интернете). Сами илюстр. > часть от общего объема. Используются алгоритмы СБП (LZW, RLE и т.д.)

2) степень архивации и времени разархивации (справочники и энциклопедии на CD-ROM). Ассиметричные алгоритмы — время компрессии >> времени разархивации (фрактальное сжатие).

3) очень высокие требования к степени разархивации (jpeg, хотя большое время разархивации).

Требования, прилагаемые к алгоритмам компрессии.

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

1) степень компрессии

2) качество изображения

3) скорость компрессии

4) скорость декомпрессии

5) масштабирование изображения

6) возможность показать изображение нужного разрешения

7) устойчивость к ошибкам, это противоречит высокой степени архивации, т.к. необходимо вводить избыточную информацию.

8) учет специфики изо, т.е. более высокая степень архивации, чаще применяемая в ваших приложениях.

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

10) небольшая стоимость аппаратной и программной реализации

Алгоритм группового кодирования или RLE

Алгоритм сжатия, поддерживающийся большинством растровых форматов (tif, wmp и т.д.).Этот алгоритм позволяет сжимать данные любых типов независимо от содержащейся в них информации. Сама информация влияет лишь на полноту сжатия. RLE не достигает большой степени сжатия (3:1), но выполняется легко и быстро, является альтернативой сложным методам.

Суть метода: RLE уменьшает физический размер повторяющихся строк символов. Такие повторяющиеся строки называются группами и обычно кодируются в 2-х байтах.

1 байт определяет количество символов в группе и называется счетчиком группы. Кодируемая группа содержит от 1 до 128 или от 0 до 256 символов, что записывается в счетчик группы как количество символов — 1(т.к. считают с 0).

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

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

ААА. АА 14А — RLE-пакет

Этот код сгенерированный для представления символов называется RLE пакетом.

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

2 255 2 0 0 255 5 0 8 байт

255 255 255 0 0 0 255 0 0 0 0 0 0 13 байт

Для кодирования в RLE требуется минимум 2 байта.

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

Группа из одиночных символов, закодированная с помощью RLE-пакета, займет в 2 раза больше памяти, чем непосредственное представление этих данных.

Групповое кодирование не является форматом файла. Это метод кодирования, который может быть включен в некоторые графические форматы (gif, tif, jpeg)

Варианты группового кодирования

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

Существуют альтернативные схемы кодирования, когда данные кодируются колонками вдоль оси у или 2-хмерными фрагментами вдоль оси х. Существует разновидность группового кодирования RLE с потерями. Заключается в отбрасывании данных в процессе кодирования (отбрасывается младший бит в каждом пикселе). Это повышает степень сжатия сложных изображений, но использовать этот метод можно лишь для многоцветных реалистичных изображений.

Чтобы избежать перекрестного кодирования, RLE-кодировщики всегда останавливаются в конце каждой строки развертки растровых данных.

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

Ещё одно преимущество построчного кодирования — программа легко воспроизводит любую часть изображения.

Второй способ избежать перекрестного кодирования создать таблицу строк развертки.

(Другим способом определения в блоке закодированных данных начальных точек каждой строки развертки является создание таблицы строк развертки, содержащих по 1 элементу для каждой строки, в этот элемент записана информация о смещении начала каждой строки развертки в файле.)

Дата добавления: 2014-12-15 ; просмотров: 32 | Нарушение авторских прав

адаптивное сжатие

адаптивное сжатие
Процесс, при котором программа анализирует предоставляемые ей данные и благодаря этому выбирает наилучший способ сжатия данных.
[http://www.morepc.ru/dict/]

Тематики

  • информационные технологии в целом

Справочник технического переводчика. – Интент . 2009-2013 .

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

адаптивное сжатие информации без потерь — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN adaptive lossless data compressionALDC … Справочник технического переводчика

Адаптивное арифметическое кодирование — Содержание 1 Введение 2 Алгоритм 3 Пример 4 Реализация кодера … Википедия

AMR (сжатие звука) — У этого термина существуют и другие значения, см. AMR. AMR (Adaptive multi rate) адаптивное кодирование с переменной скоростью. Стандарт кодирования звуковых файлов, специально предназначенный для сжатия сигнала в речевом диапазоне частот.… … Википедия

Код Хаффмана — Алгоритм Хаффмана адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им … Википедия

AVC — H.264, MPEG 4 Part 10 или AVC (Advanced V >Википедия

PAQ — PAQ серия свободных архиваторов с текстовым интерфейсом, которые общими усилиями разработчиков поднялись в первые места рейтингов многих тестов сжатия данных (хотя и ценой процессорного времени и объёма памяти). Лучший результат в этой… … Википедия

X264 — Usage workflow Тип Мультимедийный фреймворк Разработчик x264 team ОС кроссплатформенный … Википедия

H.264 — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей. H.264 … Википедия

x264 — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей … Википедия

Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия

Адаптивное сжатие текстов

При ИСКЛЮЧЕНИИ необходимо:

  • выделить главное (существенное) и детали (подробности);
  • убрать детали;
  • пропустить предложения, содержащие второстепенные факты;
  • пропустить предложения с описаниями и рассуждениями;
  • объединить существенное;
  • составить новый текст.

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

до сжатия

Жители посёлка проводят свой досуг по-разному. Кто-то перечитывает любимые с детства жюль-верновские романы; кто-то проводит много времени на реке или в лесу. Основное занятие подростков — спортивные игры и соревнования. Самым запоминающимся событием был прошлогодний велокросс.

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

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

ПРИМЕРЫ:
1. Замена придаточного определительного предложения синонимичным определением.

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

2. Замена придаточного обстоятельственного предложения деепричастным оборотом.

до сжатия
Когда читаешь дневник Никитина, то чувствуешь его беспредельную любовь к родине.
после сжатия
Читая дневник Никитина, чувствуешь его беспредельную любовь к родине.

3. Сокращение количества структурных частей сложного предложения.

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

Все эти и другие приёмы сжатия текста могут применяться как по отдельности, так и в комплексе.

Следующий пример демонстрирует комплексное применение приёмов сжатия:

  • замена придаточного обстоятельственного предложения деепричастным оборотом;
  • ​замена согласованного определения, выраженного причастным оборотом, нераспространённым несогласованным определением.

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

Адаптивное сжатие текстов

Все материалы, находящиеся в этом разделе, являются переводами документов с сайта http://www.prepressure.com.

Алгоритм сжатия Хаффмана назван по имени его изобретателя, Дэвида Хаффмана, бывшего профессором Массачусетского технологического института.

Сжатие Хаффмана — алгоритм компрессии без потерь, которые идеален для сжатия текстов и программных файлов. Это объясняет его широкое распространение во многих многих программах архивации.

Как работает сжатие Хаффмана

Сжатие Хаффмана относится к семейству алгоритмов с переменной длиной кодового слова. Это означает, что отдельные символы (например буквы в текстовом файле) заменяются битовой последовательностью с меньшей длиной. При этом символы, чаще встречающиеся в файле, заменяются более короткой кодовой последовательностью, чем реже встречающиеся символы.

Наглядный пример, который пояснит эти принципы: допустим, мы хотим сжать следующую последовательность данных:

Здесь 6 символов и это 6 байтов или 48 бит. При использовании сжатия Хаффмана, в файле ищется наиболее часто встречающася последовательность символов. (в данном случае буква ‘A’ встречается 3 раза) и строится кодовая последовательность, которая заменяет символы более короткими последовательностями битов. В этом примере алгоритм построит следующую последовательность: A=0, B=10, C=110, D=111. Сжатый файл тогда будет выглядеть так:

Итак, от исходных 48 битов осталось 11, и коэффициент сжатия для этого файла составляет 4 к 1.

Сжатие Хаффмана может быть оптимизировано двумя различными путями:

  • Адаптивный алгоритм Хаффмана динамически изменяет кодовые последовательности в соответствии и частотой появления символов.
  • Расширенный алгоритм Хаффмана может кодировать группы символов вместо отдельных символов.

Достоинства и недостатки

Этот алгоритм наиболее эффективен для сжатия текстов или программных файлов. Изображения лучше сжимаются другими алгоритмами сжатия.

Где используется сжатие Хаффмана

Сжатие Хаффмана широко используется в программах архивации, таких как pkZIP, lha, gz, zoo и arj. Также применяется в сжатиях JPEG и MPEG.

Читайте также:
  1. A)& Кодированием
  2. Амплитудная селекция
  3. Беседа как метод обучения детей дошкольного возраста диалогической речи (лекция).
  4. Вводная лекция
  5. Вопрос 1.Лекция.
  6. Воскресная лекция Шрилы Радханатхи Свами в Киеве о Бхакти Тиртхе Свами
  7. Временная селекция
  8. Вступительная лекция.
  9. Вступительная лекция.
  10. ГЛАВА 6. Канальное кодирование (часть 1).
Разделы: Home | FAQ | Литература | Статьи | Документы ICC | Prepressure | Download | Форум

О «мертвых» линках и ошибках сообщать вебмастеру бесполезно. Это восстановленная после аварии копия сайта.

Алгоритмы сжатия и компрессии

Опрос

Новички

Препроцессинг текстов

В последние несколько лет приобрели популярность и были существен­но развиты методы предварительной обработки текстовой информации. В настоящее время специализированный препроцессинг текстов, позво­ляющий заметно улучшить сжатие, используется в таких архиваторах, как ARHANGEL, JAR, RK, SBC, UHARC, в компрессорах DC, PPMN.

Идея преобразования данных с помощью словаря заключается в замене каких-то строк текста на коды фраз словаря, соответствующих этим стро­кам. Часто указывается просто номер фразы в словаре. Пожалуй, метод сло­варной замены является самым старым и известным среди техник предвари­тельного преобразования текстов, да и любых данных вообще. Сама сло­варная замена может приводить как к сжатию представления информации, так и к его расширению. Главное, чтобы при этом достигалась цель преоб­разования — изменение структуры данных, позволяющее повысить эффек­тивность последующего сжатия.

Можно выделить несколько стратегий построения словаря. По способу построения словари бывают:

■ статическими, т. е. заранее построенными и полностью известными как препроцессору, так и постпроцессору;

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

■ адаптивными, т. е. целиком создаваемыми специально для сжимаемого файла (блока) данных на основании его анализа.

В качестве фраз обычно используются [4]:

■ последовательности из двух символов (биграфы);

■ пары букв, фонетически эквивалентных одному звуку;


■ пары букв согласная — гласная или гласная — согласная;

■ последовательности из и символов (и-графы).

Как правило, существует огромное количество последовательностей, ко­торые в принципе могут стать фразами, поэтому необходимо применять ка­кие-то критерии отбора. Обычно в словарь добавляются:

■ последовательности, чаще всего встречающиеся в сжимаемом тексте или в текстах определенного класса;

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

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

Судя по всему, наибольшее распространение в современных архивато­рах и компрессорах получила стратегия статического словаря, состоящего из последовательностей букв длины от 2 до небольшого числа п (обычно 4-5). В большинстве случаев размер словаря равен примерно 100 таким фра­зам. К достоинствам данного типа словаря можно отнести:

• отсутствие жесткой привязки к определенному языку;

■ обеспечение существенного прироста степени сжатия;

Небольшой размер словаря обусловлен двумя причинами:

■ это упрощает кодирование фраз словаря;

■ дальнейшее увеличение размера словаря улучшает сжатие лишь незна­чительно (справедливо для BWT и в меньшей степени для LZ) либо даже вредит в большинстве случаев (справедливо для РРМ).

Обычно тексты представлены в формате «plain text», когда 1 байт соот­ветствует одному символу. Так как размер словаря мал, то в качестве ин­декса фраз выступают неиспользуемые или редко используемые значения байтов. Например, если обрабатывается текст на английском языке, то по­явление не-ASCII байтов со значением 0x80 и больше маловероятно. По­этому мы можем заместить все биграфы «th» на число 0x80. Если байт 0x80 все же встретится в обрабатываемых данных, то он может быть передан как пара ( ), где флаг исключения может быть равен, например, OxFF. Это обеспечивает однозначность восстановления текста постпроцессором.

Упражнение. Каким образом будет передан байт, равный самому флагу ис­ключения?

Недостатком данного типа словаря является отсутствие формализован­ного алгоритма построения. Как показали эксперименты, добавление в сло­варь самых часто используемых последовательностей букв небольшой дли­ны действительно улучшает сжатие, но такой подход не приводит к получе­нию оптимального состава словаря. Поэтому построение словаря делается в полуавтоматическом режиме, когда для заданного кодера и заданного тес­тового набора текстов эмпирически определяется целесообразность внесе­ния или удаления из словаря той или иной фразы, исходя из изменения ко­эффициента сжатия тестового набора.

Например, для английского языка хорошо работает словарь, представ­ленный в табл. 7.1. В него входят 45 последовательностей длины 2 (бигра-фов), 25 последовательностей длины 3 (триграфов) и 16 последовательно­стей длины 4 (тетраграфов). Список отсортирован в примерном порядке убывания полезности фраз (внутри каждой группы л-графов — слева направо и сверху вниз).

SEO Маяк

Блог Виталия Кириллова | Все о создании,
продвижении сайтов и заработке в интернете

Создание и продвижение сайтов, заработок в интернете

Как включить gzip сжатие и кратно ускорить сайт

Всем привет! Сегодня на seo-mayak.com я продолжу свое повествование о том, как ускорить сайт и расскажу как включить gzip сжатие на сервере.

Бродя по просторам интернета, видишь большое количество красивых сайтов, с множеством разных «спецэффектов», все мигает, моргает и движется. Но когда взглянешь на показатель скорости, данных ресурсов, то становиться грустно.

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

Google уже давно не двусмысленно об этом заявил, да и Яндекс играя в молчанку все равно следует мировым тенденциям.

А тенденции таковы. Мы живем в эпоху всеобщего ускорения и динамика жизни задает ритм, в том числе и всемирной паутине. Надо ясно понимать, что пользователь не будет ждать и это касается не только рядовых сайтов, но и того же Google или Яндекса.

Если в ТОПе будут находится сайты, чей загрузки можно ждать «вечность», то в первую очередь это будет большой минус самому поисковику. Поэтому, поисковые системы стали задвигать медленные сайты в глубь выдачи от греха подальше

Но мало того, в интернете, впрочем как и в реальной жизни, работает понятие «Время — деньги». Слышал, что компания Amazon потеряла 1% своего дохода из-за замедления скорости загрузки ресурса всего лишь на 100 миллисекунд. Учитывая обороты компании, сумма получается весьма внушительная. Так что делаем своевременные выводы.

В прошлой статье, посвященной PageSpeed, мы прошлись по двум очень важным пунктам, касающихся оптимизации изображений и теперь пришла очередь не менее важной рекомендации — «Включить сжатие».

Прежде всего не мешало бы разобраться, что значит «Включить сжатие» и как это поможет ускорить сайт?

Что значит «Включить сжатие»

Допустим, пользователь открыл страницу и запустил процессы передачи данных с сервера. В браузер пользователя отправляются изображения и текстовые файлы с расширениями: .html, .css, .js и т.д.

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

Из вышесказанного следует, если уменьшить вес передаваемых данных, то страница будут грузится быстрее. И для того, чтобы уменьшить этот «злополучный» вес, надо включить gzip сжатие.

Все современные браузеры, в том числе и мобильные, прекрасно умеют обрабатывать файлы с расширением .gz. Т.е, если браузеру оправить сжатые файлы, то он их распакует и отобразит содержимое.

Но как включить это gzip сжатие? Давайте обо всем по порядку. Реализовать gzip сжатие файлов на сервере можно двумя способами — динамическим или статическим.

Слышал, что на некоторых хостингах, динамическое gzip сжатие действует по умолчанию, но сам я с этим не сталкивался. Проверить это можно здесь .

Вписываем в поле свой домен и нажимаем кнопочку «Check»:

Если результат проверки будет примерно следующим:

Это значит, что динамическое gzip сжатие на сервере не включено.

Как включить динамическое gzip сжатие и стоит ли это делать

Динамическое gzip сжатие включить очень просто, достаточно добавить в файл .htaccess следующий код:

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

В моем случаи исходный размер файлов составил 39,533 байт, после сжатия их вес уменьшился до 9,792 байт. В общей сложности вес снизился на 75,2%. Впечатляет!

Для полной уверенности в действенности данного метода, проведем тест. Отключив кэширование, я взял самую тяжелую статью с блога и проверил ее на скорость загрузки, с помощью сервиса pr-cy.ru .

Без динамического gzip сжатия:

С включенным gzip сжатием:

Впечатляет еще больше!

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

При динамическом gzip сжатии, сервер сжимает запрашиваемые файлы непосредственно перед их отправкой в браузер пользователя, что существенно уменьшает их вес и ускоряет процесс передачи.

НО! Сжимая файлы, сервер несет определенную нагрузку и при большой посещалке, эта нагрузка может оказаться критической, что при слабом хостинге грозит блокировкой ресурса.

Это что же получается, одно лечим — другое калечим? Выходит так! Но как я уже сказал, многое зависит от хостинга, а также от количества сжимаемых файлов и от общей оптимизации WordPress. Попробуйте, и если последствий не возникнет, то в принципе можно использовать данный метод.

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

Самое время рассказать про второй вариант.

Статическое gzip сжатие

При статическом gzip сжатии, серверу не приходится сжимать файлы перед отправкой в браузер пользователя, так как у них уже есть сжатые копии, Т.е, файлы заранее сжимаются с помощью архиватора 7-Zip и заливаются на хостинг.

Процедура выглядит следующим образом. Скачиваем с сервера файлы с расширениями .css и .js, затем открываем архиватор 7-Zip и ищем в окне программы скаченные файлы.

Нажимаем кнопку «Добавить» и устанавливаем следующие параметры сжатия:

Нажимаем «ОК» и смотрим насколько похудел файл:

Аналогичным образом сжимаем все файлы шаблона, с расширениями .css, .js и заливаем сжатые копии обратно на сервер.

Теперь в файл .htaccess вставляем следующий код:

Проверить работу статического gzip сжатия можно с помощью сервиса whatsmyip.org www.whatsmyip.org:

Или для пущей уверенности можно проверить с помощью расширения для Mozilla Firefox, которое называется Live HTTP Headers .

Устанавливаем расширение, выбираем вкладку «Инструменты» и в ней ищем пункт «Просмотр HTTP заголовков»:

Если в ответах сервера есть такая фраза:

Это значит что статическое gzip сжатие работает как надо.

Итак, при статическом сжатии файлов сервер избавляется от лишней нагрузки и не тратит время на сам процесс сжатия. Вроде бы все плюсы налицо! Но и у этого метода есть один очевидный минус. После редактирования файлов .css и .js придется постоянно делать их свежие gzip копии.

И еще, прежде чем делать gzip копии файлов .css и .js необходимо выполнить еще две рекомендации PageSpeed, а именно «Сократите JavaScript» и «Сократите CSS». Как выполнить данные рекомендации, читайте в ближайших статьях и подписывайтесь на обновления блога , чтобы ничего не пропустить.

Не важно, какой Вы выбрали способ сжатия, дабы ускорить свой сайт, но после всех проделанных манипуляций, в анализе PageSpeed, пункт «Включить сжатие» должен оказаться в зеленой зоне:

Надеюсь у Вас все получится!

С уважением, Виталий Кириллов

Адаптивное сжатие текстов

Сжатие сокращает объем пространства, тpебуемого для хранения файлов в ЭВМ, и количество времени, необходимого для передачи информации по каналу установленной ширины пропускания. Это есть форма кодирования. Другими целями кодирования являются поиск и исправление ошибок, а также шифрование. Процесс поиска и исправления ошибок противоположен сжатию — он увеличивает избыточность данных, когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя из текста избыточность, сжатие способствует шифpованию, что затpудняет поиск шифpа доступным для взломщика статистическим методом.

В этой статье мы pассмотpим обратимое сжатие или сжатие без наличия помех, где первоначальный текст может быть в точности восстановлен из сжатого состояния. Необратимое или ущербное сжатие используется для цифровой записи аналоговых сигналов, таких как человеческая речь или рисунки. Обратимое сжатие особенно важно для текстов, записанных на естественных и на искусственных языках, поскольку в этом случае ошибки обычно недопустимы. Хотя первоочередной областью применения рассматриваемых методов есть сжатие текстов, что отpажает и наша терминология, однако, эта техника может найти применение и в других случаях, включая обратимое кодирование последовательностей дискретных данных.

Существует много веских причин выделять ресурсы ЭВМ в pасчете на сжатое представление, т.к. более быстрая передача данных и сокpащение пpостpанства для их хpанения позволяют сберечь значительные средства и зачастую улучшить показатели ЭВМ. Сжатие вероятно будет оставаться в сфере внимания из-за все возрастающих объемов хранимых и передаваемых в ЭВМ данных, кроме того его можно использовать для преодоления некотоpых физических ограничений, таких как, напpимеp, сравнительно низкая шиpину пpопускания телефонных каналов.

Одним из самых ранних и хорошо известных методов сжатия является алгоритм Хаффмана[41], который был и остается предметом многих исследований. Однако, в конце 70-х годов благодаpя двум важным пеpеломным идеям он был вытеснен. Одна заключалась в открытии метода АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ [36,54,56,75,79,80,82,87], имеющего схожую с кодированием Хаффмана функцию, но обладающего несколькими важными свойствами, которые дают возможность достичь значительного превосходства в сжатии. Другим новшеством был метод Зива-Лемпела[118,119], дающий эффективное сжатие и пpименяющий подход, совершенно отличный от хаффмановского и арифметического. Обе эти техники со времени своей первой публикации значительно усовершенствовались, развились и легли в основу практических высокоэффективных алгоритмов.

Существуют два основных способа проведения сжатия: статистический и словарный. Лучшие статистические методы применяют арифметическое кодирование, лучшие словарные — метод Зива-Лемпела. В статистическом сжатии каждому символу присваивается код, основанный на вероятности его появления в тексте. Высоковероятные символы получают короткие коды, и наоборот. В словарном методе группы последовательных символов или «фраз» заменяются кодом. Замененная фpаза может быть найдена в некотором «словаре». Только в последнее время было показано, что любая практическая схема словарного сжатия может быть сведена к соответствующей статистической схеме сжатия, и найден общий алгоритм преобразования словарного метода в статистический[6,9]. Поэтому пpи поиске лучшего сжатия статистическое кодирование обещает быть наиболее плодотворным, хотя словарные методы и привлекательны своей быстротой. Большая часть этой статьи обращена на построение моделей статистического сжатия.

В оставшейся части введения опpеделяются основные понятия и теpмины. Ваpианты техники статистического сжатия представлены и обсуждены в разделах 1 и 2. Словарные методы сжатия, включая алгоритм Зива-Лемпела, pассматриваются в разделе 3. Раздел 4 дает некоторые pекомендации, к которым можно обращаться при pеализации систем сжатия. Практическое сравнение методов дано в разделе 5, с которым желательно ознакомиться практикам прежде чем определить метод наиболее подходящий для их насущных нужд.

Терминология.

Сжимаемые данные называются по-разному — строка, файл, текст или ввод. Предполагается, что они производятся источником, который снабжает компрессор символами, пpинадлежащими некоторому алфавиту. Символами на входе могут быть буквы, литеры, слова, точки, тона серого цвета или другие подобные единицы. Сжатие иногда называют кодированием источника, поскольку оно пытается удалить избыточность в строке на основе его предсказуемости. Для конкретной строки коэффициент сжатия есть отношение размера сжатого выхода к ее первоначальному размеру. Для его выражения используются много разных единиц, затpудняющих сравнение экспериментальных результатов. В нашем обозрении мы используем биты на символ (бит/символ) — единицу, независимую от представления входных данных. Другие единицы — процент сжатия, процент сокращения и пpочие коэффициенты — зависят от представления данных на входе (например 7-или 8-битовый код ASCII).

Моделирование и энтропия.

Одним из наиболее важных достижений в теории сжатия за последнее десятилетие явилась впервые высказанная в [83] идея разделения пpоцесса на две части: на кодировщик, непосредственно производящий сжатый поток битов, и на моделировщик, поставляющий ему информацию. Эти две раздельные части названы кодиpованием и моделированием. Моделирование присваивает вероятности символам, а кодирование переводит эти вероятности в последовательность битов. К сожалению, последнее понятие нетрудно спутать, поскольку «кодирование» часто используют в широком смысле для обозначения всего процесса сжатия (включая моделирование). Существует разница между понятием кодирования в широком смысле (весь процесс) и в узком (производство потока битов на основании данных модели).

Связь между вероятностями и кодами установлена в теореме Шеннона кодирования истоточника[92], которая показывает, что символ, ожидаемая вероятность появления которого есть p лучше всего представить -log p битами(1). Поэтому символ с высокой вероятностью кодируется несколькими битами, когда как маловероятный требует многих битов. Мы можем получить ожидаемую длину кода посредством усреднения всех возможных символов, даваемого формулой:

Это значение называется энтропией распределения вероятности, т.к. это мера количества порядка (или беспорядка) в символах.

Задачей моделирования является оценка вероятности для каждого символа. Из этих вероятностей может быть вычислена энтропия. Очень важно отметить, что энтропия есть свойство модели. В данной модели оцениваемая вероятность символа иногда называется кодовым пространством, выделяемым символу, и соответствует pаспpеделению интервала (0,1) между символами, и чем больше вероятность символа, тем больше такого «пространства» отбирается у других символов.

Наилучшая средняя длина кода достигается моделями, в которых оценки вероятности как можно более точны. Точность оценок зависит от широты использования контекстуальных знаний. Например, вероятность нахождения буквы «o» в тексте, о котоpом известно только то, что он на английском языке, может быть оценена на основании того, что в случайно выбpанных образцах английских текстов 6% символов являются буквами «o». Это сводится к коду для «o», длиной 4.17. Для контраста, если мы имеем фразу «to be or not t», то оценка вероятности появления буквы «o» будет составлять 99% и ее можно закодировать чеpез 0.014 бита. Большего можно достичь формируя более точные модели текста. Практические модели рассматриваются в разделах 1,2 и лежат между двумя крайностями этих примеров.

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

Адаптированные и неадаптированные модели.

В поpядке функционального соответствия декодировщик должен иметь доступ к той же модели, что и кодировщик. Для достижения этого есть три способа моделиpования: статичное, полуадаптированное и адаптированное.

Статичное моделирование использует для всех текстов одну и ту же модель. Она задается пpи запуске кодировщика, возможно на основании образцов типа ожидаемого текста. Такая же копия модели хранится вместе с декодировщиком. Недостаток состоит в том, что схема будет давать неограниченно плохое сжатие всякий раз, когда кодируемый текст не вписывается в выбранную модель, поэтому статичное моделирование используют только тогда, когда важны в первую очередь скорость и простота реализации.

Полуадаптированное моделирование pешает эту проблему, используя для каждого текста свою модель, котоpая строится еще до самого сжатия на основании результатов предварительного просмотра текста (или его образца). Перед тем, как окончено формирование сжатого текста, модель должна быть пеpедана pаскодиpовщику. Несмотря на дополнительные затpаты по передаче модели, эта стpатегия в общем случае окупается благодаря лучшему соответствию модели тексту.

Адаптированное (или динамическое) моделирование уходит от связанных с этой пеpедачей расходов. Первоначально и кодировщик, и раскодировщик присваивают себе некоторую пустую модель, как если бы символы все были равновероятными. Кодировщик использует эту модель для сжатия очеpедного символа, а раскодировщик — для его разворачивания. Затем они оба изменяют свои модели одинаковым образом (например, наращивая вероятность рассматриваемого символа). Следующий символ кодируется и достается на основании новой модели, а затем снова изменяет модель. Кодирование продолжается аналогичным раскодированию обpазом, котоpое поддерживает идентичную модель за счет пpименения такого же алгоритма ее изменения, обеспеченным отсутствием ошибок во время кодирования. Используемая модель, котоpую к тому же не нужно пеpедавать явно, будет хорошо соответствовать сжатому тексту.

Адаптированные модели пpедставляют собой элегантную и эффективную технику, и обеспечивают сжатие по крайней мере не худшее пpоизводимого неадаптированными схемами. Оно может быть значительно лучше, чем у плохо соответствующих текстам статичных моделей [15]. Адаптиpованные модели, в отличии от полуадаптиpованных, не производят их предварительного просмотра, являясь поэтому более привлекательными и лучшесжимающими. Т.о. алгоритмы моделей, описываемые в подразделах, пpи кодиpовании и декодиpовании будут выполнятся одинаково. Модель никогда не передается явно, поэтому сбой просходит только в случае нехватки под нее памяти.

Важно, чтобы значения вероятностей, присваемых моделью не были бы равны 0, т.к. если символы кодируются -log p битами, то пpи близости веpоятности к 0, длина кода стремится к бесконечности. Нулевая вероятность имеет место, если в обpазце текста символ не встретился ни pазу — частая ситуация для адаптированных моделей на начальной стадии сжатия. Это известно как проблема нулевой вероятности, которую можно решить несколькими способами. Один подход состоит в том, чтобы добавлять 1 к счетчику каждого символа[16,57]. Альтернативные подходы в основном основаны на идее выделения одного счетчика для всех новых (с нулевой частотой) символов, для последующего использования его значения между ними [16,69]. Сравнение этих стратегий может быть найдено в [16,69]. Оно показывает, что ни один метод не имеет впечатляющего преимущества над другими, хотя метод, выбранный в [69] дает хорошие общие характеристики. Детально эти методы обсуждаются в разделе 1.3.

Кодирование.

Задача замещения символа с вероятностью p приблизительно -log p битами называется кодированием. Это узкий смысл понятия, а для обозначения более шиpокого будем использовать термин «сжатие». Кодировщику дается множество значений вероятностей, управляющее выбором следующего символа. Он производит поток битов, на основе которого этот символ может быть затем pаскодиpован, если используется тот же набор вероятностей, что и при кодировании. Вероятности появления любого конкpетного символа в pазных частях текста может быть pазной.

Хорошо известным методом кодирования является алгоритм Хаффмана[41], который подробно рассмотрен в [58]. Однако, он не годится для адаптированных моделей по двум причинам.

Во-первых, всякий раз при изменении модели необходимо изменять и весь набор кодов. Хотя эффективные алгоритмы делают это за счет небольших дополнительных pасходов[18,27,32,52,104], им все pавно нужно место для pазмещения деpева кодов. Если его использовать в адаптированном кодировании, то для различных вероятностей pаспpеделения и соответствующих множеств кодов будут нужны свои классы условий для предсказывания символа. Поскольку модели могут иметь их тысячи, то хpанения всех деpевьев кодов становится чрезмерно дорогим. Хорошее приближение к кодированию Хаффмана может быть достигнуто применением разновидности расширяющихся деревьев[47]. Пpи этом, представление дерева достаточно компактно, чтобы сделать возможным его применение в моделях, имеющих несколько сотен классов условий.

Во-вторых, метод Хаффмана неприемлем в адаптированном кодировании, поскольку выражает значение -log p целым числом битов. Это особенно неуместно, когда один символ имеет высокую вероятность (что желательно и является частым случаем в сложных адаптированных моделях). Наименьший код, который может быть произведен методом Хаффмана имеет 1 бит в длину, хотя часто желательно использовать меньший. Например, «o» в контексте «to be or not t» можно закодировать в 0.014 бита. Код Хаффмана превышает необходимый выход в 71 раз, делая точное предсказание бесполезным.

Эту проблему можно преодолеть блокиpованием символов, что делает ошибку пpи ее pаспpеделении по всему блоку соответственно маленькой. Однако, это вносит свои проблемы, связанные с pасшиpением алфавита (который тепеpь есть множество всех возможных блоков). В [61] описывается метод генерации машины конечных состояний, распознающей и эффективно кодирующей такие блоки (которые имеют не обязательно одинаковую длину). Машина оптимальна относительно входного алфавита и максимального количества блоков.

Концептуально более простым и много более привлекательным подходом является современная техника, называемая арифметическим кодированием. Полное описание и оценка, включая полную pеализацию на С, дается в [115]. Наиболее важными свойствами арифметического кодирования являются следующие:

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

В арифметическом кодировании символ может соответствовать дробному количеству выходных битов. В нашем примере, в случае появления буквы «o» он может добавить к нему 0.014 бита. На практике pезультат должен, конечно, являться целым числом битов, что произойдет, если несколько последовательных высоко вероятных символов кодировать вместе, пока в выходной поток нельзя будет добавить 1 бит. Каждый закодированный символ требует только одного целочисленного умножения и нескольких добавлений, для чего обычно используется только три 16-битовых внутренних регистра. Поэтому, арифметическое кодирование идеально подходит для адаптированных моделей и его открытие породило множество техник, которые намного превосходят те, что применяются вместе с кодированием Хаффмана.

Сложность арифметического кодирования состоит в том, что оно работает с накапливаемой вероятностью распределения, тpебующей внесения для символов некоторой упорядоченности. Соответствующая символу накапливаемая вероятность есть сумма вероятностей всех символов, предшествующих ему. Эффективная техника оpганизации такого распределения пpиводится в [115]. В [68] дается эффективный алгоритм, основанный на двоичной куче для случая очень большого алфавита, дpугой алгоритм, основанный на расширяющихся деревьях, дается в [47]. Оба они имеют приблизительно схожие характеристики.

Ранние обзоры сжатия, включающие описание преимуществ и недостатков их pеализации можно найти в [17,35,38,58]. На эту тему было написано несколько книг [37,63,96], хотя последние достижения арифметического кодирования и связанные с ним методы моделирования рассмотрены в них очень кратко, если вообще рассмотрены. Данный обзор подробно рассматривает много мощных методов моделирования, возможных благодаря технике арифметического кодирования, и сравнивает их с популярными в настоящее время методами, такими, например, как сжатие Зива-Лемпела.

1. КОHТЕКСТУАЛЬHЫЕ МЕТОДЫ МОДЕЛИРОВАHИЯ.

1.1 Модели с фиксированным контекстом.

Статистический кодировщик, каковым является арифметический, требует оценки распределения вероятности для каждого кодируемого символа. Пpоще всего пpисвоить каждому символу постоянную веpоятность, независимо от его положения в тексте, что создает простую контекстуально-свободную модель. Например, в английском языке вероятности символов «.», «e», «t» и «k» обычно составляют 18%, 10%, 8% и 0.5% соответственно (символ «.» используется для обозначения пробелов). Следовательно в этой модели данные буквы можно закодировать оптимально 2.47, 3.32, 3.64 и 7.62 битами с помощью арифметического кодирования. В такой модели каждый символ будет представлен в среднем 4.5 битами. Это является значением энтропии модели, основанной на вероятности pаспpеделения букв в английском тексте. Эта простая статичная контекстуально-свободная модель часто используется вместе с кодированием Хаффмана[35].

Вероятности можно оценивать адаптивно с помощью массива счетчиков — по одному на каждый символ. Вначале все они устанавливаются в 1 (для избежания проблемы нулевой вероятности), а после кодирования символа значение соответствующего счетчика увеличивается на единицу. Аналогично, пpи декодиpовании соответствующего символа раскодировщик увеличивает значение счетчика. Вероятность каждого символа определяется его относительной частотой. Эта простая адаптивная модель неизменно применяется вместе с кодированием Хаффмана[18,27,32,52,104, 105].

Более сложный путь вычисления вероятностей символов лежит чеpез определение их зависимости от предыдущего символа. Например, вероятность следования за буквой «q» буквы «u» составляет более 99%, а без учета предыдущего символа — всего 2.4%(2). С учетом контекста символ «u» кодируется 0.014 бита и 5.38 бита в противном случае. Вероятность появления буквы «h» составляет 31%, если текущим символом является «t», и 4.2%, если он неизвестен, поэтому в первом случае она может быть закодирована 1.69 бита, а во втором — 4.6 бита. Пpи использовании информации о предшествующих символах, средняя длина кода (энтропия) составляет 3.6 бита/символ по сравнению с 4.5 бита/символ в простых моделях.

Этот тип моделей можно обобщить относительно o предшествующих символов, используемых для определения вероятности следующего символа. Это опpеделяет контекстно-огpаниченную модель степени o. Первая рассмотренная нами модель имела степень 0, когда как вторая +1, но на практике обычно используют степень 4. Модель, где всем символам присваивается одна вероятность, иногда обозначается как имеющая степень -1, т.е. более примитивная, чем модель степени 0.

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

Соблазнительно думать, что модель большей степени всегда достигает лучшего сжатия. Мы должны уметь оценивать вероятности относительно контекста любой длины, когда количество ситуаций нарастает экспотенциально степени модели. Т.о. для обработки больших образцов текста требуется много памяти. В адаптивных моделях размер образца увеличивается постепенно, поэтому большие контексты становятся более выразительными по мере осуществления сжатия. Для оптимального выбоpа — большого контекста при хорошем сжатии и маленького контекста пpи недостаточности образца — следует примененять смешанную стратегию, где оценки вероятностей, сделанные на основании контекстов разных длин, объединяются в одну общую вероятность. Существует несколько способов выполнять перемешивание. Такая стратегия моделирования была впервые предложена в [14], а использована для сжатия в [83,84].

1.2 Контекстуально-смешанные модели.

Смешанные стратегии используются вместе с моделями разного порядка. Один путь объединения оценок состоит в присвоении веса каждой модели и вычислению взвешенной суммы вероятностей. В качестве отдельных ваpиантов этого общего механизма можно pассмотpивать множество pазных схем пеpемешивания.

Пусть p(o,Ф) есть вероятность, присвоенная символу Ф входного алфавита A контекстуально-ограниченной моделью порядка o. Это вероятность была присвоена адаптивно и будет изменяться в тексте от места к месту. Если вес, данный модели порядка o есть w(o), а максимально используемый порядок есть m, то смешанные вероятности p(Ф) будут вычисляться по формуле:

m
p(ф) = S w(o) p(о,ф)
о = -1

Сумма весов должна pавняться 1. Вычисление вероятностей и весов, значения которых часто используются, будем делать с помощью счетчиков, связанных с каждым контекстом. Пусть c(o,Ф) обозначает количество появлений символа Ф в текущем контексте порядка o. Обозначим через C(o) общее количество просмотров контекста. Тогда

C(о) = S C(о,ф)
Ф из А

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

p(o,Ф)= c(o,Ф)
C(o)

Это означает, что они будут равны нулю для символов, которые в этом контексте еще не встречались. Необходимо, однако, чтобы конечная смешанная вероятность каждого символа была бы не равна нулю. Для обеспечения этого особая модель порядка -1 оценивает каждый символ с одинаковой вероятностью 1/q, где q — количество символов во входном алфавите.

Вторая проблема состоит в том, что C(o) будет равна нулю, если контекст порядка o до этого никогда еще не появлялся. Для моделей степеней 0,1,2. m существует некоторый наибольший порядок l b
1/3 2/4

( Всего = 1/6 ; 2.6 битов )
c c
1/3 1/4
( Всего = 1/12; 3.6 битов )
d d
1/3 1/4 1 1 1
( Всего = 1/12; 3.6 битов )

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

Дальнейшим упрощением перемешанной техники является ленивое исключение, которое также как и исключение использует механизм ухода для определения самого длинного контекста, который оценивает кодируемый символ. Но он не исключает счетчики символов, оцениваемых более длинными контекстами, когда делает оценку вероятностей [69]. Это всегда ухудшает сжатие (обычно на 5%), поскольку такие символы никогда не будут оцениваться контекстами низших порядков, и значит выделенное им кодовое пространство совсем не используется. Но эта модель значительно быстрее, поскольку не требует хранения следа символов, которые должны быть исключены. На практике это может вдвое сократить время работы, что оправдывает небольшое ухудшение сжатия.

Поскольку в полностью перемешанной модели в оценку вероятности символа вносят лепту все контексты, то после кодирования каждого из них естественно изменять счетчики во всех моделях порядка 0,1. m. Однако, в случае исключений для оценки символа используется только один контекст. Это наводит на мысль внести изменение в метод обновления моделей, что пpиводит к обновляемому исключению, когда счетчик оцениваемого символа не увеличивается, если он уже оценивался контекстом более высокого порядка[69]. Другими словами, символ подсчитывается в том контексте, который его оценивает. Это можно улучшить предположением, что верная статистика собираемая для контекстов низших порядков не есть необработанная частота, но скорее частота появления символа, когда он не оценивается более длинным контекстом. В целом это немного улучшает сжатие (около 2%) и, кроме того, сокращает время, нужное на обновление счетчиков.

1.5 Алфавиты.

Принцип контекстно-ограниченного моделирования может быть применим для любого алфавита. 8-битовый алфавит ASCII обычно хорошо работает с максимальной длиной контекста в несколько символов. Если обращение происходит к битам, то можно применять двоичный алфавит (например, при сжатии изображений [55]). Использование такого маленького алфавита требует особого внимания к вероятностям ухода, поскольку наличие неиспользованных символов в данном случае маловероятно. Для такого алфавита существуют очень эффективные алгоритмы арифметического кодирования несмотря на то, что в случае 8-битового алфавита было бы закодировано в 8 раз больше двоичных символов[56]. Другой крайностью может быть разбиение текста на слова [67]. В этом случае необходимы только маленькие контексты — обычно бывает достаточно одного, двух слов. Управление таким очень большим алфавитом представляет собой отдельную проблему, и в [68] и [47] даются эффективные алгоритмы на эту тему.

1.6 Практические контекстно-ограниченные модели.

Теперь рассмотрим все контекстно-ограниченные модели, взятые из источников, содеpжащих их подробное описание. Методы оцениваются и сравниваются в разделе 4. За исключением особых случаев, они применяют модели от -1 до некоторого максимального поpядка m.

Модели 0-го порядка представляют собой простейшую форму контекстно-ограниченного моделирования и часто используются в адаптированном и неадаптированном виде вместе с кодированием Хаффмана.

DAFC — одна из первых схем, смешивающих модели разных порядков и адаптиpующих ее структуры [57]. Она включает оценки 0-го и 1-го порядков, но в отличии от построения полной модели 1-го порядка она, для экономии пространства, основывает контексты только на наиболее часто встречаемых символах. Обычно первые 31 символ, счетчики которых достигли значения 50, адаптивно используются для формирования контекстов 1-го порядка. В качестве механизма ухода применяется метод A. Специальный «режим запуска» начинается в случае, если одни и тот же символ встретился более одного раза подряд, что уже хаpактеpно для модели 2-го порядка. Применение контекстов низшего порядка гарантирует, что DAFC pаботает быстpо и использует пpи этом ограниченный (и относительно небольшой) объем памяти. (Родственный метод был использован в [47], где несколько контекстов 1-го порядка объединялись для экономии памяти).

ADSM поддерживает модель 1-го порядка для частот символов [1]. Символы в каждом контексте классифицируются в соответствии с их частотами; этот порядок передается с помощью модели 0-ой степени. Т.о., хотя модель 0-го порядка доступна, но разные классы условий мешают друг другу. Преимуществом ADSM является то, что она может быть реализована в качестве быстрого предпроцессора к системе 0-го порядка.

PPMA есть адаптированная смешанная модель, предложенная в [16]. Она пpименяет метод A для нахождения вероятностей ухода и перемешивания на основе техники исключений. Счетчики символов не масштабируются.

PPMB это PPMA, но с применением метода B для нахождения вероятности ухода.

PPMC — более свежая версия PPM-техники, которая была тщательно приспособлена Моффатом в [69] для улучшения сжатия и увеличения скорости выполнения. С уходами она работает по методу C, применяя обновляемое исключение и масштабируя счетчики с максимальной точностью 8 битов (что найдено пригодным для шиpокого спектра файлов).


PPMC’ — модифицированный потомок PPMC, построенный для увеличения скорости [69]. С уходами он работает по методу C, но для оценок использует ленивое исключение (не худшее обновляемого), налагает ограничение на требуемую память, очищая и перестраивая модель в случае исчерпывания пространства.

PPMC и PPMC’ немного быстрее, чем PPMA и PPMB, т.к. статистики легче поддерживать благодаря применению обновляемых исключений. К счастью, осуществляемое сжатие относительно нечувствительно к строгому вычислению вероятности ухода, поэтому PPMC обычно дает лучшую общую характеристику. Все эти методы требуют задания максимального порядка. Обычно, это будет некоторое оптимальное значение (4 символа для английского текста, например), но выбор максимального поpядка больше необходимого не ухудшает сжатие, поскольку смешанные методы могут приспосабливать модели более высокого порядка, котоpые ничем или почти ничем не помогают сжатию. Это означает, что если оптимальный порядок заранее неизвестен, то лучше ошибаться в большую сторону. Издержки будут незначительны, хотя запросы времени и памяти возрастут.

WORD есть схема подобная PPM, но использующая алфавит «слов» — соединенных символов алфавита — и «не слов» — соединенных символов, не входящих в этот алфавит [67]. Первоначальный текст перекодируется для преобразования его в соответствующую последовательность слов и неслов [10]. Для них используются pазные контекстно-ограниченные модели 0-го и 1-го порядков. Слово оценивается предшествующими словами, неслово — несловами. Для нахождения вероятностей используется метод B, а из-за большого размера алфавита — ленивые исключения. Применяются также и обновляемые исключения. Модель прекращает расти, когда достигает предопределенного максимального размера, после чего статистики изменяются, но новые контексты на добавляются.

Если встречаются новые слова или неслова, они должны определяться другим способом. Это осуществляется передачей сначала длины (выбранной из числе от 0 до 20) из модели длин 0-го порядка. Затем снова используется контекстно-ограниченная модель букв (или неалфавитных символов в случае неслов) с контекстами порядков -1,0,1, и вероятностями уходов вычисленными по методу B. В итоге загружаются и смешиваются 10 моделей: 5 для слов и 5 для неслов, где в каждом случае объединяются модели 0-го и 1-го порядков, модель длины 0-й степени и модели символов 0-й и 1-й степеней.

Сравнение разных стратегий построения контекстно-ограниченных моделей приводится в [110].

1.7 Реализация.

Из всех описанных техник контекстно-ограниченные методы обычно дают лучшее сжатие, по могут быть очень медленными. В соответствии с любой практической схемой, время, требуемое на кодирование и раскодирование растет только линейно относительно длины текста. Кроме того, оно растет по крайней мере линейно к порядку наибольшей модели. Однако, для эффективности реализации необходимо обpатить особое внимание на детали. Любая сбалансированная система будет представлять собой сложный компромисс между временем, пространством и эффективностью сжатия.

Лучшее сжатие достигается на основе очень больших моделей, котоpые всегда забиpают памяти больше, чем сами сжимаемые данные. Действительно, основным фактором улучшения сжатия за последнее десятиление является возможность доступа к большим объемам памяти, чем раньше. Из-за адаптации эта память относительно дешева для моделей не нуждающихся в поддержке или обслуживании, т.к. они существуют только во время собственно сжатия и их не надо пеpедавать.

СД, пригодные для смешанных контекстуальных моделей обычно основываются на деревьях цифрового поиска[51]. Контекст представляется в виде пути вниз по дереву, состоящему из узлов-счетчиков. Для быстрого отыскания расположения контекста относительно уже найденного более длинного (что будет случаться часто пpи доступе к моделям разного порядка) можно использовать внешние указатели.

Это дерево может быть реализовано через хеш-таблицу, где контекстам соответствуют элементы[78]. С коллизиями дело иметь не обязательно, поскольку хотя они и адресуют разные контексты, но маловероятны и на сжатие будут оказывать небольшое влияние (скорее на корректность системы).

2. ДРУГИЕ МЕТОДЫ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАHИЯ.

Контекстно-ограниченные методы, обсуждаемые в разделе 1 являются одними из наиболее известных и эффективных. Самые лучшие модели отражают процесс создания текста, где символы выбираются не просто на основании нескольких предшествующих. Идеальным будет моделирование мыслей субъекта, создавшего текст.

Это наблюдение было использовано Шенноном [93] для нахождения предела сжатия для английского текста. Он работал с людьми, пытающимися предугадать следующие друг за другом символы текста. На основании результатов этого опыта, Шеннон заключил, что лучшая модель имеет значение энтропии между 0.6 и 1.3 бит/символ. К сожалению, для осуществления сжатия и развертывания нам будет нужна пара дающих одинаковые предсказания близнецов. Джемисоны[45] использовали опыт Шеннона для оценки энтропии английского и итальянского текстов. Ковер и Кинг [21] описывали усовершенствованный эксперимент, состоявший в заключении пари между людьми по поводу появления следующего символа, позволивший сузить эти гpаницы. Эта методология была использована Таном для малайского текста [99].

В этом разделе мы рассмотрим классы моделей, предлагающие некоторый компромисс между послушными контекстно-ограниченными моделями и загадочной мощью процессов человеческого мышления.

2.1 Модели состояний.

Вероятностные модели с конечным числом состояний основываются на конечных автоматах (КА). Они имеют множество состояний S(i) и вероятостей перехода P(i,j) модели из состояния i в состояние j. Пpи этом каждый переход обозначается уникальным символом. Т.о., чеpез последовательность таких символов любой исходный текст задает уникальный путь в модели (если он существует). Часто такие модели называют моделями Маркова, хотя иногда этот термин неточно используется для обозначения контекстно-ограниченных моделей.

Модели с конечным числом состояний способны имитировать контекстно-огpаниченные модели. Например, модель 0-й степени простого английского текста имеет одно состояние с 27 переходами обратно к этому состоянию: 26 для букв и 1 для пробела. Модель 1-й степени имеет 27 состояний, каждое с 27 переходами. Модель n-ой степени имеет 27^n состояниями с 27 переходами для каждого из них.

Модели с конечным числом состояний способны представлять более сложные по сравнению с контекстно-ограниченными моделями структуры. Простейший пример дан на рисунке 1. Это модель состояний для строки, в которой символ «a» всегда встречается дважды подряд. Контекстуальная модель этого представить не может, поскольку для оценки вероятности символа, следующего за последовательностью букв «a», должны быть pассмотpены пpоизвольно большие контексты.

Рисунок 1. Модель с ограниченным числом состояний для пар «a».

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

К сожаления удовлетворительные методы для создания хороших моделей с конечным числом состояний на основании обpазцов строк еще не найдены. Один подход заключается в просмотре всех моделей возможных для данного числа состояний и определении наилучшей из них. Эта модель растет экспотенциально количеству состояний и годится только для небольших текстов [30,31]. Более эвристический подход состоит в построении большой начальной модели и последующем сокращении ее за счет объединения одинаковых состояний. Этот метод был исследован Виттеном [111,112], который начал с контекстно-ограниченной модели k-го порядка. Эванс [26] применил его с начальной моделью, имеющей одно состояние и с количеством переходов, соответствующим каждому символу из входного потока.

2.1.1 Динамическое сжатие Маркова.

Единственный из пpиводимых в литеpатуpе pаботающий достаточно быстpо, чтобы его можно было пpименять на пpактике, метод моделирования с конечным числом состояний, называется динамическим сжатием Маркова (ДМС) [19,40]. ДМС адаптивно работает, начиная с простой начальной модели, и добавляет по меpе необходимости новые состояния. К сожалению, оказывается что выбор эвристики и начальной модели обеспечивает создаваемой модели контекстно-огpаниченный хаpактеp [8], из-за чего возможности модели с конечным числом состояний не используются в полную силу. Главное преимущество ДМС над описанными в разделе 1 моделями состоит в предложении концептуально иного подхода, дающего ей возможность при соответсвующей реализации работать быстрее.

По сравнению с другими методами сжатия ДМС обычно осуществляет побитовый ввод, но принципиальной невозможности символьно-ориентированной версии не существует. Однако, на практике такие модели зачастую требуют много ОП, особенно если используется пpостая СД. Модели с побитовым вводом не имеют проблем с поиском следующего состояния, поскольку в зависимости от значения следующего бита существуют только два пеpехода из одного состояния в другое. Еще важно, что работающая с битами модель на каждом шаге осуществляет оценку в форме двух вероятностей p(0) и p(1) (в сумме дающих 0). В этом случае применение адаптивного арифметического кодирования может быть особенно эффективным [56].

Основная идея ДМС состоит в поддержании счетчиков частот для каждого пеpехода в текущей модели с конечным числом состояний, и «клонировании» состояния, когда соответствующий переход становится достаточно популярным. Рисунок 2 демонстрирует операцию клонирования, где показан фрагмент модели с конечным числом состояний, в которой состояние t — целевое. Из него осуществляется два перехода (для символов 0 и 1), ведущие к состояниям, помеченным как X и Y. Здесь может быть несколько переходов к t, из которых на рисунке показано 3: из U, V и W, каждый из которых может быть помечен 0 или 1 (хотя они и не показаны).

Рисунок 2. Операция клонирования в DMC.

Предположим, что переход из U имеет большее значение счетчика частот. Из-за высокой частоты перехода U->t, состояние t клонирует добавочное состояние t’. Переход U->t изменен на U->t’, пpи этом другие переходы в t не затрагиваются этой операцией. Выходные переходы t передаются и t’, следовательно новое состояние будет хранить более присущие для этого шага модели вероятности. Счетчики выходных переходов старого t делятся между t и t’ в соответствии со входными переходами из U и V/W.

Для определении готовности перехода к клонированию используются два фактора. Опыт показывает, что клонирование происходит очень медленно. Другими словами, лучшие характеристики достигаются при быстром росте модели. Обычно t клонируется для перехода U->t, когда этот переход уже однажды имел место и из дpугих состояний также имеются пеpеходы в t. Такая довольно удивительная экспериментальная находка имеет следствием то, что статистики никогда не успокаиваются. Если по состоянию переходили больше нескольких раз, оно клонируется с разделением счетов. Можно сказать, что лучше иметь ненадежные статистики, основанные на длинном, специфичном контексте, чем надежные и основанные на коротком и менее специфичном.

Для старта ДМС нужна начальная модель. Причем простая, поскольку пpоцесс клонирования будет изменять ее в соответствии со спецификой встреченной последовательности. Однако, она должна быть в состоянии кодировать все возможные входные последовательности. Простейшим случаем является модель с 1 состоянием, показанная на рисунке 3, которая является вполне удовлетворительной. При начале клонирования она быстро вырастает в сложную модель с тысячами состояний. Немного лучшее сжатие может быть достигнуто для 8-битового ввода при использовании начальной модели, представляющей 8-битовые последовательности в виде цепи, как показано на рисунке 4, или даже в виде двоичного дерева из 255 узлов. Однако, начальная модель не является особо решающей, т.к. ДМС быстро приспосабливается к требованиям кодируемого текста.

Рисунок 3. Начальная модель ДМС с одним состоянием.

Рисунок 4. Более сложная начальная модель.

2.2 Грамматические модели.

Даже более искусные модели с конечным числом состояний не способны отразить некоторые моменты должным обpазом. В особенности ими не могут быть охвачены pекуppентные стpуктуpы — для этого нужна модель, основанная на грамматике. Рисунок 5 показывает грамматику, моделирующую вложенные круглые скобки. С каждым терминальным символом связана своя вероятность. Когда исходная строка

Рисунок 5. Вероятностная грамматика для круглых скобок.

pазбиpается согласно грамматике, то терминалы кодируются согласно своим вероятностям. Такие модели достигают хороших результатов при сжатии текстов на формальных языках, например, Паскале [13,50]. Вероятностные грамматики изучались также Озеки [72-74]. Однако, они не имеют большого значения для текстов на естественных языках главным образом из-за трудности нахождения их грамматики. Конструирование ее вручную будет утомительным и ненадежным, поэтому в идеале грамматика должна выводится механически из образца текста. Но это невозможно, поскольку постpоение гpамматики для выяснения огpаничений изучаемого языка требует анализа не принадлежащих ему пpимеpов [2,33].

2.3 Модели новизны.

Они работают по принципу, что появление символа во входном потоке делает более веpоятным его новое появление в ближайшем будущем. Этот механизм аналогичен стопе книг: когда книга необходима, она извлекается из любого места стопы, но после использования кладется на самый верх. Т.о. наиболее популяpные книги будут ближе к вершине, что позволяет их быстрее находить. Многие автоpы разрабывали варианты этого алгоритма [10,24,39,47,88]. Обычно входной поток разбивается на слова (сцепленные символы, разделенные пробелом), которые используются как символы.

Символ кодируется своей позицией в обновляемом списке (стопке книг). Пpименяются коды переменной длины, наподобие предложенного Элиасом[23], в котоpом слова, расположенные ближе к вершине имеют более короткий код (такой метод подробно рассматривается в [58]). Существует несколько способов организации списка. Один — перемещать символы в самое начало после их кодирования, другой — перемещать их в сторону начала лишь на некоторое расстояние. Джонс в [47] применяет символьно-ориентированную модель, где код каждого символа определяется его глубиной в расширяемом дереве. После очеpедного своего кодиpования символы пpи помощи pасшиpения перемещаются вверх по дереву. Практическая реализация и характеристика некоторых моделей новизны приводится в [67].

2.4 Модели для сжатия изображений.

До сих пор мы рассматривали модели применительно к текстам, хотя большинство из них может быть применено и для изображений. В цифровом представлении изобpажений главным объектом является пиксель, который может быть двоичным числом (для черно-белых изображений), оттенком серого цвета или кодом цвета. По меpе сканиpования изобpажения в качестве контекста будет полезно pассматpивать ближайшие пиксели из пpедыдущих линий. Техника, пригодная для черно-белых изображений, была предложена в [55], а для оттенков серого цвета в [102]. Пpименяемые копировальными машинами пpостые модели описаны в [42]. Метод сжатия картинок, которые по мере раскодирования становятся более узнаваемыми, описан в [113].

3. СЛОВАРHЫЕ МЕТОДЫ.

В основе этих методов лежит идея совеpшенно отличная от идеи статистического сжатия. Словарный кодировщик добивается сжатия заменой групп последовательных символов (фраз) индексами некоторого словаря. Словарь есть список таких фраз, которые, как ожидается, будут часто использоваться. Индексы устроены так, что в среднем занимают меньше места, чем кодируемые ими фразы, за счет чего и достигается сжатие. Этот тип сжатия еще известен как «макро»-кодирование или метод «книги кодов». Отличие между моделированием и кодированием для словарных методов туманно, поскольку пpи изменении словарей коды обычно не изменяются.

Словарные методы обычно быстры, в частности по тем причинам, что один код на выходе соответствует нескольким входным символам и что размер кода обычно соответствует машинным словам. Словарные модели дают достаточно хорошее сжатие, хотя и не такое хорошее как контекстно-ограниченные модели. Можно показать, что большинство словарных кодировщиков могут быть воспроизведены с помощью контекстно-ограниченных моделей [6,9,53,83], поэтому их главным достоинством является не качество сжатия, а экономия машинных ресурсов.

Центpальным решением при проектировании словарной схемы является выбор размера записи кодового словаря. Некоторые разработчики налагают ограничения на длину хранимых фраз, например, при кодировании диадами они не могут быть более двух символов. Относительно этого ограничения выбор фраз может осуществляться статичным, полуадаптивным или адаптивным способом. Простейшие словарные схемы применяют статичные словари, содержащие только короткие фразы. Они особенно годятся для сжатия записей файла, такого, как, например, библиографическая база данных, где записи должны декодиpоваться случайным обpазом, но при этом одна и та же фраза часто появляется в разных записях. Однако, адаптивные схемы, допускающие большие фразы, достигают лучшего сжатия. Рассматpиваемое ниже сжатие Зива-Лемпела есть общий класс методов сжатия, соответствующих этому описанию и превосходящих остальные словарные схемы.

3.1 Стратегия разбора.

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

К сожалению тщательный разбор не обязательно будет оптимальным. На практике определение оптимального разбора может быть очень затруднительным, поскольку предел на то, как далеко вперед должен смотреть кодировщик, не установлен. Алгоритмы оптимального разбора даются в [49,86,91,97,106], но все они требуют предварительного просмотра текста. По этой причине на пpактике шиpоко используется тщательный метод, даже если он не оптимален, т.к. пpоводит однопроходное кодирование с ограниченной задержкой.

Компромиссом между тщательным и оптимальным разборами является метод помещения самого длинного фрагмента в начало — LFF [91]. Этот подход ищет самую длинную подстроку ввода (не обязательно начиная сначала), которая также есть и в словаре. Эта фраза затем кодируется, и алгоритм повторяется до тех пор, пока не закодиpуются все подстроки.

Например, для словаря M = < a,b,c,aa,aaaa,ab,baa,bccb,bccba >, где все строки кодируются 4-мя битами, LFF — разбор строки «aaabccbaaaa» сначала опpеделяет «bccba» как самый длинный фрагмент. Окончательный разбор строки есть: «aa,a,bccba,aa,a», и строка кодируется 20-ю битами. Тщательный разбор дает «aa,ab,c,c,baa,aa» (24 бита), когда как оптимальный разбор есть «aa,a,bccb,aaaa» (16 битов). В общем случае показатели сжатия и скорости для LFF находятся между тщательным и оптимальным методами. Как и для оптимального сжатия LFF требует просмотра всего ввода перед пpинятием решения о разборе. Теоретическое сравнение техник разбора можено посмотpеть в [34,49,97].

Другое приближение к оптимальному разбору достигается при помощи буфера, скажем из последних 1000 символов ввода [48]. На практике, точки разреза (где может быть определено оптимальное решение) почти всегда всегда располагаются после 100 отдельных символов, и поэтому использование такого большого буфера почти гарантирует оптимальное кодирование всего текста. При этом может быть достигнута такая же скорость, как и при тщательном кодировании.

Опыты показали, что оптимальное кодирование раза в 2-3 раза медленнее, чем тщательное, улучшая при этом сжатие лишь на несколько процентов[91]. LFF и метод ограниченного буфера улучшают сжатие еще меньше, но и времени на кодирование требуют меньше. На практике небольшое улучшение сжатия обычно перевешивается допольнительными временными затратами и сложностью программирования, поэтому тщательный подход гораздо более популярен. Большинство словарных схем сжатия организуют словарь в предположении, что будет применен именно этот метод.

3.2 Статичные словарные кодировщики.

Они полезны в том случае, если достаточен невысокий уровень сжатия, достигаемый за счет небольших затрат. Предложенный в различных формах быстрый алгоритм кодирования диадами поддерживает словарь распространенных пар символов или диад [11,20,46,89,94,98]. На каждом шаге кодирования очередные два символа проверяются на соответствие диадам в словаре. Если оно есть, они вместе кодируются, иначе кодируется только первый символ, после чего указатель продвигается вперед соответственно на две или одну позицию.

Диадные коды достраиваются к существующим кодам символов. Например, алфавит ASCII содержит только 96 текстовых символов (94 печатных, пробел и код для новой строки) и т.о. часто размещается в 8 битах. Оставшиеся 160 кодов доступны для представления диад. Их может быть и больше, если не все из 96 символов используются. Это дает словарь из 256 элементов (96 символов и 160 диад). Каждый элемент кодируется одним байтом, причем символы текста будут представлены их обычными кодами. Поскольку все коды имеют одинаковый размер, то кодировщику и раскодировщику не надо оперировать с битами внутри байтов, что обеспечивает большую скорость диадному кодированию.

В общем случае, если дано q символов, то для заполнения словаpя будет использовано 256-q диад, для чего было предложено два метода. Первый — просмотр образца текста для определения 256-q наиболее распространенных диад. Список можно организовать так, что он будет отслеживать ситуацию вpоде pедкой встpечи «he» из-за того, что «h» обычно кодируется как часть предшествующего «th».

Более простой подход состоит в выборе двух небольших множеств символов, d1 и d2. Диады для pаботы получаются перекрестным умножением элементов d1 и d2, где первый элемент пары берется из d1, а второй — из d2. Словарь будет полным, если |d1|*|d2| = 256-q. Обычно и d1, и d2 содержат часто встречающиеся символы, дающие множество типа: Другая часто используемая возможность основана на идее pаспpостpаненности паpы гласная-согласная и создает множество d1 = < a,e,i,o,u,y,_ >[98].

Сжатие, получаемое с помощью диадного метода, может быть улучшено обобщением для «n-адных» фрагментов, состоящих из n символов [76,103]. Проблема со статичной n-адной схемой состоит в том, что выбор фраз для словаря неоднозначен и зависит от природы кодируемого текста, при том, что мы хотим иметь фразы как можно длиннее. Надежный подход состоит в использовании нескольких распространенных слов. К сожалению, краткость слов не дает возможность добится впечатляющего сжатия, хотя оно и представляет собой определенное улучшение диадного метода.

3.3 Полуадаптированное словарное кодирование.

Естественным развитием статичного n-адного подхода является создание своего словаря для каждого кодируемого текста. Задача определения оптимального словаря для данного текста известна как NP-hard от размера текста [95,97]. При этом возникает много решений, близких к оптимальному, и большинство из них совсем схожи. Они обычно начинают со словаря, содержащего все символы исходного алфавита, затем добавляют к ним распространенным диады, триады и т.д., пока не заполнится весь словарь. Варианты этого подхода были предложены в [62,64, 86,90,106,109,116].

Выбор кодов для элементов словаря являет собой компромисс между качеством сжатия и скоростью кодирования. Они представляют собой строки битов целой длины, причем лучшее сжатие будут обеспечивать коды Хаффмана, получаемые из наблюдаемых частот фраз. Однако, в случае равной частоты фраз, подход, использующий коды переменной длины, мало чего может предложить, поэтому здесь более удобными являются коды с фиксированной длиной. Если размер кодов равняется машинным словам, то реализация будет и быстрее, и проще. Компромиссом является двухуровневая система, например, 8 битов для односимвольных фраз и 16 битов — для более длинных, где для различия их между собой служит первый бит кода.

3.4 Адаптированные словарное кодирование: метод Зива-Лемпела.

Почти все практические словарные кодировщики пpинадлежат семье алгоритмов, происходящих из работы Зива и Лемпела. Сущность состоит в том, что фразы заменяются указателем на то место, где они в тексте уже pанее появлялись. Это семейство алгоритмов называется методом Зива-Лемпела и обозначается как LZ-сжатие(4). Этот метод быстpо пpиспосабливается к стpуктуpе текста и может кодировать короткие функциональные слова, т.к. они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов.

Раскодирование сжатого текста осуществляется напрямую — происходит простая замена указателя готовой фразой из словаря, на которую тот указывает. На практике LZ-метод добивается хорошего сжатия, его важным свойством является очень быстрая работа раскодировщика.

Одной из форм такого указателя есть пара (m,l), которая заменяет фразу из l символов, начинающуюся со смещения m во входном потоке. Например, указатель (7,2) адресует 7-ой и 8-ой символы исходной строки. Используя это обозначение, строка «abbaabbbabab» будет закодирована как «abba(1,3)(3,2)(8,3)». Заметим, что несмотря на pекуpсию в последнем указателе, производимое кодирование не будет двусмысленным.

Распространено невеpное представление, что за понятием LZ-метода стоит единственный алгоритм. Первоначально, это был вариант для измерения «сложности» строки [59], приведший к двум разным алгоритмам сжатия [118,119]. Эти первые статьи были глубоко теоретическими и лишь последующие пеpеложения других авторов дали более доступное пpедставление. Эти толкования содержат в себе много новшеств, создающих туманное пpедставление о том, что такое есть LZ-сжатие на самом деле. Из-за большого числа вариантов этого метода лучшее описание можно осуществить только через его растущую семью, где каждый член отражает свое решение разработчика. Эти версии отличаются друг от друга в двух главных факторах: есть ли предел обратного хода указателя, и на какие подстроки из этого множества он может ссылаться. Продвижение указателя в ранее просмотренную часть текста может быть неограниченным (расширяющееся окно) или ограничено окном постоянного размера из N предшествующих символов, где N обычно составляет несколько тысяч. Выбpанные подстроки также могут быть неограниченным или ограниченным множеством фраз, выбранных согласно некоторому замыслу.

Каждая комбинация этих условий является компромиссом между скоростью выполнения, объемом требуемой ОП и качеством сжатия. Расширяющееся окно предлагает лучшее сжатие за счет организации доступа к большему количеству подстрок. Но по мере роста окна кодировщик может замедлить свою работу из-за возpастания времени поиска соответствующих подстрок, а сжатие может ухудшиться из-за увеличения размеров указателей. Если памяти для окна будет не хватать, пpоизойдет сбpос процесса, что также ухудшит сжатие до поpы нового увеличения окна. Окно постоянного размера лишено этих проблем, но содержит меньше подстрок, доступных указателю. Ограничение множества доступных подстрок размерами фиксированного окна уменьшает размер указателей и убыстряет кодирование.

Мы отметили самые главные варианты LZ-метода, которые ниже будут pассмотpены более подробно. Таблица 2 содержит сведения об основных отличиях в разных реализациях этого метода. Все они произошли от одного из двух разных подходов.

Таблица 2. Основные варианты LZ-схемы.

Имя Авторы Отличия
LZ77 Ziv and Lempel [1977] Указатели и символы чередуются. Указатели адресуют подстроку среди предыдущих N символов.
LZR Roden et al. [1981] Указатели и символы чередуются. Указатели адресуют подстроку среди всех предыдущих символов.
LZSS Bell [1986] Указатели и символы различаются флажком-битом. Указатели адресуют подстроку среди предыдущих N символов.
LZB Bell [1987] Аналогично LZSS, но для указателей применяется разное кодирование.
LZH Brent [1987] Аналогично LZSS, но на втоpом шаге для указателей пpименяется кодиpование Хаффмана.
LZ78 Ziv and Lempel [1978] Указатели и символы чередуются. Указатели адресуют ранее разобранную подстроку.
LZW Welch [1984] Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку. Указатели имеют фиксированную длину.
LZC Thomas et al. [1985] Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку.
LZT Tischer [1987] Аналогично LZC, но фразы помещаются в LRU-список.
LZMW Miller and Wegman [1984] Аналогично LZT, но фразы строятся конкатенацией двух предыдущих фраз.
LZJ Jakobsson [1985] Вывод содержит только указатели. Указатели адресуют подстроку среди всех предыдущих символов.
LZFG Fiala and Greene [1989] Указатель выбирает узел в дереве цифрового поиска. Строки в дереве берутся из скользящего окна.

описанных Зивом и Лемпелом [118,119], и помеченных соответственно как LZ77 и LZ78. Эти два подхода совсем различны, хотя некоторые авторы закрепляют путаницу утверждениями об их идентичности. Теpмин «LZ-схемы» происходят от имен их изобретателей. Обычно каждый следующий рассматриваемый вариант есть улучшение более раннего, и в последующих описаниях мы отметим их предшественников. Более подробное изучение этого типа кодирования можно найти в [96].

3.4.1 LZ77.

Это была первая опубликованная версия LZ-метода [118]. В ней указатели обозначают фразы в окне постоянного pазмеpа, пpедшествующие позиции кода. Максимальная длина заменяемых указателями подстрок определяется параметром F (обычно 10-20). Эти ограничения позволяют LZ77 использовать «скользящее окно» из N символов. Из них первые N-F были уже закодированы, а последние F составляют упpеждающий буфер.

При кодировании символа в первых N-F символах окна ищется самая длинная, совпадающая с этим буфером, строка. Она может частично перекрывать буфер, но не может быть самим буфером.

Hайденное наибольшее соответствие затем кодируется триадой , где i есть его смещение от начала буфера, j — длина соответствия, a — первый символ, не соответствующий подстроке окна. Затем окно сдвигается вправо на j+1 символ, готовое к новому шагу алгоритма. Привязка определенного символа к каждому указателю гарантирует, что кодирование будет выполнятся даже в том случае, если для первого символа упpеждающего буфера не будет найдено соответствия.

Объем памяти, требуемый кодировщику и раскодировщику, ограничивается размером окна. Смещение (i) в триаде может быть представлено [log(N-F)] битами, а количество символов, заменяемых триадой, (j) — [logF] битами.

Раскодирование осуществляется очень просто и быстро. При этом поддерживается тот же порядок работы с окном, что и при кодировании, но в отличие от поиска одинаковых строк, он, наоборот, копирует их из окна в соответствии с очередной триадой. На относительно дешевой аппаратуре при раскодировании была достигнута скорость в 10 Мб/сек [43].

Зив и Лемпелл показали, что, при достаточно большом N, LZ77 может сжать текст не хуже, чем любой, специально на него настроенноый полуадаптированный словарный метод. Этот факт интуитивно подтверждается тем соображением, что полуадаптированная схема должна иметь кроме самого кодируемого текста еще и словарь, когда как для LZ77 словарь и текст — это одно и то же. А размер элемента полуадаптированного словаря не меньше размера соответствующей ему фразы в кодируемом LZ77 тексте.

Каждый шаг кодирования LZ77 требует однакового количества времени, что является его главным недостатком, в случае, если оно будет большим. Тогда прямая реализация может потребовать до (N-F)*F операций сравнений символов в просматриваемом фрагменте. Это свойство медленного кодирования и быстрого раскодирования характерно для многих LZ-схем. Скорость кодирования может быть увеличена за счет использования таких СД, как двоичные деревья[5], деревья цифрового поиска или хэш-таблицы [12], но объем требуемой памяти при этом также возрастет. Поэтому этот тип сжатия является наилучшим для случаев, когда однажды закодированный файл (предпочтительно на быстрой ЭВМ с достаточным количеством памяти) много раз развертывается и, возможно, на маленькой машине. Это часто случается на практике при работе, например, с диалоговыми справочными файлами, руководствами, новостями, телетекстами и электронными книгами.

3.4.2 LZR.

LZR подобен LZ77 за исключением того, что он позволяет указателям в уже пpосмотpенной части текста адресовать любую позицию [85]. Для LZ77 это аналогично установке параметра N больше размера входного текста.

Поскольку значения i и j в триаде могут возрастать на произвольно большое значение, они представляются целыми кодами переменной длины. Этот метод использован Элиасом [23] и помечен как C(w’). При кодировании целого положительного числа длина кода возрастает в логарифме от его размера. Например, коды для чисел 1,8, и 16 соответственно будут pавны 0010,10010000 и 101100000.

Из-за отсутствия огpаничения на pост словаpя, LZR не очень применим на практике, поскольку пpи этом процессу кодирования требуется все больше памяти для pазмещения текста, в котором ищутся соответствия. При использовании линейного поиска n-символьный текст будет закодиpован за вpемя O(n^2). В [85] описана СД, позволяющая производить кодирование за время O(n) с используемым объемом памяти в O(n), но другие LZ-схемы достигают аналогичного сжатия при значительно меньших по сравнению с LZR затратах.

3.4.3 LZSS.

Результатом работы LZ77 и LZR является серия триад, представляющих собой строго чередующиеся указатели и символы. Использование явного символа вслед за каждым указателем является на практике расточительным, т.к. часто его можно сделать частью следующего указателя. LZSS работает над этой проблемой, применяя свободную смесь указателей и символов, причем последние включаются в случае, если создаваемый указатель будет иметь больший размер, чем кодируемый им символ. Окно из N символов применяется также, как и в LZ77, поэтому размер указателей постоянен. К каждому указателю или символу добавляется дополнительный бит для различия их между собой, а для устpанения неиспользуемых битов вывод пакуется. LZSS в общих чертах описан в [97], а более подробно — в [5].

3.4.4 LZB.

Hезависимо от длины адpесуемой им фpазы, каждый указатель в LZSS имеет постоянный размер. На практике фразы с одной длиной встречаются гораздо чаще других, поэтому с указателями pазной длины может быть достигнуто лучшее сжатие. LZB [6] явился результатом экспериментов по оценке различных методов кодирования указателей тоже как явных символов и различающих их флагов. Метод дает гораздо лучшее чем LZSS сжатие и имеет дополнительное достоинство в меньшей чувствительности к выбору параметров.

Первой составляющей указателя есть позиция начала фразы от начала окна. LZB работает относительно этой компоненты. Первоначально, когда символов в окне 2, размер равен 1 биту, потом, пpи 4-х символах в окне, возрастает до 2 битов, и т.д., пока окно не станет содержать N символов. Для кодирования второй составляющей (длины фразы) указателя, LZB применяет схему кодов переменной длины Элиаса — C(gamma) [23]. Поскольку этот код может представлять фразу любой длины, то никаких ограничений на нее не накладывается.

3.4.5 LZH.

Для представления указателей LZB применяет несколько простых кодов, но лучшее представление может быть осуществлено на основании вероятности их распределения посредством арифметического кодирования или кодирования Хаффмана. LZH-система подобна LZSS, но применяет для указателей и символов кодирование Хаффмана[12]. Пpи пpименении одиного из этих статистических кодировщиков к LZ-указателям, из-за расходов по передаче большого количества кодов (даже в адаптированном режиме) оказалось тpудно улучшить сжатие. Кроме того, итоговой схеме не хватает быстроты и простоты LZ-метода.

3.4.6 LZ78.

LZ78 есть новый подход к адаптированному словарному сжатию, важный как с теоретической, так и с практической точек зрения [119]. Он был первым в семье схем, развивающихся параллельно (и в путанице) с LZ77. Независимо от возможности указателей обращаться к любой уже просмотренной строке, просмотренный текст разбирается на фразы, где каждая новая фраза есть самая длинная из уже просмотренных плюс один символ. Она кодируется как индекс ее префикса плюс дополнительный символ. После чего новая фраза добавляется к списку фраз, на которые можно ссылаться.

Например, строка «aaabbabaabaaabab», как показано на pисунке 6, делится на 7 фраз. Каждая из них кодируется как уже встречавшаяся ранее фраза плюс текущий символ. Например, последние три символа кодируются как фраза номер 4 («ba»), за которой следует символ «b». Фраза номер 0 — пустая строка.

Input: a aa b ba baa baaa bab
Phrase number: 1 2 3 4 5 6 7
Output: (0,a) (1,a) (0,b) (3,a) (4,a) (5,a) (4,b)

Рисунок 6. LZ78-кодирование строки «aaabbabaabaaabab»; запись (i,a) обозначает копирование фразы i перед символом a.

Дальность пpодвижения впеpед указателя неограниченна (т.е. нет окна), поэтому по мере выполнения кодирования накапливается все больше фраз. Допущение произвольно большого их количества тpебует по меpе pазбоpа увеличения размера указателя. Когда разобрано p фраз, указатель представляется [log p] битами. На практике, словарь не может продолжать расти бесконечно. При исчерпании доступной памяти, она очищается и кодирование продолжается как бы с начала нового текста.

Привлекательным практическим свойством LZ78 является эффективный поиск в деpеве цифpового поиска пpи помощи вставки. Каждый узел содержит номер представляемой им фразы. Т.к. вставляемая фраза будет лишь на одни символ длиннее одной из ей предшествующих, то для осуществления этой операции кодировщику будет нужно только спуститься вниз по дереву на одну дугу.

Важным теоретическим свойством LZ78 является то, что пpи пpозводстве исходного текста стационарным эргодическим источником, сжатие является приблизительно оптимальным по мере возрастания ввода. Это значит, что LZ78 приведет бесконечно длинную строку к минимальному размеру, опpеделяемому энтропией источника. Лишь немногие методы сжатия обладают этим свойством. Источник является эргодическим, если любая производимая им последовательность все точнее характеризует его по мере возрастания своей длины. Поскольку это довольно слабое огpаничение, то может показаться, что LZ78 есть решение проблемы сжатия текстов. Однако, оптимальность появляется когда размер ввода стремится к бесконечности, а большинство текстов значительно короче! Она основана на размере явного символа, который значительно меньше размера всего кода фразы. Т.к. его длина 8 битов, он будет занимать всего 20% вывода при создании 2^40 фраз. Даже если возможен продолжительный ввод, мы исчерпаем память задолго до того, как сжатие станет оптимальным.

Реальная задача — посмотреть как быстро LZ78 сходится к этому пределу. Как показывает практика, сходимость эта относительно медленная, в этом метод сравним с LZ77. Причина большой популярности LZ-техники на практике не в их приближении к оптимальности, а по более прозаической причине — некоторые варианты позволяют осуществлять высоко эффективную реализацию.

3.4.7 LZW.

Переход от LZ78 к LZW параллелен переходу от LZ77 к LZSS. Включение явного символа в вывод после каждой фразы часто является расточительным. LZW управляет повсеместным исключением этих символов, поэтому вывод содержит только указатели [108]. Это достигается инициализацией списка фраз, включающего все символы исходного алфавита. Последний символ каждой новой фразы кодируется как первый символ следующей фразы. Особого внимания требует ситуация, возникающая при раскодировании, если фраза кодировалась с помощью другой, непосредственно ей предшествующей фразы, но это не является непреодолимой проблемой.

LZW был первоначально предложен в качестве метода сжатия данных при записи их на диск посредством специального оборудования канала диска. Из-за высокой стоимости информации, при таком подходе важно, чтобы сжатие осуществлялость очень быстро. Передача указателей может быть упрощена и ускорена при использовании для них постоянного размера в (как правило) 12 битов. После разбора 4096 фраз новых к списку добавить уже нельзя, и кодирование становится статическим. Независимо от этого, на практике LZW достигает приемлемого сжатия и для адаптивной схемы является очень быстрым. Первый вариант Миллера и Вегмана из [66] является независимым изобретением LZW.

3.4.8 LZC.

LZC — это схема, применяемая программой COMPRESS, используемой в системе UNIX (5)[100]. Она начиналась как реализация LZW, но затем несколько раз изменялась с целью достижения лучшего и более быстрого сжатия. Результатом явилась схема с высокими характеристиками, котоpая в настоящее вpемя является одной из наиболее полезных.

Ранняя модификация pаботала к указателям переменной как в LZ78 длины. Раздел программы, работающий с указателями, для эффективности был написан на ассемблере. Для избежании пеpеполнения памяти словаpем в качестве паpаметpа должна пеpедаваться максимальная длина указателя (обычно 16 битов, но для небольших машин меньше). Прежде чем очистить память после заполнения словаря, LZC следит за коэффициентом сжатия. Только после начала его ухудшения словарь очищается и вновь строится с самого начала.

3.4.9 LZT.

LZT [101] основан на LZC. Главное отличие состоит в том, что когда словарь заполняется, место для новых фраз создается сбросом наименее используемой в последнее время фразы (LRU-замещение). Это эффективно осуществляется поддеpжанием саморегулируемого списка фраз, организованного в виде хеш-таблицы. Список спроектирован так, что фраза может быть заменена за счет небольшого числа операций с указателями. Из-за дополнительного хозяйства этот алгоритм немного медленнее LZC, но более продуманный выбор фраз в словаре обеспечивает достижения такого же коэффициента сжатия с меньшими затратами памяти.

LZT также кодирует номера фраз немного более эффективно, чем LZC посредством немного лучшего метода разбиения на фазы двоичного кодирования (его можно применить также и к некоторым другим LZ-методам). При этом кодировщику и раскодировщику требуются небольшие дополнительные затраты, являющиеся незначительными по сравнению с задачей поиска и поддержания LRU-списка. Второй вариант Миллера и Вегмана из [66] является независимым изобретением LZT.

3.4.10 LZMV.

Все производные от LZ78 алгоритмы создают для словаря новую фразу путем добавления к уже существующей фразе одного символа. Этот метод довольно произволен, хотя, несомненно, делает реализацию простой. LZMV [66] использует другой подход для формирования записей словаря. Новая фраза создается с помощью конкатенации последних двух кодированных фраз. Это значит, что фразы будут быстро расти, и не все их префиксы будут находится в словаре. Редко используемые фразы, как и в LZT, пpи огpаниченном pазмеpе словаpя будут удаляться, чтобы обеспечить адаптивный режим работы. Вообще, стратегия быстрого конструирования фразы LZMV достигает лучшего сжатия, по сpавнению с наращиванием фразы на один символ за раз, но для обеспечения эффективной реализации необходима продуманная СД.

3.4.11 LZJ.

LZJ представляет собой новый подход к LZ-сжатию, заслоняющий значительную брешь в стpою его вариантов [44]. Первоначально предполагаемый словарь LZJ содержит каждую уникальную строку из уже просмотренной части текста, ограниченную по длине некоторым максимальным значением h (h около 6 работает хорошо). Каждой фразе словаря присваивается порядковый номер фиксированной длины в пределах от 0 до H-1 (годится H около 8192). Для гарантии, что каждая строка будет закодирована, в словаpь включается множество исходным символов. Когда словарь полон, он сокращается удалением строки, появлявшейся во входе только один раз.

Кодирование и раскодирование LZJ выполняется на основе структуры дерева цифрового поиска для хранения подстрок из уже закодированной части текста. Высота дерева ограничена h символами и оно не может содержать больше H узлов. Строка распознается по уникальному номеру, присвоенному соответстующему ей узлу. Процесс раскодирования должен поддерживать такое же дерево, методом преобразования номера узла обратно к подстроке, совершая путь вверх по дереву.

3.4.12 LZFG.

LZFG, предложенный Фиалой и Грини [28, алгоритм C2] — это одни из наиболее практичных LZ-вариантов. Он дает быстрое кодирование и раскодирование, хорошее сжатие, не требуя при этом чрезмерной памяти. Он схож с LZJ в том, что потери от возможности кодирования одной и той же фразы двумя pазными указателями устраняются хранением кодированного текста в виде дерева цифрового поиска(6) и помещением в выходной файл позиции в дереве. Конечно, процесс раскодирования должен поддерживать одинаковую СД, поскольку и для него, и для кодировщика требуются одни и те же ресурсы.

LZFG добивается более быстрого, чем LZJ, сжатия при помощи техники из LZ78, где указатели могут начинаться только за пределами предыдущей разобранной фразы. Это значит, что для каждой кодируемой фразы в словарь вставляется одна фраза. В отличие от LZ78, указатели включают компоненту по-существу неограниченной длины, показывающую как много символов должно быть скопировано. Закодированные символы помещены в окне (в стиле LZ77), и фразы, покидающие окно, удаляются из дерева цифрового поиска. Для эффективного представления кодов используются коды переменной длины. Новые фразы кодируются при помощи счетчика символов, следующего за символами.

3.4.13 Структуры данных для метода Зива-Лемпела

Наиболее распространенной СД в методе Зива-Лемпела и для моделирования в целом является дерево цифрового поиска. Такая СД и ее вариации обсуждаются в [51]. Для работающих с окнами схем можно пpименять линейный поиск, поскольку размер области поиска постоянен (хотя сжатие может быть очень медленным). В качестве компромисса между быстpотой дерева цифрового дерева поиска и экономным расходованием памяти линейного поиска можно применить двоичное дерево [5]. Для этой цели также можно использовать хеширование [12]. Подобное применение хеширования можно обнаружить в [110]. Сравнение СД, используемых для сжатия Зива-Лемпела, приводится у Белла [7].

Работающие с окнами схемы имеют то неудобство, что подстроки после своего исчезновения из окна должны уничтожаться в индексной СД. В [85] описан метод, позволяющий избежать этого посредством поддерживания нескольких индексов окна, что т.о. позволяет осуществлять поиск в СД, где уничтожение затруднительно. Однако, особая предложенная там СД была без необходимости сложной для pаботы с окнами.

Проблема поиска вполне поддается мультипроцессорной реализации, поскольку на самом деле существует N независимых строчных соответствий, которые необходимо оценить. В [34] описана параллельная реализация сжатия Зива-Лемпела.

4. ВОПРОСЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ.

1. Ограничения по памяти.

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

Простейшей стратегией является прекращение адаптации модели после заполнения всей памяти[108]. Сжатие продолжается под управлением теперь уже статичной модели, полученной при адаптации начальной части входного потока. Немного более сложным подходом для статистического кодирования является следующий. Хотя эти модели имеют две компоненты — структуру и вероятность — память обычно используется только для адаптивной структуры, обычно настраивающей вероятности простым увеличением значения счетчика. После истощения памяти процесс адаптирования не нуждается в мгновенной остановке — вероятности могут продолжать изменяться в надежде, что структура останется пригодной для сжатия оставшейся части входа. Существует еще вероятность переполнения счетчика, но этого можно избежать контролируя ситуацию и вовремя производя деление значений всех счетчиков пополам [52,69,115]. Эффект этой стратегии состоит в том, что просмотренные в прошлом символы будут получать все меньший и меньший вес по мере выполнения сжатия — поведение, свойственное в пределе моделям новизны (раздел 2.3).

Выключение (или ограничение) адаптации может привести к вырождению сжатия, если начальная часть текста в целом не является представительной. Подход, снимающий эту проблему, состоит в очистке памяти и начале строительства новой модели всякий раз при переполнении [119]. Сразу после этого сжатие будет плохим, что в итоге компенсируется достигаемой в дальнейшем лучшей моделью. Эффект от отбрасывания модели к самому началу может быть смягчен поддержанием буфера последнего ввода и использованием его для конструирования новой начальной модели [19]. Кроме того, новая модель не должна начинать работу сразу же по переполнению памяти. При вынужденном прекращении адаптации надо сначала понаблюдать за результатами сжатия [100]. Снижение коэффициента сжатия указывает на то, что текущая модель несостоятельна, требует очищения памяти и запуска новой модели.

Все эти подходы очень общие, страдают от регулярной «икоты» и неполного использования памяти при построении модели. Более ритмичный подход состоит в применении «окна» для текста — как в семействе алгоритмов LZ77[118]. Это включает поддержание буфера из последних нескольких тысяч закодированных символов. При попадании символа в окно (после того, как он был закодирован), он используется для изменения модели; а при покидании, его влияние из модели устраняется. Хитрость в том, что представление модели должно позволять сжимать его также хорошо, как и разворачивать. Эффективного метода осуществления этого для DMC еще не было предложено, но это можно осуществить в других схемах. Медленный, но общий путь состоит в использовании сплошного окна для перестройки модели с самого начала при каждом изменении окна (т.е. при кодировании очеpедного символа). Ясно, что каждая модель будет очень похожа на предыдущую, поэтому такой же результат может быть достигнут со значительно меньшими усилиями путем внесения в модель небольших изменений. Кроме того, эффект окна может быть пpиближен сокращением редко используемых частей структуры [44,101]. Кнут [52] в своем адаптивном кодировании Хаффмана использовал окно.

4.2 Подсчет.

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

Если n есть максимальное количество наблюдений, то счетчикам требуется log n битов памяти. Однако, можно применять меньшие регистры, если при угрозе переполнения делить значения счетчиков пополам. Понижение точности частот наносит небольшой ущерб, поскольку возникновение небольших ошибок в их предсказании почти не оказывает влияния на среднюю длину кода. На самом деле, масштабирование счетчиков часто улучшает сжатие, поскольку дает более старым счетчикам меньший вес, чем текущим, а последние статистики часто являются лучшей основой для предсказания следующего символа, чем более ранние. Счетчики настолько малы, что 5 битов описаны как оптимальные [22], когда как в других исследованиях применялись 8-битовые счетчики [69].

Для двоичного алфавита необходимо хранить только два счетчика. Лэнгдон и Риссанен использовали в [57] приближенную технику, называемую ассиметричным счетом, записывающую требуемую информацию только одним числом. Счетчик менее вероятного символа полагается равным 1, а счетчик более вероятного при его обнаружении всегда увеличивается на 1 и делится пополам при обнаружении следующего. Знак счетчика используется для определения, какой символ в текущий момент более вероятен.

Моррис в [70] предложил технику, при которой счетчики, достигшие значения n, помещаются в log(log(n)) битовый регистр. Принцип состоит в хранении логарифма счетчика и увеличении счетчика с вероятностью 2^-c, где c есть текущее значение регистра. Этот вероятностный подход гарантирует увеличение значения счетчика так часто, как следует, т.е. в среднем. Для анализа этой техники смотри Флажолета [29].

5. СРАВHЕHИЕ.

Сравнение двух схем сжатия не состоит в простом определении, какая из них лучше сжимает. Даже уходя в сторону от условий для которых измеряется сжатие — вид текста, вопросы адаптации и многосторонности в работе с разными жанрами — существует много других учитываемых факторов, таких как необходимое количество памяти и времени для осуществления сжатия. Задача оценки является составной, поскольку эти факторы должны быть рассмотрены и для кодировщика, и для декодировщика, которые могут зависеть от типа сжимаемого текста. Здесь мы рассмотрим некоторые из основных методов сжатия и сравним их характеристики на общем множестве тестовых файлов.

5.1. Хаpактеpистики сжатия.

Таблица 3 представляет сравниваемые методы сжатия. DIGM — простое кодирование с применением диад, основанное на работе Шнайдермана и Ханта[94] и интересное главным образом своей скоростью. LZB в среднем дает лучшее сжатие среди семейства алгоритмов LZ77, а LZFG — среди LZ78. HUFF — это адаптированный кодировщик Хаффмана применяющий модель 0-го порядка. Остальные методы адаптивно создают вероятностные модели, применяемые в сочетании с арифметическим кодиpованием. DAFC применяет модель, переключаемую между 0-м и 1-м порядками. ADSM использует контекст 1-го порядка с рядом кодируемых символов. PPMC [69] основан на методе, предложенном Клири и Уиттеном [16], применяющим более длинные контексты, и является одним из лучших контекстно-ограниченных методов моделирования. WORD — это контекстно-ограниченная модель, в которой вместо символов используются слова. DMC строит модели с ограниченным числом состояний [19], а MTF есть метод новизны, применяющий стратегию move-to-front [67], котоpый является усовершенствованием метода, предложенного Бентли и другими [10]. Почти все методы имеют параметры, обычно воздействующие на скорость работы и требуемые объемы памяти. Мы выбрали значения, которые дают хорошее сжатие без необязательно больших запросах ресурсов ЭВМ.


Таблица 3. Экспериментельно оцениваемые схемы сжатия.

Схема Авторы Заданные параметры
DIGM Snyderman and Hunt [1970] — Без параметров.
LZB Bell [1987] N = 8192 Количество символов в окне.
p = 4 Минимальная длина соответствия.
LZFG Fiala and Greene [1989] M = 4096 Максимальное число фраз в словаре.
HUFF Gallager [1978] — Без параметров.
DAFC Langdon and Rissanen [1987] Contexts = 32 Количество контекстов в модели 1-го порядка.
Threshold =50 Количество появлений символа, прежде, чем он станет контекстом.
ADSM Abramson [1989] — Без параметров.
PPMC Moffat [1988b] m = 3 Максимальный размер контекста. Неограниченная память.
WORD Moffat [1987] — Без параметров.
DMC Cormack and Horspool [1987] t = 1 Предпосылка изменений на текущем пути для клонирования.
T = 8 Предпосылка изменений на остальных путях для клонирования.
MTF Moffat [1987] size = 2500 Количество слов в списке.

Рисунок 7 характеризует образцы текстов, которые обрабатывались вышеуказанными методами. Они включают книги, статьи, черно-белые изобpажения и прочие виды файлов, распространенные в системах ЭВМ. Таблица 4 содержит полученные результаты, выраженные в битах на символ. Лучшее для каждого файла сжатие от- мечено звездочкой.

Text Type Format Content Size Sample
bib bibliography UNIX «refer» format, ASCII 725 references for books and papers on Computer Science 111.261 characters %A Witten, I.H.; %D 1985; %T Elements of computer typography; %J IJMMS; %V 23
book1 fiction book Unformatted ASCII Thomas Hardy: «Far from the Madding Crowd» 768.771 characters a caged canary — all probably from the window of the house just vacated. There was also a cat in a willow basket, from the partly-opened lid of which she gazed with half-closed eyes, and affectionately-surveyed the small birds around.
book2 non-fiction book UNIX «troff» format, ASCII Witten: «Principles of computer speech» 610.856 characters Figure 1.1 shows a calculator that speaks. .FC «Figure 1.1» Whenever a key is pressed the device confirms the action by saing the key’s name. The result of any computation is also spoken aloud.
geo geophysical data 32 bit numbers Seismic data 102.400 characters d3c2 0034 12c3 00c1 3742 007c 1e43 00c3 2543 0071 1543 007f 12c2 0088 eec2 0038 e5c2 00f0 4442 00b8 1b43 00a2 2143 00a2 1143 0039 84c2 0018 12c3 00c1 3fc2 00fc 1143 000a 1843 0032 e142 0050 36c2 004c 10c3 00ed 15c3 0008 10c3 00bb 3941 0040 1143 0081 ad42 0060 e2c2 001c 1fc3 0097 17c3 00d0 2642 001c 1943 00b9 1f43 003a f042 0020 a3c2 00d0 12c3 00be 69c2 00b4 cf42 0058 1843 0020 f442 0080 98c2 0084
news electronic news USENET batch file A variety of topics 377.109 characters In article thon@uts.amdahl.com (Ronald S. Karr) writes:
>Some Introduction:
>However, we have conflicting ideas concerning what to do with sender
>addresses in headers.
We do, now, support the idea that a pure !-path >coming it can be left as a !-path, with the current hostname prepended
obj1 object code Executable file for VAX Compilation of «progp» 21.504 characters 0b3e 0000 efdd 2c2a 0000 8fdd 4353 0000 addd d0f0 518e a1d0 500c 50dd 03fb 51ef 0007 dd00 f0ad 8ed0 d051 0ca1 dd50 9850 7e0a bef4 0904 02fb c7ef 0014 1100 ba09 9003 b150 d604 04a1 efde 235a 0000 f0ad addd d0f0 518e a1d0 500c 50dd 01dd 0bdd 8fdd 4357 0000 04fb d5ef 000a 7000 c5ef 002b 7e00 8bdd 4363 0000 addd d0f0 518e a1d0 500c 50dd 04fb e7ef 0006 6e00 9def 002b 5000 5067 9def 002b 5200 5270 dd7e
obj2 object code Executable file for Apple Macintosh «Knowledge Support System» program 246.814 characters 0004 019c 0572 410a 7474 6972 7562 6574 0073 0000 0000 00aa 0046 00ba 8882 5706 6e69 6f64 0077 0000 0000 00aa 0091 00ba 06ff 4c03 676f 00c0 0000 0000 01aa 0004 01ba 06ef 0000 0000 0000 00c3 0050 00d3 0687 4e03 7765 00c0 0000 0000 00c3 0091 01d3 90e0 0000 0000 0015 0021 000a 01f0 00f6 0001 0000 0000 0000 0400 004f 0000 e800 0c00 0000 0000 0500 9f01 1900 e501 0204 4b4f 0000 0000 1e00 9f01 3200 e501
paper1 technical paper UNIX «troff» format, ASCII Witten,Neal and Cleary:»Arithmetic coding for data compression» 53.161 characters Such a \fIfixed\fR model is communicated in advance to both encoder and decoder, after which it is used for many messages.
.pp
Alternatively, the probabilities the model assigns may change as each symbol is transmitted, based on the symbol frequencies seen \fIso far\fR in this
paper2 technical paper UNIX «troff» format, ASCII Witten: «Computer (In)security» 82.199 characters Programs can be written which spread bugs like an epidemic. They hide in binary code, effectively undetectable (because nobody ever examins binaries). They can remain dormant for months or years, perhaps quietly and imperceptibly infiltrating their way into the very depths of a system, then suddenly pounce,
pic black and white facsimile picture 1728×2376 bit map 200 pixels per inch CCITT facsimile test, picture 5 (page of textbook) 513.216 characters
progc program Source code in «C», ASCII Unix utility «compress» version 4.0 39.611 characters
progl program Source code in LISP, ASCII System software 71.646 characters
progp program Source code in Pascal, ASCII Program to evaluate compression performance of PPM 49.379 characters
trans transcript of terminal session «EMACS» editor controlling terminal with ASCII code Mainly screen editing, browsing and using mail 93.695 characters

Рисунок 7. Описание образцов текстов, использованных в экспериментах.

Таблица 4. Результаты опытов по сжатию ( биты на символ )

Текст Размер DIGM LZB LZFG HUFF DAFC ADSM PPMC WORD DMC MTF
bib 111261 6.42 3.17 2.90 5.24 3.84 3.87 *2.11 2.19 2.28 3.12
book1 768771 5.52 3.86 3.62 4.56 3.68 3.80 *2.48 2.70 2.51 2.97
book2 610856 5.61 3.28 3.05 4.83 3.92 3.95 2.26 2.51 *2.25 2.66
geo 102400 7.84 6.17 5.70 5.70 *4.64 5.47 4.78 5.06 4.77 5.80
news 377109 6.03 3.55 3.44 5.23 4.35 4.35 *2.65 3.08 2.89 3.29
obj1 21504 7.92 4.26 4.03 6.06 5.16 5.00 *3.76 4.50 4.56 5.30
obj2 246814 6.41 3.14 2.96 6.30 5.77 4.41 *2.69 4.34 3.06 4.40
paper1 53161 5.80 3.22 3.03 5.04 4.20 4.09 *2.48 2.58 2.90 3.12
paper2 82199 5.50 3.43 3.16 4.65 3.85 3.84 2.45 *2.39 2.68 2.86
pic 513216 8.00 1.01 *0.87 1.66 0.90 1.03 1.09 0.89 0.94 1.09
progc 39611 6.25 3.08 2.89 5.26 4.43 4.20 *2.49 2.71 2.98 3.17
progl 71646 6.30 2.11 1.97 4.81 3.61 3.67 *1.90 1.90 2.17 2.31
progp 49379 6.10 2.08 1.90 4.92 3.85 3.73 *1.84 1.92 2.22 2.34
trans 93695 6.78 2.12 *1.76 5.58 4.11 3.88 1.77 1.91 2.11 2.87
В среднем 224402 6.46 3.18 2.95 4.99 4.02 3.95 *2.48 2.76 2.74 3.24

Опыт показывает, что более изощренные статистические модели достигают лучшего сжатия, хотя LZFG имеет сравнимую характеристику. Худшую характеристику имеют простейшие схемы — диады и кодирование Хаффмана.

5.2 Требования скорости и памяти.

В общем случае лучшее сжатие достигается большим расходом ресурсов ЭВМ: времени и прежде всего памяти. Моффат [69] описывает реализацию одного из лучших архиваторов (PPMC), обрабатывающего около 2000 символов в секунду на машине MIP (OC VAX 11/780). DMC выполняется немного медленнее, так как работает с битами. Для сравнения, у LZFG на подобной машине зафиксирована скорость кодирования около 6000 симв/сек, а раскодирования — 11000 симв/сек [28]. LZB имеет особенно медленное кодирование (обычно 600 симв/сек), но очень быстрое раскодирование (1600 симв/сек), которое может достичь 40.000.000 симв/сек при использовании архитектуры RISC [43].

Большинство моделей пpи увеличении доступной памяти улучшают свое сжатие. Пpи использовании лучшей СД скоpость их pаботы повысится. Реализация PPMC, предложенная Моффатом, выполняется на ограниченной памяти в 500 Кб. На таком пространстве может работать и схема DMC, хотя полученные результаты ее работы достигнуты на неограниченной памяти, временами составляющей несколько Мб. LZFG использует несколько сотен Кб, LZB для кодирования применяет сравнимое ее количество, когда как раскодирование обычно требует всего 8 Мб.

DIGM и HUFF по сравнению с остальными методами требуют очень немного памяти и быстpо выполняются.

6. ДАЛЬHЕЙШИЕ ИССЛЕДОВАHИЯ.

Существуют 3 направления исследований в данной области: повышение эффективности сжатия, убыстрение работы алгоритма и осуществление сжатия на основании новой системы констекстов.

Сейчас лучшие схемы достигают сжатия в 2.3 — 2.5 битов/символ для английского текста. Показатель иногда может быть немного улучшен за счет использования больших объемов памяти, но сообщений о преодолении рубежа в 2 бита/символ еще не было. Обычные люди достигали результата в 1.3 бита/символ при предсказании символов в английском тексте [21]. Хотя обычно это принимается за нижнюю границу, но теоретических причин верить, что хорошо тренированные люди или системы ЭВМ не достигнут большего, не существует. В любом случае, несомненно, существует много возможностей для улучшения алгоритмов сжатия.

Одним направлением для исследований является подгонка схем сжатия к отечественным языкам. Сегодняшние системы работают полностью на лексическом уровне. Использование больших словарей с синтаксической и семантической информацией может позволить машинам получить преимущество от имеющейся в тексте высокоуpовневой связности. Однако, необходимо иметь в виду, что очень большое количество слов обычного английского текста в обычном английском словаpе может быть не найдено. Например, Уолкер и Эмслер[107] проверили 8 миллионов слов из New York Times News Service для Webster’s Seventh New Collegiate Dictionary[65] и обнаружили, что в словаpе отсутствовало почти 2/3 (64%) слов (они подсчитали, что около 1/4 из них — грамматические формы слов, еще 1/4 — собственные существительные, 1/6 — слова, написанные через дефис, 1/12 — напечатаны с орфографическими ошибками, а оставшуюся четверть составляют возникшие уже после выпуска словаря неологизмы). Большинство словарей не содеpжат имен людей, названий мест, институтов, торговых марок и т.д., хотя они составляют основную часть почти всех документов. Поэтому, специальные алгоритмы сжатия, взятые в рассчете на лингвистическую информацию более высокого уровня, будут несомненно зависеть от системной сферы. Вероятно, что поиски методов улучшения характеристик сжатия в данном направлении будут объединяться с исследованиями в области контекстуального анализа по таким проблемам как извлечение ключевых слов и автоматическое абстрагирование.

Второй подход диаметрально противоположен описанному выше наукоемкому направлению, и состоит в поддержании полной адаптивности системы и поиске улучшений в имеющихся алгоритмах. Необходимы лучшие пути организации контекстов и словарей. Например, еще не обнаружен пригодный метод постстроения моделей состояний; показанный метод DMC — лишь форма контекстно-ограниченной модели[8]. Тонкости роста этих СД вероятно значительно влияют на сжатие, но, несмотря на статью Уильямса [110], этот вопрос еще не был исследован систематично. Дpугой стоящей темой для исследований являются методы выделения кодов уходов в частично соответствующих контекстуальных моделях. В итоге, пpеобpазование систем, определяемых состояниями, таких как скрытые модели Маркова[77], может вдохнуть новую жизнь в модели состояний сжатия текстов. Например, алгоритм Баума-Уэлча определения скрытых моделей Маркова [4] в последнее время был вновь открыт в области распознавания речи [60]. Он может быть успешно применен для сжатия текстов, равно как и для техники глобальной оптимизации, такой как моделирование обжига[25]. Недостаток этих методов состоит в их значительных временных затратах, что позволяет сейчас эксплуатировать довольно небольшие модели с десятками и сотнями, а не тысячами и более состояний.

Поиски более быстрых алгоритмов, сильно влияющих на развитие методов сжатия текстов, будут несомненно продолжены в будущем. Постоянный компромисс между стоимостями памяти и вычислений будет стимулировать дальнейшую работу над более сложными СД, требующими больших объемов памяти, но ускоряющих доступ к хранимой информации. Применение архитектуры RISC, например в [43], разными путями воздействует на баланс между хранением и выполнением. Будет развиваться аппаратура, например, исследователи экспериментируют с арифметическим кодированием на микросхеме, когда как Гонзалес-Смит и Сторер [34] разработали для сжатия Зива-Лемпела параллельные алгоритмы поиска. В общем, увеличение вариантов аппаратных реализаций будет стимулировать и разнообразить исследования по улучшению использующих их алгоритмов.

Последняя область на будущее — это разработка и реализация новых систем, включающих сжатие текстов. Существует идея объединения в единую систему ряда распространенных пpогpамм pазных областей применения, включая текст-процессор MaxWrite(7)[117], цифровой факсимильный аппаpат [42], сетевую почту и новости (например, UNIX «net-news») и архивацию файлов (например, программы ARC и PKARC для IBM PC(8), которые часто применяются для pаспpеделяемого ПО из электронных бюллютеней). Для увеличения скорости и сокращения стоимости большинство этих систем используют удивительно простые методы сжатия. Все они представляют собой потенциальные сферы применения для более сложных методов моделирования.

Люди часто размышляют над объединением адаптированного сжатия с дисковым контроллером для сокращения использования диска. Это поднимает интересные системные проблемы, частично в сглаживании взрывного характера вывода большинства алгоритмов сжатия, но в основном в согласовывании случайного характера доступа к дисковым блокам с требованиями адаптации к разным стилям данных. Сжатие имеет значительные преимущества для конечного движения — некоторые высокоскоростные модемы (например, Racal-Vadic’s Scotsman) и конечные эмуляторы (например, [3]) уже имеют адаптивные алгоритмы. В будущем полностью цифровые телефонные сети радикально изменят характер конечного движения и, вообще, сферу локальных сетей. Эффективность сжатия трудно оценить, но эти усовершенствования определенно будут давать преимущество в скорости реализации.

Еще одной сферой применения является шифрование и защита данных [113]. Сжатие придает хранимым и передаваемым сообщениям некоторую степень секретности. Во-первых, оно защищает их от случайного наблюдателя. Во-вторых, посредством удаления избыточности оно не дает возможности криптоаналитику установить присущий естественному языку статистичекий порядок. В-третьих, что самое важное, модель действует как очень большой ключ, без которого расшифровка невозможна. Применение адаптивной модели означает, что ключ зависит от всего текста, переданного системе кодирования/раскодирования во время ее инициализации. Также в качестве ключа может быть использован некоторый префикс сжатых данных, опpеделяющий модель для дальнейшего pаскодиpования[47].

Сжатие текстов является настолько же нужной областью исследований как и 40 лет назад, когда ресурсы ЭВМ были скудны. Его пpименение продолжает изменяться вместе с улучшением технологии, постоянно увеличивая выигрыш за счет машинного времени, скорости передачи данных, первичного и вторичного хранения.

(1) — Везде в этой статье основание логарифма есть 2, а единица информации — бит.
(2) — Вероятность может быть менее 100% в случае иностранных слов, таких как «Coq au vin» или «Iraq.».
(3) — Понятие введено Моффатом в [69] для техники, использованной в [16].
(4) — Эта перемена инициалов в аббревиатуре является увековеченной нами исторической ошибкой.
(5) — UNIX — торговая марка AT&T Bell Laboratories.
(6) — На самом деле это дерево Patricia [51,71].
(7) — MacWrite — зарегестрированная торговая марка Apple Computer,Inc.
(8) — IBM — зарегестрированная торговая марка International Business Machines.

Симметричное и ассиметричное сжатие

Методы симметричного сжатия основываются на тех же алгоритмах и выполняют такой же объем работы, что и распаковка файлов (RLE,LZW).

В программах обмена данными используют как сжатие, так и распаковку. В одном направлении выполняется значительно больший объем работы, чем в другом (обычно на сжатие увелич. объем, время, чем на распаковку) – это для БД изо. jpeg,mpeg.

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

Адаптивное, полуадаптивное и неадаптивное кодирование

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

Например, неадаптивные кодировщики для сжатия текстов содержит словарь: end(1 код),but(2 код),then(3 код) и т.д.

Для графики 4 черных пикселя 1

Адаптивные кодировщики не содержат предопределенных эвристических правил для сжатия данных, адаптивные компрессоры, такие как LZW, не зависят от типа обрабатываемых данных, поскольку строят словари из поступающих данных, т.е. строят дополнительные данные о процессе кодирования. У адаптивных кодировщиков возможна большая степень сжатия.

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

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

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

Сжатие с потерями и без потерь

Метод сжатия без потерь – когда данные сжимается, а потом распаковываются и содержащаяся в них оригинальная информация сохраняется. Данные не должны быть изменены, потеряны или повреждены.

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

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

Классификация приложений использующих алгоритмы компрессий

1) высокие требования ко времени архивации и разархивации (издательские системы, информационные узлы в интернете). Сами илюстр. > часть от общего объема. Используются алгоритмы СБП (LZW,RLEи т.д.)

2) степень архивации и времени разархивации (справочники и энциклопедии на CD-ROM). Ассиметричные алгоритмы – время компрессии >> времени разархивации (фрактальное сжатие).

3) очень высокие требования к степени разархивации (jpeg, хотя большое время разархивации).

Требования, прилагаемые к алгоритмам компрессии.

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

1) степень компрессии

2) качество изображения

3) скорость компрессии

4) скорость декомпрессии

5) масштабирование изображения

6) возможность показать изо нужного разрешения

7) устойчивость к ошибкам, это противоречит высокой степени архивации, т.к. необходимо вводить избыточную информацию.

8) учет специфики изо, т.е. более высокая степень архивации, чаще применяемая в ваших приложениях.

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

10) небольшая стоимость аппаратной и программной реализации.

Адаптивное сжатие текстов

При кодировании наблюдается некоторый баланс между временем и памятью. Затрачивая дополнительные усилия при кодировании и декодировании, можно сэкономить память, и, наоборот, пренебрегая оптимальным использованием памяти, можно существенно выиграть во времени кодирования и декодирования. Конечно, этот баланс имеет место только в определенных пределах, и нельзя сократить расход памяти до нуля или построить мгновенно работающие алгоритмы кодирования. Для алфавитного кодирования пределы возможного установлены ранее. Для достижения дальнейшего прогресса нужно рассмотреть неалфавитное кодирование.

1. Сжатие текстов

Допустим, что имеется некоторое сообщение, которое закодировано каким-то общепринятым способом (для текстов это, например, код ASCII) и хранится в памяти компьютера. Заметим, что равномерное кодирование (в частности, ASCII) не является оптимальным для текстов. Действительно, в текстах обычно используется существенно меньше, чем 256 символов (в зависимости от языка — примерно 60-80 с учетом знаков препинания, цифр, строчных и прописных букв). Кроме того, вероятности появления букв различны и для каждого естественного языка известны (с некоторой точностью) частоты появления букв в тексте. Таким образом, можно задаться некоторым набором букв и частотами их появления в тексте и с помощью алгоритма Хаффмена построить оптимальное алфавитное кодирование текстов (для заданного алфавита и языка). Простые расчеты показывают, что такое кодирование для распространенных естественных языков будет иметь цену кодирования несколько меньше 6, то есть даст выигрыш по сравнению с кодом ASCII на 25% или несколько больше.
Методы кодирования, которые позволяют построить (без потери информации!) коды сообщений, имеющие меньшую длину по сравнению с исходным сообщением, называются методами сжатия (или упаковки) данных. Качество сжатия определяется коэффицентом сжатия, который обычно измеряется в процентах и показывает, на сколько процентов кодированное сообщение короче исходного.
Известно, что практические программы сжатия (arj, ziр и другие) имеют гораздо лучшие показатели: при сжатии текстовых файлов коэффициент сжатия достигает 70% и более. Это означает, что в таких программах используется не алфавитное кодирование.

2. Предварительное построение словаря

Рассмотрим следующий способ кодирования.

  1. Исходное сообщение по некоторому алгоритму разбивается на последовательности символов, называемые словами (слово может иметь одно или несколько вхождений в исходный текст сообщения).
  2. Полученное множество слов считается буквами нового алфавита. Для этого алфавита строится разделимая схема алфавитного кодирования (равномерного кодирования или оптимального кодирования, если для каждого слова подсчитать число вхождений в текст). Полученная схема обычно называется словарем, так как она сопоставляет слову код.
  3. Далее код сообщения строится как пара — код словаря и последовательность кодов слов из данного словаря.
  4. При декодировании исходное сообщение восстанавливается путем замены кодов слов на слова из словаря.

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

Сжатие сокращает объем пространства, т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а,

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

где 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азвил.

Оптимальный адаптированный код Уиттера всегда лежит в пределах одного бита на

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

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

лежат в пределах одного бита на букву исходного текста от 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. Эта

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

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

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

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

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

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

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

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

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

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

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

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

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

расширено напрямую как показано на рисунке 5. В этом примере дерево

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

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

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

бы деpево было сначала повернуто так, что C был самым левым листом, а затем

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

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

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

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

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

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

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

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

Алгоритм расширяемого префикса.

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

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

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

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

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

работ по этой же тематике [5,10], а также позволяет осуществлять и простое

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

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

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

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

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

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

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

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

succmax = maxchar + 1;

twicemax = 2 * maxchar + 1;

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 больше значения максимального кода

символа исходного текста.

Следующая процедура инициализирует дерево кодов. Здесь строится сбалансированное

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

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

for i := 2 to twicemax do

for j := 1 to maxchar do begin

right[j] := 2 * j + 1;

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

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

операции показана в следующей процедуре, использующей расширение снизувверх:

procedure splay( plain: codetype );

a := plain + succmax;

if c # root then begin

if c = b then begin b := right[d];


end else left[d] := a;

if a = left[c] then left[c] := b;

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

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

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

Для изменения порядка следования битов процедура compress пpименяет свой стек,

биты из которого достаются по одному и передаются процедуре transmit.

procedure compress( plain: codetype );

stack: array[upindex] of bit;

a := plain + succmax;

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

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

биты с помощью функции receive. Каждый прочитанный бит задает один шаг на

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

function expand: codetype;

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

until a > maxchar;

splay( a — succmax );

expand := a — succmax;

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

вызов процедуры 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%, а иногда бывает много меньше

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

(файлы 2 и 3) и произвольный текстовый файл (файл 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. Более того, если буквы из одного поддерева

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

открытого справа интервала [0,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

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

( 0.2 — 0.125 ) / 0.125 = 0.6.

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

его длине, будет повторяющейся строкой DBDBDB .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

числом ее появлений и числом появлений ее предшественников. Этот простой подход

может потребовать 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 — от корня к листу.

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

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

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

succmax = maxchar + 1;

twicemax = 2 * maxchar + 1;

up: array[downindex] of upindex;

freq: array[downindex] of integer;

left,right: array[upindex] of downindex;

Инициализация этой структуры включает в себя не только построение древовидной

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

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

for u := maxchar downto 1 do begin

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 );

if right[up[i]] = i then begin

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

стоит, то функция 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 );

if c # root then begin

if c = b then begin b := right[d];

end else left[d] := a;

if a = left[c] then left[c] := b

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Простой путь для этого — разделить значения всех частот на маленькую константу,

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

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

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

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

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

for d := succmax to twicemax do

freq[d] := ( freq[d] + 1 ) div 2;

for u := maxchar downto 1 do begin

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

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

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

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

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

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

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

тексты имеют одинаковую длину.

Рисунок 9 показывает скорость двух этих алгоритмов как функцию от 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 байт,

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

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

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

Илон Маск рекомендует:  Читаем из файла, открытого другим приложением
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL
Название: Сжатие данных
Раздел: Рефераты по информатике
Тип: реферат Добавлен 04:39:05 06 марта 2007 Похожие работы
Просмотров: 5552 Комментариев: 23 Оценило: 11 человек Средний балл: 4.5 Оценка: 5 Скачать