В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 10
Текст из файла (страница 10)
Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год321.Разбиваем текущий отрезок на 256 частей, длина которых соответствует текущейтаблице частот встречаемости (т.е. фактически длина отрезка = вероятность еговстретить) соответствующего элемента2.Смотрим, в каком по счету отрезке оказался x. Номер этого отрезка – очереднойсимвол в выходной последовательности.3.Обновляем таблицу встречаемости, ставим границы поиска равными последнемунайденному отрезку и возвращаемся к шагу 1Легко видеть, что разархивация происходит абсолютно симметрично с компрессией.Из описанного выше способа легко сделать адаптивное арифметическое кодирование.Для этого достаточно взять изначально пустую таблицу встречаемости, причем исходитьтеперь уже из того, что отрезков в разбиении пропорциональна встречаемости + 1 иобновлять таблицу встречаемости, не вычитая, а наоборот, прибавляя каждый новыйнайденный элемент.
Очевидно, такую начальную таблицу передавать уже не требуется, востальном же алгоритм работает точно таким же образом.Арифметическое кодирование не имеет четко заданной максимальной степени сжатия –в идеальном случае (сплошная последовательность 0 или 1) любая последовательность будетсжата всего в 1 бит (!). Более того, арифметическое кодирование не ухудшаетхарактеристики последовательности – если считать, что сжимается принципиальнонесжимаемая случайная последовательность, то на каждом шаге кодирования длина отрезкакодирования будет уменьшаться в среднем в 256 раз и после окончания кодирования числоx можно будет записать не более, чем 8n битами, при длине входной последовательности nбайт.
Поэтому арифметическое кодирование – один из лучших известных вариантовкодирования на основе только статистической информации о отдельных символахпоследовательности.Но все описанные алгоритмы по-прежнему «спотыкаются» о такой пример: abcd…xyzabc…xyz…, т.е. о последовательность из всех символов алфавита (машинного),периодически повторяющуюся. Здесь уже приходится вводить более сложные вариантысжатия – сжатие с словаремАлгоритм LZW (Lempel-Ziv-Welch, первые двое – авторы, третий – доработалалгоритм) – простейший пример такого сжатия.
Рассмотрим обычный вариант сжатия, когдасжимаются последовательности обычных байт, т.е. 8-битовых символов. Введем понятиесловаря – некоторой таблицы, в которой записано соответствие одних последовательностейсимволов (обычно – последовательных чисел 0, 1, 2, …) другим. В алгоритме LZW в словарепоследовательностям символов (цепочкам) ставятся в соответствии последовательные числа(коды), причем первые 256 кодов соответствуют соответствующим односимвольнымцепочкам (код 0 – цепочке из одного символа 0, код 1 – кодцепочкацепочке из 1 символа 1 и т.д.). Начиная с кода 256 уже 0aначинаются более длинные цепочки. Словарь имеет 1bфиксированные размеры (определяемые обычно длиной 2cбитового представления кодов, например, ограничив 3abсловарь 16-ти битными кодами получаем, что в словарь 4baвойдут максимум 65536 записей)Пример словаряСжатие происходит по следующему простомуалгоритму:1.Вначале словарь заполнен только кодами односимвольных цепочек; на входеалгоритма – некоторая последовательность байт, указатель на текущий элементвходной последовательности стоит на первом символе, текущая цепочка пуста.2.Пока есть входные символы, присоединяем к текущей цепочке текущий символвходной последовательности и смещаем указатель на этот символ на следующийсимвол.
Если символов нет, то переходим к шагу 63.Если текущая цепочка в словаре есть, то возвращаемся к шагу 2Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год334.Если текущей цепочки в словаре нет, то записываем в выходнуюпоследовательность код укороченной на 1 символ текущей цепочки (он всловаре, очевидно, есть) и записываем в словарь цепочку целиком5.Очищаем текущую цепочку, оставляя в ней только последний символ ивозвращаемся к шагу 2.6.Записываем в выходную последовательность код текущей цепочки изаканчиваем работуИдея сжатия состоит в том, что если у нас будет часто встречаться одинаковая цепочкасимволов, то она уже будет в нашем словаре и для ее кодирования не потребуетсядополнительного символа – налицо сжатие данныхПример сжатия: на примере алфавита из 4х символов (a,b,c,d) сожмемпоследовательность abcabcabc (в графе «вход» записана необработанная часть входнойпоследовательности)шагвходцепочка выходсловарь01234560abcabcabcabcd1bcabcabcaabcd2cabcabcababcd3cabcabcb0abcdab4abcabcbc0abcdab5abcabcc01abcdabbc6bcabcca01abcdabbc7bcabca012abcdabbcca(продолжение словаря, первая часть та же)789101112138cabcab0129abcabc01210abcc0124abc11bcca0124abc12ccab0124abc13cb01246abccab14bc012465 abccabТаким образом, мы закодировали последовательность abcabcabc в 012465.
Символыa,b,c,d кодировались во входной последовательности 2х-битовыми числами, символы 0..6можно закодировать 3х-битовыми числами – получаем, что мы сжали последовательность в18 бит в те же 18. Но если бы последовательность была бы длиннее (abcabcabcabcabc) иливходной алфавит был бы более обширным, то налицо было бы ощутимое сжатие данныхЗаметим, что при сжатии использовался словарь. Одним из главных достоинств LZWслужит то, что передавать словарь для восстановления исходной последовательности нетребуется – он будет восстановлен в ходе декодирования:Распаковка происходит по алгоритму1.Вначале словарь заполнен только кодами односимвольных цепочек; на входеалгоритма – некоторая последовательность байт, указатель на текущий элементвходной последовательности стоит на первом символе, входная цепочка пуста.2.Пока во входной последовательности есть символы - берем текущий входнойсимвол и декодируем его в соответствии со словарем и записываем в выходнуюпоследовательность (почему в словаре соответствующая запись найдется – см.далее).
Дописываем к текущей цепочке первый символ декодированнойпоследовательности и добавляем текущую цепочку в словарь (за исключениемсамого первого добавления такой цепочки в словаре еще нет)3.Заменяем текущую цепочку на последовательность, соответствующую текущемусимволу, затем переходим к следующему символу входной последовательностии возвращаемся к шагу 2.Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год34Идея алгоритма распаковки достаточно прозрачна – на каждом шаге мы можем почтиполностью восстановить состояние алгоритма сжатия – восстановить словарь и цепочку намомент кодирования, за исключением последнего символа цепочки. Этот символ мывосстановим, когда узнаем следующий символ в выходной последовательности – тогда мысможем добавить в словарь цепочку и полностью восстановить словарь. Теперь становитсяочевидным, что словарь при декомпрессии в точности на каждом шагу соответствуетсловарю на соответствующем шаге сжатия (п.
2).Проиллюстрируем все сказанное примером (для показанного ранее сжатия), здесь вцепочке значками (?) отмечены неизвестные в данный момент символы, а в выходнойпоследовательности (…) – только что дописанный кусок выходной последовательности (т.е.очередной декодированный символ)шагвход цепочкавыходсловарь01234560012465abcd112465a(a)212465a(?)aabcd32465aba(b)abcd42465b(?)ababcdab5465bcab(c)abcdab6465c(?)abcabcdabbc765caabc(ab)abcdabbcca(продолжение словаря)78910111213865ab(?)abcab95abcabcab(ca)105ca(?)abcabcaabc11cababcabca(bc)abc12bc(?)abcabcabcabccabМы декодировали 012465 обратно в abcabcabcК сожалению, такой простой и красивый алгоритм несет в себе «ловушку». Пусть наопределенной стадии обработки в словарь попала цепочка СЛОВО, а затем нам встретиласьпоследовательностьСЛОВО+СИМВОЛ+СЛОВО+СИМВОЛ+СЛОВОто при кодировании в словарь вначале попадет цепочка СЛОВО+СИМВОЛ+(ПЕРВЫЙСИМВОЛСЛОВА),затемСЛОВО+СИМВОЛ+(ДВАПЕРВЫХСИМВОЛАСЛОВА), затем Например, пусть СЛОВО – JOHN, оно уже есть всловаре, есть в словаре и JOHNA, скажем, с кодом 200, и у нас встретиласьпоследовательность JOHNAJOHNAJOHNAJOHN.
В словарь попадает JOHNAJ с кодом,например, 300, соответствующий фрагмент кодированной последовательности будетвыглядеть …, 200, 300, …; при декодировании алгоритм наткнется вначале на код 200,декодирует его в JOHNA, соответствующая цепочка алгоритма будет JOHNA(?). Какойсимвол поставить вместо ? пока непонятно – это должно стать ясно когда мы найдемследующую цепочку. Но что делать если следующая цепочка – как раз наша JOHNA(?),которую мы еще не успели добавить в словарь? В данном случае наблюдается как раз такаяситуация – кода 300 в словаре еще нет, а без этого кода мы не можем построить ту цепочку,которую и надо добавлять в словарь под номером 300.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
