Изменения

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

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

=== Алгоритм ===Современные алгоритмы (например, bzip2<ref>[http://ru.wikipedia.org/wiki/Bzip2 {{---}} bzip2]</ref>) перед алгоритмом MTF используют [[преобразование Барроуза-Уиллера|алгоритм BWT]], поэтому в качестве примера рассмотрим строку <nowikitex> Основной идеей S = BCABAAA</tex>, полученную из строки ''"ABACABA"'' в результате [[Преобразование Барроуза-Уиллера|преобразования является замена каждого входного символа его номером в специальном стэке недавно использованных символовБарроуза-Уиллера]]. Последовательности идентичных символов, к примеру, будут заменены оригинальным алгоритмом (начиная со второго символа) на последовательность нулей. Если же Первый символ долго не появлялся во входной последовательностистроки <tex>S</tex> 'B' является вторым элементом алфавита ''"ABC"'', он будет заменен большим числом. Преобразование заменяет последовательность входных символов поэтому на последовательность целых чисел, если во входных данных было много локальных корреляций, то среди этих чисел будут преобладать небольшие, лучше сжимаемые энтропийным кодированием, чем исходные данные.вывод подаётся <tex>1</nowikitex>. После перемещения '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<nowikiint> Изначально каждое возможное значение байта записывается ''' 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> , 2<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, 3tree) <font color=darkgreen> //Объединяем нашу вершину и дерево по ключу</font color=darkgreen> '''return''' result Функция <tex>\mathtt{findanswer}</tex> считает ответ так: если при спуске из вершины дерева мы должны идти вправо, …то прибавляем к ответу количество вершин левого поддерева + 1, 255)иначе ничего не добавляем к ответу. В процессе обработки данных этот список изменяется Функции <tex>\mathtt{split}</tex> и <tex>\mathtt{merge}</tex> {{---}} стандартные функции для [[Декартово_дерево|декартова дерева]]. Первый обработанный символ заменяется самим собой <tex>\mathtt{minkey}</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|} Значит, исходная строка <tex>MTF^{-1 вправо}(S)= BCABAAA</tex>. Последующие символы кодируются номером элемента == Применение == Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, содержащего их значениесамыми частыми символами которого будут нули. После кодирования каждого символа эти элементы также продвигаются Без MTF нас подстерегают разного рода трудности в решении проблемы адаптации к голове спискаданным, поскольку в разных местах данных, полученных на выходе [[Преобразование Барроуза-Уиллера|BWT-преобразования]], разные символы являются преобладающими. Зачастую мы встречаемся с последовательностями типа "bbbbbcccccdddddaaaaa". </nowiki>

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

{| | {| border=Теперь проделаем то же самое со строкой, подвергнутой MTF-преобразованию (предположим, начальный алфавит выглядит как ''"1abcd" |+ Coder !style="background: #FFCB00"|Symbol||style="background: #FFCB00"|Code||style="background: #FFCB00"|List |- |a||0||a b c d |- |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 |- |-}'').

{|borderclass="1wikitable" |+ Decoder ! style="background:#FFCB00"|CodeСимвол ||style="background:#FFCB00"Частота |Symbol|Вероятность |style="background:#FFCB00"|ListКод Хаффмана |- |0||a||a b c d |- |116 ||b4/5 ||b a c d0 |- |1||a1 ||a b c d |- |0|1/20 |a||a b c d110 |- |2||c||c a b d 1 |- |1/20 ||a||a c b d111 |- |23 ||b||b a c d 2 |- |1/10 ||a||a b c d |- |3||d|| d a b c |}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 |}