Страница: 22/29
Метод словарей
Алгоритм, положенный в основу метода словарей, был впервые описан в работах израильских исследователей Якоба Зива и Абрахама Лемпеля, которые впервые опубликовали его в 1977 г. В последующем алгоритм был назван Lempel-Ziv, или сокращенно LZ. На сегодняшний день LZ-алгоритм и его модификации получили наиболее широкое распространение, по сравнению с другими методами сжатия. В его основе лежит идея замены наиболее часто встречающихся последовательностей символов (строк) в передаваемом потоке ссылками на "образцы", хранящиеся в специально создаваемой таблице (словаре). Алгоритм основывается на том, что по потоку данных движется скользящее "окно", состоящее из двух частей. В большей по объему части содержатся уже обработанные данные, а в меньшей помещается информация, прочитанная по мере ее просмотра. Во время считывания каждой новой порции информации происходит проверка, и если оказывается, что такая строка уже помещена в словарь ранее, то она заменяется ссылкой на нее.
Большое число модификаций метода LZ — LZW, LZ77, LZSS и др. — применяются для различных целей, Так, методы LZW и BTLZ (British Telecom Lempel-Ziv) применяются для сжатия данных по протоколу V.42bis, LZ77 — в утилитах Stasker и DoudleSpase, а также во многих других системах программного и аппаратного сжатия.
5.2. Сжатие данных в протоколах MNP
Расширяемость MNP при сохранении совместимости с существующими реализациями ярко продемонстрирована в его поддержке Рекомендации ITU-T V.42bis.
В процессе установления соединения передатчик и приемник "оговаривают" использование сжатия данных в процессе. Это выполняется с помощью параметра 9 или 14 блока PDU LR. Параметр 9, который специфицирует сжатие данных MNP5 или MNP7, был расширен, чтобы обеспечить "краткую" форму спецификации V.42bis. Параметр 14 является новым параметром, применяемым для детализации особенностей V.42bis, используемого в данном канале.
Если существует возможность поддерживать MNP5 и (или) MNP7 и V.42bis, передатчик может включить как параметр 9 (сжатие MNP), так и параметр 14 (сжатие V.42bis). Ответственность за выбор типа сжатия данных, который будет использоваться, в этом случае несет приемник. Он возвращает PDU LR, который указывает выбранный тип сжатия данных. Если передатчик и приемник поддерживают несколько методов сжатия, то приемник делает свой выбор в соответствии со следующим приоритетом.
Приемник не включает информацию о поддержке V.42bis в свой PDU LR, если он не принял запрос на V.42bis в LR от передатчика. Если передатчик включил такой запрос в свой PDU LR, но не получил подтверждения, он отказывается от использования сжатия по протоколу V.42bis.
Далее рассмотрим особенности реализации сжатия в протоколах MNP.
Таблица 5.1. Приоритеты выбора метода сжатия
|
Тип сжатия |
Приоритет |
|
V.42bis |
Высокий |
|
MNP7 |
Средний |
|
MNP5 |
Низкий |
5.2.1. Протокол MNP5
Протокол MNP 5 реализует комбинацию адаптивного кодирования с применением кода Хаффмена и группового кодирования. При этом хорошо поддающиеся сжатию данные уменьшают свой исходный объем примерно на 50% и, следовательно, реальная скорость их передачи возрастает вдвое по сравнению с номинальной скоростью передачи данных модемом.
На первом этапе процедуры сжатия используется метод группового кодирования для удаления из потока передаваемых данных слишком длинных последовательностей повторяющихся символов. Этот метод преобразует каждую группу из трех и более (вплоть до 253) одинаковых смежных символов к виду символ и число символов. Поскольку групповое кодирование не связано с большими вычислениями, этот метод особенно хорош для реализации в реальном масштабе времени, в частности, при передаче данных по линиям связи.
Согласно данного метода система группового кодирования проверяет проходящий поток данных. Алгоритм остается пассивным до тех пор, пока в этом потоке не обнаружатся три одинаковых смежных символа. После этого алгоритм начинает счет и удаляет из потока данных до 250 одинаковых следующих друг за другом символов. Счетный байт посылается вслед за тремя исходными символами, и передача продолжается. На рис. 8.2 показан пример группового кодирования потока данных.
Способность метода группового кодирования сжимать длинные последовательности очевидна. Тем не менее, рис. 5.1 иллюстрирует также одну из слабостей данного алгоритма. Кодирование группы из трех символов, наоборот, расширяет поток данных.
 |
Реферат опубликован: 31/07/2007