В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 151
Текст из файла (страница 151)
Это нс обязательно так. Может быть ноль, ет ыть ноль, одно или несколько удвоений на символ. Когда последний символ обработан, а тан, результат представляет собой 110. К этому моменту конечный интервал равен [2/15, 2/3), Поскольку все двоичные числа в этом интервале начинаются с 0,01, для однозначной идентификации этого диапазона достаточно кода 01. Таким образом, мы получаеле тот же код, что и в предылушем методе (см. Рис, 20.5). Так булет всегда, потому что используются, по сути, те же самые вычисления.
20.4. Алгоритмы совпадения строк Такие алгоритмы, как метод Хаффмана и арифметическое кодирование, основаны на знании оценки статистики сжимаемых ланных. Эти алгоритмы не адаптируются к изменениям в представлении данных. Кроме того, ограничения памяти ставят предел их способности фиксировать взаимосвязи высокого порядка между словами и фразами текста. Другой подход, доказав/пий свою эффективность, используется в семействе методов, известных под названием алгоритмов совпадения строк. В то время как в методе Хаффмапа и при арифметическом копировании входные последовательности фиксированной длины преобразуются в коды переменной длины, алгоритмы совпадения строк преобразуют входные последовательности переменной длины в коды фиксированной длины.
Кроме того, алгоритмы совпадения строк не вылвигают априорных предположений о статистике данных, а адаптируются к изменениям в характере входных данных по мере их обработки. Все алгоритмы ланной категории обязаны своим происхождением израильским исследователям Якову Зива ([асоЬ 21Ъ) и Аврааму Лемпелю (АЪгаЬаш Еешре1). В 1977 г. . они описали метод, основанныи па буфере скользящего окна, в котором содержится только что обработанный текст [247[. Этот алгоритм обычно называют Е777, Р . Разновидность этого алгоритма используется в популярной в Интернете схеме сжатия гтр (РКХ1Р, 8г[р, ьйрй и т. д.).
В следующем году те же авторы описали улучшенную версию этого алгоритма, основанного на структурированном в виде дерева словаре. Этот алгоритм называется ЕХ78. Затем алгоритм ЕХ78 был ( усовершенствован и назван 1Х»т/ [234[, Многие программы сжатия основаны на алгоритмах ЪХ78 и ЕУ тй/, включая стандарт т/.42Ьтз сектора 1ТБ-Т, предназначен- ный для голосовых модемов', популярный формат сжатии изображений О1Р, а так- же программу сжатия данных в операционной системе 11[л/1Х, Рнс. 20.6.
Пример инкрементного арифметического кодирования В алгоритмах Е277, Е278 и их вариантах используется тот факт, что слова и фразы в потоке текста (элементы изображения в случае О1Р) повторяются с больпюй вероятностью. Когда встречается повторяющаяся последовательность, она может быть заменена коротким кодом. Программа сжатия ищет подобные повторяющиеся участки текста и «на лету» формирует коды, которыми заменяет пх на выходе. Те же колы могут использоваться для обозначения новых последовательностей, Алгоритм должен быть опрелелеп таким образом, чтобы программа распа- ями ковки могла нанти текуптее соответствие между кодами н последовательност исходных данных.
Другой способ повышения эффективности алгоритмов совпадения строк состоит в том, чтобы учитывать энтропию входных данных, рассматриваемых в виде ' Вата сотртем!оп Ргоеедаеж/ок Васа сипак тенета па едмрвеы (Все) сепк епое соте»о//оп /то- 652 Глава 20. Сжатие без потерь 20 4 Алгоритмы совпадения строк боЗ последовательности строк. Вспомним, чта чем выше уровень а;„сг ь а;„сгации входных символов, тем ниже энтропия. Поэтому следует ожидать, что, испо льзуя совпадения строк, можно добиться высоких коэффициентов сжатия, Алгоритм ~77 Прежде чем перейти к изучению деталей алгоритма ЕХ77, рассма , рассмотрим простой пример, основанный на примере из 12321. Пусть имеется следующая бе едующая ессмысленная фраза: гье ьгснл гох дыгреб снег гье ьгсхл гсху дсао1пд ггсд Длина этой фразы 53 байта, то есть 424 бита. Ллгоритм обрабатывает это г текст слева направо.
Вначале каждый символ преобразуется в 9-битовый кад, состоящий из двоичной единицы, за которой следует 8-битовое Л5СП-представление символа. Во время обработки текста алгоритм ищет повторяющиеся последовательности. Когда встречается повторяющаяся последовательность, алгоритм ищет конец такой последовательности, то есть каждый раз алгоритм отыскивает как можно больше символов. Первой такой последовательностью является Ьпе Ьгонп 7 . П онп ох.
овторяющаяся последовательность заменяется указателем на первый экземпляр последовательности и длиной этой последовательности. В данном с аннам случае последовательность Ьйе Ьгонп гох встречается на 26 позиций раньше и имеет длину 13 символов. Для данного примера рассмотрим два варианта кодирования: 8-битовьш указатель и 4-битовая длина или 12-битовый указатель и 6-битовая длина. При этом 2-битовый заголовок указывает, который вариант выбран: 00 означает первый вариант, а 01 — второи вариант. Таким образом, второй экземпляр последовательности Ьйе Ьгоип 7ох кодируется как <00ь><26к><13к> или 00 00011010 1101.
Оставшиеся части сжатого сообщения представляют собой букву у, последовательность < 00ь><27 к><5к>, заменяющую последовательность, состоящую из пробела, аа которьгы следует строка 3ыпр, и последовательность символов 1пд 7год. На рис. 20.7 иллюстрируется преобразование алгоритма сжатия. Сжатое сообщение состоит из 35 9-бнтовых символов и двух кодов, то есть всего нз 35 9+ + 2 ° 14 = 343 би . т.
Таким образом, при 424 бит в несжатом сообщении коэффициент сжатия данного метода в этом примере составил 1,24. ь с е Ьхснл йох дитрео стех ЬЬе":."-Ькойя .-"4оях 714гврьсд Йхсд Ьо еле Ьхонл гох зстрео оиех 'Ф 71," 91244$Ц~, ъ,'.у даг27кб>ьсд гхсд Рис 20.7. Пример работы метода Ь277 Алгоритм сжатия В алгоритме сжатия 1 777 н его вариантах используются два буфера.
В скользящем буфере предыстории хранятся Лгтолько что обработанных символов источ- / ника, а в упреждающем буфере содержатся следующие 7. символов, ожидающих обработки (рис. 20,8, а). Алгоритм пытается найти соответствие между двумя и более символами из начала упреждающего буфера и строкой в скользящем буфере предыстории. Если соответствие не обнаружено, первый символ упреждающего буфера выводится как 9-битовый символ, а также сдвигается в скользящее окно, при этом самый старый символ выбрасывается из скользящего окна. Если совпадение обнаруживается, алгоритм продолжает искать самое длинное совпадение, Затем строка, для которой найдено соответствие, выводится в виде триплета (индикатор, указатель, длина). Затем из скользящего окна выдвигаются столько символов, сколько содержится в кодированной трипл етом последовательности, и столько же новых символов исходного текста помещаются в скользящее окно.
Сдвигаемый исходный текст удаление символов Сжатый текст Зсжртсд гхс гход Рис 20 В Схемаь277 На рис. 20.8, б показана работа данной схемы с последовательностью иэ нашего примера. В иллюстрации предполагается использование 39-символьного скользящего окна и 13-символьного упреждающего буфера. В верхней части примера первые 40 символов были обработаны,и несжатая версия последних 39 символов находится в скользящем окне.
Остальная часть сообщения находится в упреждающем буфере. Ллгоритм сжатия находит следуюгцее совпадение, сдвигает 5 символов из упреждающего буфера в скользящее окно и формирует код для этой строки. Состояние буфера после этих операций показано в нижней части примера. Несмотря на то что алгоритм ЕХ77 эффективен и адаптируется к прироле текущего входного потока, он обладает рядом недостатков. Для поиска совладений в предшествующем тексте этот алгоритм использует окно конечного размера. Если размер текста намного превышает размер окна, то многие потенциальные совпадения остаются необнаруженными.
Размер окна может быть увеличен, но эта при ведет к двум нежелательным эффектам. Во-первых, время работы алгоритма ваз растет. Во-вторых, придется увеличить размер поля указателя. 654 Глава 20. Сжатие без потерь 20.4. Алгоритмы совпадения строк 655 Алгоритм распаковки Процесс распаковки текста, сжатого при помощи алгоритма 1.Х77, прост. Ал горитм распаковки должен сохранять последние й символов распакованного ре ОГО результата Когда встречается закодированная строка, алгоритм распаковки заме заменяет код с помощью полей указателя и длины.
Алгоритмы Еяг78 и ЕЕВИЧ Алгоритмы ЕХ78 и ЕХЪЪ' пытаются обойти ограничения схемы ЕХ77, вместо огра- ниченного окна создавая словари. Обзор Как и схема ЕХ77, алгоритм ЕХЪЪ' (и ЕХ78) поддерживает словарь строк вместе с их кодами как для сжатия, так и лля распаковки. Когда любая строка словаря появляется на входе алгоритма сжатия, эта строка заменяется кодом. Распаковщик, наоборот, заменяет коды соответствующими им строками.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
