Галкин В.А., Григорьев Ю.А. - Телекоммуникации и сети (1053870), страница 23
Текст из файла (страница 23)
Протокол использует словарь для хранения наиболее частовстречающихся строк вместе с кодовыми словами, которые их представляют.Словарь строится и модифицируется динамически. Размер словаря может бытьразличным, стандартизировано только минимальное значение - 512 элементов(строк). Конкретное значение выбирается обоими модемами при установлениисоединения. Кроме того, согласовывается максимальная длина строки, которая может быть сохранена в словаре, в диапазоне от 6 до 250 CHMBOJIOB.Словарь может быть представлен как набор деревьев, в котором корнюкаждого дерева соответствует символ алфавита и, наоборот, каждому символу соответствует дерево в словаре. Каждое дерево представляет набор известных (уже встретившихся) строк, начинающихся с символа, соответствующегокорню.
Каждый узел дерева соответствует набору строк в словаре, а каждыйлистьевой узел соответствует одной известной строке. Набор деревьев представленный на рис. 2.16, представляет строки А, AN, ANGEL, AND, В, С, С А,CAR, CACHE, D, Е. Каждый листьевой узел не имеет подчиненных узлов ифактически соответствует последнему символу в строке. И наоборот, узел,который не имеет родительского узла, соответствует первому символу в строке.
В самом начале каждое дерево в словаре состоит только из корневого узла.1032, Основы телекоммуникациикоторому присвоено уникальное кодовое слово. По мере поступления символовиз присоединенного к модему терминала, вьшолняется процедура отождествления накопленной (отождествленной) к предьщущему шагу строки и текущего символа (string-matcMng ргоседш"е). Фактически эта процедура сводится кпоиску строки, дополненной текущим символом, в словаре. Она начинается сединственного символа (и в этом случае всегда завершается успешно, так какв словаре всегда есть односимвольные строки, соответствующие каждомусимволу алфавита).
Если отождествленная на предьщущем шаге строка плюссимвол соответствует элементу словаря (найдена в нем), и этот элемент небьш создан при предьщущем выполнении процедуры отождествления строки(весьма важное, принципиальное и тонкое ограничение, позволяющее приемнику поддерживать адекватное состояние словаря в некоторых частных случаяхкомбинаций повторяющихся подстрок во входном потоке), строка дополняетсятекущим символом и будет использована при следующем вызове процедурыотождествления.
Процесс продолжается до тех пор, пока строка не достигнетмаксимально возможной длины (согласованной модемами при установлениисоединения), либо дополненная строка не найдена в словаре, либо она быланайдена, но этот элемент бьш создан при предьщущем вызове. В этом случае,присоединенный к строке символ удаляется из нее и называется «неотождествленным» (unmatched), строка кодируется кодовым словом, а на следующемшаге будет состоять только из неотождествленного символа.
Во время процесса сжатия словарь динамически дополняется новыми элементами (строками), которые соответствуют подстрокам, встречающимся в потоке данных.Новые строки образуются добавлением неотождествленного символа к существующей строке, что означает создание нового узла дерева. Например, в случае, если текущая отождествленная строка С4, а последнее переданное кодовое слово соответствовало строке AN^ появление символа Т приводит кдобавлению в словарь строки CAT (рис.
2.17). На следующем шаге текущаястрока соответствует неотождествленному символу Г.Словари должны бьггь модифицированы в обоих модемах: на передающей(передатчик) и принимающей (приемник) сторонах соединения. Важно понимать, что передатчик всегда находится на один шаг (на одну строку) впередиприемника в цикле модификации словаря. Таким образом, в принимающеммодеме первый символ принятого кодового слова (который будет равен С) должен быть использован для модификации словаря приемника. Приемник V.42bisвсегда полагает, что первый символ каждой строки (соответствующей принятому кодовому слову) должен быть использован для дополнения предьщущейстроки и создания нового элемента словаря. Состояние фрагмента словаряприемника после приема кодового слова, соответствующего СА, при том, чтопредьщущее кодовое слово соответствовало строке AN, показано на рис.
2.18.При приеме приемником первого символа Т следующего кодового слова егословарь будет иметь вид, изображенный на рис. 2.17.1042.2. Методы защиты от ошибок и сжатия данныхКорневые узлы© ©Рис. 2.17. Изменения в части словаря передатчика после последовательногополучения от терминала символов А, N, С, А и ТКорневые узлы© ©Рис. 2.18. Изменения в части словаря приемника после последовательногополучения кодовых слов, соответствуюпщх строкам AN и САВ протоколе сжатия V.42bis реализованы и другие возможности. К наиболееважным из которых относятся следующие.1.
Определен механизм удаления элементов словаря при его переполнении.На понятийном уровне он заключается в том, чтобы после создания новогоэлемента удалить самый «старый» (по времени создания) листьевой элементвне зависимости от частоты его использования. Кажущийся недостаток - не1052. Основы телекоммуникацииВОЗМОЖНОСТЬ учесть частоту появления подстрок и не удалять наиболее частовстречающиеся - частично устраняется логикой дополнения словаря: если впотоке данных часто встречаются подстроки, которые уже есть в словаре, тоновые элементы словаря создаются редко и словарь медленно переполняется.2. Реализован механизм постепенного увеличершя длины кодового слова.Для представления максимального номера элемента (строки) словаря требуется 9 бит для словаря в 512 элементов, 10 - для словарей, содержащих до1024 элементов, 11 - до 2048 элементов и т.
д. Однако не все номера должныбыть представлены максимальным количеством бит, и этот механизм означает, что размер кодового слова увеличивается с 9 до максимального значенияпо мере заполнения словаря. Это снижает накладные расходы на первоначальных этапах.3. Существуют два режима работы передатчика: Прозрачный и режим Сжатия. Режим Сжатия описан выше. Прозрачный режим отличается от него тем,что передача кодовых слов не осуществляется, а каждый приходящий на входпередатчика символ транслируется в линию и далее в приемник. Если на входпередатчика поступают хорошо перемешанный (в статистическом смысле)поток символов, то высока вероятность, что каждый следующий символ будет«неотождествленным» (такая же ситуация складывается сразу после ишпщализации словаря - он еще пуст). На каждый принятый и «неотождествленный»символ на выход передается кодовое слово. Длина символа, как правило, 8 бит(здесь и далее предполагается, что символы представляют из себя октеты,хотя стандарт и допускает реализацию на нетрадиционных аппаратных средствах), минимальная длина кодового слова - 9 бит.
В этом случа эффективность сжатия будет отрицательной, и потери могут составлять десятки процентов.Сравнивая качественные и количественные характеристики протоколов сжатия V.42bis и Microcom MNP5, следует отметить, что оба алгоритма используют адаптивную технологию замеш>1 определенной входной последовательности на выходную битовую последовательность. Протокол V.42bis кодируетпоследовательность символов кодовым словом постепенно нарастающего ивсегда большего, чем длина символа, размера. Протокол MNP5 устраняет длинные последовательности одинаковых символов конструкцией со счетчиком повторения и затем кодирует отдельные символы в соответствии с частотой ихповторения кодовыми словами переменной длины. Кодовые слова могут бытькороче длины символа для часто повторяющихся символов и длиннее в противном случае.
Этот протокол не определяет Прозрачного режима, и следовательно возможны ситуации, приводящие к значительному расширению выходного потока. В случае корректной реализации V.42bis это практическиневозможно, кроме того, V.42bis поддерживает возможность переинициализации словарей, что позволяет алгоритму лучше адаптироваться к хорошо пере1062.3. Методы и технологии передачи данныхмешанному потоку. Несомненным преимуществом протокола V.42bis являетсявозможность параметризации протокола, что позволяет создавать более гибкие реализащш.Реальное сжатие по протоколу V.42bis на 20...30 % эффективнее, чем сжатие по MNP5 и на 5...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
