Метод перемещения стопки книг

Дата: 2025-04-30; Просмотры: 2

Оценка:

0.00 из 5.00 — оценок

Скачиваний: 0

Скачать

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

Преобразование также известно под названием Move To Front (MTF). Суть его легко понять, если представить себе процесс перемещения книг в стопке, из которой время от времени берут нужную книгу и кладут наверх. Таким образом, наиболее часто используемые книги оказываются ближе к верхушке стопки.

Для примера произведем преобразование над примером, полученным в предыдущей главе после метода BWT. Пусть мы имеем алфавит из пяти букв, в упорядоченном виде они расположены в следующем порядке:

(а, б, д, к, р).

Первый символ из последовательности «р» находится в списке под номером 4, это число мы и записываем в выходной блок. Затем мы изменяем список таким образом, перенося символ «р» в вершину и сдвигая все элементы, находившиеся до него:

(р, а, б, д, к)

Следующий символ «д» оказывается в списке под номером 3. И так далее.

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

4 3 2 4 3 2 0 0 0 4 0

К слову, вспомним, что результат преобразования Барроуза – Уилера, как раз и представляет собой последовательность, в которой встречаются часто повторяющиеся символы. Такое преобразование увеличивает эффективность дальнейшего применения статистического кодера. Для сравнения возьмем последовательность с повторяющимися символами:

б б б б в в в в в г г г г г а а а а а б

Попробуем закодировать ее методом Хаффмана. Вероятности всех четырех символов в данной последовательности равны 0.25. Таким образом для кодирования каждого символа нам потребуется по 2 бита. Нетрудно посчитать, что длина выходного кода будет равна:

20 * 2 = 40 бит.

Теперь проделаем то же самое со строкой, подвергнутой MTF преобразованию:

б б б б в в в в в г г г г г а а а а а б

1 0 0 0 2 0 0 0 0 3 0 0 0 0 3 0 0 0 0 3

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

15 * 1 + 3 * 2 + 1 * 3 + 1 * 3 = 27 бит

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

В настоящее время, в различных модификациях и сочетаниях, два алгоритма – метод Хаффмана (или арифметическое кодирование) и метод Лемпеля-Зива – составляют основу всех коммерческих алгоритмов и программ.