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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Применение)
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =

Версия 08:52, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.


Определение:
Преобразование 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.