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

Будем считать, что эта таблица известна в компрессоре и декомпрессоре. Кодирование заключается в уменьшении рабочего интервала. Для первого символа в качестве рабочего интервала берется [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).

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

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

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

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

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

Метод Зива-Лемпела

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

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

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

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

Алгоритм PPM

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

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

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

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

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

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

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

HUFF – реализация алгоритма Хаффмана. PPMC является одним из лучших контекстно-ограниченных методов моделирования. WORD - это контекстно-ограниченная модель, в которой вместо символов используются слова. DMC строит модели  с ограниченным числом состояний. MTF есть  метод новизны, применяющий схему move-to-front.

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

Необходимость применения сжатия

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

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

Дальнейшие исследования

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

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

Одним направлением для исследований является подгонка схем сжатия к отечественным языкам. Сегодняшние системы работают полностью на лексическом уровне. Использование больших словарей с синтаксической и семантической информацией может позволить машинам получить преимущество от имеющейся в тексте высокоуровневой связности. Однако необходимо иметь в виду, что очень большое количество слов обычного английского текста в обычном английском словаре может быть не найдено. Например, был проведён такой опыт: проверили 8 миллионов слов из «New York Times News Service» в словаре «Webster's Seventh New Collegiate Dictionary» и обнаружили, что в словаре отсутствовало почти 64% слов (грамматические формы слов, собственные существительные, слова, написанные через дефис, слова с орфографическими ошибками, неологизмы). Большинство словарей не содержат имен людей, названий мест, институтов, торговых марок и т.д., хотя они составляют основную часть почти всех документов. Поэтому, специальные алгоритмы сжатия, взятые в расчете на лингвистическую информацию более высокого уровня, будут несомненно зависеть от системной сферы. Вероятно, что поиски методов улучшения характеристик сжатия в данном направлении будут объединяться с исследованиями в области контекстуального анализа по таким проблемам как извлечение ключевых слов и автоматическое абстрагирование.

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

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

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

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

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