Моделирование при сжатии текстовых данных полуадаптированное словарное кодирование

Содержание

Сжатие текстовой информации

  • повторить и обобщить понятие о кодировании текстовой информации.

1. Организационный момент, проверка домашнего задания

2. Ознакомление учащихся с понятие «сжатие информации» на примерах (см. слайды №2 и №3).

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

3. Метод Шеннона-Фано (по презентации Приложение 2, см. слайды №№ 4-9)

Как мы уже видели при решении задач, информацию нельзя сжимать до бесконечности. То есть в какой-то момент должна появиться своего рода граница, при сжатии дальше которой восстановление информации неоднозначно или просто невозможно. То есть хотелось бы, чтобы выбранный нами способ кодирования был оптимальным: с одной стороны, чтобы обеспечивалось максимально возможное сжатие, с другой стороны, чтобы записанная таким образом информация не теряла свою полноту. Одним из методов, обеспечивающих такое оптимальное кодирование отдельных символов является метод Шеннона-Фано.
Суть метода состоит в следующем: пусть дан некоторый алфавит (конечный набор символов, который будет использован для написания текста). Пусть также дано сообщение. Какие-то символы в сообщении обычно встречаются чаще, какие-то – реже. Для часто используемых символов создадим более короткие коды, для реже используемых – длинные (слайд №4 – частота использования букв русского языка).
Для начала, в качестве повторения, оценим (например, по формуле Хартли) сколько бит необходимо отвести для записи кода одного символа, и создадим «обычные» коды равной длины (слайд №5).

Теперь подсчитаем для каждого символа какую часть сообщения он занимает (проверка: сумма всех таких дробей должна быть равна единице – целому сообщению). Сведем наши данные в таблицу и упорядочим ее по убыванию долей (слайд №6).

Далее, разделим таблицу на две части, чтобы сумма долей всех символов в одной была как можно ближе к сумме долей всех символов другой. Пусть коды всех символов из первой части начинаются на 0, коды всех символов из второй – на 1 (слайд №7). Если в какой-то части находится более одного символа, то повторим для нее процесс деления, находя вторую, третью и так далее цифры кода. Как только для всех символов найдены коды – процесс завершен (слайды №8 и №9)
Осталось только подчитать количество бит, которые необходимы для представления сообщения в новом коде (слайд №10).

4. Закрепление пройденного материала, решение задач (слайд №11)

Алгоритм сжатия с использованием кодов Хаффмана

Данный алгоритм (далее для краткости — алгоритм Хаффмана) был разработан в 1952 году и относится к группе статистических методов сжатия. Статистические методы используют различные приёмы для того, чтобы наиболее часто встречающимся символам соответствовали более короткие коды. При этом каждый код однозначно соответствует конкретному символу. Например, в тексте на русском языке буква а встречается гораздо чаще, чем буква ы, поэтому имеет смысл присвоить букве а более короткий код. Соответственно выходной поток этих методов является бит-ориентированным, т.е. не форматированным по границам байтов. Статистические методы работают медленнее словарных, но достигают, как правило, более высокой степени сжатия. Они используют три основных модели для набора статистики (определения вероятностей символов):

В неадаптивных моделях вероятности всех символов алфавита определены заранее. Эта модель обычно применяется только при сжатии текстовых файлов. В полуадаптивных моделях входные данные обрабатываются за 2 прохода: 1-й – для подсчёта вероятностей, 2-й – собственно для сжатия. Эта модель может применяться для сжатия не очень больших изображений. Адаптивные модели вычисляют и корректируют вероятности символов в процессе сжатия, т.е. «на лету». Модели последнего типа сложнее предыдущих, зато являются более универсальными и часто дают наилучшее сжатие.

Рассмотрим кодирование по Хаффману более подробно. Предположим, что вероятности (их заменят частоты) всех символов алфавита уже подсчитаны одним из вышеописанных способов. Тогда:

1. Выписываем в ряд все символы алфавита в порядке убывания вероятноcтей (частоты) их появления в потоке данных (для удобства построения дерева);

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

3. Прослеживаем путь от каждого листа дерева к корню, помечая направление движения к каждому узлу (например, вверх/направо –1, вниз/налево — 0). При этом не важен конкретный вид разметки «ветвей» дерева (т.е. помечать направление вверх/направо –1, вниз/налево – 0, или наоборот), но важно придерживаться выбранного способа разметки ко всем «ветвям» дерева.

4. Получившиеся двоичные комбинации, записанные от конца к началу и формируют коды Хаффмана.

Полученный коэффициент сжатия подсчитывается по следующей формуле

n – количество бит, необходимое для кодирования символов алфавита фиксированным числом разрядов;

— вероятность (частота) повторения символа во входном потоке;

— количество бит в коде Хаффмана для символа .

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

Пример кодирования по Хаффману приведен на рис. 3.

Примечание:

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

Kобщее количество символов во входном потоке;

– количество символов во входном потоке.

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

Рис.3. Пример кодирования по Хаффману.

Если предположить, что входной поток символов был байт-ориентированным, то n=8. Тогда коэффициент сжатия

Если считать входной поток символов бит-ориентированным с равным количеством бит под каждый символ, то n=4 (т.к. для кодирования 10 различных символов a-j требуется разряда). В этом случае будет означать выигрыш, полученный от применения кодов Хаффмана по сравнению с кодами фиксированной, минимально необходимой битовой размерности. В этом случае

Кодирование по Хаффману может использоваться при сжатии изображений как самостоятельно, так и в составе других алгоритмов сжатия, например LZW и JPEG (это наиболее эффективное его применение).

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Да какие ж вы математики, если запаролиться нормально не можете. 8427 — | 7331 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Модели и алгоритмы контекстно-словарного сжатия текстовых данных Максимов Сергей Владимирович

480 руб. | 150 грн. | 7,5 долл. ‘, MOUSEOFF, FGCOLOR, ‘#FFFFCC’,BGCOLOR, ‘#393939’);» onMouseOut=»return nd();»> Диссертация — 480 руб., доставка 10 минут , круглосуточно, без выходных и праздников

Автореферат — бесплатно , доставка 10 минут , круглосуточно, без выходных и праздников

Максимов Сергей Владимирович. Модели и алгоритмы контекстно-словарного сжатия текстовых данных : 05.13.11 Максимов, Сергей Владимирович Модели и алгоритмы контекстно-словарного сжатия текстовых данных (Применительно к системам электронного обучения) : Дис. . канд. техн. наук : 05.13.11 Уфа, 2006 133 с. РГБ ОД, 61:06-5/2212

Содержание к диссертации

ГЛАВА 1. Анализ методов сжатии информации 14

1.1. Предварительные замечания 14

1.2. Модели словарного сжатия 18

1.3. Модели контекстного сжатия 20

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

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

1.3.3. Вероятность ухода 22

1.3.4. Исключения 22

1.3.5. Алфавиты 24

1.4. Другие методы статистического моделирования 24

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

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

1.4.3. Модели новизны 28

1.4.4. Выводы по первой главе 29

ГЛАВА 2. Контекстно-словарные модели сжатия 30

2.1. Предварительные замечания 30

2.2. Сжатие текстовых файлов 34

2.3. Структурная модель представления сжатия текстовой информации 35

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

структурированного вида 36

2.5. Модель сжатия использующий контекстно-словарный метод 38

% 2.5.1. Модель хранения сжатого текста 39

2.5.2. Древовидная модель словаря 40

2.5.3. Модель словаря морфем 44

2.6. Выводы по второй главе 44

ГЛАВА 3. Алгоритмы контекстно-словарного сжатия данных на основе предложенных моделей 46

3.1. Предварительные замечания 46

3.2. Приведение информации к структурированному виду 48

3.3. Преобразование словаря 50

3.3.1. Разбиение слова на слоги 50

3.3.2. Разбиение на составные части слова 55

3.3.3. Древовидное представление структуры словаря 57

3.4. Оценка построение структуры словаря от способа разложения слов. 58

3.5. Кодирование текста с использованием полученного словаря 61

3.5.1. Построение кодов переменной длины 61

3.5.2. Применение кодирования контекстных индексов арифметического кодирования 61

3.6. Оценка эффективности полученных кодов алгоритма кодирования с

помощью словаря 63

3.6.1. Стоимость кодирования текста 63

3.6.2. Оценка объема необходимой памяти 65

3.7. Управление распределением памяти 67

3.8. Выводы по третьей главе 68

ГЛАВА 4. Программный комплекс контекстно-словарного сжатия текстовых данных msv quick reader 69

4.1. Основные требования к техническому облику программного комплекса MSV Quick Reader 69

4.2. Область применения программного комплекса 70

4.3. Проблемы существующих систем 71

4.4. Задачи разработки программного комплекса 72

4.5. Этапы разработки программного комплекса 72

4.6. Реализация блока сжатия файлов 75

4.6.1. Реализация блока Compress 78

4.6.2. Реализация блока Decompress 79

4.7. Сравнительная оценка эффективности 80

4.7.1. Тестовые данные 81

4.7.2. Методика сравнения 81

4.7.3. Результаты сравнения 82

4.8. Пример преобразования и кодирования слов 84

4.9. Выводы по четвертой главе 88

Введение к работе

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

Под хорошо структурированной понимается информация, представленная в виде информационных объектов (символьных конструкций). Эти объекты состоят из некоторой совокупности связанных определенным образом элементов, имеющих ярко выраженную структуру. Примером подобной структуры является информация фактографического типа. Например: числа, математические выражения (формулы), компьютерные программы, алгоритмы и др. Для структурированных объектов характерным является наличие четких правил получения различных структур на основе базовых элементов: цифр, символов и др. В этом случае говорят, что представляемые информационные объекты имеют «жесткую» структуру подобную структуре данных в хранилищах информации.

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

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

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

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

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

7.^ — исключает повторную упаковку встречаемого объекта; — сокращает затраты на преобразование сжимаемого объекта.

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

Ы позволяет выбрать наиболее эффективные правила ее упаковки в базу данных.

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

1) увеличивается скорость обработки данных, которая идет уже по полученному шаблону и не требует дополнительных вычислений; Щ 2) исключается необходимость многократного сохранения всего шаблона в выходном файле, так как модель шаблона сохраняется на начальном этапе, либо уже содержится в комплекте программного обеспечения; данные быстрее восстанавливаются; модель сохраняется на начальном этапе, то соответственно в выходной файл отправляются только подвергающиеся изменению данные; 4 5) уменьшается объем передаваемой информации и увеличивается скорость передачи данных.

Отметим, что большие временные затраты на распаковку данных, величина которых растет при увеличении степени сжатия, препятствуют организации эффективного сжатия информации. Иными словами, требование Ж| обеспечения высокого коэффициента сжатия (по соображениям уменьшения ресурсных затрат на ее хранение и передачу) и высокой скорости распаковки (по соображениям удобства работы конечного пользователя) являются антагонистическими.

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

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

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

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

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

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

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

При решении поставленной задачи автор опирался на труды Д. Ватолина, А. Ратушняка, А. Смирнова, М. Смирнова, В. Юкина, И. Ножова,

9 И.В. Павлова, А.В. Кадача, Д. Мастрюков, Д.Сэломона, Д.Е.Кнута и других ученых.

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

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

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

Цель диссертационной работы

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

Для достижения цели поставлены следующие задачи:

1. Разработка контекстно-словарных моделей сжимающих текстовые данные.

2. Разработка древовидной логической модели пополняемой базы элементарных единиц словообразования (морфем) на основе известных правил словообразования в естественных языках.

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

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

Проверка эффективности разработанного программного обеспечения на примере организации хранения и передачи учебной информации.

10^ Результаты исследований, выполненных в работе, базируются на методах математической статистики, теории информации, теории цепей Маркова, теории исследования операций, принципах морфемного и словообразовательного анализа состава. На защиту выносятся:Ш 1. Объектно-когнитивная модель контекстно-словарного сжатия.

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

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

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

Щ Научная новизна работы заключается в следующем:

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

2. Новизна предложенных алгоритмов, реализующих сжатие текстовой информации, заключается в использовании тезаурусных моделей ее сжатия, основанных на раздельном сжатии элементов текстовой информации: слов, ссылок на них, хранящихся в словаре, самого словаря, морфем, служебных символов. ^\ 3. Новизна предложенного способа кодирования текстовой информации на основе статистических прогнозирующих моделей заключается во взаимосвязанном (контекстном) сжатии следующих классов символьных конструкций: слов, ссылок на них, хранящихся в словаре, самого словаря, морфем, служебных символов. Это позволяет более точно ^ определить условные вероятности появления символов. ^ 4. Новизна предложенного способа коррекции условных вероятностей появления символов заключается в использовании бинарного арифметического кодирования. Это позволяет обеспечить высокую степень сжатия текстовой информации в условиях возможного изменения условных вероятностей появления символов.

Ш Практическая значимость работы:

