Изменения
→Применение
{{Определение|definition ='''Движение к началуПреобразование MTF''' (англ. ''move-to-front'', MTFдвижение к началу) — преобразование {{---}} алгоритм кодирования, используемый для кодирования предварительной обработки данных (обычно потока байтов) разработанное перед сжатием, разработанный для улучшения производительности энтропийного эффективности последующего кодирования. При хорошей реализации, оно используется как дополнительный шаг в алгоритмах сжатия данных.}}== Описание алгоритма ==
{| 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>.
Данный алгоритм работает за <tex>O(N \cdot M)</tex>, где <tex>M</tex> {{---}} размер алфавита, <tex>N</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(N\log M)</tex>.
== Описание алгоритма за O(N log M) ==
|}
Значит, исходная строка <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.