Range Coding
Полосное кодирование
Полосное кодирование заранее не определено, это значит, что кодировщик пытается сохранить значения оптимальным путем. Rangе-кодирование похоже на арифметическое, менее протяженное кодирование Хаффмана и на кодирование Фано. Rice coding и Start Step Stop Coding также служат для похожей цели, но в других ситуациях. Для того, чтобы проиллюстрировать, что делает неопределенный кодировщик, предположим, что есть файл с всего четырьмя значениями: 0, 1, 2, 3. Их можно хранить в двух битах, вот так:
0 = 00
1 = 01
2 = 10
3 = 11
Это неплохо, если значения появляются с примерно одинаковой частотой. Но предположим, что 0 встречается гораздо более часто, чем другие значения (к примеру, 50% всех случаев). В этом случае, может быть лучше использовать следующие комбинации для значений 0-3:
0 = 0
1 = 10
2 = 110
3 = 111
Принимая во внимание, что значения 1-3 с равной частотой, всего бит будет использовано: 0.50*1 + 0.17*2 + 0.17*3 + 0.17*3 = 1.83
вместо 2, как в предыдущем случае. При увеличении числа бит, это становится все более и более интересным. Существует несколько методов для определения упомянутой комбинации.
Кодирование Хаффмана и Фано — самые простые для понимания, они определяют комбинации очень схожие с уже упомянутыми, в них префикс используется для определения того, сколько нужно прочитать. Неопределенное кодирование и арифметическое кодирование немного более сложные, они строят таблицу частот появления, а затем сопоставляют конкретные интервалы конкретным значениям. В Range coding целые числа используются вместо чисел с плавающей запятой.
Комментарии