1. Разработан программный комплекс MSV Quick Reader, использующий реализованные алгоритмы сжатия. Экспериментальная проверка эффективности предложенных алгоритмов контекстно-словарного сжатия текстовых данных с помощью данного комплекса показала, что они обеспечивают увеличение степени сжатия для текстовых данных по сравнению с известными его вариантами и как следствие, снижение трафика ^Р компьютерных сетей на 5 — 7 %.

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

Программный комплекс MSV Quick Reader внедрен в Башкирском государственном педагогическом университете и в настоящее время используется на кафедре программирования и вычислительной математики. Программное обеспечение данного комплекса имеет открытую архитектуру, что позволяет развивать данный программный комплекс с помощью добавления соответствующих модулей.

Связь темы с плановыми исследованиямим± Диссертационная работа выполнялась в рамках госбюджетного финансирования кафедре информатики Уфимского государственного авиационного технического университета и кафедре программирования и вычислительной математики Башкирского государственного педагогического университета, а также в рамках внутривузовского гранта «05.02. Информационные технологии в образовании» (БГПУ).

12 Объем и структура работы

Диссертация состоит из введения, четырех глав, заключения, библиографии и 2 приложения. Работа содержит 96 страницы машинописного текста, 46 страниц приложения и 79 наименований библиографических источников.

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

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

Во второй главе показана целесообразность использования системной формы (типа «сущность — связь») представления при сжатии текстовой данных на естественных языках. На основе использования системной формы предложены модели реализации контекстно-словарного сжатия текстовых данных.

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

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

13 Заключение содержит основные результаты и выводы по диссертационной работе.

Апробация работа и публикации

Основные положения, представленные в диссертационной работе, докладывались всероссийских и международных конференциях (VI международный симпозиум Intels»2004 (г. Саратов, 2004), V международная научная техническая конференция «Проблемы Техники и Технологий Телекоммуникаций» (г. Самара, 2004); 7-й Международная конференция по проблемам информатики и информационных технологий CSIT’2005 (г. Уфа, 2005)), обсуждались и получили положительную оценку. Достоверность основных результатов работы подтверждена корректным использованием методов поиска информации в иерархических (древовидных) моделях представления данных, теории цепей Маркова, методов математической статистики, правил словообразования в естественных языках, а также результатами проведенных экспериментов.

Основные материалы, представленные в диссертационной работе опубликованы в 7 работах.

Результаты диссертационной работы внедрены в Башкирском государственном педагогическом университете и в настоящее время используется на кафедре программирования и вычислительной математики. ф Глава 1. Анализ методов сжатии информации

1.1. Предварительные замечания

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

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

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

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

Одним направлением для исследований является подгонка схем сжатия Щ> к отечественным языкам. Сегодняшние системы работают полностью на лексическом уровне. Использование больших словарей с синтаксической и семантической информацией может позволить машинам получить преимущество от имеющейся в тексте высокоуровневой связности. Однако необходимо иметь в виду, что очень большое количество слов обычного ‘Щ английского текста в обычном английском словаре может быть не найдено. ^ Данный факт касается и остальных языков. Например, Уолкер и Эмслер [73] проверили 8 миллионов слов из New York Times News Service для Webster’s Seventh New Collegiate Dictionary [58] и обнаружили, что в словаре отсутствовало почти 2/3 (64%) слов (они подсчитали, что около 1/4 из них -грамматические формы слов, еще 1/4 — собственные существительные, 1/6 —

Щ слова, написанные через дефис, 1/12 — напечатаны с орфографическими ошибками, а оставшуюся четверть составляют возникшие уже после выпуска словаря неологизмы). Большинство словарей не содержат имен людей, названий мест, институтов, торговых марок и т.д., хотя они составляют основную часть почти всех документов. Поэтому, специальные алгоритмы сжатия, взятые в расчете на лингвистическую информацию более высокого уровня будут, несомненно, зависеть от системной сферы. Вероятно, что

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

Второй подход диаметрально противоположен описанному выше наукоемкому направлению, и состоит в поддержании полной адаптивности ^| системы и поиске улучшений в имеющихся алгоритмах. Необходимы лучшие пути организации контекстов и словарей. Например, еще не обнаружен пригодный метод построения моделей состояний; показанный метод DMC -лишь форма контекстно-ограниченной модели [27]. Тонкости роста этих сжимаемых данных, вероятно значительно влияют на сжатие, но, несмотря на статью Уильямса [74], этот вопрос еще не был исследован систематично.

It Другой актуальной темой для исследований являются методы выделения кодов ухода в частично соответствующих контекстуальных моделях. В итоге, преобразование систем, определяемых состояниями, таких как скрытые модели Маркова [63], может дать новые идеи моделям состояний сжатия текстов. Например, алгоритм Баума-Уэлча определения скрытых моделей ф Маркова [26] в последнее время был вновь открыт в области распознавания речи [57]. Он может быть успешно применен для сжатия текстов, равно как и для техники глобальной оптимизации, такой как моделирование обжига [38]. Недостаток этих методов состоит в их значительных временных затратах, что позволяет сейчас эксплуатировать довольно небольшие модели с десятками и сотнями, а не тысячами и более состояний. ‘Щ Поиски более быстрых алгоритмов, сильно влияющих на развитие методов сжатия текстов, будут, несомненно, продолжены в будущем. Постоянный компромисс между стоимостями памяти и вычислений будет стимулировать дальнейшую работу над более сложными системами данных, требующими больших объемов памяти, но ускоряющих доступ к хранимой информации. Применение архитектуры RISC, например в [51], разными путями воздействует на баланс между хранением и выполнением. Будет ^ развиваться аппаратура, например, исследователи экспериментируют с арифметическим кодированием на микросхеме, тогда как Гонзалес-Смит и Сторер [43] разработали для сжатия Зива-Лемпела параллельные алгоритмы поиска. Увеличение вариантов аппаратных реализаций будет стимулировать и разнообразить исследования по улучшению использующих их алгоритмов.

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

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

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

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

1.2. Модели словарного сжатия

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

Выходной поток Рис. 1 Модель сжатия реляционным словарем

Такой способ сжатия файла имеет как положительные, так и отрицательные стороны.

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

1. Размер сжатого файла получается компактный.

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

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

4. Декодирование выполняется быстро, так как файл содержит ссылки на место положения слова в словаре.

Необходимо также отметить и отрицательные стороны:

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

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

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

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

Динамический словарь содержит последовательности, ранее поступившие из входного файла, при этом разрешается добавлять и удалять эти последовательности по мере чтения из входного файла. Примером модели сжатия динамическим словарем является модель со скользящим окном. [1,2, 77, 78]

Скользящее окно rz.

Динамический словарь содержит последовательности, ранее поступившие (1 АД) (1,0,и) О Ан) (1 Да) (1 Дм) (4,1,4) (1 Де) (1 Де) (1 Дк) (5,1,й) (1,0, « » ) (5)1,л)

Рис. 2 Модель сжатия динамическим словарем

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

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

1.3. Модели контекстного сжатия

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

Под моделированием понимается построение модели информационного источника, породившего сжимаемые данные, а под кодированием — отображение обрабатываемых данных в сжатую форму представленную на основе построенной модели [1].

Кодирование на основании вероятности

Рис. 3 Модель контекстного сжатия

21 У данной модели, как и предыдущих моделей сжатия, также имеются недостатки: скорость сжатия на много ниже скорости, чем для словарных методов; медленное декодирование; несовместимость кодера и декодера в случае изменения алгоритма, так как в словарных методах допускается серьезная модификация кодера без изменения декодера; медленная обработка мало избыточных данных; большие запросы на память; проигрыш в эффективности сжатия для длинных повторяющихся блоков, по сравнению со словарными методами.

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

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

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

22 контекстов разных длин, объединяются в одну общую вероятность. Существует несколько способов выполнять перемешивание. Такая стратегия моделирования была впервые предложена в [33], а использована для сжатия в [68, 69].

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

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

1.3.3. Вероятность ухода

Этот подход, который сначала может показаться совсем не похожим на перемешивание, выделяет каждой модели некоторое кодовое пространство, учитывая при этом возможность доступа к моделям низшего порядка для предсказания следующего символа [34, 67]. Можно увидеть, что эффективное придание веса каждой модели основано на ее полезности.

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

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

23 устраняет указанные проблемы посредством преобразования вероятности символа в более простые оценки.

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

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

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

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

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

1.4. Другие методы статистического моделирования 1.4.1. Динамическое сжатие Маркова

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

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

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

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

Рис. 4 Операция клонирования в DMC. ^i Предположим, что переход из U имеет большее значение счетчика частот. Из-за высокой частоты перехода U—*t, состояние / клонирует добавочное состояние t’. Переход U—*t изменен на U—*t\ при этом другие переходы в f не затрагиваются этой операцией. Выходные переходы t передаются и Ґ, следовательно, новое состояние будет хранить более

0 і присущие для этого шага модели вероятности. Счетчики выходных переходов старого t делятся между t и Ґ в соответствии с входными переходами из U и V/W.

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

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

Однако, начальная модель не является особо решающей, т.к. ДМС быстро приспосабливается к требованиям кодируемого текста.

Рис. 5. Начальная модель ДМС с одним состоянием -> х1—- ХІ—> х1—> xl—^ xl—> xl—^ xL— xl— pf Х|—у Xj—^ Х|—у Xi—^ Хі—У Xi—У X,—)> Х|— 1_1 о LJ о I—I п I—JQl_lnl—IqI—I q L_l n

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

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

Даже более искусные модели с конечным числом состояний не способны отразить некоторые моменты должным образом. В особенности ими не могут быть охвачены рекуррентные структуры — для этого нужна модель, основанная на грамматике. Рисунок 7 показывает грамматику, моделирующую вложенные круглые скобки. С каждым терминальным символом связана своя вероятность. Когда исходная строка разбирается message seeing string substring substring = string «.» < 1 >= substring string < 0.6 ) = empty-string < 0.4 ) = "a" < 0.5 >— «(» string «)» і 0.5 > string ( ( parse

I— 5: П.5 —’ « S: 0.5 -J

1: 1.0 probabilities 0.5 0.5 0.5 0.5 0.4 0.6 0.6 0.5 1.0 combined probability = 0.0045 [ 7.80 bits )

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

28 согласно грамматике, то терминалы кодируются согласно своим вероятностям. Такие модели достигают хороших результатов при сжатии текстов на формальных языках, например, Паскале [31,53]. Вероятностные грамматики изучались также Озеки [63, 64, 65]. Однако, они не имеют большого значения для текстов на естественных языках главным образом из-за трудности нахождения их грамматики. Конструирование ее вручную будет утомительным и ненадежным, поэтому в идеале грамматика должна выводиться механически из образца текста. Но это невозможно, поскольку построение грамматики для выяснения ограничений изучаемого языка требует анализа не принадлежащих ему примеров [24, 43].

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

Они работают по принципу, что появление символа во входном потоке делает более вероятным его новое появление в ближайшем будущем. Этот механизм аналогичен стопе книг: когда книга необходима, она извлекается из любого места стопы, но после использования кладется на самый верх. Наиболее популярные книги будут ближе к вершине, что позволяет их быстрее находить. Многие авторы разрабатывали варианты этого алгоритма [31, 38, 47, 52, 70]. Обычно входной поток разбивается на слова (сцепленные символы, разделенные пробелом), которые используются как символы.

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

29 Практическая реализация и характеристика некоторых моделей новизны приводится в [60].

1.4.4. Выводы по первой главе

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

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

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

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

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

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

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

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

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

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

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

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

Структурная модель представления сжатия текстовой информации

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

Учитывая, что сжатие предусматривает замену часто используемых символов короткими кодами, объем информации можно уменьшить до 30-50%. » Как известно текст на естественных языках является слабоструктурированной информацией. Исследования сжатия текстов показало, что обычными приемами сжатия высокую степень сжатия для текстовых файлов невозможно получить по следующим причинам:

Редко встречаются повторяющиеся последовательности вида «аааааааааа». Необходимо рассматривать не только отдельный символ, но группу символов образующие слова. Для текстов на естественных языках длина повторяющихся последовательностей обычно не превышает 20 символов.

Илон Маск рекомендует:  Что такое код sin sinh

Из рисунка видим, что текстовыми данными необходимо провести следующие преобразования: построить реляционную модель словаря. Для построения словаря необходимо разбить текст на слова (разбиение на слова используются разделительные знаки), полученные слова разбить на морфемы ш (строится правила аналогичные правилам как на естественных языках). Реляционную модель словаря используем для кодирования теста, полученный словарь морфемы используется для построения древообразной модели словаря и кодирования ее с помощью словаря морфем. Узлы древообразного словаря являются ссылками на словарь морфем. Все полученные данные сохраняются в той последовательности как показано на рисунке.

Пусть A= — некоторый алфавит. Имеется последовательность символов х єАк: О lN-\

Пусть существует некоторый поток текстовых данных Г. Под текстовыми данными Т понимаем последовательность символов х разделенных знаками препинаниями, которые определили в начальном этапе в группе G. Элементы группы G данной последовательности разделят текстовый поток на подгруппу GS, состоящую из строк xt , концевыми элементами являются элементы группы G.

Приведение информации к структурированному виду

Приводя файл к структурированному виду, создаем словарь слов и список ссылок на индексы в словаре, точно повторяющий преобразованный текст, что позволяет исключать из словаря повторяющиеся слова, а в тексте будет храниться только ссылка на это слово. Обычно для сохранения индекса ссылок используют код фиксированной длины. Но если объем словаря будет слишком большой, то такой способ хранения не подходит. Поэтому лучше всего воспользоваться кодами ссылок переменной длины. Часто встречаемому слову присваиваем короткий код индекса, а редко встречающимся словам длинный код, если код оказывается длиннее, чем слово, то в этом случае сохраняем слово, а не индекс. Индексом служит место нахождение слова в словаре. Полученный словарь используем для кодирования заданного текста, заменяя слова, встречающиеся в тексте, их индексами. Так как словарь является упорядоченной последовательностью, существует возможность дальнейшего уменьшения его размера. Преобразование словаря, может, проведено двумя способами, используем особенности словообразования: Текст на естественных языках Слова Слоги Корни, приставки, суффиксы, окончания Буквы, символы, знаки Рис. 13 Модель представления текста в естественных языках. Приведение структурированному виду текстового файла проводится в 2 этапа: 1) выявление структуры и построение модели; 2) построение и проведение кодирования на основе выявленных структур. В блоке выявление структур и построение моделей производится первичная обработка.

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

