Преобразование MTF
Движение к началу (англ. move-to-front, MTF) — преобразование для кодирования данных (обычно потока байтов) разработанное для улучшения производительности энтропийного кодирования. При хорошей реализации, оно используется как дополнительный шаг в алгоритмах сжатия данных.
Алгоритм
Основной идеей преобразования является замена каждого входного символа его номером в специальном стэке недавно использованных символов. Последовательности идентичных символов, к примеру, будут заменены оригинальным алгоритмом (начиная со второго символа) на последовательность нулей. Если же символ долго не появлялся во входной последовательности, он будет заменен большим числом. Преобразование заменяет последовательность входных символов на последовательность целых чисел, если во входных данных было много локальных корреляций, то среди этих чисел будут преобладать небольшие, лучше сжимаемые энтропийным кодированием, чем исходные данные.
Изначально каждое возможное значение байта записывается в список, в ячейку с номером равным значению байта, т.е (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. Первый обработанный символ заменяется самим собой, после чего элемент, соответствующий этому символу перемещается в голову списка (сдвигая элементы с 0 по свое положение на 1 вправо). Последующие символы кодируются номером элемента, содержащего их значение. После кодирования каждого символа эти элементы также продвигаются к голове списка.
Coder и Decoder
Coder
| Symbol |
Code |
List
|
| a |
0 |
a b c d
|
| b |
1 |
b a c d
|
| a |
1 |
a b c d
|
| a |
0 |
a b c d
|
| c |
2 |
c a b d
|
| a |
1 |
a c b d
|
| b |
2 |
b a c d
|
| a |
1 |
a b c d
|
| d |
3 |
d a b c
|
Decoder
| Code |
Symbol |
List
|
| 0 |
a |
a b c d
|
| 1 |
b |
b a c d
|
| 1 |
a |
a b c d
|
| 0 |
a |
a b c d
|
| 2 |
c |
c a b d
|
| 1 |
a |
a c b d
|
| 2 |
b |
b a c d
|
| 1 |
a |
a b c d
|
| 3 |
d |
d a b c
|
Ссылки
|
