ПРОТОКОЛ СЖАТИЯ ДАННЫХ ДЛЯ МОДЕМОВ V.42bis
1. Введение
Среди терминов и магических понятий, окружающих пользователей
телефонных коммуникационных устройств, непременно встречается обоз-
начение какого-либо протокола сжатия информации. Так сложилось, что
публичной информации об этих функциональных возможностях модемов
несколько меньше, чем о других аспектах их использования. В значи-
тельной степени отсутствие публичной информации о двух наиболее ши-
роко распространенных стандартах этого класса - международном стан-
дарте CCITT (ныне ITU-T) V.42bis и промышленном стандарте MNP5 фирмы
Microcom - может объясняться их лицензионным характером. Производи-
тели модемов обязаны были (по крайней мере до недавнего времени) по-
купать у Microcom лицензию на право использования MNP5 (и более
старших уровней этого семейства протоколов), а патенты на реализацию
V.42bis принадлежат IBM и Unisys, несмотря на то, что алгоритм явля-
ется международным стандартом и опубликован CCITT. Данный материал
был задуман как справочная статья об этих протоколах и их сравнении
для широкого круга потребителей, а также как описание реализации
V.42bis в модемах серии AnCom(R) компании "Аналитик ТелекомСистемы".
Материал статьи разделен на слои по интересам читателя. Если Вас ин-
тересует только информация о том, что из себя представляют протоколы
сжатия при модемной передаче, Вы можете ограничиться Введением и
последней главой о сравнении протоколов. Если Вас интересует сам ал-
горитм V.42bis, его популярное изложение приведено в главе Как уст-
роен V.42bis. Ну и, наконец, если Вы читатель энциклопедического
склада и Вас интересуют тонкости мироустройства, то специально для
Вас глава Описание Реализации.
История вопроса
Во время работы над протоколом V.42, которая была завершена в
1988 году, исследовательская группа CCITT под экзотическим названием
XVII, пришла к выводу о необходимости включения процедуры сжатия в
модемы. Эта необходимость была обусловлена требованием увеличения
пропускной способности модема и предполагалось, что эта функциональ-
ная возможность будет расширением процедуры коррекции ошибок. Необ-
ходимо заметить, что разработка (или выбор существующего) алгоритма
сжатия для использования в модеме далеко не тривиальны. Дело в том,
что схема сжатия принципиально должна быть, во-первых, однопроходной
(где заканчивается сжимаемый поток просто неизвестно), во-вторых,
допускающей автоматическое поддержание идентичности управляющей ин-
формации на удаленном конце соединения (не передавать же словари,
индексы, таблицы частотности, либо что-то еще вместе со сжатым пото-
ком), и, наконец, в-третьих, эта схема должна быть алгоритмом реаль-
ного времени (реализация алгоритма должна успевать сжимать и расжи-
мать данные не медленнее, чем они передаются по каналу связи). Види-
мо, именно по этой причине было принято решение об использовании в
качестве базового варианта одного из существующих и использующихся в
модемах алгоритмов сжатия. Последовательно были исследованы алгорит-
мы BTLZ фирмы British Telecom, Hayes' System, MNP5 и MNP7 фирмы
Microcom, а также ACT Formula.
В конечном итоге был выбран алгоритм BTLZ, подвергнут опреде-
ленной переработке, и, в конце концов, наречен V.42bis. V.42bis не
был опубликован в Blue Book от 1988 года, однако, в результате ин-
тенсивной деятельности CCITT, был обнародован в виде отдельного до-
кумента, подписанного 31 января 1990 года. Документ содержит, кроме
стандартного для CCITT бюрократического вступления, весьма формали-
зованное и корректное определение используемых терминов, параметров
и режимов работы алгоритма, достаточно полное, непротиворечивое и
формальное описание функционирования, логическое описание используе-
мых структур и необходимых преобразований данных. Документ снабжен
ссылками на идеологические источники и "рядом расположенные" стан-
дарты (что любопытно - нет ссылки на BTLZ), формальным описанием
структур данных, используемых при согласовании параметров в процессе
установлении соединения между модемами, диаграммами (почти блок-схе-
мами), иллюстрирующими функционирование Передатчика (Приемник остав-
лен в качестве домашнего задания) и рекомендациями разработчикам. С
точки зрения авторов документа место стандарта (видимо, топологичес-
кое) в существующей идеологии взимодействия компонент модема может
быть проиллюстрировано диаграммой, изображенной на рис. 1.
В завершение необходимо заметить, что качество документа как
исходных спецификаций на разработку очень высоко.
Несколько слов о физической сущности сжатия
при модемной передаче
Практически все носители информации (знаки, символы), исполь-
зуемые компьютерами, представляют из себя фиксированное количество
бит, кодирующих этот знак. Кодовые таблицы (например, ASCII) разра-
ботаны в расчете на фиксированную битовую длину, так как это повыша-
ет машинную эффективность обработки данных. Во многих машинах ис-
пользуются коды, выравненные на границу октета (8 бит). Фиксирован-
ная длина символов означает, что все передаваемые символы - одинако-
вой длины, даже если частота их передачи различна. Например, при пе-
редаче этого текста существенно более часто будут встречаться симво-
лы, представляющие строчные кириллические буквы, нежели чем символы
прописных латинских букв. Такого рода практика приводит к значитель-
ным потенциальным потерям при передаче информации.
Один из наиболее часто применяемых подходов к решению этой
проблемы заключается в использовании кодов переменной длины для
представления символов постоянной длины. В таком случае наиболее
часто встречающиеся символы сжимаются - они представляются набором
бит, который короче, чем их традиционное битовое представление. Та-
кого рода технология может привести к значительному увеличению про-
пускной способности канала связи. Широко известный представитель ал-
горитмов этого типа - MNP5 фирмы Microcom.
V.42bis не заменяет конкретные, наиболее часто встречающиеся
символы на более короткие кодовые слова, а делает это для последова-
тельностей символов (строк). Алгоритм использует словарь для сохра-
нения наиболее часто встречающихся строк вместе с кодовыми словами,
которые их представляют. Словарь строится и модифицируется динами-
чески.
Размер словаря может быть различным, стандартизировано только
минимальное значение - 512 элементов (строк). Конкретное значение
выбирается обоими модемами при установлении соединения. Кроме того,
согласовывается максимальная длина строки, которая может быть сохра-
нена в словаре, в диапазоне от 6 до 250 символов. Пользователь дол-
жен представлять, что изменение этих параметров влияет на эффектив-
ность сжатия, причем это влияние и его направление зависит от харак-
тера передаваемых или принимаемых данных. Квазиоптимальные значения
этих параметров, рекомендации по результатам исследований этого ал-
горитма и способы влияния пользователя на функционирование V.42bis
будут кратко обсуждаться позже.
2. Как устроен V.42bis
Словарь может быть представлен как набор (лес) деревьев, в ко-
тором корню каждого дерева соответствует символ алфавита и, наобо-
рот, каждому символу соответствует дерево в словаре. Каждое дерево
представляет набор известных (уже встретившихся) строк, начинающихся
с символа, соответствующего корню. Каждый узел дерева соответствует
набору строк в словаре. И, наконец, каждый листьевой узел соответс-
твует одной известной строке. Так, набор деревьев на рис. 2 предс-
тавляет строки A, B, BA, BAG, BAR, BI, BIN, C, D, DE, DO и DOG.
Каждый листьевой узел - это узел, не имеющий подчиненных узлов
и фактически соответствующий последнему символу в строке. И наобо-
рот, узел, который не имеет родительского узла, соответствует перво-
му символу в строке.
В самом начале каждое дерево в словаре состоит только из кор-
невого узла, которому присвоено уникальное кодовое слово. По мере
поступления символов из присоединенного к модему терминала, выполня-
ется процедура отождествления накопленной (отождествленной) к преды-
дущему шагу строки и текущего символа [string-matching procedure].
Фактически эта процедура сводится к поиску строки, дополненной теку-
щим символом, в словаре. Эта процедура начинается с единственного
символа (и в этом случае всегда завершается успешно, так как в сло-
варе всегда есть односимвольные строки, соответствующие каждому сим-
волу алфавита). Если отождествленная на предыдущем шаге строка плюс
символ соответствует элементу словаря (найдена в нем), и этот эле-
мент не был создан при предыдущем выполнении процедуры отождествле-
ния строки (весьма важное, принципиальное и тонкое ограничение, поз-
воляющее Приемнику поддерживать адекватное состояние словаря в неко-
торых частных случаях комбинаций повторяющихся подстрок во входном
потоке), строка дополняется текущим символом и будет использована
при следующем вызове процедуры отождествления. Процесс продолжается
до тех пор, пока строка не достигает максимально возможной длины
(согласованной модемами при установлении соединения), либо дополнен-
ная строка не найдена в словаре, либо она была найдена, но этот эле-
мент был создан при предыдущем вызове. В этот момент, присоединенный
к строке символ удаляется из нее и называется "неотождествленным"
("unmatched"), строка кодируется кодовым словом, а на следующем шаге
будет состоять только из неотождествленного символа.
Во время процесса сжатия словарь динамически дополняется новы-
ми элементами (строками), которые соответствуют подстрокам, встреча-
ющимся в потоке данных. Новые строки образуются добавлением неотож-
дествленного символа к существующей строке, и это означает создание
нового узла дерева. Например, в случае, если текущая отождествленная
строка DO, а последнее переданное кодовое слово соответствовало
строке BA, появление символа T приводит к добавлению в словарь стро-
ки DOT (рис. 3). На следующем шаге текущая строка соответствует нео-
тождествленному символу T.
Словари должны быть модифицированы в обоих модемах (на переда-
ющей - Передатчик - и принимающей - Приемник - сторонах соединения).
Способ, и весьма простой способ, которым может осуществить Приемник
адекватную Передатчику модификацию словаря - одно из самых красивых
проявлений изящества алгоритма V.42bis. Важно понимать, что Передат-
чик всегда находится на один шаг (на одну строку) впереди Приемника
в цикле модификации словаря. Таким образом, в принимающем модеме
первый символ принятого кодового слова (который будет равен D) дол-
жен быть использован для модификации словаря Приемника. Приемник
V.42bis всегда полагает, что первый символ каждой строки (соответс-
твующей принятому кодовому слову) должен быть использован для допол-
нения предыдущей строки и создания нового элемента словаря. Состоя-
ние фрагмента словаря Приемника после приема кодового слова, соот-
ветствующего DO, при том, что предыдущее кодовое слово соответство-
вало строке BA, показано на рис. 4. Первый символ T следующего кодо-
вого слова, принятого Приемником, приведет его словарь к виду, изоб-
раженному на рис. 3.
В завершение краткого описания функционирования V.42bis необ-
ходимо заметить, что не все так просто, и стандарт определяет другие
режимы и ситуации функционирования алгоритма. К наиболее важным из
них относятся следующие.
- Определен механизм удаления элементов словаря при его переполне-
нии. На понятийном уровне он заключается в том, чтобы после создания
нового элемента удалить самый "старый" (по времени создания) листь-
евой элемент вне зависимости от частоты его использования. Кажущийся
недостаток - невозможность учесть частоту появления подстрок и не
удалять наиболее часто встречающиеся - косвенно парируется логикой
дополнения словаря: если в потоке данных часто встречаются те подс-
троки, которые уже есть в словаре, то новые элементы словаря созда-
ются редко и словарь медленно переполняется.
- Реализован механизм постепенного увеличения длины кодового сло-
ва. Для представления максимального номера элемента (строки) словаря
требуется 9 бит для словаря в 512 элементов, 10 - для словарей, со-
держащих до 1024 элементов, 11 - до 2048 элементов и так далее. Од-
нако, не все номера должны быть представлены максимальным количест-
вом бит, и этот механизм означает, что размер кодового слова увели-
чивается с 9 до максимального значения по мере заполнения словаря.
Это снижает накладные расходы на первоначальных этапах.
- Существуют два режима работы Передатчика: Прозрачный и режим
Сжатия. Режим Сжатия в основном был описан выше, Прозрачный режим
отличается от него тем, что передача кодовых слов не осуществляется,
а каждый приходящий на вход Передатчика символ транслируется в линию
и далее в Приемник. Понятно для чего нужен Прозрачный режим - если
на вход Передатчика поступают хорошо перемешанный (в статистическом
смысле) поток символов, то высока вероятность, что каждый следующий
символ будет "неотождествленным" (такая же ситуация существует сразу
после инициализации словаря - он еще пуст). На каждый принятый и
"неотождествленный" символ на выход передается кодовое слово, длина
символа, как правило, 8 бит (здесь и далее предполагается, что сим-
волы представляют из себя октеты, хотя стандарт и допускает реализа-
цию на нетрадиционных аппаратных средствах), минимальная длина кодо-
вого слова - 9 бит, а вывод очень прост: в таком случает эффектив-
ность сжатия будет отрицательной, и потери могут достигать десятков
процентов.
- Стандарт предписывает, что реализация V.42bis должна поддержи-
вать кроме запроса на обработку поступающего из DTE символа, еще три
функции: запрос на переинициализацию словарей, запрос на сброс на-
копленных, но не переданных в линию данных (Flush) и запрос на оцен-
ку эффективности сжатия.
- Запрос на переинициализацию может быть выработан Управляющей
функцией V.42 по внешним причинам, либо связан с неэффективностью
сжатия на текущем словаре и попыткой начать "новую жизнь".
- Необходимость и своевременность выдачи Flush не фиксируется в
стандарте, однако понятно, что он должен вырабатываться по крайней
мере по истечении определенного тайм-аута (в случае пользователя,
работающего в терминальном режиме и не обладающего скорострельностью
профессиональной машинистки). Для Передатчика это означает, в част-
ности, что должна быть принудительно завершена процедура отождест-
вления строки. Это должно быть сделано так, чтобы адекватные дейс-
твия предпринял Приемник, что приводит к тому, что процедура обра-
ботки следующего символа должна быть модифицирована, что в свою оче-
редь изящно именуется Процедурой Обработки Символа в условиях Исклю-
чения.
- Запрос на оценку эффективности сжатия означает необходимость ре-
ализации важнейшего свойства алгоритма - попытку эффективно переклю-
чаться из Прозрачного режима в режим Сжатия и наоборот в зависимости
от передаваемых данных. Нужно учитывать, что это действительно необ-
ходимость - неэффективное переключение может изменять степень сжатия
на десятки и даже сотни процентов, кроме того само переключение оз-
начает накладные расходы на передачу управляющих данных. Пикантность
ситуации заключается в том, что стандарт не определяет саму процеду-
ру оценки эффективности сжатия и, соответственно, моменты, в которые
необходимо или возможно переключение. Фигурально говоря, соответс-
твующее положение стандарта предписывает переключаться в режим Сжа-
тия тогда, когда предшествующие данные (которые уже переданы и не
могут быть сжаты задним числом) могли бы быть сжаты, и переключаться
в Прозрачный режим когда уже сжатые и переданные предшествующие дан-
ные были сжаты плохо (то есть с отрицательной эффективностью). С од-
ной стороны, авторов алгоритма (или скорее авторов стандарта) можно
понять - передаваемые через модем данные неизвестны и сформулировать
оптимальные в глобальном смысле условия переключения, видимо, далеко
не тривиальная задача. Кроме того, это не влияет на совместимость
реализаций, использующих разные механизмы переключения - Приемник не
чувствует различий в этом механизме. Такая формулировка стандарта
допускает полностью корректные, но в то же время абсурдные крайности
- реализацию V.42bis, которая никогда не переключается в режим Сжа-
тия и "сжимает" с эффективностью 1:1 или реализацию, которая всегда
работает в режиме Сжатия и часто "сжимает" с эффективностью более
100%.
ПРИМЕЧАНИЕ. Обозначение типа 1:1 оценки эффективности сжатия поче-
му-то является почти общепринятым. Мне представляется более ра-
зумным (видимо по причине большего интереса к более мелким дета-
лям) использовать далее по тексту оценку в виде процентной доли
объема сжатого потока к объему первоначального. Таким образом,
каноническое (и неправильное) представление об эффективности сжа-
тия V.42bis 4:1 будет представляться как 25%, а сравнительные
оценки - ухудшение сжатия на 10 процентов - будут означать отно-
сительное изменение этой доли - до 35%.
Этот факт может наводить на мысль о том, что идеи Хайека о по-
лезности конкуренции впитываются при определенном воспитании с моло-
ком матери, и механизмы создания конкурентной борьбы появляются ав-
томатически (если это конечно не грозит экономическим интересам соз-
дателя). В данном случае все обстоит именно так - авторы стандарта
развязали руки тем, кто занимается его реализацией в позиции, кото-
рую можно назвать ключевой с точки зрения потребительских свойств
модема, поддерживающего сжатие данных. "Аналитик ТелекомСистемы" в
своей реализации V.42bis в модемах серии AnCom(R) включился в конку-
рентную борьбу и реализовал собственный, оптимальный в локальном
смысле, механизм переключения. Он будет кратко изложен ниже.
3. Описание реализации
Структуры данных
Ключевым вопросом реализации является организация словарей,
обеспечивающая быстрое отождествление (поиск в словаре) накопленной
строки и текущего символа, а также эффективную модификацию словаря
(добавление новой строки и освобождение элемента при переполнении
словаря). British Telecom предложила в свое время схему представле-
ния деревьев в словаре, которая получила название TRIE. На рис. 5
представлено условное изображение набора элементов из предыдущих
примеров для корневого узла D.
В соответствии со схемой TRIE словарь представляет из себя
массив однородных элементов. Каждый элемент соответствует набору
строк (или одной строке для листьевого элемента), хранящихся в сло-
варе и состоит из:
- поля символа,
- ссылки на предшествующий символ в строке (ссылка вверх на
предшественника - Родителя), если этот символ не первый,
- ссылки на последующий символ в строке (ссылка вниз на после-
дователя - Наследника), если этот символ не последний в
строке,
- ссылки на другое возможное продолжение строки, имеющей такое
же начало, как и текущая строка (ссылка вправо на Брата) и
- значения кодового слова, соответствующего элементу словаря.
Структура массива, соответствующего рис. 5, приведена ниже (Null оз-
начает отсутствие ссылки).
---------T----------T-----------T------T---------------¬
¦ Символ ¦ Родитель ¦ Наследник ¦ Брат ¦ Кодовое слово ¦
L--------+----------+-----------+------+----------------
...
---------T----------T-----------T------T---------------¬
¦ D ¦ Null ¦ E ¦ Null ¦ 71 ¦
L--------+----------+-----------+------+----------------
...
---------T----------T-----------T------T---------------¬
¦ E ¦ D ¦ Null ¦ O ¦ 311 ¦
¦ O ¦ D ¦ T ¦ Null ¦ 312 ¦
¦ T ¦ O ¦ Null ¦ G ¦ 313 ¦
¦ G ¦ O ¦ Null ¦ Null ¦ 314 ¦
L--------+----------+-----------+------+----------------
...
Текущая строка представляется номером элемента в массиве,
отождествление текущей строки, дополненной очередным символом, про-
изводится просмотром цепочки элементов, соединенных ссылкой вправо,
а ссылка на эту цепочку есть ссылка на потомка (вниз) от текущей
строки. Удаление строки (листьевого элемента) естественным образом
реализуется удалением элемента из цепочки братьев с корректировкой
ссылок вправо и, возможно, ссылки вниз родителя цепочки.
V.42bis от "Аналитик ТелекомСистемы" идеологически соответс-
твует TRIE, однако отличается на уровне реализации, что преследовало
целью уменьшение требований по памяти под словари и увеличение ско-
рости доступа.
Влияние параметров V.42bis на эффективность,
их оптимальные значения
Параметры V.42bis, согласуемые в процессе установления соеди-
нения между модемами, оказывают значительное воздействие на эффек-
тивность функционирования протокола сжатия и, следовательно, на про-
пускную способность канала. Заводские установки параметров, как пра-
вило, наиболее универсальны и различаются лишь в зависимости от сто-
имости модема (объема установленной памяти) и пристрастий системных
интеграторов (напомним, что V.42bis, как правило, никто не разраба-
тывает, а лишь использует готовую лицензированную реализацию). Одна-
ко, представление о смысле этих параметров и их влиянии может быть
полезно для настройки конкретных сеансов связи.
При установлении соединения согласовываются три параметра:
направление сжатия, размер словаря и максимальная длина строки.
Направление сжатия задает комбинацию использования или неис-
пользования протокола сжатия в каждом из направлений (от вызывающего
модема к отвечающему и от отвечающего к вызывающему). С одной сторо-
ны, наличие сжатия никогда никому не мешало (при условии, разумеет-
ся, корректной реализации), однако возможность запрета сжатия по
конкретному направлению представляет собой достаточно тонкий инстру-
мент, особенно, если этот запрет позволяет увеличить размер словаря
для сжатия по оставшемуся направлению. Это ниоткуда не следует и
должно быть проверено на конкретной модели модема, однако вполне ес-
тественно и возможно.
Размер словаря определяет количество найденных в потоке и сох-
раняющихся для отождествления подстрок, включая 256 односимвольных
строк и 3 несуществующих элемента для зарезервированных кодовых
слов. Минимальный размер словаря - 512 элементов, максимальный - не
ограничен. Увеличение размера словаря увеличивает количество подс-
трок, которые могут быть отождествлены (и, соответственно, заменены
кодовыми словами, то есть сжаты), однако это увеличивает максималь-
ную длину кодового слова (то есть снижает эффективность сжатия). В
самом тексте стандарта, в разделе рекомендаций разработчикам, ут-
верждается, что существуют данные, для которых наибольшая эффектив-
ность может быть достигнута на меньшем размере словаря. Кроме этого,
там же утверждается, что изменение размера словаря в диапазоне от
2**n + 1 до 1.3 * 2**n не приводит к каким либо значимым улучшениям
по сравнению со значением 2n. Там же утверждается, что значение 2048
элементов является хорошим компромиссом при выборе размера словаря
и, соответственно, размера кодового слова. Эта рекомендация, похоже,
основана на серьезных исследованиях алгоритма и обычно принимается
на веру всеми производителями модемов, если они по каким-либо причи-
нам не экономят оперативную память.
Максимальный размер строки согласовывается модемами как мини-
мальный из того, что они предпочитают, в диапазоне от 6 до 250 сим-
волов включительно. Обычное предпочитаемое значение - 16 или 32 сим-
вола. Удачно выбранное значение может значительно изменить степень
сжатия для определенных потоков и, если есть информация о характере
данных, которые будут передаваться, время, потраченное на выбор это-
го параметра, вполне может окупиться. Если в передаваемых данных
встречаются длинные повторяющиеся подстроки, выбор длины максималь-
ной строки не меньшей, чем их длина, приведет к значительному выиг-
рышу, и наоборот, в хорошо перемешанном потоке уменьшение максималь-
ной длины строки может (далеко не всегда) увеличивать количество
хранящихся в словаре подстрок.
Этот уровень настройки реализуется через соответствующие
AT-команды и доступен в большинстве модемов. Следующие два раздела
посвящены внутренним аспектам, влияющим на эффективность сжатия в
алгоритме V.42bis и соответствующей реализации в модемах AnCom(R).
Влияние качества переключения
Алгоритм сжатия, стандартизованный документом CCITT V.42bis,
обладает уникальной особенностью: для снижения потерь при сжатии
"несжимаемого" потока он обладает возможностью работать в Прозрачном
режиме (когда словарь продолжает отслеживать входной поток, однако
встречающиеся подстроки не заменяются кодовыми словами), однако не
предписывает, когда же Передатчик должен переключиться в режим Сжа-
тия для выполнения своей основной функции. Как уже упоминалось выше,
рекомендация о моменте переключения в стандарте носит апостериорный
характер: она основана на анализе данных, которые уже прошли через
Передатчик, а из этого следует, что принятое решение может быть и
неправильным, так как Передатчик не знает какие символы будут посту-
пать ему на вход после этого. Кроме того, само переключение означает
накладные расходы (включение в выходной поток команд переключения),
так что Передатчик должен быть достаточно консервативен в этом смыс-
ле. Основным недостатком такого подхода для пользователя является
возможное "отрицательное сжатие", например при передаче хорошо сжа-
тых файлов. Однако такой подход вполне возможен и условно может быть
назван Стандартной Реализацией, полностью соответствующей букве
CCITT V.42bis.
В Стандартной Реализации Передатчик должен после попытки отож-
дествления каждого символа модифицировать значение некоторой Функции
Качества, по значениям которой и принимаются решения о переключени-
ях. В Стандартной Реализации модемов AnCom(R) Функцией Качества яв-
ляется разность между количеством бит, переданных на выход (включая
служебные команды, извещающие Приемник о переключениях и других осо-
бых ситуациях), и количеством бит всех принятых со входа октетов.
Передатчик может находится в Прозрачном режиме и передавать октеты
на выход "как есть", однако Функция Качества подсчитывается так, как
будто бы Передатчик всегда находится в режиме Сжатия. Если функция
качества становится положительной, это означает, что эффективнее
применение Прозрачного режима (на выход передается больше чем прини-
мается), в противном случае полезнее работать в режиме Сжатия. Если
Функция Качества снижается ниже некоторого отрицательного порога -
порога переключения в режим Сжатия (его абсолютное значение должно
как-то интуитивно соотносится со стоимостью переключения в режим
Сжатия) - Передатчик принимает решение о переключении. Аналогично,
если Функция Качества превышает некоторый положительный порог - по-
рог переключения в Прозрачный режим - Передатчик переключается в
Прозрачный режим (рис. 6). Кроме того, выше порога переключения в
Прозрачный режим лежит уровень положительной поддержки на котором
фиксируются слишком большие положительные значения Функции Качества,
ниже уровня порога переключения в режим Сжатия находится уровень
фиксации слишком маленьких отрицательных значений Функции Качества.
Уровни поддержки или фиксации необходимы для обеспечения быстрого
переключения при резких изменениях свойств входного потока при сох-
ранении определенного консерватизма Передатчика (чтобы не слишком
переключался).
Напомним, что решение о переключении принимается на основе
анализа свойств потока данных, которые уже прошли через Передатчик и
переданы в линию и которые могут коррелироваться, а могут и не кор-
релироваться с продолжением потока, а следовательно получить значе-
ние порогов переключения и уровней фиксации аналитическим путем
весьма затруднительно или невозможно. В Стандартной Реализации моде-
ма AnCom(R) эти значения были определены путем моделирования на дос-
таточно представительной группе файлов, существующих в среде MS DOS
(табл. 1) и потенциально доступны для настройки пользователем через
AT-команды.
Smart-реализация
Возможно построение механизма оптимального (при отсутствии ис-
ключительных ситуаций) переключения Передатчика между Прозрачным ре-
жимом и режимом Сжатия. Эта реализация в модеме AnCom(R) условно
названа Smart-реализацией. Основная идея заключается в том, чтобы
буферизовать (в Smart-буфере) поступающие на вход символы, вычислять
соответствующие значения Функции Качества и принимать решения о пе-
реключениях (или непереключениях) только тогда, когда это либо заве-
домо правильно, либо наступают непредсказуемые события (Flush или
переполнение Smart-буфера). Таким образом, решение о работе в соот-
ветствующем режиме (и необходимые переключения) выполняются перед
выдачей тех данных, для которых это оптимально, а не после их выда-
чи, как в Стандартной Реализации.
Основная проблема непосредственно вытекает из основной идеи.
Словарь и текущая строка должны модифицироваться после прихода каж-
дого символа, однако уже упоминалось, что характер этих модификаций
может быть различным в зависимости от того, было ли принято на пре-
дыдущем шаге решение о переключении (ситуация Исключения). Однако,
можно строго показать, что если переключения будут выполняться "зад-
ним числом" не в произвольном месте, а перед приходом символа, за-
вершающего процесс отождествления (unmatched-символ), то будет дос-
тигнута эквивалентность косвенных эффектов процессов обработки сим-
вола в обычной ситуации и ситуации Исключения. Эти точки названы
точками вероятного переключения. Smart-буфер должен быть несколько
больше, чем текущая максимальная длина строки, так чтобы в нем могло
оказаться как минимум две точки вероятного переключения (одна из них
в начале Smart-буфера). Элемент буфера содержит:
- входной символ (который будет передан на выход, если в мо-
мент разгрузки буфера будет установлен Прозрачный режим),
- кодовое слово для отождествленной строки либо 0, если это не
unmatched-символ (это кодовое слово будет передано на выход,
если в момент разгрузки буфера будет установлен режим Сжа-
тия) и
- текущее значение Функции Качества.
Строго определены (в математическом смысле) пороги Гарантиро-
ванного переключения, при достижении которых Функцией Качества га-
рантировано оправдано переключение из режима в режим. Из вероятност-
ных соображений определены пороги полезного переключения для случаев
требований на разгрузку всех накопленных Передатчиком данных (Flush)
или переполнения буфера. Кстати, переполнение буфера возможно только
в случаях, когда Функция Качества достаточно долго колеблется в уз-
ком коридоре между порогами Гарантированного переключения, а это
подходящий случай для того, чтобы задуматься об одновременной переи-
нициализации словарей Передатчика и Приемника. Выработать такой же
четкий критерий в Стандартной реализации весьма затруднительно.
Подведем итоги. Эффективность сжатия в Smart-реализации почти
всегда выше и никогда не хуже, чем в Стандартной Реализации. Хотя
алгоритм функционирования Передатчика и не соответствует описанию в
тексте V.42bis, однако Smart-реализация остается полностью совмести-
мой с корректной Стандартной Реализацией любого производителя. И хо-
тя в большинстве случаев помеховая обстановка оказывает большее вли-
яние на скорость передачи, чем эффективность переключения режимов в
V.42bis, использование Smart-реализации все-таки представляется ос-
мысленным.
4. Качественные и количественные характеристики
протоколов сжатия
Представляет определенный интерес обсуждение сравнительных ха-
рактеристик V.42bis и наиболее распространенного протокола сжатия
фирмы Microcom MNP5, как по их количественной способности сжимать
передаваемые данные, так и различий в алгоритмах. Существует расп-
ространенное и ошибочное мнение об эффективности MNP5 как 2:1 (50%)
и V.42bis как 4:1 (25%). Это пагубное заблуждение создано, видимо,
вполне добросовестными авторами в условиях отсутствия информации о
стандарте и его лицензированных и защищаемых патентами реализациях.
Такая ситуация мешает большинству потребителей иметь достоверное
представление о своих инвестициях в аппаратные средства и способах
решения возникающих проблем. На самом деле, в соответствии с одним
из немногих толкований V.42bis сжатие по нему на 20-30% эффективнее,
чем сжатие по MNP5 и на 5-10% эффективнее, чем по MNP7. Это также
подтверждается результатами испытаний реализаций V.42bis в модемах
AnCom(R) и некоторых других моделях модемов. Испытания проводились
на реальной достаточно чистой (незашумленной) телефонной линии, а
также на модельной реализации AnCom(R) (имитация идеального случая).
Приведенные в табл. 1 цифры должны рассматриваться как иллюстратив-
ный материал и, в основном, они характеризуют влияние характера пе-
редаваемых данных на возможную степень сжатия.
Таблица 1
-------------T-------T-----------------------------------T-------¬
¦ ¦ ¦ ¦ Hayes ¦
¦ ¦ ¦ AnCom(R) ST-2442 ¦ Smart ¦
¦ ¦ ¦ ¦ modem ¦
¦ ¦ +-------T-------T---------T---------+-------+
¦ Файлы ¦Размер ¦Пропус-¦Пропус-¦ Коэфф. ¦Модельный¦Пропус-¦
¦ разного ¦файла в¦кная ¦кная ¦увеличен.¦коэфф. ¦кная ¦
¦ типа ¦байтах ¦способ-¦способ-¦пропускн.¦увеличен.¦способ-¦
¦ ¦ ¦ность ¦ность ¦способн. ¦пропускн.¦ность ¦
¦ ¦ ¦ MNP 5 ¦V.42bis¦ V.42bis ¦способн. ¦V.42bis¦
¦ ¦ ¦(в cps)¦2048/32¦ ¦ ¦2048/32¦
¦============+=======+=======+=======+=========+=========+=======¦
¦`abcd ¦ 31680 ¦ 609 ¦ 960 ¦ 3.15 ¦ 25.64 ¦ 931 ¦
¦ambassai.ttf¦ 40476 ¦ 385 ¦ 355 ¦ 1.23 ¦ 1.47 ¦ 381 ¦
¦ancom.tif ¦ 58561 ¦ 266 ¦ 261 ¦ 0.93 ¦ 1.00 ¦ 266 ¦
¦owner.dbf ¦ 45435 ¦ 946 ¦ 744 ¦ 2.51 ¦ 4.69 ¦ 857 ¦
¦emm386.arj ¦ 37515 ¦ 264 ¦ 267 ¦ 0.93 ¦ 1.00 ¦ 264 ¦
¦gorilla.bas ¦ 29434 ¦ 452 ¦ 600 ¦ 1.96 ¦ 2.08 ¦ 555 ¦
¦io.sys ¦ 33430 ¦ 388 ¦ 321 ¦ 1.09 ¦ 1.31 ¦ 348 ¦
¦graphics.doc¦ 29508 ¦ 461 ¦ 590 ¦ 1.96 ¦ 1.98 ¦ 536 ¦
¦mtez.dir ¦ 37000 ¦ 949 ¦ 822 ¦ 2.74 ¦ 14.71 ¦ 925 ¦
¦tartan.bmp ¦ 32886 ¦ 764 ¦ 747 ¦ 3.11 ¦ 12.05 ¦ 747 ¦
¦wword20.inf ¦ 51029 ¦ 432 ¦ 750 ¦ 2.53 ¦ 2.56 ¦ 671 ¦
L------------+-------+-------+-------+---------+---------+--------
Оба алгоритма используют адаптивную технологию замены опреде-
ленной входной последовательности на выходную битовую последователь-
ность. V.42bis кодирует последовательность символов кодовым словом
постепенно нарастающего и всегда большего, чем длина символа, разме-
ра. MNP5 устраняет длинные последовательности одинаковых символов
конструкцией со счетчиком повторения и затем кодирует отдельные сим-
волы в соответствии с частотой их повторения кодовыми словами пере-
менной длины. Кодовые слова могут быть короче длины символа для час-
то повторяющихся символов и длиннее в противном случае. MNP5 не оп-
ределяет Прозрачного режима, и, следовательно, возможны ситуации,
приводящие к значительному расширению выходного потока. В случае
корректной реализации V.42bis это практически невозможно, кроме того
V.42bis поддерживает возможность переинициализации словарей, что
позволяет алгоритму лучше адаптироваться к хорошо перемешанному по-
току. Несомненным преимуществом V.42bis является возможность пара-
метризации протокола, что позволяет создавать более гибкие реализа-
ции. Кроме того, возможность настройки или самонастройки алгоритма
проявляется хотя бы в возможности постепенного увеличения длины ис-
пользуемого кодового слова V.42bis. Это сравнение носит в основном
аналитический характер. Вывод о перспективности использования
V.42bis как международного стандарта (в отличие от промышленного
стандарта, каковым является MNP5 и даже его более мощное расширение
MNP7) всеми осознан и не оспаривается. Хотя, необходимо отметить,
что существуют приложения, на которых преимущества V.42bis могут
быть и не очевидны.
Библиография
1. CCITT Recommendation V.42bis: "Data compression procedures for
DCE's using error correcting procedures".
2. Uyless Black "The V Series Recommendations", McGraw Hill, Inc.,
1991.
3. Hayek F.A. "Individualism and economic order", London:
Routledge & Kegan Poul, Ltd., 1948.
Юрий Дyдоров
НПП "Аналитик ТС"
тел/факс: (095) 490-0713/0799
postmaster@analytic.msk.ru
2:5020/200.12
|