Можно заметить, что существует возможность уменьшения объема словаря, при его создании: 1. Разбиение слова на слоги 2. Разбиение на составные части слова (морфемы) 3. Представление словаря древовидной форме на основе приведенных ранее разбиений. Выбранный нами метод обусловлен тем, что язык обладает рядом особенностей.

Известно, что слова делятся на слоги. Слог — это один гласный звук или несколько звуков в слове, которые произносятся одним толчком воздуха: я -ма, до — ро — га, шос — се. Слова делятся по правилу: в слове столько слогов, сколько в нем гласных букв. На основе этого, слова в словаре делятся на слоги, и создается словарь слогов. Затем кодируется словарь, заменяя слог в слове на полученный индекс.

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

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

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

Например: слово «информация» закодируется, применяя нами предлагаемый метод, как «1234» (длина слова 10 символов, закодированного 4 символа), слово «информатика» — «12378»(5 символов к 11), слово «политика» — «5678»(4 символа к 8), слово «полиформа» — «5623»(4 символа к 9) и т.д. Для кодирования 38 символов нами было потрачено всего 17 символов.

Область применения программного комплекса

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

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

Созданный нами программный продукт ориентирован на использовании студентами для систематизации имеющейся электронной информации. Данный программный комплекс предназначен для хранения, просмотра и передачи по компьютерным сетям учебных материалов в процессе электронного обучения. При разработке данного комплекса выполнены следующие предъявленные требования: 1. Программный комплекс должен иметь дружественный интерфейс. 2. Возможность работы различными типами данных. 3. Сжатие часто используемых данных.

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

У Наличие возможности работать с различными типами данных позволяет использование данного программного продукта в широкой сфере. Для универсализации данного продукта есть возможность подключения для поддержки новых типов данных. Сжатие часто используемых данных позволяет добавить (освободить) место для хранения. (Сжимать данные одноразового использования не имеет значения). Эта особенность позволяет сократить объем данных тогда, когда объем вмещающей памяти на устройстве имеет ограничения (карманные компьютеры, коммуникаторы и т.д.). Разрабатываемый программный продукт можно отнести программа типа bookreader.

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

Достаточно большое количество ссылок на bookreader имеется на сайтах http://www.mi.ru/ zserge/bv_simil.html и http://read.textory.ru. Для , большей объективности была также предпринята попытка найти и зарубежные аналоги. Удалось найти несколько таких программ, однако часть оказалась выполнена с интерфейсом лишь в виде раскрытой книги, а остальные были не слишком удачными, да и с чтением русских текстов в кодировках отличных от кодировки Windows проблемы были у всех.

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

Курсовая работа: Алгоритмы сжатия данных

Алгоритмы сжатия данных

Энтропия и количество информации

Комбинаторная, вероятностная и алгоритмическая оценка количества информации

Моделирование и кодирование

Некоторые алгоритмы сжатия данных

BWT — преобразование и компрессор

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

Реализация алгоритма арифметического кодирования

Доказательство правильности декодирования

Приращаемая передача и получение

Переполнение и завершение

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

Приложение 1. Программный код

Приложение 2. Интерфейс программы

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

Первые алгоритмы сжатия были примитивными в связи с тем, что была примитивной вычислительная техника. С развитием мощностей компьютеров стали возможными все более мощные алгоритмы. Настоящим прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. До этого момента сжатие сводилось к примитив­ному кодированию символов. Словарные алгоритмы позволяли кодир­овать повторяющиеся строки символов, что позволило резко повысить степень сжатия. Важную роль сыграло изобретение примерно в это же время арифметического кодирования, позволившего воплотить в жизнь идею Шеннона об оптимальном кодировании. Следующим прорывом было изобретение в 1984 г. алгоритма РРМ. Следует отметить, что это изобретение долго оставалось незамеченным. Дело в том, что алгоритм сложен и требует больших ресурсов, в первую очередь больших объемов памяти, что было серьезной проблемой в то время. Изобретенный в том же 1984 г. алгоритм LZW был чрезвычайно популярен благодаря своей простоте, хорошей рекламе и нетребовательности к ресурсам, несмотря на относительно низкую степень сжатия. На сегодняшний день алгоритм РРМ является наилучшим алгоритмом для сжатия текстовой информации, aLZW давно уже не встраивается в новые приложения (однако широко используется в старых).

Будущее алгоритмов сжатия тесно связано с будущим компью­терных технологий. Современные алгоритмы уже вплотную приблизи­лись к Шенноновской оценке 1.3 бита на символ, но ученые не видят причин, по которым компьютер не может предсказывать лучше, чем человек. Для достижения высоких степеней сжатия приходится использовать более сложные алгоритмы. Однако существовавшее одно время предубеждение, что сложные алгоритмы с более высокой степенью сжатия всегда более медленны, несостоятельно. Так, существуют крайне быстрые реализации алгоритмов РРМ для текстовой информации и SPIHT для графики, имеющие очень высокую степень сжатия.

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

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

Количество нужной человеку информации неуклонно растет. Объемы устройств для хранения данных и пропускная способность линий связи также растут. Однако количество информации растет быстрее. У этой проблемы есть три решения. Первое — ограничение количества информации. К сожалению, оно не всегда приемлемо. Например, для изображений это означает уменьшение разрешения, что приведет к потере мелких деталей и может сделать изображения вообще бесполезными (например, для медицинских или космических изображений). Второе — увеличение объема носителей информации и пропускной способности каналов связи. Это решение связано с материальными затратами, причем иногда весьма значительными. Третье решение — использование сжатия информации. Это решение позволяет в несколько раз сократить требования к объему устройств хранения данных и пропускной способности каналов связи без дополнительных издержек (за исключением издержек на реализацию алгоритмов сжатия). Условиями его применимости является избы­точность информации и возможность установки специального програм­много обеспечения либо аппаратуры как вблизи источника, так и вблизи приемника информации. Как правило, оба эти условия удовлетворяются.

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

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

При реализации алгоритма арифметического кодирования использовался язык C# и визуальная среда программирования MicrosoftVisualStudio 2005. Язык C# имеет следующие преимущества: простота, объектная ориентированность, типовая защищенность, “сборка мусора”, поддержка совместимости версий, упрощение отладки программ.

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

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

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

Таким образом, для передачи состояния объекта достаточно I=log2 Nбит информации. Заметим, что количество информации может быть дробным. Разумеется, дробное количество информации невозможно сохранить на носителе или передать по каналам связи. В то же время, если необходимо передать либо сохранить большое количество блоков информации дробной длины, их всегда можно сгруппировать таким образом, чтобы полностью исключить потери (например, посредством арифметического кодирования).

Основным недостатком комбинаторного подхода является его ориентированность на системы с равновероятными состояниями. В реальном мире события, как правило, не равновероятны. Вероятностный подход к оценке количества информации, учитывающий этот фактор, является наиболее широко используемым на сегодняшний день. Пусть переменная х может принимать N значений хi с вероятностью р(хi ). Тогда энтропия N

Обозначим через р(у|х) условную вероятность того, что наступит событие у если событие х уже наступило. В таком случае условная энтропия для переменной Y, которая может принимать М значений yi с условными вероятностями р(уi |х) будет

Приведенные формулы показывают, что вне зависимости от того, как были получены вероятности наступления следующих событий, для кодирования события с вероятностью р достаточно — log2 pбит (в полном соответствии с теоремой Шеннона об оптимальном кодировании).

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

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

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

Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 г., но сам алгоритм разработан не позднее 1975 г.

Алгоритм LZ77 является родоначальником целого семейства словарных схем — так называемых алгоритмов со скользящим словарем, или скользящим окном. Действительно, в LZ77 в качестве словаря используется блок уже закодированной последовательности. Как правило, по мере выполнения обработки положение этого блока относительно начала последовательности постоянно меняется, словарь «скользит» по входному потоку данных.

Скользящее окно имеет длину N, т. е. в него помещается N символов, и состоит из двух частей:

■ последовательности длины W=N-nуже закодированных символов, которая и является словарем;

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

Пусть к текущему моменту времени мы уже закодировали tсимволов S1 , S2 , . St . Тогда словарем будут являться Wпредшествующих символов St -( W -1) , St -( W -1)+1, …, St . Соответственно, в буфере находятся ожидающие кодирования символы St +1 , St +2 , …, St + n . Очевидно, что если W≥ t, то словарем будет являться вся уже обработанная часть входной последовательности.

Идея алгоритма заключается в поиске самого длинного совпадения между строкой буфера, начинающейся с символа St +1 , и всеми фразами словаря. Эти фразы могут начинаться с любого символа St -( W -1) , St -( W -1)+1, …, St выходить за пределы словаря, вторгаясь в область буфера, но должны лежать в окне. Следовательно, фразы не могут начинаться с St +1 . поэтому буфер не может сравниваться сам с собой. Длина совпадения не должна превышать размера буфера. Полученная в результате поиска фраза St -( i -1) , St -( i -1)+1, …, St -( i -1)+( j -1) кодируется с помощью двух чисел:

1) смещения (offset) от начала буфера, i;

2) длины соответствия, или совпадения (matchlength), j;

Смещение и длина соответствия играют роль указателя (ссылки), одно­значно определяющего фразу. Дополнительно в выходной поток записывается символ s, непосредственно следующий за совпавшей строкой буфера.

Таким образом, на каждом шаге кодер выдает описание трех объектов: смещения и длины соответствия, образующих код фразы, равной обработанной строке буфера, и одного символа s(литерала). Затем окно смещается на j+1 символов вправо и осуществляется переход к новому циклу кодирования. Величина сдвига объясняется тем, что мы реально закодировали именно j+1 символов: j с помощью указателя на фразу в словаре и 1(? i) с помощью тривиального копирования. Передача одного символа в явном виде позволяет разрешить проблему обработки еще ни разу не виденных символов, но существенно увеличивает размер сжатого блока.

Алгоритм LZ78, предложенный в 1978 г. Лемпелом и Зивом, нашел свое практическое применение только после реализации LZW84, предложенной Велчем в 1984 г.

Словарь является расширяющимся (expanding). Первоначально в нем содержится только 256 строк длиной в одну букву-все коды ASCII. В процессе работы словарь разрастается до своего максимального объема |Vmax | строк (слов). Обычно, объем словаря достигает нескольких десятков тысяч слов. Каждая строка в словаре имеет свою известную длину и этим похожа на привычные нам книжные словари и отличается от строк LZ77, которые допускали использование подстрок. Таким образом, количество слов в словаре точно равно его текущему объему. В процессе работы словарь пополняется по следующему закону:

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позиции posисходного текста. Так как словарь первоначально не пустой, такое слово всегда найдется;

2. В выходной файл помещается номер найденного слова в словаре positionи следующий символ из входного текста В (на котором обнаружилось различие) —

