В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 152
Текст из файла (страница 152)
По мере работы алгоритма сжатия к словарю добавляются новые строки. В любои момент времени словарь содержит все односимвольные строки плюс некоторые многосимвольные строки. Механизм работает так, что любые ,чтолю ыеведущие подстроки присутствующей в словаре строки также могут использоваться в качестве элементов словаря. Например, если в словаре есть строка МЕОЪЪ', снабженная своим уникальным кодовым словом, тогда строки МЕО и МЕ также присутствуют в словаре и у каждой есть свое уникальное кодовое слово. Логически словарь может быть представлен в виде набора дерсвьев, при этом корень каждого дерева соответствует символу алфавита. Таким образом, по умолчанию имеется 256 деревьев (все возможные 8-битовые символы).
Далее мы более детально опишем алгоритм, имеющий много общего со стандартом Ъг.42ЬЬ и схемами 1.Х78 и ЕХЪЪ'. Сжатие Прежде чем перейти к описанию алгоритма, введем следующие обозначения: + С| — следующее доступное неиспользуемое кодовое слово; + С~ — размер кодового слова, по умолчанию 9 бит; + И— 2 — максимальный размер словаря, равный количеству кодовых слов ( 2с'); + Лз — размер символа, по умолчанию 8 бит; + И Л~5 — первое кодовое слово, используемое для обозначения строки из более чем одного символа; + ЛГ— № — максимальная длина сгроки, которая может быль закодирована.
Алгоритм сжатия реализует три основные действияг + поиск совпадений строк и кодирование; + добавление новых строк к словарю; + удаление старых строк из словаря. Алгоритм всегда ищет в словаре строку максимальной длины, совпадающую с входной строкой. Передатчик разбивает входной поток на строки, присутствующие в словаре, и преобразует каждую строку в соответствующее кодовое слово, Поскольку все односимвольные строки уже находятся в словаре, весь входной поток может быть разбит на строки, присутствующие в словаре. Приемник принимает поток кодовых слов и преобразует каждое кодовое слово в соответствуюгцую символьную строку. Алгоритм всегда ищет новые строки, которые можно добавить к словарю, а также заменить ими старые строки, которые вряд ли встретятся в будущем.
Процедура выглядит следующим образом: 1. Входные символы обрабатываются, чтобы получить совпадая>щие строки большей длины. 2. Если совпадающая строка имеет максимальную длину (№ символов), тогда алгоритм передаст код для этой строки и переходит к шагу 1. 3. В противном случае к совпадающей строке добавляется следующий символ, а сама строка добавляется к словарю и ей назначается код. Однако носко.льку зта строка егце отсутствует в словаре получателя, алгоритм передает код оригинальной строки и использует оставшийся символ, чтобы опять начать с шага 1. Процедура добавления новой строки к словарю зависит от того, является ли словарь полным или нет.
В любом случае передатчик хранит переменную Сь представляющую собой значение следующего доступного кодового слова. При инициализации системы переменной С~ присваивается значение Мъ которое представляет собой следующее значение, после того как всем односимвольным строкам присвоены значения. Таким образом, по умолчанию значение С1 начинается с 256.
До тех пор пока словарь пуст, при определении каждой новой строки ей назначается код С, и этот код увеличивается на единицу. Когда словарь полон, при определении новой строки ей назначается кодовое значение Сь затем выполняется следующая процедура: 1. С1 увеличивается на единицу. 2. Если значение С| равно максимальному размеру словаря Л"ь оно устанавливается равным №. То есть как только величина С~ достигает своего максимального значения, опа снова устанавливается равной минимальному значению.
3. Если узел, идентифицируемый значением Сь не является листовым узлом, тогда выполняется переход к шагу 1. 4. Если узел является листовым узлом, тогда он удаляется из словаря. В конце этой процедуры в словаре появляется место для новой записи, а С~ представляет собой неиспользуемый код, присваиваемый этой записи. Теперь система готова к определению следующей новой строки словаря. Рисунок 20.9, п иллюстрирует работу алгоритма сжатия, для которого используется трехсимвольный алфавит. Вначале в словаре находятся только односимвольные строки (верхняя часть табл. 20.7).
Входные данные считываются слева на- баб Глава 20. Сжатие без потерь право. Поскольку в таблице нет совпадающих строк длиннее а, для этой строки выводится код 1, а к таблице добавляется новая строка аЬ, которой назначается код 4, Затем для начала новой строки используется символ Ь. Поскольку строки Ье нет в словаре, она добавляется в словарь с кодом 5, а в выходной поток направляется символ Ь. Процесс продолжается подобным образом. КОР Ь (2) с (3) Входные символы Выходные коды а Ь а Ь с Ь а Ь а Ь а а а а а 1 2 4 8 1 10 11 Ьа (5) аа (10) сЬ (7) Новые строки, добавленные е таблицу 10 Входные КОДЫ ЬаЬ (8) Ьа ЬаЬ а аа ааа ааа (11) Выходные данные аЬ Новые строки, добавленные в таблицу -'„,' ЬаЬа [9) 10 5 7 д Рис.
20.9. Пример работы алгоритма (Луу Таблица 20.?. Словарь |.2УУ для примера, показанного на рис. 20.9 Сгроковаятвблица Символ Код Альтернативная таблица Символ Код с 1Ь аЬ Ьа аЬс сЬ ЬаЬ ЬаЬа аеаа В таблице показан словарь, формируемый в данном примере. Более компактный метод хранения иллюстрирует правая часть таблицы, в которой каждая строка представляется в виде префиксного кода строки и последнего символа. При таком представлении все многосимвольные элементы словаря имеют равную длину.
1 2 3 4 5 б 7 8 9 10 11 2а 4с 3Ь 5Ь 8а 1а 10а 1 2 3 4 5 5 7 8 9 1О 11 20.5. Рекомендуемые литература и веб-сайты 657 Такое представление также предполагает структуру словаря, состоящую из не'[ скольких деревьев, как показано на рис. 20.10, Рис. 20. 10. ПРедставление словаря (2 е виде деревьев Распаковка Интересный аспект работы семейства алгоритмов (.278 заклточается в том, что словарь не передастся явно алгоритму распаковки.
Вместо этого алгоритм распаковки создает идентичный словарь в процессе распаковки. Это возможно благодаря тому, что при распаковке строка, ссютветствующая коду, всегда встречается прежде самого кода. Рисунок 20.9 6 иллюстрирует процесс распаковки. Каждый встреченный код преобразуется в оютветствующую символьную строку. Между тем, выходной поток используется для создания новых элементов словаря по тем же правилам, что и в алгоритме сжатия. 20.5.
Рекомендуемые литература и веб-сайты Подробное техническое описание алгоритма, обсуждавшегося в этой главе, приведено в [1971. Другие две полезные книги по сжатию данных — зто [194] н [1181. В обеих книгах содержится ряд примеров программ сжатия и распаковки данных, а также анализируется восприимчивость данных к сжатию. Рекомендуемым веб-сайтом является Сотлргетз(олротлгетг. Это хороший источттик информации о книгах, алгоритмах, продуктах и т.
д. по сжатию данных. Глава 20. Сжатие без потерь 20.6. Задания 659 20.6. Задания 1, В протоколе МИР (М!сгоссвп )4егч огй Ргогосо! — сетевой протокол от М!сго- Исходные денные Сжатые денные ОААА 1ввв 2ССС ААА ВВВВ ССССС а) метод Хаффмана; б) алгоритм ЕХЪ', в) арифметическое кодирование. 7. Один из способов повышения эффективности алгоритма сжатия заключа 2.
3. 5. сот) используется разновидность схемы, представленной на рис. 20.1. Реализованный в более чем 1 млн модемов протокол МЬ!Р, возможно, представ ляет собой самую популярную схему группового кодирования. В протоколе МЬ!Р любая строка из трех и более повторяющихся символов представляется в виде СХХХ, где С вЂ” количество повторений символа, а Х вЂ” сам символ (см. пример ниже).
Перечислите преимущества и недостатки метода МЬ(р для группового кодирования по сравнению с методом, который иллюст!щрует рнс. 20.1. Постройте код Е277 для следующей последовательности. Используйте скользящий буфер предыстории и упреждающий буфер по 8 символов каждый. 0100010011010001010010000101000 Декодируйте последовательность 0 0 1 3 5 2, сформированную при ьюмощи метода Е7ЛЪ', используя (сравните с рис. 20.10) начальный словарь а(0) и Ь(1). В этом упражнении два вопроса. а) что при прямолинейной реализации метода кодирования Е277 будет работать быстрее — сжатие нли распаковка? Почему; б) ответьте на тот же вопрос для метода кодирования !.278.
Предположим, ваы дается входная последовательность вида аааа... ааа, в которой символ повторяется я раз. Какая схема кодирования будет в данном случае более эффективной, АХ?7 или Е278? Аргументируйте свой ответ, а также расскажите о сделанных вами предположениях. Рассмотрим показанную далее символьную строку и предположим, что в этой строке отражены относительные вероятности появления символов (например, Рг(а) = 2/40). Покажите код для этой строки, полученный с помощью каждого из перечисленных методов: аа ЬЬЬ сссс Ссгсс ееееее ГГГГГГГЯЧЧЬЧУУЯ ется в предварительной обработке данных и придании им вида, более пригодного для сжатия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
