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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
'''Преобразование MTF''' (''move-to-front'', движение к началу) {{---}} алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения эффективности последующего кодирования.
+
{{Определение
 
+
|definition =
 +
'''Преобразование MTF''' (англ. ''move-to-front'', движение к началу) {{---}} алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения эффективности последующего кодирования.
 +
}}
 
== Описание алгоритма ==
 
== Описание алгоритма ==
  
Строка 29: Строка 31:
 
Данный алгоритм работает за <tex>O(N \cdot M)</tex>, где <tex>N</tex> {{---}} размер алфавита, <tex>M</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(N</tex><tex>\log</tex><tex>M)</tex>.
 
Данный алгоритм работает за <tex>O(N \cdot M)</tex>, где <tex>N</tex> {{---}} размер алфавита, <tex>M</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(N</tex><tex>\log</tex><tex>M)</tex>.
  
== Описание алгоритма за O(Nlog(N+M)) ==
+
== Описание алгоритма за O(N log(N+M)) ==
  
 
=== Идея ===
 
=== Идея ===
Строка 45: Строка 47:
 
     '''list<int>''' result(N)
 
     '''list<int>''' result(N)
 
     '''list<int>''' used(N+M)
 
     '''list<int>''' used(N+M)
     '''for''' i = 1 '''to''' M                                      <font color=darkgreen>//Заполняем последние N ячеек единицами</font color=darkgreen>  
+
     '''for''' i = 1 '''to''' M                                      <font color=darkgreen>//Заполняем последние M ячеек единицами</font color=darkgreen>  
 
       used[i+N] = 1
 
       used[i+N] = 1
 
     '''for''' i = 1 '''to''' N
 
     '''for''' i = 1 '''to''' N

Версия 15:18, 15 января 2015

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

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

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

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

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

Идея

Пусть дан алфавит размером [math]M[/math] и строка [math]S[/math] длиной [math]N[/math]. Заведем массив [math]used[1..N+M][/math] и последние [math]M[/math] ячеек заполним единицами. Запомним для каждого символа алфавита позицию в нашем массиве. Например, [math]alphabet['a'] = N+1[/math], [math]alphabet['b'] = N+2[/math], ... , [math]alphabet['z'] = N+M[/math].

При обработке [math]i[/math]-го символа посчитаем и выпишем сумму на отрезке [math][1, alphabet[S[i]] - 1][/math], поменяем значения ячеек [math]used[N-i+1][/math] и [math]used[alphabet[S[i]]][/math] местами, также стоит поменять значение в ячейке [math]alphabet[S[i]][/math] на [math]N-i+1[/math].

Чтобы добиться сложности алгоритма [math]O(N[/math][math]\log[/math][math](N+M))[/math] нужно использовать дерево отрезков или подобное.

Псевдокод

list<int> mtf(N):
   list<int> result(N)
   list<int> used(N+M)
   for i = 1 to M                                      //Заполняем последние M ячеек единицами 
      used[i+N] = 1
   for i = 1 to N
      result.append(sum(1, alphabet[S[i]] - 1))        //Запоминаем ответ
      swap(used[N-i+1], used[alphabet[S[i]]])          //Меняем значения
      alphabet[S[i]] = N-i+1                           //Изменяем позицию символа в массиве
   return result

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

Пусть даны строка [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. Легко посчитать, что в результате кодирования мы получим последовательность длиной [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] бит. Стоит заметить, что выигрыш от применения арифметического кодирования для данного примера будет еще значительней.

Ссылки