. Длина кода равна |position|+|B||=[logVmax]+8 (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте posсмещается на |strB|=|str|+l байт дальше к символу, следующему за В.

В таком варианте алгоритм почти не нашел практического применения и был значительно модернизирован. Изменения коснулись принципов управления словарем (его расширения и обновления) и способа формирования выходного кода:

Птак как словарь увеличивается постепенно и одинаково для кодировщика и декодировщика, для кодирования позиции нет необходимости использовать [logVmax ] бит, а можно брать лишь [logV] бит, где V-текущий объем словаря.

Самая серьезная проблема LZ78-переполнение словаря: если словарь полностью заполнен, прекращается его обновление и процесс сжатия может быть заметно ухудшен (метод FREEZE). Отсюда следует вывод-словарь нужно иногда обновлять. Самый простой способ как только словарь заполнился его полностью обновляют. Недостаток очевиден кодирование начинается на пустом месте, как бы с начала, и пока словарь не накопится сжатие будет незначительным, а дальше-замкнутый цикл опять очистка словаря. Поэтому предлагается словарь обновлять не сразу после его заполнения, а только после того, как степень сжатия начала падать (метод FLUSH). Более сложные алгоритмы используют два словаря, которые заполняются синхронно, но с задержкой на |V|/2 слов один относительно другого. После заполнения одного словаря, он очищается, а работа переключается на другой (метод SWAP). Еще более сложными являются эвристические методы обновления словарей в зависимости от частоты использования тех или иных слов (LRU, TAG).

Выходной код также формируется несколько иначе (сравните с предыдущим описанием):

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позицииposисходного текста;

2. В выходной файл помещается номер найденного слова в словаре

. Длина кода равна |position|=[logV] (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте posсмещается на |str| байт дальше к символу В.

Алгоритм PPM (predictionbypartialmatching) — это метод контекстно-ограниченного моделирования, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Модели, в которых для оценки вероятности используются контексты длиной не более чем N, принято называть моделями порядка N.

Вероятность символа может быть оценена в контекстах разных порядков. Например, символ «о» в контексте «tobeornott» может быть оценен в контексте первого порядка «t», в контексте второго порядка «_t», в контексте третьего порядка «t_t» и т.д. Он также может быть оценен в контексте нулевого порядка, где вероятности символов не зависят от контекста, и в контексте минус первого порядка, где все символы равновероятны. Контекст минус первого порядка используется для того, чтобы исключить ситуацию, когда символ будет иметь нулевую вероятность и не сможет быть закодирован. Это может случиться, если вероятность символа не будет оценена ни в одном из контекстов (что возможно, если символ в них ранее не встречался).

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

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

BWT — преобразование и компрессор

BWT-компрессор (Преобразование Барроуза – Уиллера) — сравнительно новая и революционная техника для сжатия информации (в особенности-текстов), основанная на преобразовании, открытом в 1983 г. и описанная в 1994 г.. BWT является удивительным алгоритмом. Во-первых, необычно само преобразование, открытое в научной области, далекой от архиваторов. Во-вторых,даже зная BWT, не совсем ясно, как его применить к сжатию информации. В-третьих, BW преобразование чрезвычайно просто. И, наконец, сам BWT компрессор состоит из «магической» последовательности нескольких рассмотренных ранее алгоритмов и требует, поэтому, для своей реализации самых разнообразных программных навыков.

BWT не сжимает данные, но преобразует блок данных в формат, исключительно подходящий для компрессии. Рассмотрим его работу на упрощенном примере. Пусть имеется словарь V из N символов. Циклически переставляя символы в словаре влево, можно получить N различных строк длиной N каждая. В нашем примере словарь-это слово V=»БАРАБАН» и N=7. Отсортируем эти строки лексикографически и запишем одну под другой:

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

Фактический «выход» преобразования состоит из строки L=»РББАНАА» и первичного индекса I, показывающего, какой символ из L является действительным первым символом словаря V (в нашем случае I=2). Зная L и I можно восстановить строку V.

Этот алгоритм кодиро­вания информации был предложен Д.А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

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

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

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

Допустим, у нас есть следующая таблица частот:

Название: Алгоритмы сжатия данных
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 02:50:21 26 июля 2009 Похожие работы
Просмотров: 1052 Комментариев: 14 Оценило: 3 человек Средний балл: 5 Оценка: неизвестно Скачать
15 7 6 6 5
А Б В Г Д

На первом шаге из листьев дерева выбираются два с наименьшими весами — Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5+6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д — ветви 1.

На следующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и В удаляются из списка свободных. После всего этого дерево кодирования выглядит так, как показано на рис. 2.

Рис. 2. Дерево кодирования Хаффмана после второго шага

На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д—ветви 1.

На последнем шаге в списке свободных осталось только два узла — это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис. 3.

Рис. 3. Окончательное дерево кодирования Хаффмана

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

Дня данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

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

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

Арифметическое сжатие — достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дроби, при этом строим дробь таким образом, чтобы наш текст был представлен как можно компактнее. Для примера рассмотрим построение такой дроби на интервале [0, 1) (0 — включается, 1 — нет). Интервал [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваем его на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов.

Пусть мы сжимаем текст «КОВ.КОРОВА» (что, очевидно, означает «коварная корова»). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны:

Символ Частота Вероятность Диапазон
О 3 0.3 [0.0; 0.3)
К 2 0.2 [0.3; 0.5)
В 2 0.2 [0.5; 0.7)
Р 1 0.1 [0.7; 0.8)
А 1 0.1 [0.8; 0.9)
“.” 1 0.1 [0.9; 1.0)

Будем считать, что эта таблица известна в компрессоре и декомпрессоре. Кодирование заключается в уменьшении рабочего интервала. Для первого символа в качестве рабочего интервала берется [0, 1). Мы разбиваем его на диапазоны в соответствии с заданными частотами символов (см. таблицу диапазонов). В качестве следующего рабочего интервала берется диапазон, соответствующий текущему кодируемому символу. Его длина пропорциональна вероятности появления этого символа в потоке. Далее считываем следующий символ. В качестве исходного берем рабочий интервал, полученный на предыдущем шаге, и опять разбиваем его в соответствии с таблицей диапазонов. Длина рабочего интервала уменьшается пропорционально вероятности текущего символа, а точка начала сдвигается вправо пропорционально началу диапазона для этого символа. Новый построенный диапазон берется в качестве рабочего и т. д.

Используя исходную таблицу диапазонов, кодируем текст «КОВ.КОРОВА»:

Исходный рабочий интервал [0,1).

Символ «К» [0.3; 0.5) получаем [0.3000; 0.5000).

Символ «О» [0.0; 0.3) получаем [0.3000; 0.3600).

Символ «В» [0.5; 0.7) получаем [0.3300; 0.3420).

Символ «.» [0.9; 1.0) получаем [0,3408; 0.3420).

Графический процесс кодирования первых трех символов можно представить так, как на рис. 4.

Рис. 4. Графический процесс кодирования первых трех символов

Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а его начало зависит от порядка следования символов в потоке. Можно обозначить диапазон символа с как [а[с]; b[с]), а интервал для i-го кодируемого символа потока как [li , hi ).

Большой вертикальной чертой на рисунке выше обозначено произвольное число, лежащее в полученном при работе интервале [/i , hi ). Для последовательности «КОВ.», состоящей из четырех символов, за такое число можно взять 0.341. Этого числа достаточно для восстановления исходной цепочки, если известна исходная таблица диапазонов и длина цепочки.

Рассмотрим работу алгоритма восстановления цепочки. Каждый следующий интервал вложен в предыдущий. Это означает, что если есть число 0.341, то первым символом в цепочке может быть только «К», поскольку только его диапазон включает это число. В качестве интервала берется диапазон «К» — [0.3; 0.5) и в нем находится диапазон [а[с]; b[с]), включающий 0.341. Перебором всех возможных символов по приведенной выше таблице находим, что только интервал [0.3; 0.36), соответствующий диапазону для «О», включает число 0.341. Этот интервал выбирается в качестве следующего рабочего и т. д.

Ниже показан фрагмент псевдокода процедур кодирования и декодирования. Символы в нем нумеруются как 1,2,3. Частотный интервал для i-го символа задается от cum_freq[i] до cum_freq[i-1]. Пpи убывании i cum_freq[i] возрастает так, что cum_freq[0] = 1. (Причина такого «обpатного» соглашения состоит в том, что cum_freq[0] будет потом содеpжать ноpмализующий множитель, котоpый удобно хpанить в начале массива). Текущий pабочий интеpвал задается в [low; high] и будет в самом начале pавен [0; 1) и для кодиpовщика, и для pаскодиpовщика.

С каждым символом текста обpащаться к пpоцедуpе encode_symbol(). Пpовеpить, что «завеpшающий» символ закодиpован последним. Вывести полученное значение интеpвала [low; high).

range = high — low

high = low + range*cum_freq[symbol-1]

low = low + range*cum_freq[symbol]

Value — это поступившее на вход число. Обpащение к пpоцедуpе decode_symbol() пока она не возвpатит «завеpшающий» символ.

//поиск такого символа, что

Из выражения (1) имеем:

В отличие от псеводокода, программа представляет low и high целыми числами. В псевдокоде текущий интеpвал пpедставлен чеpез [low; high), а в пpогpамме это [low; high] — интеpвал, включающий в себя значение high. Hа самом деле более пpавильно, хотя и более непонятно, утвеpждать, что в пpогpамме пpедставляемый интеpвал есть [low; high + 0.1111. ) по той пpичине, что пpи масштабитовании гpаниц для увеличения точности, нули смещаются к младшим битам low, а единицы смещаются в high.

По меpе сужения кодового интеpвала, стаpшие биты low и high становятся одинаковыми, и поэтому могут быть пеpеданы немедленно, т.к. на них будущие сужения интеpвала все pавно уже не будут влиять. Поскольку мы знаем, что low≤high, это воплотится в следующую пpогpамму:

low = 2 * (low — Half);

high = 2 * (high — Half) + 1;

гаpантиpующую, что после ее завеpшения будет спpеведливо неpавенство: low Half)

value = 2 * (value — Half) + input_bit();

low = 2 * (low — Half);

high = 2 * (high — Half) + 1;

Как показано в псевдокоде, арифметическое кодирование работает при помощи масштабирования накопленных вероятностей, поставляемых моделью в интервале [low; high] для каждого передаваемого символа. Пpедположим, что low и high настолько близки дpуг к дpугу, что опеpация масштабиpования пpиводит полученные от модели pазные символы к одному целому числу, входящему в [low; high]. В этом случае дальнейшее кодиpование пpодолжать невозможно. Следовательно, кодиpовщик должен следить за тем, чтобы интеpвал [low; high] всегда был достаточно шиpок. Пpостейшим способом для этого является обеспечение шиpины интеpвала не меньшей max_frequency — максимального значения суммы всех накапливаемых частот.

Как можно сделать это условие менее стpогим? Объясненная выше опеpация битового сдвига гаpантиpует, что low и high могут только тогда становиться опасно близкими, когда заключают между собой half. Пpедположим, они становятся настолько близки, что

first_qtr ≤low 14 — 1 и top_value = 2 16 — 1.

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

Теперь рассмотрим возможность переполнения при целочисленном умножении. Переполнения не произойдет, если произведение range*max_frequency вмещается в целое слово, т.к. накопленные частоты не могут превышать max_frequency. range имеет наибольшее значение в top_value + 1, поэтому максимально возможное произведение в программе есть 2 16 *(2 14 — 1), которое меньше 2 30 .

При завершении процесса кодирования необходимо послать уникальный завершающий символ (EOF-символ), а затем послать вслед достаточное количество битов для гарантии того, что закодированная строка попадет в итоговый рабочий интервал. Т.к. пpоцедуpа done_encoding() может быть увеpена, что low и high огpаничены либо выpажением (1a), либо (1b), ему нужно только пеpедать 01 или 10 соответственно, для удаления оставшейся неопpеделенности. Удобно это делать с помощью пpоцедуpы bit_plus_follow(). Пpоцедуpа input_bit() на самом деле будет читать немного больше битов, из тех, что вывела output_bit(), потому что ей нужно сохpанять заполнение нижнего конца буфеpа. Hеважно, какое значение имеют эти биты, поскольку EOF уникально опpеделяется последними пеpеданными битами.

Программа должна работать с моделью, которая предоставляет пару перекодировочных таблиц index_to_char[] и char_to_index[], и массив накопленных частот cum_freq[]. Причем к последнему предъявляются следующие требования:

никогда не делается попытка кодиpовать символ i, для котоpого

cum_freq[0] — 4 битов/символ.

Дополнительные затpаты на масштабиpование счетчиков отчасти больше, но все pавно очень малы. Для коpотких текстов (меньших 2 14 байт) их нет. Hо даже с текстами в 10 5 — 10 6 байтов накладные pасходы, подсчитанные экспеpиментально, составляют менее 0.25% от кодиpуемой стpоки.

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

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

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

Для реализации использовался язык C# и визуальная среда программирования MicrosoftVisualStudio 2005. В результате программное обеспечение очень компактно, интуитивно понятно и эффективно в работе.

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: ДИАЛОГ-МИФИ, 2002. — 384 с.

2. Сэломон Д. Сжатие данных, изображений и звука. Data Compression Methods. Серия: Мир программирования. Издательство: Техносфера, 2004. — 368 с.

3. Артюшенко В. М., Шелухин О. И., Афонин М. Ю. Цифровое сжатие видеоинформации и звука. Издательство: Дашков и Ко, 2004. — 426 с.

4. Седжвик Р. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск. Издательство: ДиаСофт, 2002. — 688 с.

// Количество бит для кода

// Максимально возможное значениекода

const int top_value = (int)(((long)1 = 0; i—)

freq[i] = (freq[i] + 1) / 2;

/* Обновление перекодировочных таблиц в случае перемещения символа */

for (i = symbol; freq[i] == freq[i — 1]; i—) ;

Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива

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

В 1978 г. авторами LZ77 был разработан алгоритм LZ78, лишенный названных недостатков.

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

Ключевым для размера получаемых кодов является размер словаря во фразах, потому что каждый код при кодировании по методу LZ78 содержит номер фразы в словаре. Из последнего следует, что эти коды имеют постоянную длину, равную округленному в большую сторону двоичному логарифму размера словаря (это количество бит в байт-коде расширенного ASCII).

Пример. Закодировать по алгоритму LZ78 строку «КРАСНАЯ КРАСКА», используя словарь длиной 16 фраз.

Указатель на любую фразу такого словаря — это число от 0 до 15, для его кодирования достаточно четырех бит.

В последнем примере длина полученного кода равна битам.

Алгоритмы LZ77, LZ78 и LZSS разработаны математиками и могут использоваться свободно.

В 1984 г. Уэлчем (Welch) был путем модификации LZ78 создан алгоритм LZW.

Пошаговое описание алгоритма-кодера.

Шаг 1. Инициализация словаря всеми возможными односимвольными фразами (обычно 256 символами расширенного ASCII).Инициализация входной фразы w первым символом сообщения.

Шаг 2. Считать очередной символ K из кодируемого сообщения.

Шаг 3. Если КОНЕЦ_СООБЩЕНИЯ

Выдать код для w

Если фраза wK уже есть в словаре

Присвоить входной фразе значение wK

Перейти к Шагу 2

Добавить wK в словарь

Присвоить входной фразе значение K

Перейти к Шагу 2.

Как и в случае с LZ78 для LZW ключевым для размера получаемых кодов является размер словаря во фразах: LZW-коды имеют постоянную длину, равную округленному в большую сторону двоичному логарифму размера словаря.

Пример. Закодировать по алгоритму LZW строку «КРАСНАЯ КРАСКА». Размер словаря — 500 фраз.

В этом примере длина полученного кода равна битам.

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

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

Любопытна история патентования LZW. Заявку на LZW подали почти одновременно две фирмы — сначала IBM и затем Unisys, но первой была рассмотрена заявка Unisys, которая и получила патент. Однако, еще до патентования LZW был использован в широко известной в мире Unix программе сжатия данных compress.

Упражнение 30 Закодировать сообщния «AABCDAACCCCDBB», «КИБЕРНЕТИКИ» и «СИНЯЯ СИНЕВА СИНИ», вычислить длины в битах полученных кодов, используя алгоритмы,

LZ77 (словарь — 12 байт, буфер — 4 байта),

LZ78 (словарь — 16 фраз),

LZSS (словарь — 12 байт, буфер — 4 байта),

LZW (словарь — ASCII+ и 16 фраз).

Упражнение 31 Может ли для первого символа сообщения код LZ78 быть короче кода LZW при одинаковых размерах словарей? Обосновать. Для LZW в размер словаря не включать позиции для ASCII+.

Дата добавления: 2015-12-26 ; просмотров: 943 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Моделирование при сжатии текстовых данных полуадаптированное словарное кодирование

Автор: Timothy Bell

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 содержит сведения об основных отличиях в разных реализациях этого метода. Все они произошли от одного из двух разных подходов,

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

Это была первая опубликованная версия 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], но объем требуемой памяти при этом также возрастет. Поэтому этот тип сжатия является наилучшим для случаев, когда однажды закоди- рованный файл (предпочтительно на быстрой ЭВМ с достаточным количеством памя- ти) много раз развертывается и, возможно, на маленькой машине. Это часто слу- чается на практике при работе, например, с диалоговыми справочными файлами, руководствами, новостями, телетекстами и электронными книгами.

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 затратах.

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

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

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

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

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

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

Дальность п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-техники на практике не в их приб- лижении к оптимальности, а по более прозаической причине — некоторые варианты позволяют осуществлять высоко эффективную реализацию.

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

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

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

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

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

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

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

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

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

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] описана параллельная реализация сжатия Зива-Лемпела.

АЛГОРИТМЫ СЖАТИЯ

Методы сжатия данных можно разделить на два типа:

  1. Неискажающие (loseless) методы сжатия гарантируют, что декодированные данные будут в точности совпадать с исходными;
  2. Искажающие (lossy) методы сжатия (называемые также методами сжатия с потерями) могут искажать исходные данные, например за счет удаления несущественной части данных, после чего полное восстановление невозможно.

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

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

Кроме того, можно выделить:

  • методы сжатия общего назначения (general-purpose), которые не зависят от физической природы входных данных и, как правило, ориентированы на сжатие текстов, исполняемых программ, объектных модулей и библиотек и т. д., т. е. данных, которые в основном и хранятся в ЭВМ;
  • специальные (special) методы сжатия, которые ориентированны на сжатие данных известной природы, например, звука, изображений и т. д. И за счет знания специфических особенностей сжимаемых данных достигают существенно лучшего качества и/или скорости сжатия, чем при использовании методов общего назначения.

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

Критерии оценки методов сжатия

Основными свойствами какого-либо алгоритма сжатия данных являются:

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

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

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

Понятно, что критерии оценки методов сжатия с практической точки зрения сильно зависят от предполагаемой области применения. Например, при использовании сжатия в системах реального времени необходимо обеспечить высокую скорость кодирования и декодирования; для встроенных систем критический параметр – объем требуемой памяти; для систем долговременного хранения данных – качество сжатия и/или скорость декодирования и т. д.

Надежность программ и сложность алгоритмов

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

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

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

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

Современные методы сжатия

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

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

Наилучшие по качеству сжатия алгоритмы статистического моделирования источников Маркова семейств PPM (от англ. Prediction by Partial Matching), DMC (от англ. Dynamic Markov Compression), ACB (от англ. Associative Coding by Buyanovski) предсказывают вероятность появления следующего символа на основе анализа частоты появления различных последовательностей символов в ранее закодированной части сообщения.

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

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

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

Алгоритмы словарного сжатия

Алгоритмы словарного сжатия заменяют подстроки кодируемой последовательности символов ссылками в словарь на идентичные подстроки. С практической точки зрения наилучшими представляются алгоритмы семейства LZ77 (впервые предложенные Лемпелом и Зивом в 1977г.), которые заменяют начало не просмотренной части кодируемого сообщения ссылкой на самое длинное вхождение идентичной подстроки в уже закодированной части.

Обычно для ускорения поиска совпадающих подстрок и ограничения объема требуемой памяти область поиска ограничивается определенным количеством последних символов закодированной части: такая модификация LZ77 называется LZ77 со скользящим окном (LZ77 with sliding window).

Алгоритмы семейства LZ77 в 1.3-1.7 раза уступают методам статистического моделирования по качеству сжатия, однако обладают очень высокой скоростью кодирования при сравнительно небольшом объеме требуемой памяти.

Огромное преимущество алгоритмов семейства LZ77 – чрезвычайно высокая скорость декодирования. Это позволяет применять их в тех случаях, когда Декодирование осуществляется гораздо чаще кодирования или скорость декодирования очень важна (например, при хранении данных на CD-ROM, в файловых системах со сжатием и т. д.).

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

Алгоритмы сжатия сортировкой блоков

Алгоритмы сжатия сортировкой блоков семейства BWT/BS, разработанные в 1994г. Барроузом и Уилером, разбивают кодируемую последовательность на блоки символов, представляют (обратимым образом) символы каждого блока так, что появляется много повторений одного и того же символа, а затем сжимают преобразованные данные каким-либо достаточно простым способом.

По качеству сжатия они приближаются к методам статистического моделирования (уступая им в 1.2-1.3 раза), а по скорости – к алгоритмам семейства LZ77, при меньшем по сравнению с методами статистического моделирования объеме требуемой памяти; скорость декодирования также достаточно высока.

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

Методы энтропийного кодирования

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

Такие методы кодирования известны с конца 40-х гг. и хорошо изучены. Их можно разбить на два больших класса: префиксные (методы Хаффмана, Шеннона, Шеннона-Фано) и арифметические.

Префиксные коды

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

Известно много способов построения префиксных кодов: коды Шеннона и Шеннона-Фано почти идеальны, а код Хаффмана – оптимален среди префиксных кодов.

Так как длина каждого кодового слова выражается целым числом битов, то префиксные коды неэффективны на алфавитах малой мощности (2-8 символов) или при наличии символов с очень большой (более 30-50%) вероятностью появления и по качеству сжатия могут уступать арифметическим.

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

Как правило, алгоритмы словарного сжатия и сжатия сортировкой блоков используют для кодирования выхода основного алгоритма сжатия коды Хаффмана.

Арифметические коды

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

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

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

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

АЛГОРИТМЫ СЖАТИЯ

Методы сжатия данных можно разделить на два типа:

  1. Неискажающие (loseless) методы сжатия гарантируют, что декодированные данные будут в точности совпадать с исходными;
  2. Искажающие (lossy) методы сжатия (называемые также методами сжатия с потерями) могут искажать исходные данные, например за счет удаления несущественной части данных, после чего полное восстановление невозможно.

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

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

Кроме того, можно выделить:

  • методы сжатия общего назначения (general-purpose), которые не зависят от физической природы входных данных и, как правило, ориентированы на сжатие текстов, исполняемых программ, объектных модулей и библиотек и т. д., т. е. данных, которые в основном и хранятся в ЭВМ;
  • специальные (special) методы сжатия, которые ориентированны на сжатие данных известной природы, например, звука, изображений и т. д. И за счет знания специфических особенностей сжимаемых данных достигают существенно лучшего качества и/или скорости сжатия, чем при использовании методов общего назначения.

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

Критерии оценки методов сжатия

Основными свойствами какого-либо алгоритма сжатия данных являются:

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

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

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

Понятно, что критерии оценки методов сжатия с практической точки зрения сильно зависят от предполагаемой области применения. Например, при использовании сжатия в системах реального времени необходимо обеспечить высокую скорость кодирования и декодирования; для встроенных систем критический параметр – объем требуемой памяти; для систем долговременного хранения данных – качество сжатия и/или скорость декодирования и т. д.

Надежность программ и сложность алгоритмов

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

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

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

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

Современные методы сжатия

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

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

Наилучшие по качеству сжатия алгоритмы статистического моделирования источников Маркова семейств PPM (от англ. Prediction by Partial Matching), DMC (от англ. Dynamic Markov Compression), ACB (от англ. Associative Coding by Buyanovski) предсказывают вероятность появления следующего символа на основе анализа частоты появления различных последовательностей символов в ранее закодированной части сообщения.

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

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

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

Алгоритмы словарного сжатия

Алгоритмы словарного сжатия заменяют подстроки кодируемой последовательности символов ссылками в словарь на идентичные подстроки. С практической точки зрения наилучшими представляются алгоритмы семейства LZ77 (впервые предложенные Лемпелом и Зивом в 1977г.), которые заменяют начало не просмотренной части кодируемого сообщения ссылкой на самое длинное вхождение идентичной подстроки в уже закодированной части.

Обычно для ускорения поиска совпадающих подстрок и ограничения объема требуемой памяти область поиска ограничивается определенным количеством последних символов закодированной части: такая модификация LZ77 называется LZ77 со скользящим окном (LZ77 with sliding window).

Алгоритмы семейства LZ77 в 1.3-1.7 раза уступают методам статистического моделирования по качеству сжатия, однако обладают очень высокой скоростью кодирования при сравнительно небольшом объеме требуемой памяти.

Огромное преимущество алгоритмов семейства LZ77 – чрезвычайно высокая скорость декодирования. Это позволяет применять их в тех случаях, когда Декодирование осуществляется гораздо чаще кодирования или скорость декодирования очень важна (например, при хранении данных на CD-ROM, в файловых системах со сжатием и т. д.).

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

Алгоритмы сжатия сортировкой блоков

Алгоритмы сжатия сортировкой блоков семейства BWT/BS, разработанные в 1994г. Барроузом и Уилером, разбивают кодируемую последовательность на блоки символов, представляют (обратимым образом) символы каждого блока так, что появляется много повторений одного и того же символа, а затем сжимают преобразованные данные каким-либо достаточно простым способом.

По качеству сжатия они приближаются к методам статистического моделирования (уступая им в 1.2-1.3 раза), а по скорости – к алгоритмам семейства LZ77, при меньшем по сравнению с методами статистического моделирования объеме требуемой памяти; скорость декодирования также достаточно высока.

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

Методы энтропийного кодирования

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

Такие методы кодирования известны с конца 40-х гг. и хорошо изучены. Их можно разбить на два больших класса: префиксные (методы Хаффмана, Шеннона, Шеннона-Фано) и арифметические.

Префиксные коды

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

Известно много способов построения префиксных кодов: коды Шеннона и Шеннона-Фано почти идеальны, а код Хаффмана – оптимален среди префиксных кодов.

Так как длина каждого кодового слова выражается целым числом битов, то префиксные коды неэффективны на алфавитах малой мощности (2-8 символов) или при наличии символов с очень большой (более 30-50%) вероятностью появления и по качеству сжатия могут уступать арифметическим.

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

Как правило, алгоритмы словарного сжатия и сжатия сортировкой блоков используют для кодирования выхода основного алгоритма сжатия коды Хаффмана.

Арифметические коды

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

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

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

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

Моделирование при сжатии текстовых данных полуадаптированное словарное кодирование

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

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

Избыточность в представлении строки S есть L(S) — H(S), где L(S) есть длина представления в битах, а H(S) — энтропия — мера содержания информации, также выраженная в битах. Алгоритмов, которые могли бы без потери информации сжать строку к меньшему числу бит, чем составляет ее энтропия, не существует. Если из исходного текста извлекать по одной букве некоторого случайного набоpа, использующего алфавит А, то энтропия находится по формуле:

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

Модели, основанные на применении статичной вероятности, не позволяют хорошо характеризовать многие источники. Например, в английском тексте, буква U менее распространена чем E, поэтому модель статичной вероятности будет неправильно предсказывать, что QE должно быть более растространенным сочетанием, чем QU. Хорошо описывать такие источники позволяют вероятностные модели Маркова. Источники Маркова имеют множество состояний, смена которых происходит при появлении очередной буквы. Каждое состояние связывается с распределением вероятности, определяющим следующее состояние модели и следующую производимую букву. Когда марковский источник, представляющий собой текст, подобный английскому, выдает букву Q, он установливает состояние, в котором U есть более вероятный вывод. Дальнейшее изучение вопросов, связанных с энтропией, статичными источниками и источниками Маркова может быть продолжено в большинстве книг по теории информации [2].

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

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

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


Коды префиксов

Большинство широко изучаемых алгоритмов сжатия данных основаны на кодах Хаффмана. В коде Хаффмана каждая буква исходного текста представляется в архиве кодом переменной длины. Более частые буквы представляются короткими кодами, менее частые — длинными. Коды, используемые в сжатом тексте должны подчиняться свойствам префикса, а именно: код, использованный в сжатом тексте не может быть префиксом любого другого кода.

Коды префикса могут быть найдены посредством дерева, в котором каждый лист соответствует одной букве алфавита источника. Hа pисунке 1 показано дерево кода префикса для алфавита из 4 букв. Код префикса для буквы может быть прочитан при обходе деpева от корня к этой букве, где 0 соответствует выбору левой его ветви, а 1 — правой. Дерево кода Хаффмана есть дерево с выравненным весом, где каждый лист имеет вес, равный частоте встречаемости буквы в исходном тексте, а внутренние узлы своего веса не имеют. Дерево в примере будет оптимальным, если частоты букв A, B, C и D будут 0.125, 0.125, 0.25 и 0.5 соответственно.

Рисунок 1: Дерево представления кода префикса

Обычные коды Хаффмана требуют предварительной информации о частоте встречаемости букв в исходном тексте, что ведет к необходимости его двойного просмотра — один для получения значений частот букв, другой для проведения самого сжатия. В последующем, значения этих частот нужно объединять с самим сжатым текстом, чтобы в дальнейшем сделать возможным его развертывание. Адаптивное сжатие выполняется за один шаг, т.к. код, используемый для каждой буквы исходного текста, основан на частотах всех остальных кpоме нее букв алфавита. Основы для эффективной реализации адаптивного кода Хаффмана были заложены Галлагером[3], Кнут опубликовал практическую версию такого алгоритма[5], а Уиттер его pазвил[10].

Оптимальный адаптированный код Уиттера всегда лежит в пределах одного бита на букву источника по отношению к оптимальному статичному коду Хаффмана, что обычно составляет несколько процентов от H . К тому же, статичные коды Хаффмана всегда лежат в пределах одного бита на букву исходного текста от H ( они достигают этот предел только когда для всех букв p(C) = 2 ). Такие же ограничения могут быть отнесены к источникам Маркова, если статичное или адаптированное дерево Хаффмана используется для каждого состояния источника, выведеного из его исходного текста. Существуют алгоритмы сжатия которые могут преодолевать эти ограничения. Алгоритм Зива-Лемпелла, например, присваивает слова из аpхива фиксированной длины строкам исходного текста пеpеменной длины[11], а арифметическое сжатие может использовать для кодирования букв источника даже доли бита[12].

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

Расширяющиеся деревья были впервые описаны в 1983 году[8] и более подpобно рассмотрены в 1985[9]. Первоначально они понимались как вид самосбалансиpованных деpевьев двоичного поиска, и было также показано, что они позволяют осуществить самую быструю реализацию приоритетных очередей[4]. Если узел расширяющегося дерева доступен, то оно является расширенным. Это значит, что доступный узел становится корнем, все узлы слева от него образуют новое левое поддерево, узлы справа — новое правое поддерево. Расширение достигается при обходе дерева от старого корня к целевому узлу и совершении пpи этом локальных изменений, поэтому цена расширения пропорциональна длине пройденного пути.

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

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

В случае зигзагообразного обхода лексикографического дерева, проведение как расширения, так и полурасширения усложняется, в отличие от прямого маршрута по левому или правому краю дерева к целевому узлу ( случаи зигзага рассмотрены в [8], [9] ). Этот простой случай показан на рисунке 2. Воздействие полурасширения на маршруте от корня ( узел w ) до листа узла A заключается в перемене местами каждой пары внутренних следующих друг за другом узлов, в результате чего длина пути от корня до узла-листа сокращается в 2 раза. В процессе полурасширения узлы каждой пары, более далекие от корня, включаются в новый путь ( узлы x и z ), а более близкие из него исключаются ( узлы w и y ).

Рисунок 2: Полурасширение вокруг самого левого листа дерева кодов

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

Hенужность поддержки лексикографического порядка значительно упрощает проведение операции полурасширения за счет исключения случая зигзага. Это может быть сделано проверкой узлов на пути от корня к целевому листу и переменой местами правых наследников с их братьями. Назовем это ПОВОРОТОМ дерева. Тепеpь новый код префикса для целевого листа будет состоять из одних нулей, поскольку он стал самым левым листом. На рисунке 3 дерево было повернуто вокруг листа C. Эта операция не нарушает никаких ограничений представления полурасширения. Доказательство этого просто выводится из потенциальной функции, приведенной в [9] для доказательства независимости ограничений представления от порядка следования поддеревьев узла.

Рисунок 3: Поворот вокруг C исключает необходимость зигзагообразного полурасширения

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

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

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

Рисунок 5: Полурасширение вокруг C с использованием полуобоpота

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

Представленная здесь программа написана по правилам языка Паскаль с выражениями, имеющими постоянное значение и подставляемыми в качестве констант для повышения читаемости программы. Структуры данных, используемые в примере, реализованы на основе массивов, даже если логическая структура могла быть более ясной при использовании записей и ссылок. Это соответствует форме представления из ранних работ по этой же тематике [5,10], а также позволяет осуществлять и простое решение в более старых, но широко используемых языках, таких как Фортран, и компактное представление указателей. Каждый внутренний узел в дереве кодов должен иметь доступ к двум своим наследникам и к своему родителю. Самый простой способ для этого — использовать для каждого узла 3 указателя: влево, вправо и вверх. Такое представление, обсуждаемое в [9] было реализовано только при помощи двух указателей на узел(2), но при этом компактное хранение их в памяти будет компенсировано возрастанием длительности выполнения программы и запутанностью ее кода. Нам потребуются следующие основные структуры данных:

Типы upindex и downindex используются для указателей вверх и вниз по дерева кодов. Указатели вниз должны иметь возможность указывать и на листья, и на внутренние узлы, в то время как ссылки вверх указывают только на внутренние узлы. Внутренние узлы будут храниться ниже листьев, поэтому значения индексов между 1 и maxchar включительно будут применены для обозначения ссылок на внутренние узлы, когда как значения индексов между maxchar + 1 и 2 * maxchar + 1 включительно — ссылок на листья. Заметим что корень дерева всегда находится в 1-ой ячейке и имеет неопределенного родителя. Cоотвествующая листу буква может быть найдена вычитанием maxchar + 1 из его индекса.

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

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

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

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

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

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

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

На практике, расширяемые деревья, на которых основываются коды префикса, хоть и не являются оптимальными, но обладают некоторыми полезными качествами. Прежде всего это скорость выполнения, простой программный код и компактные структуры данных. Для алгоритма расширяемого префикса требуется только 3 массива, в то время как для Л-алгоритма Уитерса, вычисляющего оптимальный адаптированный код префикса, — 11 массивов [10]. Предположим, что для обозначения множества символов исходного текста используется 8 бит на символ, а конец файла определяется символом, находящимся вне 8-битового предела, maxchar = 256, и все элементы массива могут содержать от 9 до 10 битов ( 2 байта на большинстве машин)(3). Неизменные запросы памяти у алгоритма расширяемого префикса составляют приблизительно 9.7К битов (2К байтов на большинстве машин). Подобный подход к хранению массивов в Л-алгоритме требует около 57К битов (10К байтов на большинстве машин ).

Другие широко применяемые алгоритмы сжатия требуют еще большего пространства, например, Уэлч советует для реализации метода Зива-Лемпела [11] использовать хеш-таблицу из 4096 элементов по 20 битов каждый, что в итоге составляет уже 82К битов ( 12К байтов на большинстве машин ). Широко используемая команда сжатия в системе ЮНИКС Беркли применяет код Зива-Лемпела, основанный на таблице в 64К элементов по крайней мере в 24 бита каждый, что в итоге дает 1572К битов ( 196К байтов на большинстве машин ).

В таблица I показано как Л-алгоритм Уиттера и алгоритм расширяющегося префикса характеризуются на множестве разнообразных тестовых данных. Во всех случаях был применен алфавит из 256 отдельных символов, расширенный дополнительным знаком конца файла. Для всех файлов, результат работы Л-алгоритма находится в пределах 5% от H и обычно составляет 2% от H . Результат работы алгоритма расширяющегося префикса никогда не превышает H больше, чем на 20%, а иногда бывает много меньше H .

Тестовые данные включают программу на Си (файл 1), две программы на Паскале (файлы 2 и 3) и раннюю редакцию данной статьи (файл 4). Все 4 текстовые файлы используют множество символов кода ASCII с табуляцией, заменяющей группы из 8 пробелов в начале, и все пробелы в конце строк. Для всех этих файлов Лалгоритм достигает результатов, составляющих примерно 60% от размеров исходного текста, а алгоритм расширения — 70%. Это самый худший случай сжатия, наблюдаемый при сравнении алгоритмов.

Два объектых файла М68000 были сжаты ( файлы 5 и 6 ) также хорошо, как и файлы вывода TEX в формате .DVI ( файл 7 ). Они имеют меньшую избыточность, чем текстовые файлы, и поэтому ни один метод сжатия не может сократить их размер достаточно эффективно. Тем не менее, обоим алгоритмам удается успешно сжать данные, причем алгоритм расширения дает результаты, большие результатов работы Л-алгоритма приблизительно на 10%.

Были сжаты три графических файла, содержащие изображения человеческих лиц ( файлы 8, 9 и 10 ). Они содержат различное число точек и реализованы через 16 оттенков серого цвета, причем каждый хранимый байт описывал 1 графическую точку. Для этих файлов результат работы Л-алгоритма составлял приблизительно 40% от первоначального размера файла, когда как алгоритма расширения — только 25% или 60% от H . На первый взгляд это выглядит невозможным, поскольку H есть теоретический информационный минимум, но алгоритм расширения преодолевает его за счет использования марковских характеристик источников.

Последние 3 файла были искусственно созданы для изучения класса источников, где алгоритм расширяемого префикса превосходит ( файлы 11, 12 и 13 ) все остальные. Все они содержат одинаковое количество каждого из 256 кодов символов, поэтому H одинакова для всех 3-х файлов и равна длине строки в битах. Файл 11, где полное множество символов повторяется 64 раза, алгоритм расширения префикса преобразует незначительно лучше по сравнению с H . В файле 12 множество символов повторяется 64 раза, но биты каждого символа обращены, что препятствует расширению совершенствоваться относительно H . Ключевое отличие между этими двумя случаями состоит в том, что в файле 11 следующие друг за другом символы вероятно исходят из одного поддерева кодов, в то время как в файле 12 это маловероятно. В файле 13 множество символов повторяется 7 раз, причем последовательность, образуемая каждым символом после второго повторения множества, увеличивается вдвое. Получается, что файл заканчивается группой из 32 символов «a», за которой следуют 32 символа «b» и т.д. В этом случае алгоритм расширяемого префикса принимает во внимание длинные последовательности повторяющихся символов, поэтому результат был всего 25% от H , когда как Л-алгоритм никогда не выделял символ, вдвое более распространенный в тексте относительно других, поэтому на всем протяжении кодирования он использовал коды одинаковой длины.

Когда символ является повторяющимся алгоритм расширяемого префикса последовательно назначает ему код все меньшей длины: после по крайней мере log n повторений любой буквы n-буквенного алфавита, ей будет соответствовать код длиной всего лишь в 1 бит. Это объясняет блестящий результат применения алгоритма расширения к файлу 13. Более того, если буквы из одного поддерева дерева кодов имеют повторяющиеся ссылки, алгоритм уменьшит длину кода сразу для всех букв поддерева. Это объясняет, почему алгоритм хорошо отработал для файла 11.

Таблица: Результаты тестирования Л-алгоритма и алгоритма расширяемого префикса

Среди графических данных редко когда бывает, чтобы несколько последовательных точек одной графической линии имели одинаковую цветовую интенсивность, но в пределах любой области с однородной структурой изображения, может быть применено свое распределение статичной вероятности. При сжатии последовательных точек графической линии, происходит присвоение коротких кодов тем точкам, цвета которых наиболее распространены в текущей области. Когда алгоритм переходит от области с одной структурой к области с другой структурой, то короткие коды быстро передаются цветам, более распространенным в новой области, когда как коды уже не используемых цветов постепенно становятся длиннее. Исходя из характера такого поведения, алгоритм расширяемого префикса можно назвать ЛОКАЛЬНО АДАПТИВНЫМ. Подобные локально адаптивные алгоритмы способны достигать приемлимых результатов пpи сжатии любого источника Маркова, который в каждом состоянии имеет достаточную длину, чтобы алгоритм приспособился к этому состоянию.

Другие локально адаптированные алгоритмы сжатия данных были предложены Кнутом[5] и Бентли et al [1]. Кнут предложил локально адаптированный алгоритм Хаффмана, в котором код, используемый для очередной буквы определяется n последними буквами. Такой подход с точки зрения вычислений ненамного сложнее, чем простые адаптированные алгоритмы Хаффмана, но соответствующее значение n зависит от частоты изменения состояний источника. Бентли et al предлагает использовать эвристическую технику перемещения в начало ( move-to-front ) для организации списка последних использованных слов ( предполагая, что текст источника имеет лексическую ( словарную ) структуру ) в соединении с локально адаптированным кодом Хаффмана для кодирования количества пробелов в списке. Этот код Хаффмана включает периодическое уменьшение весов всех букв дерева посредством умножения их на постоянное число, меньше 1. Похожий подход использован в [12] для арифметических кодов. Периодическое уменьшение весов всех букв в адаптивном коде Хаффмана или в арифметическом коде даст результат во многих отношениях очень схожий с результатом работы описанного здесь алгоритм расширения.

Компактные структуры данных, требуемые алгоритмом расширяемого префикса, позволяют реализуемым моделям Маркова иметь дело с относительно большим числом состояний. Например, модели более чем с 30 состояниями могут быть реализованы в 196К памяти, как это сделано в команде сжатия в системе ЮНИКС Беркли. Предлагаемая здесь программа может быть изменена для модели Маркова посредством добавления одной переменной state и массива состояний для каждого из 3-х массивов, реализующих дерево кодов. Деревья кодов для всех состояний могут быть инициированы одинаково, и один оператор необходимо добавить в конец процедуры splay для изменения состояния на основании анализа предыдущей буквы ( или в более сложных моделях, на основании анализа предыдущей буквы и предыдущего состояния ).

Для системы с n состояниями, где предыдущей буквой была С, легко использовать значение С mod n для определения следующего состояния. Такая модель Маркова слепо переводит каждую n-ю букву алфавита в одно состояние. Для сжатия текстового, объектного и графического ( файл 8 ) файлов значения n изменялись в пределах от 1 до 64. Результаты этих опытов показаны на рисунке 6. Для объектного файла было достаточно модели с 64 состояниями, чтобы добиться результата, лучшего чем у команды сжатия, основанной на методе Зива-Лемпела, а модель с 4 состояниями уже перекрывает H . Для текстового файла модель с 64 состояниями уже близка по результату к команде сжатия, а модель с 8 состояниями достаточна для преодоления барьера H . Для графических данных ( файл 8 ) модели с 16 состояниями достаточно, чтобы улучшить результат команды сжатия, при этом все модели по своим результатам великолепно перекрывают H . Модели Маркова более чем с 8 состояниями были менее эффективны, чем простая статичная модель, применяемая к графическим данным, а самый плохой результат наблюдался для модели с 3 состояниями. Это получилось по той причине, что использование модели Маркова служит помехой локально адаптированному поведению алгоритма расширяемого префикса.

Рисунок 6: Характеристика алгоритма расширяющегося префикса с марковской моделью

Оба алгоритма, Л- и расширяемого префикса, выполняются по времени прямо пропорционально размеру выходного файла, и в обоих случаях, выход в наихудшем варианте имеет длину 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) может быть разделен следующим образом:

