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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 27: Строка 27:
 
|}
 
|}
  
Таким образом, результат работы алгоритма: <tex>MTF(\mathtt{S}) = </tex> ''"1222100"''.  
+
Таким образом, результат работы алгоритма: <tex>MTF(\mathtt{S}) = </tex> ''"1222100"''.
 +
 
 +
Вот примерная реализация этого алгоритма. Здесь массив <tex>\mathtt{alphabet}</tex> хранит количество символов перед символом <tex>\mathtt{S}[\mathtt{i}]</tex>, <tex>/mathtt{N}</tex> {{---}} длина строки <tex>/mathtt{S}</tex>.
 +
 
 +
<code>
 +
'''list<int>''' mtf(N):
 +
    '''list<int>''' result(N)
 +
    '''for''' i = 1 '''to''' N
 +
      result.append(alphabet[S[i]])
 +
      помещаем символ S[i] в начало алфавита
 +
    '''return''' result
 +
</code> 
  
 
Данный алгоритм работает за <tex>O(\mathtt{N} \cdot \mathtt{M})</tex>, где <tex>\mathtt{N}</tex> {{---}} размер алфавита, <tex>\mathtt{M}</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(\mathtt{N}\log(\mathtt{N+M}))</tex>.
 
Данный алгоритм работает за <tex>O(\mathtt{N} \cdot \mathtt{M})</tex>, где <tex>\mathtt{N}</tex> {{---}} размер алфавита, <tex>\mathtt{M}</tex> {{---}} длина строки, что не очень быстро. Этот алгоритм можно реализовать за <tex>O(\mathtt{N}\log(\mathtt{N+M}))</tex>.
  
 
== Описание алгоритма за O(N log(N+M)) ==
 
== Описание алгоритма за O(N log(N+M)) ==
 
=== Идея ===
 
  
 
Пусть дан алфавит размером <tex>\mathtt{M}</tex> и строка <tex>\mathtt{S}</tex> длиной <tex>\mathtt{N}</tex>. Заведем массив <tex>\mathtt{used}[1..\mathtt{N+M}]</tex> и последние <tex>\mathtt{M}</tex> ячеек заполним единицами. Запомним для каждого символа алфавита позицию в нашем массиве. Например, <tex>\mathtt{alphabet}['a'] = \mathtt{N}+1</tex>, <tex>\mathtt{alphabet}['b'] = \mathtt{N}+2</tex>, ... , <tex>\mathtt{alphabet}['z'] = \mathtt{N+M}</tex>.  
 
Пусть дан алфавит размером <tex>\mathtt{M}</tex> и строка <tex>\mathtt{S}</tex> длиной <tex>\mathtt{N}</tex>. Заведем массив <tex>\mathtt{used}[1..\mathtt{N+M}]</tex> и последние <tex>\mathtt{M}</tex> ячеек заполним единицами. Запомним для каждого символа алфавита позицию в нашем массиве. Например, <tex>\mathtt{alphabet}['a'] = \mathtt{N}+1</tex>, <tex>\mathtt{alphabet}['b'] = \mathtt{N}+2</tex>, ... , <tex>\mathtt{alphabet}['z'] = \mathtt{N+M}</tex>.  
  
 
При обработке <tex>\mathtt{i}</tex>-го символа посчитаем и выпишем сумму на отрезке <tex>[1, \mathtt{alphabet}[\mathtt{S}[\mathtt{i}]] - 1]</tex>, поменяем значения ячеек <tex>\mathtt{used}[\mathtt{N-i}+1]</tex> и <tex>\mathtt{used}[\mathtt{alphabet}[\mathtt{S}[\mathtt{i}]]]</tex> местами, также стоит поменять значение в ячейке <tex>\mathtt{alphabet}[\mathtt{S}[\mathtt{i}]]</tex> на <tex>\mathtt{N-i}+1</tex>.
 
