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

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

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

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

{| class="wikitable"
! Символ || Список || Вывод
|-
| B || A'''B'''C || 1
|-
| C || BA'''C''' || 2
|-
| A || CB'''A''' || 2
|-
| B || AC'''B''' || 2
|-
| A || B'''A'''C || 1
|-
| A || '''A'''BC || 0
|-
| A || '''A'''BC || 0
|}

Таким образом, результат работы алгоритма: <tex>MTF(s) = </tex> ''"1222100"''.

Данный алгоритм работает за <tex>O(N \cdot M)</tex>, где <tex>N</tex> {{---}} размер алфавита, <tex>M</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(N</tex><tex>\log</tex><tex>M)</tex>.

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

=== Идея ===

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

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

Чтобы добиться сложности алгоритма <tex>O(N</tex><tex>\log</tex><tex>(N+M))</tex> нужно использовать дерево отрезков или подобное.

=== Псевдокод ===

<code>
'''list<int>''' mtf(N):
'''list<int>''' result(N)
'''list<int>''' used(N+M)
'''for''' i = 1 '''to''' M //Заполняем последние N ячеек единицами
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
</code>

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

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

{| class ="wikitable"
! Символ || Список || Вывод
|-
| 1 || A'''B'''C || B
|-
| 2 || BA'''C''' || C
|-
| 2 || CB'''A''' || A
|-
| 2 || AC'''B''' || B
|-
| 1 || B'''A'''C || A
|-
| 0 || '''A'''BC || A
|-
| 0 || '''A'''BC || A
|}

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

== Применение ==

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

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

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

''"bbbbbcccccdddddaaaaa"'' {{---}} исходная строка

''"10000200003000030000"'' {{---}} строка после MTF

{| class="wikitable"
! Символ || Частота || Вероятность || Код Хаффмана
|-
| 0 || 16 || 4/5 || 0
|-
| 1 || 2 || 1/10 || 10
|-
| 2 || 1 || 1/20 || 110
|-
| 3 || 1 || 1/20 || 111
|}

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

== Ссылки ==

* [http://compression.ru/arctest/descript/bwt-faq.htm Burrows Wheeler Transform FAQ]

* [http://ru.wikipedia.org/wiki/Move-To-Front Move-To-Front (Википедия)]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Алгоритмы сжатия ]]