Деление интервала легко осуществляется посредством накопления вероятностей каждой буквы алфавита и ее предшественников. Дан сжатый текст 0.6 ( представленный в виде десятичной дроби ), тогда первой его буквой должна быть D, потому что это число лежит в интервале [ 0.5, 1 ). Пересчет дает результат:

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

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

Первоочередной проблемой здесь является высокая точность арифметики для понимания и опеpиpования со сплошным битовым потоком, каковым выглядит сжатый текст, рассматриваемый в качестве числа. Эта проблема была решена в 1979 году [6]. Эффективность сжатия методом статичного арифметического кодирования будет равна H , только при использовании арифметики неограниченной точности. Но и ограниченной точности большинства машин достаточно, чтобы позволять осуществлять очень хорошее сжатие. Целых переменных длиной 16 битов, 32-битовых произведений и делимых достаточно, чтобы результат адаптивного арифметического сжатия лежал в нескольких процентах от предела и был едва ли не всегда немного лучше, чем у оптимального адаптированного кода Хаффмана, предложенного Уитером.

Как и в случае кодов Хаффмана, статичные арифметические коды требуют двух проходов или первоначального знания частот букв. Адаптированные арифметические коды требуют эффективного алгоритма для поддержания и изменения информации о бегущей и накапливаемой частотах по мере обработки букв. Простейший путь для этого — завести счетчик для каждой буквы, увеличивающий свое значение на единицу всякий раз, когда встречена сама эта буква или любая из следующих после нее в алфавите. В соответствии с этим подходом, частота буквы есть разница между числом ее появлений и числом появлений ее предшественников. Этот простой подход может потребовать O(n) операций над буквой n-арного алфавита. В реализованном на Си Уиттеном, Нейлом и Клири алгоритме сжатия арифметических данных [12], среднее значение было улучшено посредством использования дисциплины move -to-front, что сократило количество счетчиков, значения которых измененяются каждый раз, когда обрабатывается буква.

