Изменения

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

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

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

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

Данный алгоритм работает за <tex>O(\mathtt{N} \cdot \mathtt{M})</tex>, где <tex>\mathtt{N}M</tex> {{---}} размер алфавита, <tex>\mathtt{M}N</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(\mathtt{N}\log(\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}M</tex>-го символа посчитаем и выпишем сумму на отрезке строка <tex>[1, \mathtt{alphabet}[\mathtt{S}[\mathtt{i}]] - 1]</tex>, поменяем значения ячеек длиной <tex>N</tex>. Запомним для каждого символа алфавита свой ключ. Изначально <tex>\mathtt{usedkeys}[\mathtt{N-i}+1'a']= 0</tex> и , <tex>\mathtt{used}[\mathtt{alphabet}[\mathtt{Skeys}[\mathtt{i}]]'b']= 1</tex> местами, также стоит поменять значение в ячейке <tex>\mathtt{alphabet}[\mathtt{S}[\mathtt{i}]]dots</tex> на , <tex>\mathtt{Nkeys}['z'] = M-i}+1</tex>. Соединим все вершины в дерево по ключу.

'''list<int>''' used(N+M)minkey = 0 '''for''' i = 1 0 '''to''' M N result.append(findanswer(S[i])) <font color=darkgreen> //Заполняем последние M ячеек единицамиСчитаем ответ</font color=darkgreen> used[i+N] = 1 '''for''' i cur = 1 '''to''' N result.append(sumfind(1, alphabetkeys[S[i]] - 1)) <font color=darkgreen> //Запоминаем ответНаходим вершину в дереве </font color=darkgreen> swapsplit(used[N-i+1], used[alphabet[S[i]]]cur.key) <font color=darkgreen> //Меняем значенияВырезаем вершину из дерева</font color=darkgreen> alphabet[S[i]] min_key-- <font color= Ndarkgreen> //Уменьшаем минимально-i+1 возможный ключ</font color=darkgreen> cur.key = minkey <font color=darkgreen> //Изменяем позицию символа Ставим ключ в массивенайденной вершине на минимальный</font color=darkgreen> merge(cur, tree) <font color=darkgreen> //Объединяем нашу вершину и дерево по ключу</font color=darkgreen>

Функцию Функция <tex>sum\mathtt{findanswer}</tex> можно реализовывать по-разномусчитает ответ так: если при спуске из вершины дерева мы должны идти вправо, то прибавляем к ответу количество вершин левого поддерева + 1, иначе ничего не добавляем к ответу.

Функции <codetex> '''int''' sum(left, right) result = 0 '''for''' i = left '''to''' right result = result + used[i] '''return''' result\mathtt{split}</tex> и <tex>\mathtt{merge}</codetex>{{---}} стандартные функции для [[Декартово_дерево|декартова дерева]].

Такая реализация работает за <tex>O(right-left)</tex>, общая сложность алгоритма равна <tex>O(\mathtt{Nminkey} \cdot \mathtt{M})</tex> Но можно находить сумму на отрезке при помощи [[Дерево_отрезков._Построение | дерева отрезков]], что сократит время работы до <tex>O(\log(\mathtt{right{---left}))</tex>} число, которое меньше любого ключа дерева. Итого, общая сложность будет равна <tex>O(\mathtt{N}\log(\mathtt{N+M}))</tex>

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

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

| 1 || 2 1 || 1/10 20 || 10110

| 2 || 1 || 1/20 || 110111

| 3 || 1 2 || 1/20 10 || 11110

== Ссылки == * # [http://compression.ru/arctest/descript/bwt-faq.htm Burrows Wheeler Transform FAQ] * # [http://ru.wikipedia.org/wiki/Move-To-Front Move-To-Front (Википедия)] == Литература ==