Преобразование MTF
| Определение: |
| Преобразование MTF (англ. move-to-front, движение к началу) — алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения эффективности последующего кодирования. |
Описание алгоритма
Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.
Современные алгоритмы (например, bzip2[1]) перед алгоритмом MTF используют алгоритм BWT, поэтому в качестве примера рассмотрим строку "BCABAAA", полученную из строки "ABACABA" в результате преобразования Барроуза-Уиллера. Первый символ строки 'B' является вторым элементом алфавита "ABC", поэтому на вывод подаётся . После перемещения 'B' в начало алфавита тот принимает вид "BAC". Дальнейшая работа алгоритма показана в таблице:
| Символ | Список | Вывод |
|---|---|---|
| B | ABC | 1 |
| C | BAC | 2 |
| A | CBA | 2 |
| B | ACB | 2 |
| A | BAC | 1 |
| A | ABC | 0 |
| A | ABC | 0 |
Таким образом, результат работы алгоритма: "1222100".
Данный алгоритм работает за , где — размер алфавита, — длина строки, что не очень быстро. Этот алгоритм можно реализовать за .
Описание алгоритма за O(N log(N+M))
Идея
Пусть дан алфавит размером и строка длиной . Заведем массив и последние ячеек заполним единицами. Запомним для каждого символа алфавита позицию в нашем массиве. Например, , , ... , .
При обработке -го символа посчитаем и выпишем сумму на отрезке , поменяем значения ячеек и местами, также стоит поменять значение в ячейке на .
Чтобы добиться сложности алгоритма нужно использовать дерево отрезков или подобное.
Псевдокод
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
Обратное преобразование
Пусть даны строка "1222100" и исходный алфавит "ABC". Символ с номером в алфавите — это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером в алфавите — это 'A', поэтому 'A' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.
| Символ | Список | Вывод |
|---|---|---|
| 1 | ABC | B |
| 2 | BAC | C |
| 2 | CBA | A |
| 2 | ACB | B |
| 1 | BAC | A |
| 0 | ABC | A |
| 0 | ABC | A |
Значит, исходная строка "BCABAAA".
Применение
Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, самыми частыми символами которого будут нули. Без MTF нас подстерегают разного рода трудности в решении проблемы адаптации к данным, поскольку в разных местах данных, полученных на выходе BWT-преобразования, разные символы являются преобладающими. Зачастую мы встречаемся с последовательностями типа "bbbbbcccccdddddaaaaa".
Попробуем сжать эту последовательность при помощи, например, метода Хаффмана. Вероятности всех четырех символов в данном примере равны . Легко посчитать, что в результате кодирования мы получим последовательность длиной бит.
Теперь проделаем то же самое со строкой, подвергнутой 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 |
В результате сжатия получаем последовательность длиной бит. Стоит заметить, что выигрыш от применения арифметического кодирования для данного примера будет еще значительней.