Дальнейшее улучшение организации распределения накопленной частоты требует коренного отхода от простых СД, используемых в [12]. Требования которым должна отвечать эта СД лучше изучить, если выразить ее через абстрактный тип данных со следующими пятью операциями: 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 — от корня к листу.

Рисунок 7: Дерево накапливаемых частот

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

Инициализация этой структуры включает в себя не только построение древовидной СД, но и инициализацию частот каждого листа и узла следующим образом:

Для того, чтобы отыскать букву и соответствующий ей интервал накопленной частоты, когда известна отдельная накопленная частота, необходимо обойти дерево начиная с корня по направлению к букве, производя беглое вычисление интервала частот, соответствующего текущей ветке дерева. Интервал, соответствующий корню, есть [0, freq[root]], он должен содержать f. Если отдельный узел деpева i связан с интервалом [a, b), где a — b = freq[i], то интервалами, связанными с двумя поддеревьями будут интервалы [a, a+freq[left[i]] ) и [a+freq[left[i]], b). Они не пересекаются, поэтому путь вниз по дереву будет таким, что f содержится в подинтервале, связанном с каждым узлом на этом пути. Это показано в следующей процедуре:

Чтобы найти связанный с буквой частотный интервал, процесс, описанный в 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]]].

Если проблема сохранения сбалансированности в дереве накапливаемых частот не стоит, то функция 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иведенные опытные результаты показывают, что эти постоянные множители более чем компенсируются простотой алгоритма расширяющегося префикса.

