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

Алгоритмы, использующие методы словарного сжатия, заменяют подстроки кодируемой последовательности символов ссылками в словарь на идентичные подстроки.

Рассмотрим метод LZ77, который является одним из наиболее распространенных словарных методов сжатия.

1. Выделить область памяти под буфер.

2. Выделить область памяти под словарь.

3. Заполнить буфер символами исходной последовательности

4. Определить максимальную часть буфера (L символов от начала буфера), совпадающих с частью словаря (L символов с позиции P в словаре).

5. Выдать тройку <L, P, S>, где S – (L + 1) – ый символ в буфере.

6. Переместить L + 1 символ из начала буфера (с удалением их в буфере) в конец словаря.

7. Переместить на освободившиеся позиции в начале буфера оставшиеся символы и дополнить его символами исходной последовательности.

8. Повторять пп. 4 – 7 до тех пор, пока буфер не станет пуст после выполнения п. 7.

Приведенный алгоритм является общим описанием метода. Его более конкретную реализацию рассмотрим на следующем примере.

Пример 5.10. Сжать методом LZ77 последовательность

aaaabaabbb.

Пусть буфер имеет длину 4 символа, а словарь – 8 символов.

1. Выделить память под буфер и словарь.

Буфер: пуст, словарь: пуст, последовательность: aaaabaabbb.

2. Заполнить буфер.

Буфер: aaaa, словарь: пуст, последовательность: baabbb.

3. Найти максимальную часть буфера от его начала, совпадающую с частью словаря. Так как словарь пуст, то длина найденной части равна 0.

4. Выдать тройку <0, 0, a>.

5. Изменить буфер, словарь и последовательность.

Буфер: aaab, словарь: a, последовательность: aabbb.

6. Найти максимальную часть буфера от его начала, совпадающую с частью словаря. Данная часть имеет длину 1.

7. Выдать тройку <1, 1, a>.

8. Изменить буфер, словарь и последовательность.

Буфер: abaa, словарь: aaa, последовательность: bbb.

9. Найти максимальную часть буфера от его начала, совпадающую с частью словаря. Данная часть имеет длину 1.

10. Выдать тройку <1, 1, b>.

11. Изменить буфер, словарь и последовательность.

Буфер: aabb, словарь: aaaab, последовательность: b.

12. Найти максимальную часть буфера от его начала, совпадающую с частью словаря. Данная часть имеет длину 3.

13. Выдать тройку <3, 3, b>.

14. Изменить буфер, словарь и последовательность.

Буфер: b, словарь: aaabaabb, последовательность: пуста.

15. Найти максимальную часть буфера от его начала, совпадающую с частью словаря. Данная часть имеет длину 1.

16. Выдать тройку <1, 4, U>, где U – признак отсутствия символа.

17. Изменить буфер, словарь и последовательность.

Буфер: пуст, словарь: aabaabbb, последовательность: пуста.

18. Так как буфер пуст, то процесс сжатия закончен.

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

<0, 0, a>, <1, 1, a>, <1, 1, b>, <3, 3, b>, <1, 4, U>.

5.3. Методы сжатия с потерями

Методы сжатия с потерями широко применяются при преобразовании аналоговой информации в цифровую форму. Например, часто используется следующий метод (рациональная выборка), который основывается на аппроксимации сигнала определенным аналитическим выражением. Предварительно сигнал подвергается равномерной дискретизации, а затем полученная дискретная последовательность фильтруется по заданному алгоритму. Обычно фильтрация заключается в нахождении выборок, амплитуды которых отличаются от значений, полученных с помощью аппроксимации, на величину ошибки, которая больше допустимой. Эти выборки считаются информативными и подлежат передаче или хранению, а остальные исключаются как несущественные. Полученная отфильтрованная последовательность выборок сжимается каким – нибудь методом без потерь.

Пример 5.11. Дана последовательность выборок

10.1, 12.5, 12.3, 12.7, 13.1, 12.9.

Выполнить сжатие последовательности с ошибкой не более 0.5.

Будем в качестве значения аппроксимирующей зависимости использовать значение предыдущей выборки. Если текущая выборка отличается от нее на величину ошибки, то дальнейшие сравнения производятся с ее значением.

1. Прочитать значение 10.1. Зафиксировать это значение для последующих сравнений и передать его на выход значение.

2. Прочитать значение 12.5. Так как оно отличается от 10.1 на величину, превышающую 0.5, то зафиксировать его для последующих сравнений и передать на выход.

3. Прочитать значение 12.3. Это значение отличается от 12.5 менее, чем на величину 0.5. Поэтому на выход передается опять предыдущее значение.

4. Прочитать значение 12.7. Оно отличается от 12.5 менее, чем на величину 0.5. На выход передается значение 12.5.

5. Прочитать значение 13.1. Оно отличается от 12.5 на величину, превышающую 0.5. Поэтому это значение передается на выход и фиксируется для последующих сравнений.

6. Прочитать значение 12.9. Это значение отличается от 13.1 на величину, не превышающее 0.5. Поэтому на выход передается значение 13.1

Таким образом, на выходе сформирована следующая последовательность:

10.1, 12.5, 12.5, 12.5, 13.1, 13.1.

После применения метода RLE получается: <10.1, 1>, <12.5, 3>, <13.1, 2>.

Вопросы

5.1. Выполните классификацию методов сжатия по возможности адаптации к сжимаемым данным, симметричности операций кодирования и декодирования данных, допустимости искажений информации.

5.2. Опишите алгоритм RLE – кодирования.

5.3. Опишите алгоритм сжатия данных с представлением целых чисел. Приведите пример адаптивного варианта такого сжатия.

5.4. Опишите алгоритм энтропийного сжатия по Хаффмену. Приведите адаптивный вариант сжатия с использованием метода кодирования Шеннона-Фано.

5.5. Опишите арифметический метод сжатия.

5.6. Почему метод контекстного моделирования является более эффективным для длинных последовательностей символов, чем методы Хаффмена и арифметического сжатия?

5.7. Опишите метод словарного сжатия. Приведите пример его использования.

5.8. Приведите вариант сжатия с потерями информации.

Упражнения

5.1. Найдите коэффициент сжатия арифметическим методом последовательности ASCII – символов (т.е. каждый символ имеет длину 8 бит), которая имеет вид: abaaa.

5.2. Выполните сжатие последовательности символов из п. 5.1 методом RLE.

5.3. Приведите коды Фибоначчи для чисел 131, 148, 87, 17, 33.

5.4. Приведите последовательность кодов Хаффмена после выполнения адаптивного сжатия последовательности ASCII – символов, которая имеет вид: abaaabbb.

5.5. Выполните сжатие последовательности символов из п. 5.4 методом LZ77. Придумайте способ сокращения числа полей в кодовой тройке <длина, позиция, символ>.

5.6. Найти последовательность кодов при контекстном моделировании последовательности символов из п. 5.4. Считать, что максимальный порядок контекстной модели равен 2. При кодировании использовать метод Хаффмена.

5.7. Сжать последовательность выборок, полученных при первичном преобразовании в информационно – измерительной системе. Допускается сжатие с потерями информации с максимальной ошибкой 0.4. Последовательность выборок имеет вид: 10.1, 12.5, 11.9, 11.5, 11.7, 12, 12.1, 11.8, 11.4, 11.2, 10.9.