Преобразование MTF — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
'''Движение к началу''' (англ. move-to-front, MTF) — преобразование для кодирования данных (обычно потока байтов) разработанное для улучшения производительности энтропийного кодирования. При хорошей реализации, оно используется как дополнительный шаг в алгоритмах сжатия данных.
+
{{Определение
 +
|definition=
 +
'''Преобразование MTF''' (''move-to-front'', движение к началу) {{---}} алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения производительности последующего кодирования.
 +
}}
  
−
=== Алгоритм ===
 
−
Основной идеей преобразования является замена каждого входного символа его номером в специальном стэке недавно использованных символов. Последовательности идентичных символов, к примеру, будут заменены оригинальным алгоритмом (начиная со второго символа) на последовательность нулей. Если же символ долго не появлялся во входной последовательности, он будет заменен большим числом. Преобразование заменяет последовательность входных символов на последовательность целых чисел, если во входных данных было много локальных корреляций, то среди этих чисел будут преобладать небольшие, лучше сжимаемые энтропийным кодированием, чем исходные данные.
 
  
−
Изначально каждое возможное значение байта записывается в список, в ячейку с номером равным значению байта, т.е (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. Первый обработанный символ заменяется самим собой, после чего элемент, соответствующий этому символу перемещается в голову списка (сдвигая элементы с 0 по свое положение на 1 вправо). Последующие символы кодируются номером элемента, содержащего их значение. После кодирования каждого символа эти элементы также продвигаются к голове списка.
+
== Описание алгортима ==
  
−
=== Coder и Decoder===
+
Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.
−
----
 
  
−
{|
+
Рассмотрим действие алгоритма на примере алфавита ''"ABC"'' и строки <tex>s = </tex>''"BCABAAA"'', полученной из строки ''"ABACABA"'' в результате [[Преобразование Барроуза-Уиллера|преобразования Барроуза-Уиллера]]. Первый символ строки <tex>s = </tex> 'B' является вторым элементом алфавита, поэтому на вывод подаётся 1. После перемещения 'B' в начало алфавита тот принимает вид ''"BAC"''. Дальнейшая работа алгоритма показана в таблице:
−
|
 
−
{| border="1"
 
−
  |+ 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
 
−
  |-
 
−
 
−
  |-}
 
  
 +
{| 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
  
−
{|border="1"
+
{| class="wikitable"
−
    |+ Decoder
+
! Символ || Частота || Вероятность || Код Хаффмана
−
  ! style="background:#FFCB00"|Code||style="background:#FFCB00"|Symbol||style="background:#FFCB00"|List
+
|-
−
  |-
+
| 0 || 16 || 4/5 || 0
−
  |0||a||a b c d
+
|-
−
  |-
+
| 1 || 2 || 1/10 || 10
−
  |1||b||b a c d
+
|-
−
  |-
+
| 2 || 1 || 1/20 || 110
−
  |1||a||a b c d
+
|-
−
  |-
+
| 3 || 1 || 1/20 || 111
−
  |0||a||a b c d
 
−
  |-
 
−
  |2||c||c a b d
 
−
  |-
 
−
  |1||a||a c b d
 
−
  |-
 
−
  |2||b||b a c d
 
−
  |-
 
−
  |1||a||a b c d
 
−
  |-
 
−
  |3||d|| d a b c
 
−
 
 
−
|}
 
 
|}
 
|}
  
−
=== Ссылки ===
+
В результате сжатия получаем последовательность длиной 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
 
−
 
 
−
  |}
 

Версия 05:19, 28 октября 2011

Определение:
Преобразование MTF (move-to-front, движение к началу) — алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения производительности последующего кодирования.


Описание алгортима

Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.

Рассмотрим действие алгоритма на примере алфавита "ABC" и строки [math]s = [/math]"BCABAAA", полученной из строки "ABACABA" в результате преобразования Барроуза-Уиллера. Первый символ строки [math]s = [/math] 'B' является вторым элементом алфавита, поэтому на вывод подаётся 1. После перемещения 'B' в начало алфавита тот принимает вид "BAC". Дальнейшая работа алгоритма показана в таблице:

Символ Список Вывод
B ABC 1
C BAC 2
A CBA 2
B ACB 2
A BAC 1
A ABC 0
A ABC 0

Таким образом, результат работы алгоритма: [math]MTF(s) = [/math] "1222100".


Обратное преобразование

Пусть даны строка [math]s = [/math]"1222100" и исходный алфавит "ABC". Символ с номером 1 в алфавите — это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером 2 в алфавите — это 'A', поэтому 'A' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.

Символ Список Вывод
1 ABC B
2 BAC C
2 CBA A
2 ACB B
1 BAC A
0 ABC A
0 ABC A

Значит, исходная строка [math]MTF^{-1}(s) = [/math]"BCABAAA".

Применение

Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, самыми частыми символами которого будут нули. Без MTF нас подстерегают разного рода трудности в решении проблемы адаптации к данным, поскольку в разных местах данных, полученных на выходе BWT-преобразования, разные символы являются преобладающими. Зачастую мы встречаемся с последовательностями типа "bbbbbcccccdddddaaaaa".

Попробуем сжать эту последовательность при помощи, например, метода Хаффмана. Вероятности всех четырех символов в данном примере равны 1/4. Легко посчитать, что в результате кодирования мы получим последовательность длиной 20*2 = 40 бит.

Теперь проделаем то же самое со строкой, подвергнутой MTF-преобразованию (предположим, начальный алфавит выглядит как "abcd").

"bbbbbcccccdddddaaaaa" — исходная строка

"10000200003000030000" — строка после MTF

Символ Частота Вероятность Код Хаффмана
0 16 4/5 0
1 2 1/10 10
2 1 1/20 110
3 1 1/20 111

В результате сжатия получаем последовательность длиной 16*1 + 2*2 + 3*2 = 26 бит. Стоит заметить, что выигрыш от применения арифметического кодирования для данного примера будет еще значительней.


Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Преобразование_MTF&oldid=12173»