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