Рисунок 8: Полуобоpот в дереве накапливаемых частот

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

Программа игнорирует проблему переполнения счетчиков частот. Арифметическое сжатие данных постоянно производит вычисление по формуле a * b / c, и предел точности результата вычисления определяется размером памяти, выделяемой промежуточным произведениям и делимым, а не самим целочисленным переменным. Многие 32-битные машины накладывают 32-битовое ограничение на произведения и делимые, и т.о. на самом деле устанавливают 16-битовый предел на представление целых чисел a, b и c в вышеуказанном выражении. Когда это ограничение передается коду самой программе архиватора, то чистый результат имеет ограничение в 16383 для максимального значения, возвращаемого функцией maxrange или значения freq[root]. Поэтому, если сжатый файл имеет длину более 16383 байтов, необходимо периодически пересчитывать все частоты в СД, чтобы втиснуть их в этот интервал. Простой путь для этого — разделить значения всех частот на маленькую константу, например 2, и округлением вверх предохранить частоты от обнуления.

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

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

Hа основе алгоpитма Виттена, Нейла и Клири[12] вышепредставленные процедуры были обьединены в среде языка Паскаль. Как и ожидалось, значительной разницы между сжатыми текстами, полученными в результате работ первоначального и модифицированного алгоритмов арифметического сжатия не оказалось. Обычно эти тексты имеют одинаковую длину.

:
Рисунок 9: Характеристика алгоритмов арифметического сжатия

Рисунок 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 ) является более эффективным для маленьких типовых алфавитов(4).

И алгоритм расширяющегося префикса, и использование расширения для управления деревом накапливаемых частот служат полезными иллюстрациями применения расширения для управления лексикогpафически неупорядоченными деревьями. Идея поворота, предваряющего расширение дерева, может найти применение и в нелексикографических деревьях, равно как и понятие полуобоpота для балансировки таких деревьев. Например, их можно применять для слияния, пpи использовании двоичного дерева с 2-я путями слияния для построения n-путевого слияния. У Сарасвата уже появлялись подобные идеи при разработке средств слияния деревьев на Прологе[7].

Интересно отметить, что по сравнению с другими адаптивными схемами сжатия, потеря здесь 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 байт, хотя, чтобы позволить расширению установить дерево во все возможные состояния, нужны ключи еще длиннее чем этот, но даже короткий ключ может позволить осуществить шифрование на приемлемом уровне.

Алгоритмы сжатия данных — курсовая работа

Категория: Курсовые работы
Рубрика: Программирование, компьютеры и кибернетика, ИТ технологии
Размер файла: 341 Kb
Количество загрузок:
Количество просмотров:
Описание работы: курсовая работа на тему Алгоритмы сжатия данных
Подробнее о работе: Читать или Скачать
ВНИМАНИЕ: Администрация сайта не рекомендует использовать бесплатные Курсовые работы для сдачи преподавателю, чтобы заказать уникальные Курсовые работы, перейдите по ссылке Заказать Курсовые работы недорого
Смотреть
Скачать
Заказать

