Структуры данных
Ключевым вопросом реализации является организация словарей,
обеспечивающая быстрое отождествление (поиск в словаре) накопленной
строки и текущего символа, а также эффективную модификацию словаря
(добавление новой строки и освобождение элемента при переполнении
словаря). British Telecom предложила в свое время схему представле-
ния деревьев в словаре, которая получила название TRIE. На рис. 5
представлено условное изображение набора элементов из предыдущих
примеров для корневого узла D.
В соответствии со схемой TRIE словарь представляет из себя
массив однородных элементов. Каждый элемент соответствует набору
строк (или одной строке для листьевого элемента), хранящихся в сло-
варе и состоит из:
- поля символа,
- ссылки на предшествующий символ в строке (ссылка вверх на
предшественника - Родителя), если этот символ не первый,
- ссылки на последующий символ в строке (ссылка вниз на после-
дователя - Наследника), если этот символ не последний в
строке,
- ссылки на другое возможное продолжение строки, имеющей такое
же начало, как и текущая строка (ссылка вправо на Брата) и
- значения кодового слова, соответствующего элементу словаря.
Структура массива, соответствующего рис. 5, приведена ниже (Null оз-
начает отсутствие ссылки).
+--------+----------+-----------+------+---------------+
| Символ | Родитель | Наследник | Брат | Кодовое слово |
+--------+----------+-----------+------+---------------+
...
+--------+----------+-----------+------+---------------+
| D | Null | E | Null | 71 |
+--------+----------+-----------+------+---------------+
...
+--------+----------+-----------+------+---------------+
| E | D | Null | O | 311 |
| O | D | T | Null | 312 |
| T | O | Null | G | 313 |
| G | O | Null | Null | 314 |
+--------+----------+-----------+------+---------------+
...
Текущая строка представляется номером элемента в массиве,
отождествление текущей строки, дополненной очередным символом, про-
изводится просмотром цепочки элементов, соединенных ссылкой вправо,
а ссылка на эту цепочку есть ссылка на потомка (вниз) от текущей
строки. Удаление строки (листьевого элемента) естественным образом
реализуется удалением элемента из цепочки братьев с корректировкой
ссылок вправо и, возможно, ссылки вниз родителя цепочки.
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-реализации все-таки представляется ос-
мысленным.
|
