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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Decoder)
(Описание алгоритма за O(N log M))
(не показано 36 промежуточных версий 9 участников)
Строка 1: Строка 1:
'''Преобразование MTF'''
+
{{Определение
+
|definition =
'''Движение к началу''' (англ. move-to-front, MTF) — преобразование для кодирования данных (обычно потока байтов) разработанное для улучшения производительности энтропийного кодирования. При хорошей реализации, оно достаточно быстро для включения как дополнительный шаг в алгоритмах сжатия данных.
+
'''Преобразование MTF''' (англ. ''move-to-front'', движение к началу) {{---}} алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения эффективности последующего кодирования.
 +
}}
 +
== Описание алгоритма ==
  
 +
Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. <tex>(0, 1, 2, 3, \dots, 255)</tex>. В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.
  
 +
Современные алгоритмы (например, bzip2<ref>[http://ru.wikipedia.org/wiki/Bzip2 {{---}} bzip2]</ref>) перед алгоритмом MTF используют [[преобразование Барроуза-Уиллера|алгоритм BWT]], поэтому в качестве примера рассмотрим строку <tex>S = BCABAAA</tex>, полученную из строки ''"ABACABA"'' в результате [[Преобразование Барроуза-Уиллера|преобразования Барроуза-Уиллера]]. Первый символ строки <tex>S</tex> 'B' является вторым элементом алфавита ''"ABC"'', поэтому на вывод подаётся <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) = 1222100</tex>. 
  
=== Алгоритм ===
+
Вот примерная реализация этого алгоритма. Здесь массив <tex>\mathtt{alphabet}</tex> хранит количество символов перед символом <tex>S[i]</tex>, <tex>N</tex> {{---}} длина строки <tex>S</tex>.
  
Основной идеей преобразования является замена каждого входного символа его номером в специальном стэке недавно использованных символов. Последовательности идентичных символов, к примеру, будут заменены оригинальным алгоритмом (начиная со второго символа) на последовательность нулей. Если же символ долго не появлялся во входной последовательности, он будет заменен большим числом. Преобразование заменяет последовательность входных символов на последовательность целых чисел, если во входных данных было много локальных корреляций, то среди этих чисел будут преобладать небольшие, лучше сжимаемые энтропийным кодированием, чем исходные данные.
+
'''list<int>''' mtf(N):
Алгоритм впервые описан в работе. Изначально алгоритм назывался «стопка книг» («book stack»).
+
    '''list<int>''' result(N)
Часто используется при преобразовании байтов. Изначально каждое возможное значение байта записывается в список, в ячейку с номером равным значению байта, т.е (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. Первый обработанный символ заменяется самим собой, после чего элемент, соответствующий этому символу перемещается в голову списка (сдвигая элементы с 0 по свое положение на 1 вправо). Последующие символы кодируются номером элемента, содержащего их значение. После кодирования каждого символа эти элементы также продвигаются к голове списка.
+
    '''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> , <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, tree)        <font color=darkgreen>              //Объединяем нашу вершину и дерево по ключу</font color=darkgreen>
 +
    '''return''' result
  
 +
Функция <tex>\mathtt{findanswer}</tex> считает ответ так: если при спуске из вершины дерева мы должны идти вправо, то прибавляем к ответу количество вершин левого поддерева + 1, иначе ничего не добавляем к ответу.
  
+
Функции <tex>\mathtt{split}</tex> и <tex>\mathtt{merge}</tex> {{---}} стандартные функции для [[Декартово_дерево|декартова дерева]].
=== Coder ===
 
  
{|
+
<tex>\mathtt{minkey}</tex> {{---}} число, которое меньше любого ключа дерева.
|
 
{| class="standard"
 
  !Code||Symbol||List
 
  |-
 
  |0||a||a b c d
 
  |-
 
  |1||b||b a c d
 
  |-
 
  |1||a||a b c d
 
  |-
 
  |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
 
  |-
 
 
| ||
 
|}
 
=== Decoder ===
 
  
{|
+
== Обратное преобразование ==
|
 
{|border="1"
 
  
  !style="background: #FFCB00"|Symbol||style="background: #FFCB00"|Code||style="background: #FFCB00"|List
+
Пусть даны строка <tex>S = 1222100</tex> и исходный алфавит ''"ABC"''. Символ с номером <tex>1</tex> в алфавите {{---}} это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером <tex>2</tex> в алфавите {{---}} это 'C', поэтому 'C' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.
  |-
 
  |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"
{|
+
! Символ || Список || Вывод
|
+
|-
{| class="standard"
+
| 1 || A'''B'''C || B
  !
+
|-
  |-
+
| 2 || BA'''C''' || C
  |[http://www.arturocampos.com/ac_mtf.html "Move to front" by Arturo San Emeterio Campos  ]
+
|-
  |-
+
| 2 || CB'''A''' || A
  |http://ru.wikipedia.org/wiki/Move-To-Front
+
|-
 
+
| 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".
 +
 
 +
Попробуем сжать эту последовательность при помощи, например, [[Алгоритм Хаффмана|метода Хаффмана]]. Вероятности всех четырех символов в данном примере равны <tex>1/4</tex>. Легко посчитать, что в результате кодирования мы получим последовательность длиной <tex>20\cdot2 = 40</tex> бит.
 +
 
 +
Теперь проделаем то же самое со строкой, подвергнутой MTF-преобразованию (предположим, начальный алфавит выглядит как ''"abcd"'').
 +
 
 +
''"bbbbbcccccdddddaaaaa"'' {{---}} исходная строка
 +
 
 +
''"10000200003000030000"'' {{---}} строка после MTF
 +
 
 +
{| class="wikitable"
 +
! Символ || Частота || Вероятность || Код Хаффмана
 +
|-
 +
| 0 || 16 || 4/5 || 0
 +
|-
 +
| 1 || 2 || 1/10 || 10
 +
|-
 +
| 2 || 1 || 1/20 || 110
 +
|-
 +
| 3 || 1 || 1/20 || 111
 +
|}
 +
 
 +
В результате сжатия получаем последовательность длиной <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.
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 
 +
[[Категория: Алгоритмы сжатия ]]

Версия 10:10, 13 сентября 2018

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

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

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

Современные алгоритмы (например, bzip2[1]) перед алгоритмом MTF используют алгоритм BWT, поэтому в качестве примера рассмотрим строку [math]S = BCABAAA[/math], полученную из строки "ABACABA" в результате преобразования Барроуза-Уиллера. Первый символ строки [math]S[/math] 'B' является вторым элементом алфавита "ABC", поэтому на вывод подаётся [math]1[/math]. После перемещения '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) = 1222100[/math].

Вот примерная реализация этого алгоритма. Здесь массив [math]\mathtt{alphabet}[/math] хранит количество символов перед символом [math]S[i][/math], [math]N[/math] — длина строки [math]S[/math].

list<int> mtf(N):
   list<int> result(N)
   for i = 1 to N
      result.append(alphabet[S[i]])
      помещаем символ S[i] в начало алфавита
   return result

Данный алгоритм работает за [math]O(N \cdot M)[/math], где [math]M[/math] — размер алфавита, [math]N[/math] — длина строки, что не очень быстро. Этот алгоритм можно реализовать за [math]O(N\log M)[/math].

Описание алгоритма за O(N log M)

Для решения будем использовать декартово дерево.

Пусть дан алфавит размером [math]M[/math] и строка [math]S[/math] длиной [math]N[/math]. Запомним для каждого символа алфавита свой ключ. Изначально [math]\mathtt{keys}['a'] = 0[/math], [math]\mathtt{keys}['b'] = 1[/math], [math]\dots[/math] , [math]\mathtt{keys}['z'] = M-1[/math]. Соединим все вершины в дерево по ключу.

list<int> mtf(N):
   list<int> result(N)
   minkey = 0
   for i = 0 to N 
      result.append(findanswer(S[i]))        //Считаем ответ        
      cur = find(keys[S[i]])                 //Находим вершину в дереве 
      split(cur.key)                         //Вырезаем вершину из дерева
      min_key--                              //Уменьшаем минимально-возможный ключ
      cur.key = minkey                       //Ставим ключ в найденной вершине на минимальный
      merge(cur, tree)                       //Объединяем нашу вершину и дерево по ключу
   return result

Функция [math]\mathtt{findanswer}[/math] считает ответ так: если при спуске из вершины дерева мы должны идти вправо, то прибавляем к ответу количество вершин левого поддерева + 1, иначе ничего не добавляем к ответу.

Функции [math]\mathtt{split}[/math] и [math]\mathtt{merge}[/math] — стандартные функции для декартова дерева.

[math]\mathtt{minkey}[/math] — число, которое меньше любого ключа дерева.

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

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

Символ Список Вывод
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) = BCABAAA[/math].

Применение

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

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

Теперь проделаем то же самое со строкой, подвергнутой 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

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

См. также

Примечания

Источники информации

  1. Burrows Wheeler Transform FAQ
  2. Move-To-Front (Википедия)
  3. Ryabko, B. Ya. Data compression by means of a «book stack», Problems of Information Transmission, 1980, v. 16: (4), pp. 265–269.
  4. 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.