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

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

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

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

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

Современные алгоритмы (например, bzip2) перед алгоритмом MTF используют алгоритм BWT, поэтому в качестве примера рассмотрим строку [math]S = BCABAAA[/math], полученную из строки "ABACABA" в результате преобразования Барроуза-Уиллера. Первый символ строки [math]S[/math] 'B' является вторым элементом алфавита "ABC", поэтому на вывод подаётся [math]1[/math]. После перемещения '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) = 1222100[/math].

Вот примерная реализация этого алгоритма. Здесь массив [math]\mathtt{alphabet}[/math] хранит количество символов перед символом [math]S[i][/math], [math]N[/math] — длина строки [math]S[/math].

list<int> mtf(N):
   list<int> result(N)
   for i = 1 to N
      result.append(alphabet[S[i]])
      помещаем символ S[i] в начало алфавита
   return result

Данный алгоритм работает за [math]O(N \cdot M)[/math], где [math]N[/math] — размер алфавита, [math]M[/math] — длина строки, что не очень быстро. Этот алгоритм можно реализовать за [math]O(N\log(N+M))[/math].

Описание алгоритма за O(N log(N+M))

Пусть дан алфавит размером [math]M[/math] и строка [math]S[/math] длиной [math]N[/math]. Заведем массив [math]\mathtt{used}[1..N+M][/math] и последние [math]M[/math] ячеек заполним единицами. Запомним для каждого символа алфавита позицию в нашем массиве. Например, [math]\mathtt{alphabet}['a'] = N+1[/math], [math]\mathtt{alphabet}['b'] = N+2[/math], ... , [math]\mathtt{alphabet}['z'] = N+M[/math].

При обработке [math]i[/math]-го символа посчитаем и выпишем сумму на отрезке [math][1, \mathtt{alphabet}[S[i]] - 1][/math], поменяем значения ячеек [math]\mathtt{used}[N-i+1][/math] и [math]\mathtt{used}[\mathtt{alphabet}[S[i]]][/math] местами, также стоит поменять значение в ячейке [math]\mathtt{alphabet}[S[i]][/math] на [math]N-i+1[/math].

list<int> mtf(N):
   list<int> result(N)
   list<int> used(N+M)
   for i = 1 to M                                      //Заполняем последние M ячеек единицами 
      used[i+N] = 1
   for i = 1 to N
      result.append(sum(1, alphabet[S[i]] - 1))        //Запоминаем ответ
      swap(used[N-i+1], used[alphabet[S[i]]])          //Меняем значения
      alphabet[S[i]] = N-i+1                           //Изменяем позицию символа в массиве
   return result

Функцию [math]\mathtt{sum}[/math] можно реализовывать по-разному.

int sum(left, right)
   result = 0
   for i = left to right
      result = result + used[i]
   return result

Такая реализация работает за [math]O(right-left)[/math], общая сложность алгоритма равна [math]O(N \cdot M)[/math] Но можно находить сумму на отрезке при помощи дерева отрезков, что сократит время работы до [math]O(\log(right-left))[/math]. Итого, общая сложность будет равна [math]O(N\log(N+M))[/math]

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

Пусть даны строка [math]S = 1222100[/math] и исходный алфавит "ABC". Символ с номером [math]1[/math] в алфавите — это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером [math]2[/math] в алфавите — это '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) = BCABAAA[/math].

Применение

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

Попробуем сжать эту последовательность при помощи, например, метода Хаффмана. Вероятности всех четырех символов в данном примере равны [math]1/4[/math]. Легко посчитать, что в результате кодирования мы получим последовательность длиной [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] бит. Стоит заметить, что выигрыш от применения арифметического кодирования для данного примера будет еще значительней.

Источники информации

1. Burrows Wheeler Transform FAQ
2. Move-To-Front (Википедия)
3. Ryabko, B. Ya. Data compression by means of a «book stack», Problems of Information Transmission, 1980, v. 16: (4), pp. 265–269.
4. Ryabko, B. Ya.; Horspool, R. Nigel; Cormack, Gordon V. Comments to: «A locally adaptive data compression scheme» by J. L. Bentley, D. D. Sleator, R. E. Tarjan and V. K. Wei. Comm. ACM 30 (1987), no. 9, 792—794.