10
правок
Изменения
Нет описания правки
|}
Таким образом, результат работы алгоритма: <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>.
== Описание алгоритма за 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{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>.
<code>
'''return''' result
</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>
== Обратное преобразование ==
* [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. 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.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
