Преобразование MTF

Определение:

Преобразование MTF (move-to-front, движение к началу) — алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения производительности последующего кодирования.

Описание алгортима

Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.

Современные алгоритмы (например, bzip2) перед алгоритмом MTF используют алгоритм BWT, поэтому в качестве примера рассмотрим строку [math]s = [/math]"BCABAAA", полученную из строки "ABACABA" в результате преобразования Барроуза-Уиллера. Первый символ строки [math]s[/math] 'B' является вторым элементом алфавита "ABC", поэтому на вывод подаётся 1. После перемещения 'B' в начало алфавита тот принимает вид "BAC". Дальнейшая работа алгоритма показана в таблице:

Символ	Список	Вывод
B	ABC	1
C	BAC	2
A	CBA	2
B	ACB	2
A	BAC	1
A	ABC	0
A	ABC	0

Таким образом, результат работы алгоритма: [math]MTF(s) = [/math] "1222100".

Обратное преобразование

Пусть даны строка [math]s = [/math]"1222100" и исходный алфавит "ABC". Символ с номером 1 в алфавите — это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером 2 в алфавите — это 'A', поэтому 'A' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.

Символ	Список	Вывод
1	ABC	B
2	BAC	C
2	CBA	A
2	ACB	B
1	BAC	A
0	ABC	A
0	ABC	A

Значит, исходная строка [math]MTF^{-1}(s) = [/math]"BCABAAA".

Применение

Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, самыми частыми символами которого будут нули. Без MTF нас подстерегают разного рода трудности в решении проблемы адаптации к данным, поскольку в разных местах данных, полученных на выходе BWT-преобразования, разные символы являются преобладающими. Зачастую мы встречаемся с последовательностями типа "bbbbbcccccdddddaaaaa".

Попробуем сжать эту последовательность при помощи, например, метода Хаффмана. Вероятности всех четырех символов в данном примере равны 1/4. Легко посчитать, что в результате кодирования мы получим последовательность длиной [math]20\cdot2 = 40[/math] бит.

Теперь проделаем то же самое со строкой, подвергнутой MTF-преобразованию (предположим, начальный алфавит выглядит как "abcd").

"bbbbbcccccdddddaaaaa" — исходная строка

"10000200003000030000" — строка после MTF

Символ	Частота	Вероятность	Код Хаффмана
0	16	4/5	0
1	2	1/10	10
2	1	1/20	110
3	1	1/20	111

В результате сжатия получаем последовательность длиной [math]16\cdot1 + 2\cdot2 + 3\cdot2 = 26[/math] бит. Стоит заметить, что выигрыш от применения арифметического кодирования для данного примера будет еще значительней.

Ссылки

• Burrows Wheeler Transform FAQ

• Move-To-Front (Википедия)