Еще о сжатии информации
В предыдущей заметке о методах сжатия информации обсуждались современные алгоритмы, которые можно назвать статистическими. В силу того, что для их работы требуется большая вычислительная мощность процессора и значительный объем памяти, они не получили очень широкого распространения. Впрочем, для этого есть и другие причины.
Сразу нужно сказать, что подстановочные алгоритмы, которые будут описаны, являются адаптивными. То есть повторяющиеся последовательности символов выявляются по мере чтения исходных данных непосредственно в ходе кодирования, а этап предварительного просмотра и анализа отсутствует. Мне кажется, что такое решение в значительной мере является вынужденным, поскольку далеко не простой является задача предварительного статистического анализа текста, в ходе которого мог бы быть выявлен самый удачный набор подстрок текста из всех возможных.
Схема LZ78 предполагает, что по мере чтения исходного текста создается так называемый словарь, представляющий собою таблицу встречающихся в тексте строк. Когда в тексте встречается последовательность символов, уже находящаяся в словаре, она заменяется индексом, то есть номером строки в таблице. Среди всех LZ-алгоритмов самым известным является LZW, разработанный в 1984 году Терри Велчем для аппаратной реализации в высокопроизводительных дисковых контроллерах.
LZW начинает работу с таблицей, рассчитанной на 4К строк. Строки с индексами от 0 до 255 инициализированы кодами единичных символов (байтов), то есть предназначены для строк единичной длины. Индексы от 256 до 4095 предназначены для строк из двух и более символов, а соответствующие им строки — пустые. Договоримся, что "W" обозначает временную рабочую строку-буфер и опишем алгоритм следующим псевдокодом:
Установить W = пусто
ЦИКЛ
Прочесть из исходного текста очередной символ С
ЕСЛИ строка WС есть в словаре ТО
Присоединить С к W: W = WС
ИНАЧЕ
Записать в выходной файл код для строки W
Добавить строку WС в словарь
Установить W = С
КОНЕЦ ЦИКЛА
Предположим, что сжимается текст /АБВ/АБ/АББ/АБГ. Следующая таблица показывает шаги работы алгоритма.
Для распаковки сжатого текста вовсе не требуется передавать вместе с кодом текста еще и словарь. Распаковка начинается со словарем, первые 256 строк которого содержат коды единичных символов, то есть уже готовы к работе. Дело в том, что, читая, один за другим, коды сжатого текста, мы не только записываем в выходной файл соответствующие им символы, но и воссоздаем словарь.
Это происходит точно так же, как по ходу сжатия. Только роль входных символов играют только что распакованные. Так что к моменту, когда в сжатом тексте встретится код больше 255, то есть код многосимвольной строки, словарная позиция с соответствующим индексом окажется уже заполненной!
Шаги работы алгоритма по распаковке сжатого текста "/АБВ<256>Б<260><261><257>Г", полученного в предыдущем примере, показаны в следующей таблице.
Строго говоря, упакованный текст начинается вовсе не с символов "/АБВ", а с соответствующих им индексов. Это упрощение было сделано для большей ясности примера. Поскольку в словаре 4096 позиций, то для записи каждого индекса нужно 12 битов. А с учетом того, что для записи одного символа требуется 8 битов, получается, что "сжатая" последовательность индексов "/АБВ" в полтора раза длиннее, чем исходная строка! Таким образом, действительный выигрыш получается только при кодировании строк длиной не менее двух символов.
Вариант алгоритма LZW, известный в мире UNIX как LZC, использует индексы более экономным и изобретательным образом. В начале работы алгоритм генерирует 9-битовые индексы. Как только число заполненных строк словаря переваливает за 512, алгоритм начинает создавать 10-битовые индексы, — и так далее. Естественно, что максимальная длина индекса, а по существу, размер словаря, оговаривается заранее.
Кроме того, в описанном элементарном алгоритме LZW ничего не говорится о случае, когда словарь заполняется на 100%. Можно, конечно, просто "заморозить" словарь, то есть пытаться работать с уже существующим набором строк, ничего туда больше не добавляя. LZC предлагает иное решение. Программа ведет контроль за текущей степенью сжатия информации и, если она начинает падать, очищает словарь и с нуля начинает строить новый. Более современные схемы в подобной ситуации не полностью очищают словарь, а используют стратегию по исключению из него строк, которые реже всего использовались для генерации кода.
Наконец, существуют разные способы построения словаря. Так, алгоритм LZW строит строки наращиванием, добавляя к ним по одному символу за раз. Алгоритм LZMW делает это сцеплением двух предыдущих строк словаря. В итоге словарь заполняется быстрее и содержит более длинные строки, чем в предыдущем случае. Недостатком этого метода является более сложная работа с таблицей.
Понимание принципов работы подстановочных алгоритмов сжатия информации семейства LZ78 существенно упрощает знакомство с идеями, используемыми в алгоритмах семейства LZ77. Самый известный алгоритм этого семейства разработан Сторером и Шиманским в 1982 году и называется LZSS.
Основная мысль LZ77 состоит в том, что словарь отсутствует, а его роль играет сам сжатый код исходного текста. Поэтому, если по ходу чтения исходного текста программа встречает повторяющуюся строку, в качестве выходного кода записывается адрес первого вхождения строки в код и количество символов в ней. На практике область кода, рассматриваемого как словарь, ограничена 4 Кб. По мере генерации сжатого кода она "сдвигается" во избежание переполнения. Таким образом, мы имеем дело с окном (рабочим буфером) заданного размера, как бы "плывущим" над уже готовым кодом по мере его роста.
Схема LZSS начинает работу с пустым окном размером 4096 байтов и небольшим буфером предварительного просмотра, куда прочитаны первые N символов исходного текста. Сначала выполняется поиск вхождения подстроки максимальной длины. При этом проверяется, не содержится ли строка из всех N символов входного буфера в окне. Если нет, то проверяется наличие в окне строки из первых N-1 символов, потом строки длиной N-2 и так далее.
Поиск вхождения какой-либо из подстрок входного буфера может завершиться безуспешно. В этом случае в окно без кодирования выводится первый символ буфера, затем этот символ удаляется из буфера. Потом буфер дополняется очередным символом исходного текста, и поиск вхождения максимальной подстроки начинается заново. Если же вхождение подстроки было обнаружено, то в окно записывается код, состоящий из адреса подстроки в окне и длины подстроки. После этого из входного буфера удаляется вся закодированная подстрока, и буфер дополняется соответствующим числом символов исходного текста. И вновь запускается процедура поиска вхождения.
В ходе работы алгоритма рано или поздно возникнет момент, когда окно (размером всего 4К) заполнится и записать следующий код будет некуда. Как уже упоминалось, эта ситуация разрешается сдвигом окна. Другими словами, байты кода, которые первыми были сгенерированы, первыми выталкиваются из окна так, чтобы освободить место для вновь заносимого кода. Другими словами, работает очередь FIFO.
Для практических целей реализации описанного алгоритма удобно все же не ставить знака равенства между рабочим окном и получаемым сжатым кодом. Дело в том, что перед выводом в окно незакодированного символа или кода (пары адрес-длина) на деле в выходной поток нужно записывать дополнительный бит (0 или 1), чтобы в ходе декодирования можно было различить эти ситуации. Кроме того, поиск вхождения подстроки 8-битовых символов в окне с 9-битовыми символами и включениями кодов, трудно эффективно запрограммировать. А ведь именно поиск является самой массовой операцией в ходе работы LZSS.
Эту операцию можно упростить и сделать быстрее: записывать коды в выходной поток в момент, когда их полагалось бы записывать в окно, а не по мере их выталкивания из окна. В окно же можно заносить только 8-битовые незакодированные единичные символы. Конечно, после этого окно перестанет быть окном, превратившись в простой буфер, который к тому же можно сделать кольцевым.
Распаковка сжатого кода производится быстро и просто. Сначала считывается направляющий бит. В зависимости от его значения, в выходной поток записывается либо единичный символ, с параллельным занесением его в 4 Кб кольцевой буфер, либо в выходной поток поступает подстрока указанной длины, расположенная в буфере по указанному адресу. Вот, пожалуй, и все хитрости.
Говоря о популярности подстановочных схем сжатия информации, я нисколько не преувеличивал, поскольку такие знаменитые архиваторы, как arj, lha, zip и zoo, являются вариациями на тему LZ77. Но и это еще не все, так как существуют гибридные алгоритмы, сочетающие в себе статистический и подстановочный подходы.
Примером может послужить LZARI, принадлежащий Харушико Окамура. Идея LZARI состоит в том, что одни подстроки встречаются заметно чаще других, и для кодирования ссылок на них используется меньше битов, чем для ссылок на более редкие подстроки. Для этой цели коды, то есть пары адрес-длина, перед записью в выходной поток обрабатываются алгоритмом арифметического сжатия.
Другой пример — архиватор lharc (Харуясу Йошизаки), в котором реализован алгоритм LZHUF — гибрид LZ77 и адаптивного сжатия по Хаффману. Хотя алгоритм Хаффмана теоретически не может превзойти арифметический, на деле разница оказывается очень небольшой, а скорость работы алгоритма повышается.
Евгений Щербатюк
Сразу нужно сказать, что подстановочные алгоритмы, которые будут описаны, являются адаптивными. То есть повторяющиеся последовательности символов выявляются по мере чтения исходных данных непосредственно в ходе кодирования, а этап предварительного просмотра и анализа отсутствует. Мне кажется, что такое решение в значительной мере является вынужденным, поскольку далеко не простой является задача предварительного статистического анализа текста, в ходе которого мог бы быть выявлен самый удачный набор подстрок текста из всех возможных.
Схема LZ78 предполагает, что по мере чтения исходного текста создается так называемый словарь, представляющий собою таблицу встречающихся в тексте строк. Когда в тексте встречается последовательность символов, уже находящаяся в словаре, она заменяется индексом, то есть номером строки в таблице. Среди всех LZ-алгоритмов самым известным является LZW, разработанный в 1984 году Терри Велчем для аппаратной реализации в высокопроизводительных дисковых контроллерах.
LZW начинает работу с таблицей, рассчитанной на 4К строк. Строки с индексами от 0 до 255 инициализированы кодами единичных символов (байтов), то есть предназначены для строк единичной длины. Индексы от 256 до 4095 предназначены для строк из двух и более символов, а соответствующие им строки — пустые. Договоримся, что "W" обозначает временную рабочую строку-буфер и опишем алгоритм следующим псевдокодом:
Установить W = пусто
ЦИКЛ
Прочесть из исходного текста очередной символ С
ЕСЛИ строка WС есть в словаре ТО
Присоединить С к W: W = WС
ИНАЧЕ
Записать в выходной файл код для строки W
Добавить строку WС в словарь
Установить W = С
КОНЕЦ ЦИКЛА
Предположим, что сжимается текст /АБВ/АБ/АББ/АБГ. Следующая таблица показывает шаги работы алгоритма.
Входные символы | Выходной код | Индексы и соответствующие строки словаря |
| /А | / | 256 = /А |
| Б | А | 257 = АБ |
| В | Б | 258 = БВ |
| / | В | 259 = В/ |
| АБ | 256 | 260 = /АБ |
| / | Б | 261 = Б/ |
| АББ | 260 | 262 = /АББ |
| /А | 261 | 263 = Б/А |
| БГ | 257 | 264 = АБГ |
| <Конец> | Г |
Для распаковки сжатого текста вовсе не требуется передавать вместе с кодом текста еще и словарь. Распаковка начинается со словарем, первые 256 строк которого содержат коды единичных символов, то есть уже готовы к работе. Дело в том, что, читая, один за другим, коды сжатого текста, мы не только записываем в выходной файл соответствующие им символы, но и воссоздаем словарь.
Это происходит точно так же, как по ходу сжатия. Только роль входных символов играют только что распакованные. Так что к моменту, когда в сжатом тексте встретится код больше 255, то есть код многосимвольной строки, словарная позиция с соответствующим индексом окажется уже заполненной!
Шаги работы алгоритма по распаковке сжатого текста "/АБВ<256>Б<260><261><257>Г", полученного в предыдущем примере, показаны в следующей таблице.
Входной код | Выходной символ | Индексы и соответствующие строки словаря |
| / | / | |
| А | А | 256 = /А |
| Б | Б | 257 = АБ |
| В | В | 258 = БВ |
| 256 | /А | 259 = В/ |
| Б | Б | 260 = /АБ |
| 260 | /АБ | 261 = Б/ |
| 261 | Б/ | 262 = /АББ |
| 257 | АБ | 263 = Б/А |
| Г | Г | 264 = АБГ |
Строго говоря, упакованный текст начинается вовсе не с символов "/АБВ", а с соответствующих им индексов. Это упрощение было сделано для большей ясности примера. Поскольку в словаре 4096 позиций, то для записи каждого индекса нужно 12 битов. А с учетом того, что для записи одного символа требуется 8 битов, получается, что "сжатая" последовательность индексов "/АБВ" в полтора раза длиннее, чем исходная строка! Таким образом, действительный выигрыш получается только при кодировании строк длиной не менее двух символов.
Вариант алгоритма LZW, известный в мире UNIX как LZC, использует индексы более экономным и изобретательным образом. В начале работы алгоритм генерирует 9-битовые индексы. Как только число заполненных строк словаря переваливает за 512, алгоритм начинает создавать 10-битовые индексы, — и так далее. Естественно, что максимальная длина индекса, а по существу, размер словаря, оговаривается заранее.
Кроме того, в описанном элементарном алгоритме LZW ничего не говорится о случае, когда словарь заполняется на 100%. Можно, конечно, просто "заморозить" словарь, то есть пытаться работать с уже существующим набором строк, ничего туда больше не добавляя. LZC предлагает иное решение. Программа ведет контроль за текущей степенью сжатия информации и, если она начинает падать, очищает словарь и с нуля начинает строить новый. Более современные схемы в подобной ситуации не полностью очищают словарь, а используют стратегию по исключению из него строк, которые реже всего использовались для генерации кода.
Наконец, существуют разные способы построения словаря. Так, алгоритм LZW строит строки наращиванием, добавляя к ним по одному символу за раз. Алгоритм LZMW делает это сцеплением двух предыдущих строк словаря. В итоге словарь заполняется быстрее и содержит более длинные строки, чем в предыдущем случае. Недостатком этого метода является более сложная работа с таблицей.
Понимание принципов работы подстановочных алгоритмов сжатия информации семейства LZ78 существенно упрощает знакомство с идеями, используемыми в алгоритмах семейства LZ77. Самый известный алгоритм этого семейства разработан Сторером и Шиманским в 1982 году и называется LZSS.
Основная мысль LZ77 состоит в том, что словарь отсутствует, а его роль играет сам сжатый код исходного текста. Поэтому, если по ходу чтения исходного текста программа встречает повторяющуюся строку, в качестве выходного кода записывается адрес первого вхождения строки в код и количество символов в ней. На практике область кода, рассматриваемого как словарь, ограничена 4 Кб. По мере генерации сжатого кода она "сдвигается" во избежание переполнения. Таким образом, мы имеем дело с окном (рабочим буфером) заданного размера, как бы "плывущим" над уже готовым кодом по мере его роста.
Схема LZSS начинает работу с пустым окном размером 4096 байтов и небольшим буфером предварительного просмотра, куда прочитаны первые N символов исходного текста. Сначала выполняется поиск вхождения подстроки максимальной длины. При этом проверяется, не содержится ли строка из всех N символов входного буфера в окне. Если нет, то проверяется наличие в окне строки из первых N-1 символов, потом строки длиной N-2 и так далее.
Поиск вхождения какой-либо из подстрок входного буфера может завершиться безуспешно. В этом случае в окно без кодирования выводится первый символ буфера, затем этот символ удаляется из буфера. Потом буфер дополняется очередным символом исходного текста, и поиск вхождения максимальной подстроки начинается заново. Если же вхождение подстроки было обнаружено, то в окно записывается код, состоящий из адреса подстроки в окне и длины подстроки. После этого из входного буфера удаляется вся закодированная подстрока, и буфер дополняется соответствующим числом символов исходного текста. И вновь запускается процедура поиска вхождения.
В ходе работы алгоритма рано или поздно возникнет момент, когда окно (размером всего 4К) заполнится и записать следующий код будет некуда. Как уже упоминалось, эта ситуация разрешается сдвигом окна. Другими словами, байты кода, которые первыми были сгенерированы, первыми выталкиваются из окна так, чтобы освободить место для вновь заносимого кода. Другими словами, работает очередь FIFO.
Для практических целей реализации описанного алгоритма удобно все же не ставить знака равенства между рабочим окном и получаемым сжатым кодом. Дело в том, что перед выводом в окно незакодированного символа или кода (пары адрес-длина) на деле в выходной поток нужно записывать дополнительный бит (0 или 1), чтобы в ходе декодирования можно было различить эти ситуации. Кроме того, поиск вхождения подстроки 8-битовых символов в окне с 9-битовыми символами и включениями кодов, трудно эффективно запрограммировать. А ведь именно поиск является самой массовой операцией в ходе работы LZSS.
Эту операцию можно упростить и сделать быстрее: записывать коды в выходной поток в момент, когда их полагалось бы записывать в окно, а не по мере их выталкивания из окна. В окно же можно заносить только 8-битовые незакодированные единичные символы. Конечно, после этого окно перестанет быть окном, превратившись в простой буфер, который к тому же можно сделать кольцевым.
Распаковка сжатого кода производится быстро и просто. Сначала считывается направляющий бит. В зависимости от его значения, в выходной поток записывается либо единичный символ, с параллельным занесением его в 4 Кб кольцевой буфер, либо в выходной поток поступает подстрока указанной длины, расположенная в буфере по указанному адресу. Вот, пожалуй, и все хитрости.
Говоря о популярности подстановочных схем сжатия информации, я нисколько не преувеличивал, поскольку такие знаменитые архиваторы, как arj, lha, zip и zoo, являются вариациями на тему LZ77. Но и это еще не все, так как существуют гибридные алгоритмы, сочетающие в себе статистический и подстановочный подходы.
Примером может послужить LZARI, принадлежащий Харушико Окамура. Идея LZARI состоит в том, что одни подстроки встречаются заметно чаще других, и для кодирования ссылок на них используется меньше битов, чем для ссылок на более редкие подстроки. Для этой цели коды, то есть пары адрес-длина, перед записью в выходной поток обрабатываются алгоритмом арифметического сжатия.
Другой пример — архиватор lharc (Харуясу Йошизаки), в котором реализован алгоритм LZHUF — гибрид LZ77 и адаптивного сжатия по Хаффману. Хотя алгоритм Хаффмана теоретически не может превзойти арифметический, на деле разница оказывается очень небольшой, а скорость работы алгоритма повышается.
Евгений Щербатюк
Компьютерная газета. Статья была опубликована в номере 05 за 2000 год в рубрике soft :: файлы
