Изменения

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

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

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

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

Данный алгоритм работает за Вот примерная реализация этого алгоритма. Здесь массив <tex>O(N \cdot M)mathtt{alphabet}</tex>, где хранит количество символов перед символом <tex>NS[i]</tex> {{---}} размер алфавита, <tex>MN</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(N</tex><tex>\log</tex><tex>M)S</tex>.

== Описание алгоритма за O '''list<int>''' mtf(NlogN): '''list<int>''' result(N+M) '''for''' i = 1 '''to''' N result.append(alphabet[S[i]]) == помещаем символ S[i] в начало алфавита=== Идея === '''return''' result

Пусть дан алфавит размером <tex>M</tex> и строка <tex>S</tex> длиной Данный алгоритм работает за <tex>O(N</tex>. Заведем массив <tex>used[1..N+\cdot M])</tex> и последние , где <tex>M</tex> ячеек заполним единицами. Запомним для каждого символа {{---}} размер алфавита позицию в нашем массиве. Например, <tex>alphabet['a'] = N+1</tex>, <tex>alphabet['b'] = N+2</tex>{{---}} длина строки, что не очень быстро... , Этот алгоритм можно реализовать за <tex>alphabet['z'] = O(N+\log M)</tex>.

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

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

Пусть дан алфавит размером <tex>M</tex> и строка <tex>S</tex> длиной <tex>N</tex>. Запомним для каждого символа алфавита свой ключ. Изначально <tex>\mathtt{keys}['a'] =0</tex>, <tex>\mathtt{keys}['b'] =1</tex>, <tex>\dots</tex> , <tex>\mathtt{keys}['z'] = Псевдокод ===M-1</tex>. Соединим все вершины в дерево по ключу.

'''list<int>''' used(N+M)minkey = 0 '''for''' i = 1 0 '''to''' M N result.append(findanswer(S[i])) <font color=darkgreen> //Заполняем последние N ячеек единицамиСчитаем ответ</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>\mathtt{findanswer}</tex> считает ответ так: если при спуске из вершины дерева мы должны идти вправо, то прибавляем к ответу количество вершин левого поддерева + 1, иначе ничего не добавляем к ответу. Функции <tex>\mathtt{split}</tex> и <tex>\mathtt{merge}</tex> {{---}} стандартные функции для [[Декартово_дерево|декартова дерева]]. <tex>\mathtt{minkey}</codetex>{{---}} число, которое меньше любого ключа дерева.

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

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

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

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

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

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

== Ссылки См. также == * [[Преобразование Барроуза-Уиллера]]* [[Алгоритм LZW]] == Примечания ==<references />

* # [http://compression.ru/arctest/descript/bwt-faq.htm Burrows Wheeler Transform FAQ]# [http://ru.wikipedia.org/wiki/Move-To-Front Move-To-Front (Википедия)]# Ryabko, B. Ya. ''Data compression by means of a «book stack»'', Problems of Information Transmission, 1980, v. 16: (4), pp.&nbsp;265–269.# 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.