Преобразование MTF — различия между версиями
Yulya3102 (обсуждение | вклад) м |
Yulya3102 (обсуждение | вклад) м |
||
| Строка 14: | Строка 14: | ||
! Символ || Список || Вывод | ! Символ || Список || Вывод | ||
|- | |- | ||
| − | | B || | + | | B || A'''B'''C || 1 |
|- | |- | ||
| − | | C || | + | | C || BA'''C''' || 2 |
|- | |- | ||
| − | | A || | + | | A || CB'''A''' || 2 |
|- | |- | ||
| − | | B || | + | | B || AC'''B''' || 2 |
|- | |- | ||
| − | | A || | + | | A || B'''A'''C || 1 |
|- | |- | ||
| − | | A || | + | | A || '''A'''BC || 0 |
|- | |- | ||
| − | | A || | + | | A || '''A'''BC || 0 |
|} | |} | ||
| Строка 39: | Строка 39: | ||
! Символ || Список || Вывод | ! Символ || Список || Вывод | ||
|- | |- | ||
| − | | 1 || | + | | 1 || A'''B'''C || B |
|- | |- | ||
| − | | 2 || | + | | 2 || BA'''C''' || C |
|- | |- | ||
| − | | 2 || | + | | 2 || CB'''A''' || A |
|- | |- | ||
| − | | 2 || | + | | 2 || AC'''B''' || B |
|- | |- | ||
| − | | 1 || | + | | 1 || B'''A'''C || A |
|- | |- | ||
| − | | 0 || | + | | 0 || '''A'''BC || A |
|- | |- | ||
| − | | 0 || | + | | 0 || '''A'''BC || A |
|} | |} | ||
| Строка 80: | Строка 80: | ||
|} | |} | ||
| − | В результате сжатия получаем последовательность длиной 16*1 + 2*2 + 3*2 = 26 бит. Стоит заметить, что выигрыш от применения [[Арифметическое кодирование|арифметического кодирования]] для данного примера будет еще значительней. | + | В результате сжатия получаем последовательность длиной <tex>16*1 + 2*2 + 3*2 = 26</tex> бит. Стоит заметить, что выигрыш от применения [[Арифметическое кодирование|арифметического кодирования]] для данного примера будет еще значительней. |
Версия 05:13, 29 октября 2011
| Определение: |
| Преобразование MTF (move-to-front, движение к началу) — алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед сжатием, разработанный для улучшения производительности последующего кодирования. |
Описание алгортима
Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.
Современные алгоритмы (например, bzip2) перед алгоритмом MTF используют алгоритм BWT, поэтому в качестве примера рассмотрим строку "BCABAAA", полученную из строки "ABACABA" в результате преобразования Барроуза-Уиллера. Первый символ строки '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 |
Таким образом, результат работы алгоритма: "1222100".
Обратное преобразование
Пусть даны строка "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 |
Значит, исходная строка "BCABAAA".
Применение
Этот метод позволяет легко преобразовать данные, насыщенные длинными повторами разных символов в блок данных, самыми частыми символами которого будут нули. Без MTF нас подстерегают разного рода трудности в решении проблемы адаптации к данным, поскольку в разных местах данных, полученных на выходе BWT-преобразования, разные символы являются преобладающими. Зачастую мы встречаемся с последовательностями типа "bbbbbcccccdddddaaaaa".
Попробуем сжать эту последовательность при помощи, например, метода Хаффмана. Вероятности всех четырех символов в данном примере равны 1/4. Легко посчитать, что в результате кодирования мы получим последовательность длиной 20*2 = 40 бит.
Теперь проделаем то же самое со строкой, подвергнутой 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 |
В результате сжатия получаем последовательность длиной бит. Стоит заметить, что выигрыш от применения арифметического кодирования для данного примера будет еще значительней.
