Читайте также:
|
Статистические методы сжатия используют статистическую модель данных и качества сжатия информации напрямую зависит от того, насколько хороша эта модель. Методы, основанные на словарном подходе, не рассматривают статистические модели, они также не используют коды переменной длины. Вместо этого они выбирают некоторые последовательности символов, сохраняют их в словаре, а сами последовательности в результирующем файле кодируются в виде меток, ссылающихся на запись в словаре. Словарь может быть статическим или динамическим (адаптивным). Первый является постоянным; иногда в него добавляются новые последовательности, но старые никогда не удаляются. Динамический словарь содержит последовательности, ранее поступившие из входного файла, при этом разрешается и добавление, и удаление данных из словаря по мере чтения входного файла.
Простейшим примером статического словаря может служить словарь английского языка, используемый для сжатия англоязычных текстов. Слово (последовательность символов, заканчивающаяся пробелом или знаком препинания) читается из входного файла и ищется в словаре. Если оно найдено в словаре, его индекс, или словарная метка, записывается в выходной файл. В противном случае записывается само это слово без сжатия (это пример логического сжатия).
В результате выходной файл содержит индексы и слова, поэтому необходимо уметь делать различие между ними. Возможный способ состоит в добавлении к записываемой последовательности дополнительного бита. Например, 19-битового индекса достаточно, чтоб закодировать 219 = 524288 элементов. Поэтому, если прочитанное слово найдено в словаре, можно записать 20-битную ссылку, состоящую из нулевого сигнального бита и индекса. Если же слово не найдено в словаре, записывается сигнальный бит, равный 1, длина слово и, наконец, само слово.
Если считать, что размер записывается в виде 7-битового числа и что средний размер слова равен 5 символам, то несжатое слово будет в среднем занимать 6 байт (48 бит). Сжатие 48 бит до 20 бит является вполне хорошим при условии, что происходит достаточно часто. При этом возникает вопрос: «Сколько слов нужно обнаруживать в словаре для того, чтобы иметь общее сжатие?». Пусть вероятность обнаружения слова в словаре равна P. После чтения и записи N слов размер выходного файла будет равен N (20 P +48(P –1). Размер входного файла в среднем будет равен 40 N. Тогда сжатие будет достигаться в случае, если N (48 – 28 P) < 40 N, то есть при P > 0,29. Следовательно, сжатия можно будет добиться при 29% успешных нахождений слов в словаре.
До тех пор, пока входной файл содержит английский текст, большинство слов будут обнаружены в словаре. Для других типов файлов ситуация изменится. В файле, содержащем текст компьютерной программы, будут встречаться слова типа malloc, cout и т.д., которые, возможно, не будут найдены в словаре. А бинарный файл, если его рассматривать как последовательность ASCII-кодов, обычно содержит разный «мусор», которого точно не будет в словаре. В результате вместо сжатия произойдёт разрастание размера файла.
Поэтому в общем случае более предпочтительно использование динамического словаря. Такой метод начинает работу с пустого или небольшого исходного словаря, добавляет в него слова по мере поступления из входного файла и удаляет старые слова, так как поиск по большому словарю осуществляется медленно. Алгоритм работает циклически, каждая итерация цикла начинается с чтения входного файла и разбиения его на слова и фразы. Потом производится поиск каждого слова в словаре. Если слово в словаре найдено, то в выходной файл записывается соответствующая метка или индекс. В противном случае в выходной файл записывается несжатое слово, оно же добавляется в словарь. На последнем шаге производится проверка, не надо ли удалить из словаря старое слово. Несмотря на более высокую сложность, метод имеет два преимущества:
1) алгоритм использует только операции над последовательностями строк типа поиска и сравнения и не использует арифметические вычисления;
2) декодер очень прост, так как от него требуется только проводить поиск слова в словаре.
Один из первых методов словарного сжатия – LZ77, названный по фамилиям разработчиков – А. Лемпела и Я. Зива. Основная идея этого метода состоит в использовании ранее прочитанной части файла в качестве словаря. Кодер создаёт окно для входного файла и двигает его справа налево в виде строки символов, требующих сжатия. Окно разбивается на две части. Левая часть окна называется буфером поиска. Она служит текущим словарём, в ней всегда содержатся символы, которые только что поступили и были закодированы. Правая часть окна называется упреждающим буфером и содержит текст, который будет закодирован. На практике буфер поиска состоит из десятков тысяч байт, а длина упреждающего буфера равна нескольким десяткам символов. Пример скользящего окна (буфер поиска и упреждающий буфер разделены вертикальной чертой):
sir_sid_eastman_easily_t|eases_sea_sick_seals.
Кодер просматривает буфер поиска в обратном порядке (справа налево) и ищет в нём первое появление символа e из упреждающего буфера. Он обнаруживает такой символ в начале слова easily. Значит, e находится по смещению 8 от конца буфера поиска. Далее кодер определяет, сколько совпадающих символов следует за найденным символом e. В данном случае совпадение по символам eas имеет длину 3. Кодер продолжает поиск, пытаясь найти более длинные совпадающие последовательности. В нашем случае имеется ещё одна совпадающая последовательность той же длины 3 в слове eastman со смещением 16. Кодер выбирает самую длинную из них, а при совпадении длин – самую удалённую, и готовит метку (16,3, e).
Выбор более удалённой ссылки упрощает кодер. Следует отметить, что выбор ближайшего совпадения, несмотря на некоторое усложнение программы, также имеет определённые преимущества, связанные с возможным использованием совместно с LZ77 кодирования Хаффмана или другого статистического кодирования, при котором коротким смещениям присваиваются самые коротки коды. Такой метод называется LZH, при большом количестве коротких смещений LZH позволяет добиться большой степени сжатия.
Декодеру неизвестно, какое именно совпадение выбрал кодер - ближайшее или самое дальнее, но ему это знать и не нужно. Декодер просто читает метки и использует смещение для нахождения текстовой строки в буфере поиска. Для него неважно, первое ли это совпадение, или последнее.
В общем случае метка в LZ77 имеет три поля: смещение, длина и следующий символ в упреждающем буфере (в нашем случае – e). Метка (16,3, e) записывается в выходной файл, а окно сдвигается на 4 позиции вперёд: три позиции для совпадающей последовательности и одна позиция – для следующего символа:
sir_sid_eastman_easily_tease|s_sea_sick_seals.
Если обратный поиск не обнаружил совпадение символов, то записывается метка со смещением 0 и длиной 0. Третья компонента метки содержит текущий символ. Такие метки очень часто возникают при начале работы алгоритма, в то время, когда словарь ещё не заполнен. Например, результаты первых трёх шагов работы алгоритма таковы:
|sir_sid_eastman_easily_teases_sea_sick_seals → (0, 0, s);
s|ir_sid_eastman_easily_teases_sea_sick_seals → (0, 0, i);
si|r_sid_eastman_easily_teases_sea_sick_seals → (0, 0, r).
Большое количество таких меток ухудшает степень сжатия. Фактически, вместо одного байта записываются несколько, поэтому в том случае, если количество совпадений со словарём в файле невелико, возможно даже разрастание размера вместо сжатия файла.
Декодер метода LZ77 устроен гораздо проще, чем кодер. Он должен создать такой же буфер поиска, как кодер. Декодер вводит считывает метку, находит совпадение в своём буфере, записывает совпадающие символы и символ из третьего поля в буфер. Этот метод или его модификация хорошо работают в том случае, если файл сжимается один раз, но часто разжимается.
Дата добавления: 2015-01-05; просмотров: 73 | Поможем написать вашу работу | Нарушение авторских прав |