Алгоритмы сжатия данных

  • Введение
  • Общие сведения
  • Энтропия и количество информации
  • Комбинаторная, вероятностная и алгоритмическая оценка количества информации
  • Моделирование и кодирование
  • Некоторые алгоритмы сжатия данных
  • Алгоритм LZ77
  • Алгоритм LZ78-LZW84
  • Алгоритм PPM
  • BWT — преобразование и компрессор
  • Кодирование Хаффмана
  • Арифметическое кодирование
  • Алгоритм арифметического кодирования
  • Реализация алгоритма арифметического кодирования
  • Реализация модели
  • Доказательство правильности декодирования
  • Приращаемая передача и получение
  • Отрицательное переполнение
  • Переполнение и завершение
  • Адаптивная модель для арифметического кодирования
  • Эффективность сжатия
  • Заключение
  • Список литературы
  • Приложение 1. Программный код
  • Приложение 2. Интерфейс программы
  • Введение
  • Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и на сколько та или иная информация при этом сожмется. Кроме того, им были проведены опыты по эмпирической оценке избыточности английского текста. Он предлагал людям угадывать следующую букву и оценивал вероятность правильного угадывания. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0.6 — 1.3 бита на символ. Несмотря на то, что результаты исследований Шеннона были по-настоящему востребованы лишь десятилетия спустя, трудно переоценить их значение.
  • Первые алгоритмы сжатия были примитивными в связи с тем, что была примитивной вычислительная техника. С развитием мощностей компьютеров стали возможными все более мощные алгоритмы. Настоящим прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. До этого момента сжатие сводилось к примитив-ному кодированию символов. Словарные алгоритмы позволяли кодир-овать повторяющиеся строки символов, что позволило резко повысить степень сжатия. Важную роль сыграло изобретение примерно в это же время арифметического кодирования, позволившего воплотить в жизнь идею Шеннона об оптимальном кодировании. Следующим прорывом было изобретение в 1984 г. алгоритма РРМ. Следует отметить, что это изобретение долго оставалось незамеченным. Дело в том, что алгоритм сложен и требует больших ресурсов, в первую очередь больших объемов памяти, что было серьезной проблемой в то время. Изобретенный в том же 1984 г. алгоритм LZW был чрезвычайно популярен благодаря своей простоте, хорошей рекламе и нетребовательности к ресурсам, несмотря на относительно низкую степень сжатия. На сегодняшний день алгоритм РРМ является наилучшим алгоритмом для сжатия текстовой информации, a LZW давно уже не встраивается в новые приложения (однако широко используется в старых).
  • Будущее алгоритмов сжатия тесно связано с будущим компью-терных технологий. Современные алгоритмы уже вплотную приблизи-лись к Шенноновской оценке 1.3 бита на символ, но ученые не видят причин, по которым компьютер не может предсказывать лучше, чем человек. Для достижения высоких степеней сжатия приходится использовать более сложные алгоритмы. Однако существовавшее одно время предубеждение, что сложные алгоритмы с более высокой степенью сжатия всегда более медленны, несостоятельно. Так, существуют крайне быстрые реализации алгоритмов РРМ для текстовой информации и SPIHT для графики, имеющие очень высокую степень сжатия.
  • Таким образом, будущее за новыми алгоритмами с высокими требованиями к ресурсам и все более и более высокой степенью сжатия.
  • Устаревают не только алгоритмы, но и типы информации, на которые они ориентированы. Так, на смену графике с малым числом цветов и неформатированному тексту пришли высококачественные изображения и электронные документы в различных форматах. Известные алгоритмы не всегда эффективны на новых типах данных. Это делает крайне актуальной проблему синтеза новых алгоритмов.
  • Количество нужной человеку информации неуклонно растет. Объемы устройств для хранения данных и пропускная способность линий связи также растут. Однако количество информации растет быстрее. У этой проблемы есть три решения. Первое — ограничение количества информации. К сожалению, оно не всегда приемлемо. Например, для изображений это означает уменьшение разрешения, что приведет к потере мелких деталей и может сделать изображения вообще бесполезными (например, для медицинских или космических изображений). Второе — увеличение объема носителей информации и пропускной способности каналов связи. Это решение связано с материальными затратами, причем иногда весьма значительными. Третье решение — использование сжатия информации. Это решение позволяет в несколько раз сократить требования к объему устройств хранения данных и пропускной способности каналов связи без дополнительных издержек (за исключением издержек на реализацию алгоритмов сжатия). Условиями его применимости является избы-точность информации и возможность установки специального програм-много обеспечения либо аппаратуры как вблизи источника, так и вблизи приемника информации. Как правило, оба эти условия удовлетворяются.
  • Именно благодаря необходимости использования сжатия информации методы сжатия достаточно широко распространены. Однако существуют две серьезные проблемы. Во-первых, широко используемые методы сжатия, как правило, устарели и не обеспечивают достаточной степени сжатия. В то же время они встроены в большое количество программных продуктов и библиотек и поэтому будут использоваться еще достаточно долгое время. Второй проблемой является частое применение методов сжатия, не соответствующих характеру данных. Например, для сжатия графики широко используется алгоритм LZW, ориентированный на сжатие одномерной информации, например текста. Решение этих проблем позволяет резко повысить эффективность применения алгоритмов сжатия.
  • Таким образом, разработка и внедрение новых алгоритмов сжатия, а также правильное использование существующих позволит значительно сократить издержки на аппаратное обеспечение вычислительных систем.
  • При реализации алгоритма арифметического кодирования использовался язык C# и визуальная среда программирования Microsoft Visual Studio 2005. Язык C# имеет следующие преимущества: простота, объектная ориентированность, типовая защищенность, “сборка мусора”, поддержка совместимости версий, упрощение отладки программ.

Энтропия и количество информации

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

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

Комбинаторная, вероятностная и алгоритмическая оценка количества информации

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

Таким образом, для передачи состояния объекта достаточно I=log2N бит информации. Заметим, что количество информации может быть дробным. Разумеется, дробное количество информации невозможно сохранить на носителе или передать по каналам связи. В то же время, если необходимо передать либо сохранить большое количество блоков информации дробной длины, их всегда можно сгруппировать таким образом, чтобы полностью исключить потери (например, посредством арифметического кодирования).

Основным недостатком комбинаторного подхода является его ориентированность на системы с равновероятными состояниями. В реальном мире события, как правило, не равновероятны. Вероятностный подход к оценке количества информации, учитывающий этот фактор, является наиболее широко используемым на сегодняшний день. Пусть переменная х может принимать N значений хi с вероятностью р(хi). Тогда энтропия N

Обозначим через р(у|х) условную вероятность того, что наступит событие у если событие х уже наступило. В таком случае условная энтропия для переменной Y, которая может принимать М значений yi с условными вероятностями р(уi|х) будет

Приведенные формулы показывают, что вне зависимости от того, как были получены вероятности наступления следующих событий, для кодирования события с вероятностью р достаточно — log2 p бит (в полном соответствии с теоремой Шеннона об оптимальном кодировании).

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

Моделирование и кодирование

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

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

Некоторые алгоритмы сжатия данных

Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 г., но сам алгоритм разработан не позднее 1975 г.

Алгоритм LZ77 является родоначальником целого семейства словарных схем — так называемых алгоритмов со скользящим словарем, или скользящим окном. Действительно, в LZ77 в качестве словаря используется блок уже закодированной последовательности. Как правило, по мере выполнения обработки положение этого блока относительно начала последовательности постоянно меняется, словарь «скользит» по входному потоку данных.

Скользящее окно имеет длину N, т. е. в него помещается N символов, и состоит из двух частей:

¦ последовательности длины W=N-n уже закодированных символов, которая и является словарем;

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

Пусть к текущему моменту времени мы уже закодировали t символов S1, S2, . St. Тогда словарем будут являться W предшествующих символов St-(W-1), St-(W-1)+1, …, St. Соответственно, в буфере находятся ожидающие кодирования символы St+1, St+2, …, St+n. Очевидно, что если W? t, то словарем будет являться вся уже обработанная часть входной последовательности.

Идея алгоритма заключается в поиске самого длинного совпадения между строкой буфера, начинающейся с символа St+1, и всеми фразами словаря. Эти фразы могут начинаться с любого символа St-(W-1), St-(W-1)+1,…, St выходить за пределы словаря, вторгаясь в область буфера, но должны лежать в окне. Следовательно, фразы не могут начинаться с St+1. поэтому буфер не может сравниваться сам с собой. Длина совпадения не должна превышать размера буфера. Полученная в результате поиска фраза St-(i-1), St-(i-1)+1, …, St-(i-1)+(j-1) кодируется с помощью двух чисел:

1) смещения (offset) от начала буфера, i;

2) длины соответствия, или совпадения (match length), j;

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

Таким образом, на каждом шаге кодер выдает описание трех объектов: смещения и длины соответствия, образующих код фразы, равной обработанной строке буфера, и одного символа s (литерала). Затем окно смещается на j+1 символов вправо и осуществляется переход к новому циклу кодирования. Величина сдвига объясняется тем, что мы реально закодировали именно j+1 символов: j с помощью указателя на фразу в словаре и 1(? i) с помощью тривиального копирования. Передача одного символа в явном виде позволяет разрешить проблему обработки еще ни разу не виденных символов, но существенно увеличивает размер сжатого блока.

Алгоритм LZ78, предложенный в 1978 г. Лемпелом и Зивом, нашел свое практическое применение только после реализации LZW84, предложенной Велчем в 1984 г.

Словарь является расширяющимся (expanding). Первоначально в нем содержится только 256 строк длиной в одну букву-все коды ASCII. В процессе работы словарь разрастается до своего максимального объема |Vmax| строк (слов). Обычно, объем словаря достигает нескольких десятков тысяч слов. Каждая строка в словаре имеет свою известную длину и этим похожа на привычные нам книжные словари и отличается от строк LZ77, которые допускали использование подстрок. Таким образом, количество слов в словаре точно равно его текущему объему. В процессе работы словарь пополняется по следующему закону:

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позиции pos исходного текста. Так как словарь первоначально не пустой, такое слово всегда найдется;

2. В выходной файл помещается номер найденного слова в словаре position и следующий символ из входного текста В (на котором обнаружилось различие) —

. Длина кода равна |position|+|B||=[logVmax]+8 (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте pos смещается на |strB|=|str|+l байт дальше к символу, следующему за В.

В таком варианте алгоритм почти не нашел практического применения и был значительно модернизирован. Изменения коснулись принципов управления словарем (его расширения и обновления) и способа формирования выходного кода:

Птак как словарь увеличивается постепенно и одинаково для кодировщика и декодировщика, для кодирования позиции нет необходимости использовать [logVmax] бит, а можно брать лишь [logV] бит, где V-текущий объем словаря.

Самая серьезная проблема LZ78-переполнение словаря: если словарь полностью заполнен, прекращается его обновление и процесс сжатия может быть заметно ухудшен (метод FREEZE). Отсюда следует вывод-словарь нужно иногда обновлять. Самый простой способ как только словарь заполнился его полностью обновляют. Недостаток очевиден кодирование начинается на пустом месте, как бы с начала, и пока словарь не накопится сжатие будет незначительным, а дальше-замкнутый цикл опять очистка словаря. Поэтому предлагается словарь обновлять не сразу после его заполнения, а только после того, как степень сжатия начала падать (метод FLUSH). Более сложные алгоритмы используют два словаря, которые заполняются синхронно, но с задержкой на |V|/2 слов один относительно другого. После заполнения одного словаря, он очищается, а работа переключается на другой (метод SWAP). Еще более сложными являются эвристические методы обновления словарей в зависимости от частоты использования тех или иных слов (LRU, TAG).

Выходной код также формируется несколько иначе (сравните с предыдущим описанием):

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позицииpos исходного текста;

2. В выходной файл помещается номер найденного слова в словаре

. Длина кода равна |position|=[logV] (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте pos смещается на |str| байт дальше к символу В.

Алгоритм PPM (prediction by partial matching) — это метод контекстно-ограниченного моделирования, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Модели, в которых для оценки вероятности используются контексты длиной не более чем N, принято называть моделями порядка N.

Вероятность символа может быть оценена в контекстах разных порядков. Например, символ «о» в контексте «to be or not t» может быть оценен в контексте первого порядка «t», в контексте второго порядка «_t», в контексте третьего порядка «t_t» и т.д. Он также может быть оценен в контексте нулевого порядка, где вероятности символов не зависят от контекста, и в контексте минус первого порядка, где все символы равновероятны. Контекст минус первого порядка используется для того, чтобы исключить ситуацию, когда символ будет иметь нулевую вероятность и не сможет быть закодирован. Это может случиться, если вероятность символа не будет оценена ни в одном из контекстов (что возможно, если символ в них ранее не встречался).

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

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

BWT — преобразование и компрессор

BWT-компрессор (Преобразование Барроуза — Уиллера) — сравнительно новая и революционная техника для сжатия информации (в особенности-текстов), основанная на преобразовании, открытом в 1983 г. и описанная в 1994 г.. BWT является удивительным алгоритмом. Во-первых, необычно само преобразование, открытое в научной области, далекой от архиваторов. Во-вторых, даже зная BWT, не совсем ясно, как его применить к сжатию информации. В-третьих, BW преобразование чрезвычайно просто. И, наконец, сам BWT компрессор состоит из «магической» последовательности нескольких рассмотренных ранее алгоритмов и требует, поэтому, для своей реализации самых разнообразных программных навыков.

BWT не сжимает данные, но преобразует блок данных в формат, исключительно подходящий для компрессии. Рассмотрим его работу на упрощенном примере. Пусть имеется словарь V из N символов. Циклически переставляя символы в словаре влево, можно получить N различных строк длиной N каждая. В нашем примере словарь-это слово V=»БАРАБАН» и N=7. Отсортируем эти строки лексикографически и запишем одну под другой:

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

Фактический «выход» преобразования состоит из строки L=»РББАНАА» и первичного индекса I, показывающего, какой символ из L является действительным первым символом словаря V (в нашем случае I=2). Зная L и I можно восстановить строку V.

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

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

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

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

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

Допустим, у нас есть следующая таблица частот:

На первом шаге из листьев дерева выбираются два с наименьшими весами — Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5+6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д — ветви 1.

На следующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и В удаляются из списка свободных. После всего этого дерево кодирования выглядит так, как показано на рис. 2.

Рис. 2. Дерево кодирования Хаффмана после второго шага

На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д—ветви 1.

На последнем шаге в списке свободных осталось только два узла — это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис. 3.

Рис. 3. Окончательное дерево кодирования Хаффмана

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

Дня данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

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

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

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

Арифметическое сжатие — достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дроби, при этом строим дробь таким образом, чтобы наш текст был представлен как можно компактнее. Для примера рассмотрим построение такой дроби на интервале [0, 1) (0 — включается, 1 — нет). Интервал [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваем его на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов.

Пусть мы сжимаем текст «КОВ.КОРОВА» (что, очевидно, означает «коварная корова»). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны:

Илон Маск рекомендует:  Пять вещей, которые надо знать об HTML5
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL