355
правок
Изменения
м
Рассмотрим действие алгоритма на примере алфавита ''"ABC"'' и строки Современные алгоритмы (например, [http://ru.wikipedia.org/wiki/Bzip2 bzip2]) перед алгоритмом MTF используют [[преобразование Барроуза-Уиллера|алгоритм BWT]], поэтому в качестве примера рассмотрим строку <tex>s = </tex>''"BCABAAA"'', полученной полученную из строки ''"ABACABA"'' в результате [[Преобразование Барроуза-Уиллера|преобразования Барроуза-Уиллера]]. Первый символ строки <tex>s = </tex> 'B' является вторым элементом алфавита''"ABC"'', поэтому на вывод подаётся 1. После перемещения 'B' в начало алфавита тот принимает вид ''"BAC"''. Дальнейшая работа алгоритма показана в таблице:
Нет описания правки
Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо.
{| class="wikitable"
|}
В результате сжатия получаем последовательность длиной 16*1 + 2*2 + 3*2 = 26 бит. Стоит заметить, что выигрыш от применения [http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 [Арифметическое кодирование|арифметического кодирования]] для данного примера будет еще значительней.
