Изменения

Перейти к: навигация, поиск

Преобразование MTF

2162 байта добавлено, 05:19, 28 октября 2011
Нет описания правки
{{Определение|definition='''Движение к началуПреобразование MTF''' (англ. ''move-to-front'', MTFдвижение к началу) — преобразование {{---}} алгоритм кодирования, используемый для кодирования предварительной обработки данных (обычно потока байтов) разработанное перед сжатием, разработанный для улучшения производительности энтропийного последующего кодирования. При хорошей реализации, оно используется как дополнительный шаг в алгоритмах сжатия данных.}}
=== Алгоритм ===
Основной идеей преобразования является замена каждого входного символа его номером в специальном стэке недавно использованных символов. Последовательности идентичных символов, к примеру, будут заменены оригинальным алгоритмом (начиная со второго символа) на последовательность нулей. Если же символ долго не появлялся во входной последовательности, он будет заменен большим числом. Преобразование заменяет последовательность входных символов на последовательность целых чисел, если во входных данных было много локальных корреляций, то среди этих чисел будут преобладать небольшие, лучше сжимаемые энтропийным кодированием, чем исходные данные.
Изначально каждое возможное значение байта записывается в список, в ячейку с номером равным значению байта, т.е (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. Первый обработанный символ заменяется самим собой, после чего элемент, соответствующий этому символу перемещается в голову списка (сдвигая элементы с 0 по свое положение на 1 вправо). Последующие символы кодируются номером элемента, содержащего их значение. После кодирования каждого символа эти элементы также продвигаются к голове списка.== Описание алгортима ==
=== Coder и Decoder===----Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.
{| | {| border=Рассмотрим действие алгоритма на примере алфавита ''"1ABC" |+ Coder !style'' и строки <tex>s =</tex>''"background: #FFCB00BCABAAA"|Symbol||style='', полученной из строки ''"background: #FFCB00ABACABA"'' в результате [[Преобразование Барроуза-Уиллера|Code||styleпреобразования Барроуза-Уиллера]]. Первый символ строки <tex>s =</tex> 'B' является вторым элементом алфавита, поэтому на вывод подаётся 1. После перемещения 'B' в начало алфавита тот принимает вид ''"backgroundBAC"''. Дальнейшая работа алгоритма показана в таблице: #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 |- |-}
{| class="wikitable"
! Символ || Список || Вывод
|-
| B || ABC || 1
|-
| C || BAC || 2
|-
| A || CBA || 2
|-
| B || ACB || 2
|-
| A || BAC || 1
|-
| A || ABC || 0
|-
| A || ABC || 0
|}
 
Таким образом, результат работы алгоритма: <tex>MTF(s) = </tex> ''"1222100"''.
 
 
== Обратное преобразование ==
 
Пусть даны строка <tex>s = </tex>''"1222100"'' и исходный алфавит ''"ABC"''. Символ с номером 1 в алфавите {{---}} это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером 2 в алфавите {{---}} это 'A', поэтому 'A' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.
 
{| class="wikitable"
! Символ || Список || Вывод
|-
| 1 || ABC || B
|-
| 2 || BAC || C
|-
| 2 || CBA || A
|-
| 2 || ACB || B
|-
| 1 || BAC || A
|-
| 0 || ABC || A
|-
| 0 || ABC || A
|}
 
Значит, исходная строка <tex>MTF^{-1}(s) = </tex>''"BCABAAA"''.
 
== Применение ==
 
Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, самыми частыми символами которого будут нули. Без MTF нас подстерегают разного рода трудности в решении проблемы адаптации к данным, поскольку в разных местах данных, полученных на выходе [[Преобразование Барроуза-Уиллера|BWT-преобразования]], разные символы являются преобладающими. Зачастую мы встречаемся с последовательностями типа "bbbbbcccccdddddaaaaa".
 
Попробуем сжать эту последовательность при помощи, например, [[Алгоритм Хаффмана|метода Хаффмана]]. Вероятности всех четырех символов в данном примере равны 1/4. Легко посчитать, что в результате кодирования мы получим последовательность длиной 20*2 = 40 бит.
 
Теперь проделаем то же самое со строкой, подвергнутой MTF-преобразованию (предположим, начальный алфавит выглядит как ''"abcd"'').
 
''"bbbbbcccccdddddaaaaa"'' {{---}} исходная строка
''"10000200003000030000"'' {{---}} строка после MTF
{|borderclass="1wikitable" |+ Decoder ! style="background:#FFCB00"|CodeСимвол ||style="background:#FFCB00"Частота |Symbol|Вероятность |style="background:#FFCB00"|ListКод Хаффмана |- |0||a16 ||a b c d 4/5 |- |1||b||b a c d0 |- |1||a||a b c d |- |0||a||a b c d |- |2||c||c a b d |- |1/10 ||a||a c b d10 |- |2||b||b a c d 1 |- |1/20 ||a||a b c d110 |- |3||d1 || d a b c 1/20 ||}111
|}
В результате сжатия получаем последовательность длиной 16*1 + 2*2 + 3*2 =26 бит. Стоит заметить, что выигрыш от применения [http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 арифметического кодирования] для данного примера будет еще значительней.  == Ссылки === * [http://compression.ru/arctest/descript/bwt-faq.htm Burrows Wheeler Transform FAQ]
* [http://ru.wikipedia.org/wiki/Move-To-Front Move-To-Front (Википедия)]
{| | {| 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 |}
Yulya3102
355
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/12173»

Навигация