Изменения
→Применение
{{Определение|definition ='''Преобразование MTF''' '''Движение к началу''' (англ. ''move-to-front'', MTFдвижение к началу) — преобразование {{---}} алгоритм кодирования, используемый для кодирования предварительной обработки данных (обычно потока байтов) разработанное перед сжатием, разработанный для улучшения производительности энтропийного эффективности последующего кодирования. При хорошей реализации, оно используется как дополнительный шаг в алгоритмах сжатия данных.}}== Описание алгоритма ==
Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. <tex>(0, 1, 2, 3, \dots, 255)</tex>. В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.
Современные алгоритмы (например, bzip2<ref>[http://ru.wikipedia.org/wiki/Bzip2 {{---}} bzip2]</ref>) перед алгоритмом MTF используют [[преобразование Барроуза-Уиллера|алгоритм BWT]], поэтому в качестве примера рассмотрим строку <tex>S = BCABAAA</tex>, полученную из строки ''"ABACABA"'' в результате [[Преобразование Барроуза-Уиллера|преобразования Барроуза-Уиллера]]. Первый символ строки <tex>S</tex> 'B' является вторым элементом алфавита ''"ABC"'', поэтому на вывод подаётся <tex>1</tex>. После перемещения '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) = 1222100</tex>.
Вот примерная реализация этого алгоритма. Здесь массив <tex>\mathtt{alphabet}</tex> хранит количество символов перед символом <tex>S[i]</tex>, <tex>N</tex> {{---}} длина строки <tex>S</tex>.
'''list<int>''' mtf(N):
'''list<int>''' result(N)
'''for''' i = 1 '''to''' N
result.append(alphabet[S[i]])
помещаем символ S[i] в начало алфавита
'''return''' result
Данный алгоритм работает за <tex>O(N \cdot M)</tex>, где <tex>M</tex> {{---}} размер алфавита, <tex>N</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(N\log M)</tex>.
== Описание алгоритма за O(N log M) ==
Для решения будем использовать [[Декартово_дерево | декартово дерево]].
Пусть дан алфавит размером <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>''' mtf(N):
'''list<int>''' result(N)
minkey = 0
'''for''' i = 0 '''to''' N
result.append(findanswer(S[i])) <font color=darkgreen> //Считаем ответ</font color=darkgreen>
cur = find(keys[S[i]])<font color=darkgreen> //Находим вершину в дереве </font color=darkgreen>
split(cur.key) <font color=darkgreen> //Вырезаем вершину из дерева</font color=darkgreen>
min_key-- <font color=darkgreen> //Уменьшаем минимально-возможный ключ</font color=darkgreen>
cur.key = minkey <font color=darkgreen> //Ставим ключ в найденной вершине на минимальный</font color=darkgreen>
merge(cur, tree) <font color=darkgreen> //Объединяем нашу вершину и дерево по ключу</font color=darkgreen>
'''return''' result
Функция <tex>\mathtt{findanswer}</tex> считает ответ так: если при спуске из вершины дерева мы должны идти вправо, то прибавляем к ответу количество вершин левого поддерева + 1, иначе ничего не добавляем к ответу.
Функции <tex>\mathtt{split}</tex> и <tex>\mathtt{merge}</tex> {{---}} стандартные функции для [[Декартово_дерево|декартова дерева]].
== Обратное преобразование ==
Пусть даны строка <tex>S = 1222100</tex> и исходный алфавит ''"ABC"''. Символ с номером <tex>1</tex> в алфавите {{---}} это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером <tex>2</tex> в алфавите {{---}} это 'C', поэтому 'C' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.
{| 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
|}
Значит, исходная строка <nowikitex> Изначально каждое возможное значение байта записывается в список, в ячейку с номером равным значению байта, т.е (0, MTF^{-1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. Первый обработанный символ заменяется самим собой, после чего элемент, соответствующий этому символу перемещается в голову списка }(сдвигая элементы с 0 по свое положение на 1 вправоS). Последующие символы кодируются номером элемента, содержащего их значение. После кодирования каждого символа эти элементы также продвигаются к голове списка. = BCABAAA</nowikitex>.
==Применение = Coder и Decoder===----
Попробуем сжать эту последовательность при помощи, например, [[Алгоритм Хаффмана|метода Хаффмана]]. Вероятности всех четырех символов в данном примере равны <tex>1/4</tex>. Легко посчитать, что в результате кодирования мы получим последовательность длиной <tex>20\cdot2 = 40</tex> бит.
Теперь проделаем то же самое со строкой, подвергнутой MTF-преобразованию (предположим, начальный алфавит выглядит как ''"abcd"'').
|}
В результате сжатия получаем последовательность длиной <tex>16\cdot1 + 2\cdot2 + 3\cdot2 =26</tex> бит. Стоит заметить, что выигрыш от применения [[Арифметическое кодирование|арифметического кодирования]] для данного примера будет еще значительней. == Ссылки См. также == * [[Преобразование Барроуза-Уиллера]]* [[Алгоритм 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. 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.