Символ-ориентированные методы сжатия

4.2.1. Метод интервалов. Наиболее простым из анализируемой группы методов является метод интервалов. Суть метода заключается в поиске комбинаций одинаковых символов и замене их на специальную комбинацию abc, где а – специальный символ, b – один из символов анализируемой повторяющейся последовательности (интервала) и с – количество повторений. Как правило, принимается, что длина минимального интервала составляет два символа. При реализации метода сжатия важным является выбор специального символа (а). Его подбирают так, чтобы вероятность его появления в тексте стремилась к минимуму.

Пример 4.3. X_k = mkkkcb0000fkff. Можно выделить три интервала (подчеркнуты): X_k = mkkkcb0000fkff. Возьмем в качестве специального символ «*». После преобразования (сжатия) получим такую последовательность: X_n = m*k3cb*04fk*f2.

Как видно из примера, метод является эффективным при количестве повторений не ниже трех.

4.2.2. Метод Берроуза – Уиллера. Суть метода (Burrows –Wheller ) состоит в том, что исходная информационная последовательность (X_k) разбивается на блоки произвольной, но одинаковой длины k. Преобразованию подвергается каждый блок в отдельности. На каждом этапе создается квадратная матрица W₁ размерности k × k. Каждая последующая строка этой матрицы, начиная со второй, является циклическим сдвигом на один символ влево предыдущей строки. На основе первой матрицы создается вторая матрица (W₂) такой же размерности, содержащая строки первой матрицы, отсортированные в лексикографическом порядке.

Результатом преобразования является столбец h_k матрицы W₂ и число N, соответствующее номеру строки матрицы W₂, в которой записана исходная последовательность X_k.

Обратное преобразование основано на свойстве рекуррентности преобразования матриц W₁ и W₂. Задача состоит в воссоздании матрицы W₂. Эту процедуру начинаем с заполнения последнего столбца будущей матрицы. Дальнейшие действия иллюстрируются на основе используемого примера.

4.2.3. Словарные методы сжатия. В известном смысле таблицу кодов ASCII (American Standard Code for Information Interchange, американский кодовый стандарт для обмена информацией), в которой один символ исходного алфавита всегда представляется одним байтом двоичных символов, можно рассматривать как один из методов сжатия. Здесь таблица может выступать как своеобразный словарь. Словарь этот является полным и исчерпывающим. Однако на практике в словарь помещаются наиболее часто встречающиеся слова и словосочетания.

В общем случае словарь может содержать произвольное число комбинаций произвольной длины. Основным вопросом при этом является размер словаря. Некоторые особенности рассмотрим на примере.

Пример 4.5. Положим, что текст, подлежащий компрессии, строится на основе 4-символьных слов из 26 символов латинского алфавита и 6 специальных знаков (например, точка, тире и т. д).

По принципу кодов ASCII каждый из 32 символов может быть заменен бинарным кодом длиной 5 бит. Общее же количество всех возможных слов длиной 4 бит на основе этих символов составляет: 32⁴ = 2²⁰ = 10 048 567. Вероятность того, что данное произвольное слово будет равно какой-то конкретной комбинации, составит Р = 1∕ 10 048 567 (принимая, что все слова равновероятны). Если все комбинации разместить в словаре, то каждой комбинации должен соответствовать бинарный код длиной 20 бит. Встает вопрос. Что лучше: 32 и 5 или 10 048 567 и 20?

Положим, что из миллиона слов все-таки имеются те, которые встречаются реже, другие – чаще. Допустим, что в словаре размещено 256 наиболее часто встречающихся слов, т.е. весь массив из 4-разрядных слов разделен на 2 подмассива: подмассив {X₄}¹, состоящий из 2⁸ комбинаций, и подмассив {X₄}², состоящий из остальных комбинаций и находящийся вне словаря.

