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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Применение)
(не показано 14 промежуточных версий 4 участников)
Строка 1: Строка 1:
'''Преобразование MTF''' (''move-to-front'', движение к началу) {{---}} алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения эффективности последующего кодирования.
+
{{Определение
 
+
|definition =
 +
'''Преобразование MTF''' (англ. ''move-to-front'', движение к началу) {{---}} алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения эффективности последующего кодирования.
 +
}}
 
== Описание алгоритма ==
 
== Описание алгоритма ==
  
Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. (0, 1, 2, 3, , 255). В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.
+
Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. <tex>(0, 1, 2, 3, \dots, 255)</tex>. В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.
  
Современные алгоритмы (например, [http://ru.wikipedia.org/wiki/Bzip2 bzip2]) перед алгоритмом MTF используют [[преобразование Барроуза-Уиллера|алгоритм BWT]], поэтому в качестве примера рассмотрим строку <tex>s = </tex>''"BCABAAA"'', полученную из строки ''"ABACABA"'' в результате [[Преобразование Барроуза-Уиллера|преобразования Барроуза-Уиллера]]. Первый символ строки <tex>s</tex> 'B' является вторым элементом алфавита ''"ABC"'', поэтому на вывод подаётся 1. После перемещения 'B' в начало алфавита тот принимает вид ''"BAC"''. Дальнейшая работа алгоритма показана в таблице:
+
Современные алгоритмы (например, 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"
 
{| class="wikitable"
Строка 25: Строка 27:
 
|}
 
|}
  
Таким образом, результат работы алгоритма: <tex>MTF(s) = </tex> ''"1222100"''.  
+
Таким образом, результат работы алгоритма: <tex>MTF(S) = 1222100</tex>.
  
Данный алгоритм работает за <tex>O(N \cdot M)</tex>, где <tex>N</tex> {{---}} размер алфавита, <tex>M</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(N</tex><tex>\log</tex><tex>M)</tex>.
+
Вот примерная реализация этого алгоритма. Здесь массив <tex>\mathtt{alphabet}</tex> хранит количество символов перед символом <tex>S[i]</tex>, <tex>N</tex> {{---}} длина строки <tex>S</tex>.
  
== Описание алгоритма за O(Nlog(N+M)) ==
+
'''list<int>''' mtf(N):
 
+
    '''list<int>''' result(N)
=== Идея ===
+
    '''for''' i = 1 '''to''' N
 +
      result.append(alphabet[S[i]])
 +
      помещаем символ S[i] в начало алфавита
 +
    '''return''' result
  
Пусть дан алфавит размером <tex>M</tex> и строка <tex>S</tex> длиной <tex>N</tex>. Заведем массив <tex>used[1..N+M]</tex> и последние <tex>M</tex> ячеек заполним единицами. Запомним для каждого символа алфавита позицию в нашем массиве. Например, <tex>alphabet['a'] = N+1</tex>, <tex>alphabet['b'] = N+2</tex>, ... , <tex>alphabet['z'] = N+M</tex>.  
+
Данный алгоритм работает за <tex>O(N \cdot M)</tex>, где <tex>M</tex> {{---}} размер алфавита, <tex>N</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(N\log M)</tex>.
  
При обработке <tex>i</tex>-го символа посчитаем и выпишем сумму на отрезке <tex>[1, alphabet[S[i]] - 1]</tex>, поменяем значения ячеек <tex>used[N-i+1]</tex> и <tex>used[alphabet[S[i]]]</tex> местами, также стоит поменять значение в ячейке <tex>alphabet[S[i]]</tex> на <tex>N-i+1</tex>.
+
== Описание алгоритма за O(N log M) ==
  
Чтобы добиться сложности  алгоритма <tex>O(N</tex><tex>\log</tex><tex>(N+M))</tex> нужно использовать дерево отрезков или подобное.
+
Для решения будем использовать [[Декартово_дерево | декартово дерево]].
  
=== Псевдокод ===
+
Пусть дан алфавит размером <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>. Соединим все вершины в дерево по ключу.
  
<code>
 
 
  '''list<int>''' mtf(N):
 
  '''list<int>''' mtf(N):
 
     '''list<int>''' result(N)
 
     '''list<int>''' result(N)
     '''list<int>''' used(N+M)
+
     minkey = 0
     '''for''' i = 1 '''to''' M                                      <font color=darkgreen>//Заполняем последние N ячеек единицами</font color=darkgreen>  
+
     '''for''' i = 0 '''to''' N
       used[i+N] = 1
+
      result.append(findanswer(S[i])) <font color=darkgreen>       //Считаем ответ</font color=darkgreen>      
    '''for''' i = 1 '''to''' N
+
       cur = find(keys[S[i]])<font color=darkgreen>                 //Находим вершину в дереве </font color=darkgreen>
      result.append(sum(1, alphabet[S[i]] - 1))       <font color=darkgreen>//Запоминаем ответ</font color=darkgreen>
+
       split(cur.key)     <font color=darkgreen>                   //Вырезаем вершину из дерева</font color=darkgreen>
       swap(used[N-i+1], used[alphabet[S[i]]])         <font color=darkgreen>//Меняем значения</font color=darkgreen>
+
       min_key--          <font color=darkgreen>                  //Уменьшаем минимально-возможный ключ</font color=darkgreen>
       alphabet[S[i]] = N-i+1                          <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
 
     '''return''' result
</code>
+
 
 +
Функция <tex>\mathtt{findanswer}</tex> считает ответ так: если при спуске из вершины дерева мы должны идти вправо, то прибавляем к ответу количество вершин левого поддерева + 1, иначе ничего не добавляем к ответу.
 +
 
 +
Функции <tex>\mathtt{split}</tex> и <tex>\mathtt{merge}</tex> {{---}} стандартные функции для [[Декартово_дерево|декартова дерева]].
 +
 
 +
<tex>\mathtt{minkey}</tex> {{---}} число, которое меньше любого ключа дерева.
  
 
== Обратное преобразование ==
 
== Обратное преобразование ==
  
Пусть даны строка <tex>s = </tex>''"1222100"'' и исходный алфавит ''"ABC"''. Символ с номером 1 в алфавите {{---}} это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером 2 в алфавите {{---}} это 'A', поэтому 'A' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.
+
Пусть даны строка <tex>S = 1222100</tex> и исходный алфавит ''"ABC"''. Символ с номером <tex>1</tex> в алфавите {{---}} это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером <tex>2</tex> в алфавите {{---}} это 'C', поэтому 'C' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.
  
 
{| class ="wikitable"
 
{| class ="wikitable"
Строка 76: Строка 86:
 
|}
 
|}
  
Значит, исходная строка <tex>MTF^{-1}(s) = </tex>''"BCABAAA"''.
+
Значит, исходная строка <tex>MTF^{-1}(S) = BCABAAA</tex>.
  
 
== Применение ==
 
== Применение ==
Строка 82: Строка 92:
 
Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, самыми частыми символами которого будут нули. Без MTF нас подстерегают разного рода трудности в решении проблемы адаптации к данным, поскольку в разных местах данных, полученных на выходе [[Преобразование Барроуза-Уиллера|BWT-преобразования]], разные символы являются преобладающими. Зачастую мы встречаемся с последовательностями типа "bbbbbcccccdddddaaaaa".
 
Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, самыми частыми символами которого будут нули. Без MTF нас подстерегают разного рода трудности в решении проблемы адаптации к данным, поскольку в разных местах данных, полученных на выходе [[Преобразование Барроуза-Уиллера|BWT-преобразования]], разные символы являются преобладающими. Зачастую мы встречаемся с последовательностями типа "bbbbbcccccdddddaaaaa".
  
Попробуем сжать эту последовательность при помощи, например, [[Алгоритм Хаффмана|метода Хаффмана]]. Вероятности всех четырех символов в данном примере равны 1/4. Легко посчитать, что в результате кодирования мы получим последовательность длиной <tex>20\cdot2 = 40</tex> бит.
+
Попробуем сжать эту последовательность при помощи, например, [[Алгоритм Хаффмана|метода Хаффмана]]. Вероятности всех четырех символов в данном примере равны <tex>1/4</tex>. Легко посчитать, что в результате кодирования мы получим последовательность длиной <tex>20\cdot2 = 40</tex> бит.
  
 
Теперь проделаем то же самое со строкой, подвергнутой MTF-преобразованию (предположим, начальный алфавит выглядит как ''"abcd"'').  
 
Теперь проделаем то же самое со строкой, подвергнутой MTF-преобразованию (предположим, начальный алфавит выглядит как ''"abcd"'').  
Строка 95: Строка 105:
 
| 0 || 16 || 4/5 || 0
 
| 0 || 16 || 4/5 || 0
 
|-
 
|-
| 1 || 2 || 1/10 || 10
+
| 1 || 1 || 1/20 || 110
 
|-
 
|-
| 2 || 1 || 1/20 || 110
+
| 2 || 1 || 1/20 || 111
 
|-
 
|-
| 3 || 1 || 1/20 || 111
+
| 3 || 2 || 1/10 || 10
 
|}
 
|}
  
 
В результате сжатия получаем последовательность длиной <tex>16\cdot1 + 2\cdot2 + 3\cdot2 = 26</tex> бит. Стоит заметить, что выигрыш от применения [[Арифметическое кодирование|арифметического кодирования]] для данного примера будет еще значительней.
 
В результате сжатия получаем последовательность длиной <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 (Википедия)]
+
# [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.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Алгоритмы сжатия ]]
 
[[Категория: Алгоритмы сжатия ]]

Версия 17:49, 6 марта 2020

Определение:
Преобразование 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 1 1/20 110
2 1 1/20 111
3 2 1/10 10

В результате сжатия получаем последовательность длиной [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.