При обработке <tex>\mathtt{i}</tex>-го символа посчитаем и выпишем сумму на отрезке <tex>[1, \mathtt{alphabet}[\mathtt{S}[\mathtt{i}]] - 1]</tex>, поменяем значения ячеек <tex>\mathtt{used}[\mathtt{N-i}+1]</tex> и <tex>\mathtt{used}[\mathtt{alphabet}[\mathtt{S}[\mathtt{i}]]]</tex> местами, также стоит поменять значение в ячейке <tex>\mathtt{alphabet}[\mathtt{S}[\mathtt{i}]]</tex> на <tex>\mathtt{N-i}+1</tex>.
 
Чтобы добиться сложности  алгоритма <tex>O(\mathtt{N}</tex><tex>\log</tex><tex>(\mathtt{N+M}))</tex> нужно использовать дерево отрезков или подобное.
 
 
=== Псевдокод ===
 
  
 
<code>
 
<code>
Строка 55: Строка 60:
 
     '''return''' result
 
     '''return''' result
 
</code>
 
</code>
 +
 +
Функцию <tex>sum</tex> можно реализовывать по-разному.
 +
 +
<code>
 +
'''int''' sum(left, right)
 +
    result = 0
 +
    '''for''' i = left '''to''' right
 +
      result = result + used[i]
 +
    '''return''' result
 +
</code>
 +
 +
Такая реализация работает за <tex>O(right-left)</tex>, общая сложность алгоритма равна <tex>O(\mathtt{N} \cdot \mathtt{M})</tex> Но можно находить сумму на отрезке при помощи [[Дерево_отрезков._Построение | дерева отрезков]], что сократит время работы до <tex>O(\log(\mathtt{right-left}))</tex>. Итого, общая сложность будет равна <tex>O(\mathtt{N}\log(\mathtt{N+M}))</tex>
  
 
== Обратное преобразование ==
 
== Обратное преобразование ==
Строка 115: Строка 132:
  
 
* [http://ru.wikipedia.org/wiki/Move-To-Front Move-To-Front (Википедия)]
 
* [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:59, 15 января 2015

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

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

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

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

Вот примерная реализация этого алгоритма. Здесь массив [math]\mathtt{alphabet}[/math] хранит количество символов перед символом [math]\mathtt{S}[\mathtt{i}][/math], [math]/mathtt{N}[/math] — длина строки [math]/mathtt{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(\mathtt{N} \cdot \mathtt{M})[/math], где [math]\mathtt{N}[/math] — размер алфавита, [math]\mathtt{M}[/math] — длина строки, что не очень быстро. Этот алгоритм можно реализовать за [math]O(\mathtt{N}\log(\mathtt{N+M}))[/math].

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

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

При обработке [math]\mathtt{i}[/math]-го символа посчитаем и выпишем сумму на отрезке [math][1, \mathtt{alphabet}[\mathtt{S}[\mathtt{i}]] - 1][/math], поменяем значения ячеек [math]\mathtt{used}[\mathtt{N-i}+1][/math] и [math]\mathtt{used}[\mathtt{alphabet}[\mathtt{S}[\mathtt{i}]]][/math] местами, также стоит поменять значение в ячейке [math]\mathtt{alphabet}[\mathtt{S}[\mathtt{i}]][/math] на [math]\mathtt{N-i}+1[/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]sum[/math] можно реализовывать по-разному.

int sum(left, right)
   result = 0
   for i = left to right
      result = result + used[i]
   return result

Такая реализация работает за [math]O(right-left)[/math], общая сложность алгоритма равна [math]O(\mathtt{N} \cdot \mathtt{M})[/math] Но можно находить сумму на отрезке при помощи дерева отрезков, что сократит время работы до [math]O(\log(\mathtt{right-left}))[/math]. Итого, общая сложность будет равна [math]O(\mathtt{N}\log(\mathtt{N+M}))[/math]

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

Пусть даны строка [math]\mathtt{S} = [/math]"1222100" и исходный алфавит "ABC". Символ с номером [math]1[/math] в алфавите — это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита. Символ с номером [math]2[/math] в алфавите — это '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}(\mathtt{S}) = [/math]"BCABAAA".

Применение

Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, самыми частыми символами которого будут нули. Без 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. Ryabko, B. Ya. Data compression by means of a «book stack», Problems of Information Transmission, 1980, v. 16: (4), pp. 265–269.
  2. 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.