Очевидно, что в силу принятого разделения принцип кодирования слов обоих подмассивов должен быть разным: каждому из слов {X₄}¹ должна соответствовать фиксированная бинарная последовательность из 8 бит плюс дополнительный символ (например 0), который дописывается впереди как флаг, что в сумме дает 9 бит. Аналогично рассуждая, слова второго подмассива можно заменить 20-разрядным кодом плюс флаг («1»), что в сумме дает 21 бинарный символ.

Если предположить, что вероятность появления в тексте каждого из слов словаря равна P_с, а каждого из остальных слов – (P_с– 1), то можем дать вероятностно-символьную оценку принятому принципу построения словаря:

В соответствии с этим можно определить, каким должно быть P, чтобы размещение определенных слов в словаре дало нужный эффект (в сравнении с методом размещения в словаре всех 2²⁰ слов). Очевидно, если мы разместим все слова в словаре, то значение С составит 20. Следовательно, нужно решить простое неравенство:

В общем случае при построении словаря исходят из следующих критериев:

1) требуемая скорость кодирования комбинаций (сжатия) и скорость обратного преобразования: чем больше словарь, тем скорость ниже;

2) размеры требуемой памяти: чем больше словарь, тем больше размер требуемой памяти для хранения словаря;

3) эффективность сжатия в первом приближении можно оценить параметром С.

Наилучшим является подход, при котором словарь строится под тип данных. Важнейшей проблемой при проектировании словарной схемы является выбор размера кодового словаря.

В связи с этим часто ограничение накладывается на размер фраз, помещаемых в словарь. Относительно размера фраз составление словаря может быть статическим, полуадаптивным и адаптивным.

Способ разбиения текста на фразы для их дальнейшего кодирования называется разбором текста.

Статический (неизменный) словарь строится предварительно для разнообразных типов документов и практически не изменяется. Полуадаптивный алгоритм предполагает создание словаря под конкретный тип документов. Адаптивный алгоритм строит словарь под каждый документ.

Важнейшей особенностью адаптивного (и в определенной степени – полуадаптивного) словаря является необходимость его передачи вместе со сжатой информацией.

4.2.4. Метод Лемпеля – Зива. До появления метода, описанного в 1977 г. Лемпелем и Зивом (Lempel, Ziv), все методы были в основном статическими.

Важнейшей особенностью метода Лемпеля – Зива было то, что не требуется передавать словарь, создаваемый под каждый документ. Этот словарь формально становится частью сжатой информации.

Сейчас созданы и составляют основу всех известных компьютерных архиваторов многочисленные модификации первоначального метода, известного как LZ77. Основой метода является поиск комбинаций, которые уже встречались, и замена того повтора на комбинации символов (p, q), где p – индекс начала комбинации в передаваемом документе, а q – длина этой повторяющейся комбинации.

Преобразование информации заключается в «прохождении» текста через два окна и параллельном анализе символов с текущим словарем. Общая схема реализации алгоритма показана на рис. 4.1.

Как правило, n (общая длина двух окон, называемых буферами) составляет и тысячи символов. Окно 02 – буфер данных, в него «въезжают» данные (исходный текст), которые нужно сжимать, кодировать. Далее эти данные «въезжают» в окно 01 – словарь.

Преобразование осуществляется по принципу размещения и передачи исходного сообщения через буфер, который делится на две части: буфер данных (буфер кодирования) и словарь.

 

 

Рис. 4.1. Иллюстрация общего принципа преобразования данных

по методу Лемпеля – Зива

Принцип состоит в том, чтобы выявить в тексте повторяющиеся комбинации. Анализируемые данные находятся в буфере кодирования, а обнаруженные ранее повторения – в словаре. Найденный повторяющийся ряд символов в буфере данных заменяется в основном парой (p, q) символов. Кроме этого, к данной паре добавляется еще один символ (с _i ), который является частью потока X _k и следует за найденным повторением в буфере данных. Буфер работает по принципу регистра сдвига.

⇐ Предыдущая12345Следующая ⇒

Поделиться:

Популярное:

1. При изотермическом сжатии температура постоянная и от воздуха отводится вся теплота, которая выделяется в процессе сжатия.
2. Приёмы сжатия (компрессии ) текста
3. Статистические методы сжатия