Изменения
→Применение
{{Определение|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) ==----Основной идеей преобразования является замена каждого входного символа его номером в специальном стэке недавно использованных символов. Последовательности идентичных символов, к примеру, будут заменены оригинальным алгоритмом (начиная со второго символа) на последовательность нулей. Если же символ долго не появлялся во входной последовательности, он будет заменен большим числом. Преобразование заменяет последовательность входных символов на последовательность целых чисел, если во входных данных было много локальных корреляций, то среди этих чисел будут преобладать небольшие, лучше сжимаемые энтропийным кодированием, чем исходные данные.Алгоритм впервые описан в работе. Изначально алгоритм назывался «стопка книг» («book stack»).Часто используется при преобразовании байтов. Изначально каждое возможное значение байта записывается в список, в ячейку с номером равным значению байта, т.е (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. Первый обработанный символ заменяется самим собой, после чего элемент, соответствующий этому символу перемещается в голову списка (сдвигая элементы с 0 по свое положение на 1 вправо). Последующие символы кодируются номером элемента, содержащего их значение. После кодирования каждого символа эти элементы также продвигаются к голове списка.
Пусть дан алфавит размером <tex>M</tex> и строка <tex>S</tex> длиной <tex>N</tex>. Запомним для каждого символа алфавита свой ключ. Изначально <tex>\mathtt{| | keys}['a'] = 0</tex>, <tex>\mathtt{| borderkeys}['b'] ="1" |+ Coder !style="background: #FFCB00"|Symbol||style="background: #FFCB00"|Code||style</tex>, <tex>\dots</tex> , <tex>\mathtt{keys}['z'] ="background: #FFCB00"|List |- |a||0||a b c d |M- |b||1||b a c d |- |a||1||a b c d |- |a||0||a b c d |- |c||2||c a b d |- |a||1||a c b d |- |b||2||b a c d |- |a||1||a b c d |- |d||3|| d a b c |- |-}</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>MTF^{-1}(S) =BCABAAA</tex>. == Ссылки Применение == Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, самыми частыми символами которого будут нули. Без MTF нас подстерегают разного рода трудности в решении проблемы адаптации к данным, поскольку в разных местах данных, полученных на выходе [[Преобразование Барроуза-Уиллера|BWT-преобразования]], разные символы являются преобладающими. Зачастую мы встречаемся с последовательностями типа "bbbbbcccccdddddaaaaa". Попробуем сжать эту последовательность при помощи, например, [[Алгоритм Хаффмана|метода Хаффмана]]. Вероятности всех четырех символов в данном примере равны <tex>1/4</tex>. Легко посчитать, что в результате кодирования мы получим последовательность длиной <tex>20\cdot2 =40</tex> бит. Теперь проделаем то же самое со строкой, подвергнутой MTF-преобразованию (предположим, начальный алфавит выглядит как ''"abcd"''). ''"bbbbbcccccdddddaaaaa"'' {{---}} исходная строка ''"10000200003000030000"'' {{---}} строка после MTF {| class="wikitable"! Символ || Частота || Вероятность || Код Хаффмана|-| 0 || 16 || 4/5 || 0|-| 1 || 1 || 1/20 || 110|-| 2 || 1 || 1/20 || 111|-| 3 || 2 || 1/10 || 10|} В результате сжатия получаем последовательность длиной <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.
