Показать меню

Интервальное кодирование

24.05.2022
17

Интервальное кодирование (диапазонное кодирование) — энтропийный метод кодирования, предложенный Г. Н. Н. Мартином в 1979 году. Это разновидность арифметического кодирования.

Описание

Интервальное кодирование кодирует все символы сообщения в одно число, в отличие от, например, кода Хаффмана, который присваивает каждому символу последовательность бит и объединяет все битовые последовательности вместе.

Пример

Допустим, необходимо зашифровать сообщение «AABA<EOM>», где <EOM> — это символ конца сообщения (англ. end of message). Для этого примера предполагается, что декодировщик знает, что мы намерены закодировать ровно пять символов в десятичной системе счисления (алгоритм в данном случае поддерживает 105 различных комбинаций символов в диапазоне [0, 100000)) используя распределение вероятностей {A: 0.60; B: 0.20; <EOM>: 0.20}. Кодировщик делит диапазон [0, 100000) на три поддиапазона:

A: [ 0, 60000) B: [ 60000, 80000) <EOM>: [ 80000, 100000)

Поскольку наш первый символ — A, это снижает наш первоначальный диапазон до [0, 60000). Второй символ делит этот диапазон еще на три части:

AA: [ 0, 36000) AB: [ 36000, 48000) A<EOM>: [ 48000, 60000)

С двумя закодированными символами наш диапазон становится [0, 36000) и наш третий символ предоставляет следующие варианты:

AAA: [ 0, 21600) AAB: [ 21600, 28800) AA<EOM>: [ 28800, 36000)

На этот раз выбор падает на второй из трех вариантов, которые представляют собой сообщение, которое мы хотим закодировать, и наш диапазон становится [21600, 28800). Может показаться, что стало сложнее определить наши поддиапазоны в данном случае, но на самом деле это не так: мы можем просто вычесть нижнюю границу из верхней границы, чтобы определить, что в нашем диапазоне доступно 7200 чисел; первые 4320 из них представляют 0,60 от общего числа, следующие 1440 представляют следующие 0,20, а остальные 1440 представляют оставшиеся 0,20 от общего диапазона. Прибавка нижней границы дает нам наши диапазоны:

AABA: [21600, 25920) AABB: [25920, 27360) AAB<EOM>: [27360, 28800)

Наконец, наш диапазон сузился до [21600, 25920), у нас остался только один символ для кодирования. Используя ту же технику, как и прежде, для разделения диапазона между нижней и верхней границей мы находим три оставшихся поддиапазона:

AABAA: [21600, 24192) AABAB: [24192, 25056) AABA<EOM>: [25056, 25920)

И так как <EOM> — это наш последний символ — наш конечный диапазон - [25056, 25920). Так как все пятизначные числа, начинающиеся с «251», попадают в наш последний ряд, то мы могли бы передать один из трехзначных префиксов, чтобы однозначно выразить исходное сообщение (тот факт, что на самом деле существует восемь таких префиксов, говорит о том, что можно оптимизировать алгоритм. Но они возникли из-за использования десятичной системы счисления, а не двоичной).

Связь с арифметическим кодированием

Арифметическое кодирование аналогично интервальному, использует дробные числа в диапазоне [0,1). Соответственно, в результате арифметический код интерпретируется как начало с неявным «0.», так как это просто разные интерпретации одних и тех же методов кодирования, то любой арифметический кодировщик — это соответствующий интервальный кодировщик, и наоборот.

На практике, однако, так называемое диапазонные кодировщики имеют тенденцию быть реализованными в значительной степени, как описано в статье Мартина, в то время как арифметические кодировщики вообще не называют диапазонными. Часто разницей является побайтовая и побитовая ренормализация. Интервальные кодировщики склонны использовать байты, а не биты. Хотя это и снижает уровень сжатия, это быстрее, чем выполнение перенормировки для каждого бита.

Еще по этой теме:
International Standard Identifier for Libraries and Related Organizations
01:00, 25 сентябрь
International Standard Identifier for Libraries and Related Organizations
ISIL (англ. International Standard Identifier for Libraries and Related Organizations) — представляет собой универсальный идентификатор (условное обозначение) для библиотек и родственных им
Сжатие данных
12:00, 13 май
Сжатие данных
Сжатие данных (англ. data compression) — алгоритмическое преобразование данных, производимое с целью уменьшения занимаемого ими объёма. Применяется для более рационального использования устройств
Теория кодирования
13:06, 19 декабрь
Теория кодирования
Теория кодирования — наука о свойствах кодов и их пригодности для достижения поставленной цели. Кодирование в рамках теории рассматривается как процесс преобразования данных из формы, удобной для
Base58
18:55, 12 декабрь
Base58
Base58 — вариант кодирования цифрового кода в виде буквенно-цифрового текста на основе латинского алфавита. Алфавит кодирования содержит 58 символов. Применяется для передачи данных в разнородных
Габидулин, Эрнст Мухамедович
18:42, 12 декабрь
Габидулин, Эрнст Мухамедович
Габидулин Эрнст Мухамедович (р. 4 июня 1937) — доктор технических наук, профессор, заведующий кафедрой радиотехники с 1989 по 2010 г. МФТИ (ГУ), Заслуженный деятель науки Российской Федерации.
Качественная переменная
23:22, 01 декабрь
Качественная переменная
Качественная, дискретная, или категорийная переменная — это переменная, которая может принимать одно из ограниченного и обычно фиксированного числа возможных значений, назначая каждую единицу
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail: