Изменения

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

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

Изначально каждое возможное значение байта записывается в списокСовременные алгоритмы (например, в ячейку с номером равным значению байта, тbzip2<ref>[http://ru.wikipedia.е (0org/wiki/Bzip2 {{---}} bzip2]</ref>) перед алгоритмом MTF используют [[преобразование Барроуза-Уиллера|алгоритм BWT]], 1поэтому в качестве примера рассмотрим строку <tex>S = BCABAAA</tex>, 2, 3, …, 255). В процессе обработки данных этот список изменяетсяполученную из строки ''"ABACABA"'' в результате [[Преобразование Барроуза-Уиллера|преобразования Барроуза-Уиллера]]. Первый обработанный символ заменяется самим собой, после чего элементстроки <tex>S</tex> 'B' является вторым элементом алфавита ''"ABC"'', соответствующий этому символу перемещается в голову списка (сдвигая элементы с 0 по свое положение поэтому на вывод подаётся <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) == Coder и Decoder===1222100</tex>.  Вот примерная реализация этого алгоритма. Здесь массив <tex>\mathtt{alphabet}</tex> хранит количество символов перед символом <tex>S[i]</tex>, <tex>N</tex> {{----}} длина строки <tex>S</tex>.

{| |'''list<int>''' mtf(N): {| border="1" '''list<int>''' result(N) |+ Coder !style="background: #FFCB00"|Symbol||style '''for''' i ="background: #FFCB00"|Code||style="background: #FFCB00"|List |- |a||0||a b c d |- |b||1||b a c d |-'''to''' N |a||1||a b c d result.append(alphabet[S[i]]) |- |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 |- помещаем символ S[i] в начало алфавита |-} '''return''' result

Для решения будем использовать [[Декартово_дерево | декартово дерево]]. Пусть дан алфавит размером <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{|borderkeys}['z'] ="M-1"</tex>. Соединим все вершины в дерево по ключу.   '''list<int>''' mtf(N): '''list<int>''' result(N) minkey = 0 |+ Decoder'''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> ! style merge(cur, tree) <font color=darkgreen> //Объединяем нашу вершину и дерево по ключу</font color="backgrounddarkgreen> '''return''' result Функция <tex>\mathtt{findanswer}</tex> считает ответ так:#FFCB00"если при спуске из вершины дерева мы должны идти вправо, то прибавляем к ответу количество вершин левого поддерева + 1, иначе ничего не добавляем к ответу. Функции <tex>\mathtt{split}</tex> и <tex>\mathtt{merge}</tex> {{---}} стандартные функции для [[Декартово_дерево|Code||styleдекартова дерева]]. <tex>\mathtt{minkey}</tex> {{---}} число, которое меньше любого ключа дерева. == Обратное преобразование == Пусть даны строка <tex>S =1222100</tex> и исходный алфавит ''"background:#FFCB00ABC"''. Символ с номером <tex>1</tex> в алфавите {{---}} это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером <tex>2</tex> в алфавите {{---}} это 'C', поэтому 'C' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично. {|Symbol||styleclass ="background:#FFCB00wikitable"|List ! Символ |- |0Список ||a||a b c dВывод |- |1||bA'''B'''C ||b a c dB |- |12 ||aBA'''C''' ||a b c dC |- |02 ||aCB'''A''' ||a b c dA |- |2||cAC'''B''' ||c a b dB |- |1||aB'''A'''C ||a c b dA |- |2||b|0 |b a c d |- |1||a'''A'''BC ||a b c dA |- |30 ||d'''A'''BC || d a b c |}A

Значит, исходная строка <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.&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.

{| | {| class="standard" ! |- |[http[Категория://www.arturocampos.com/ac_mtf.html "Move to front" by Arturo San Emeterio Campos Алгоритмы сжатия ] |- |[http://yury.name/internet/02ianote.pdf Преобразование Барроуза-Вилера] |- |http://ru.wikipedia.org/wiki/Move-To-Front |}