Ю. Дудоров
ПРОТОКОЛ СЖАТИЯ ДАННЫХ ДЛЯ МОДЕМОВ 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 означает отсутствие ссылки).

...

...

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

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

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