10
правок
Изменения
Нет описания правки
Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.
Современные алгоритмы (например, [http://ru.wikipedia.org/wiki/Bzip2 bzip2]) перед алгоритмом MTF используют [[преобразование Барроуза-Уиллера|алгоритм BWT]], поэтому в качестве примера рассмотрим строку <tex>s \mathtt{S} = </tex>''"BCABAAA"'', полученную из строки ''"ABACABA"'' в результате [[Преобразование Барроуза-Уиллера|преобразования Барроуза-Уиллера]]. Первый символ строки <tex>s\mathtt{S}</tex> 'B' является вторым элементом алфавита ''"ABC"'', поэтому на вывод подаётся <tex>1</tex>. После перемещения 'B' в начало алфавита тот принимает вид ''"BAC"''. Дальнейшая работа алгоритма показана в таблице:
{| class="wikitable"
|}
Таким образом, результат работы алгоритма: <tex>MTF(s\mathtt{S}) = </tex> ''"1222100"''.
Данный алгоритм работает за <tex>O(\mathtt{N } \cdot \mathtt{M})</tex>, где <tex>\mathtt{N}</tex> {{---}} размер алфавита, <tex>\mathtt{M}</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(\mathtt{N</tex><tex>}\log</tex><tex>(\mathtt{N+M}))</tex>.
== Описание алгоритма за O(N log(N+M)) ==
=== Идея ===
Пусть дан алфавит размером <tex>\mathtt{M}</tex> и строка <tex>\mathtt{S}</tex> длиной <tex>\mathtt{N}</tex>. Заведем массив <tex>\mathtt{used}[1..\mathtt{N+M}]</tex> и последние <tex>\mathtt{M}</tex> ячеек заполним единицами. Запомним для каждого символа алфавита позицию в нашем массиве. Например, <tex>\mathtt{alphabet}['a'] = \mathtt{N}+1</tex>, <tex>\mathtt{alphabet}['b'] = \mathtt{N}+2</tex>, ... , <tex>\mathtt{alphabet}['z'] = \mathtt{N+M}</tex>.
При обработке <tex>\mathtt{i}</tex>-го символа посчитаем и выпишем сумму на отрезке <tex>[1, \mathtt{alphabet}[\mathtt{S}[\mathtt{i}]] - 1]</tex>, поменяем значения ячеек <tex>\mathtt{used}[\mathtt{N-i}+1]</tex> и <tex>\mathtt{used}[\mathtt{alphabet}[\mathtt{S}[\mathtt{i}]]]</tex> местами, также стоит поменять значение в ячейке <tex>\mathtt{alphabet}[\mathtt{S}[\mathtt{i}]]</tex> на <tex>\mathtt{N-i}+1</tex>.
Чтобы добиться сложности алгоритма <tex>O(\mathtt{N}</tex><tex>\log</tex><tex>(\mathtt{N+M}))</tex> нужно использовать дерево отрезков или подобное.
=== Псевдокод ===
== Обратное преобразование ==
Пусть даны строка <tex>\mathtt{s } = </tex>''"1222100"'' и исходный алфавит ''"ABC"''. Символ с номером <tex>1 </tex> в алфавите {{---}} это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером <tex>2 </tex> в алфавите {{---}} это 'A', поэтому 'A' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.
{| class ="wikitable"
|}
Значит, исходная строка <tex>MTF^{-1}(s\mathtt{S}) = </tex>''"BCABAAA"''.
== Применение ==
Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, самыми частыми символами которого будут нули. Без MTF нас подстерегают разного рода трудности в решении проблемы адаптации к данным, поскольку в разных местах данных, полученных на выходе [[Преобразование Барроуза-Уиллера|BWT-преобразования]], разные символы являются преобладающими. Зачастую мы встречаемся с последовательностями типа "bbbbbcccccdddddaaaaa".
Попробуем сжать эту последовательность при помощи, например, [[Алгоритм Хаффмана|метода Хаффмана]]. Вероятности всех четырех символов в данном примере равны <tex>1/4</tex>. Легко посчитать, что в результате кодирования мы получим последовательность длиной <tex>20\cdot2 = 40</tex> бит.
Теперь проделаем то же самое со строкой, подвергнутой MTF-преобразованию (предположим, начальный алфавит выглядит как ''"abcd"'').
