Кодирование диапазона - Range encoding

Кодирование диапазона является энтропийное кодирование метод, определенный Дж. Найджелом Н. Мартином в статье 1979 г.,^[1] который эффективно заново открыл арифметический код FIFO, впервые представленный Ричардом Кларком Паско в 1976 году.^[2] Учитывая поток символов и их вероятности, кодер диапазона создает эффективный по пространству поток битов для представления этих символов, а, учитывая поток и вероятности, декодер диапазона меняет процесс на обратное.

Кодирование диапазона очень похоже на арифметическое кодирование, за исключением того, что кодирование выполняется цифрами в любой базе, а не битами, поэтому это быстрее при использовании больших баз (например, байт ) при небольших затратах на эффективность сжатия.^[3] После истечения срока действия первого (1978 г.) патента на арифметическое кодирование,^[4] кодирование диапазонов явно не связано с патентами. Это особенно вызвало интерес к технике в Открытый исходный код сообщество. С тех пор истек срок действия патентов на различные известные методы арифметического кодирования.

Как работает кодирование диапазона

Графическое представление процесса кодирования. Кодируемое здесь сообщение - "AABA "

Кодирование диапазона концептуально кодирует все символы сообщения в одно число, в отличие от Кодирование Хаффмана который назначает каждому символу битовый шаблон и объединяет все битовые шаблоны вместе. Таким образом, кодирование диапазона может достигать большей степени сжатия, чем нижняя граница одного бит на символ на Кодирование Хаффмана и он не страдает от неэффективности, которую делает Хаффман при работе с вероятностями, которые не являются точными силы двух.

Центральная концепция кодирования диапазона заключается в следующем: при достаточно большом диапазоне целые числа и оценка вероятности для символов, начальный диапазон можно легко разделить на поддиапазоны, размеры которых пропорциональны вероятности символа, который они представляют. Затем каждый символ сообщения может быть закодирован по очереди, уменьшая текущий диапазон до того поддиапазона, который соответствует следующему символу, который должен быть закодирован. Декодер должен иметь ту же оценку вероятности, что и используемый кодер, которая может быть либо отправлена заранее, получена из уже переданных данных, либо быть частью компрессора и декомпрессора.

Когда все символы закодированы, простой идентификации поддиапазона достаточно для передачи всего сообщения (при условии, конечно, что декодер каким-то образом уведомляется, когда он извлекает все сообщение). Одного целого числа на самом деле достаточно для идентификации поддиапазона, и может даже не потребоваться передавать все целое число; если существует такая последовательность цифр, что каждое целое число, начинающееся с этого префикса, попадает в поддиапазон, то только префикс - это все, что нужно для идентификации поддиапазона и, таким образом, передачи сообщения.

пример

Предположим, мы хотим закодировать сообщение «AABA », где - это символ конца сообщения. В этом примере предполагается, что декодер знает, что мы намерены кодировать ровно пять символов в система счисления по основанию 10 (с учетом 10⁵ различные комбинации символов с диапазоном [0, 100000)) с использованием распределение вероятностей {A: 0,60; B: 0,20; : .20}. Кодировщик разбивает диапазон [0, 100000) на три поддиапазона:

A: [0, 60000) B: [60000, 80000) : [80000, 100000)

Поскольку наш первый символ - A, он уменьшает наш начальный диапазон до [0, 60000). Выбор второго символа оставляет нам три поддиапазона этого диапазона. Мы показываем их, следуя уже закодированной букве «А»:

AA: [0, 36000) AB: [36000, 48000) A : [48000, 60000)

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

AAA: [0, 21600) AAB: [21600, 28800) AA : [28800, 36000)

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

AABA: [21600, 25920) AABB: [25920, 27360) AAB : [27360, 28800)

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

AABAA: [21600, 24192) AABAB: [24192, 25056) AABA : [25056, 25920)

И поскольку - наш последний символ, наш окончательный диапазон равен [25056, 25920). Поскольку все пятизначные целые числа, начинающиеся с «251», попадают в наш окончательный диапазон, это один из трехзначных префиксов, которые мы могли бы передать, что однозначно передало бы наше исходное сообщение. (Тот факт, что на самом деле существует восемь таких префиксов, означает, что у нас все еще есть недостатки. Они были введены в результате использования нами база 10 скорее, чем база 2.)

Может показаться, что центральной проблемой является выбор достаточно большого начального диапазона, чтобы независимо от того, сколько символов мы должны кодировать, у нас всегда будет текущий диапазон, достаточно большой, чтобы разделить его на ненулевые поддиапазоны. На практике, однако, это не проблема, потому что вместо того, чтобы начинать с очень большого диапазона и постепенно сужать его, кодировщик работает с меньшим диапазоном чисел в любой момент времени. После кодирования некоторого количества цифр крайние левые цифры не изменятся. В примере после кодирования всего трех символов мы уже знали, что наш окончательный результат будет начинаться с «2». Больше цифр смещается справа, а цифры слева отправляются. Это показано в следующем коде:

int низкий = 0;int ассортимент = 100000;пустота Бегать(){	Кодировать(0, 6, 10);	// А	Кодировать(0, 6, 10);	// А	Кодировать(6, 2, 10);	// B	Кодировать(0, 6, 10);	// А	Кодировать(8, 2, 10);	// 	// выводим последние цифры - см. ниже	в то время как (ассортимент < 10000)		EmitDigit();	низкий += 10000;	EmitDigit();}пустота EmitDigit(){	Консоль.Написать(низкий / 10000);	низкий = (низкий % 10000) * 10;	ассортимент *= 10;}пустота Кодировать(int Начните, int размер, int Всего){	// настраиваем диапазон в зависимости от интервала символа	ассортимент /= Всего;	низкий += Начните * ассортимент;	ассортимент *= размер;	// проверяем, одинакова ли самая левая цифра во всем диапазоне	в то время как (низкий / 10000 == (низкий + ассортимент) / 10000)		EmitDigit();	// скорректировать диапазон - см. причину ниже	если (ассортимент < 1000)	{		EmitDigit();		EmitDigit();		ассортимент = 100000 - низкий;	}}

Для завершения нам может потребоваться ввести несколько дополнительных цифр. Верхняя цифра низкий вероятно, слишком мало, поэтому нам нужно увеличить его, но мы должны убедиться, что мы не увеличиваем его за низкий + диапазон. Итак, сначала нам нужно убедиться ассортимент достаточно большой.

// выводим последние цифрыв то время как (ассортимент < 10000)	EmitDigit();низкий += 10000;EmitDigit();

Одна проблема, которая может возникнуть с Кодировать функция выше заключается в том, что ассортимент может стать очень маленьким, но низкий и низкий + диапазон все еще имеют разные первые цифры. Это может привести к тому, что интервал будет иметь недостаточную точность, чтобы различать все символы в алфавите. Когда это происходит, нам нужно немного поиграть, вывести первую пару цифр, даже если мы можем отклониться на одну, и заново отрегулировать диапазон, чтобы дать нам как можно больше места. Декодер будет следовать тем же шагам, поэтому он будет знать, когда это нужно сделать, чтобы сохранить синхронизацию.

// это происходит непосредственно перед концом Encode () вышеесли (ассортимент < 1000){	EmitDigit();	EmitDigit();	ассортимент = 100000 - низкий;}

В этом примере использовалась база 10, но в реальной реализации будет использоваться только двоичный файл с полным диапазоном целочисленного типа данных. Вместо того 10000 и 1000 вы, вероятно, будете использовать шестнадцатеричные константы, такие как 0x1000000 и 0x10000. Вместо того, чтобы выдавать цифру за раз, вы должны выдавать байт за раз и использовать операцию байтового сдвига вместо умножения на 10.

Декодирование использует точно такой же алгоритм с добавлением отслеживания текущего код значение, состоящее из цифр, считываемых компрессором. Вместо высшей цифры низкий вы просто выбросите его, но вы также сдвинете верхнюю цифру код и сдвиньте новую цифру, считанную компрессором. Использовать AppendDigit ниже вместо EmitDigit.

int код = 0;int низкий = 0;int ассортимент = 1;пустота InitializeDecoder(){        AppendDigit();  // в этом примере кода на самом деле нужен только 1 из них        AppendDigit();        AppendDigit();        AppendDigit();        AppendDigit();}пустота AppendDigit(){	код = (код % 10000) * 10 + ReadNextDigit();	низкий = (низкий % 10000) * 10;	ассортимент *= 10;}пустота Декодировать(int Начните, int размер, int Всего)  // Декодирование такое же, как и кодирование, с заменой EmitDigit на AppendDigit{	// настраиваем диапазон в зависимости от интервала символа	ассортимент /= Всего;	низкий += Начните * ассортимент;	ассортимент *= размер;	// проверяем, одинакова ли самая левая цифра во всем диапазоне	в то время как (низкий / 10000 == (низкий + ассортимент) / 10000)		AppendDigit();	// скорректировать диапазон - см. причину ниже	если (ассортимент < 1000)	{		AppendDigit();		AppendDigit();		ассортимент = 100000 - низкий;	}}

Чтобы определить, какие интервалы вероятности применять, декодеру необходимо посмотреть текущее значение код в пределах интервала [минимум, минимум + диапазон) и решите, какой символ он представляет.

пустота Бегать(){	int Начните = 0;	int размер;	int Всего = 10;	AppendDigit();                    // нужно получить диапазон / всего> 0	в то время как (Начните < 8)                 // останавливаемся при получении EOM	{		int v = GetValue(Всего);  // код в каком диапазоне символов?		переключатель (v)                // конвертируем значение в символ		{			кейс 0:			кейс 1:			кейс 2:			кейс 3:			кейс 4:			кейс 5: Начните=0; размер=6; Консоль.Написать("А"); перерыв;			кейс 6:			кейс 7: Начните=6; размер=2; Консоль.Написать("B"); перерыв;			по умолчанию: Начните=8; размер=2; Консоль.WriteLine("");		}		Декодировать(Начните, размер, Всего);	}}int GetValue(int Всего){        вернуть (код - низкий) / (ассортимент / Всего);}

Для приведенного выше примера AABA это вернет значение в диапазоне от 0 до 9. Значения от 0 до 5 будут представлять A, 6 и 7 будут представлять B, а 8 и 9 будут представлять .

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

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

Однако на практике так называемый диапазон кодеры как правило, реализуются примерно так, как описано в статье Мартина,^[1] в то время как арифметические кодеры обычно не называются кодировщиками диапазона. Часто отмечаемой особенностью таких кодировщиков диапазона является тенденция выполнять перенормировку по байтам за раз, а не по одному биту за раз (как это обычно бывает). Другими словами, кодеры диапазонов обычно используют байты в качестве кодирующих цифр, а не биты. Хотя это действительно снижает степень сжатия, которое может быть достигнуто очень небольшой величиной, это быстрее, чем при выполнении перенормировки для каждого бита.

Смотрите также

использованная литература

^ ^а ^б Г. Найджел Н. Мартин, Кодирование диапазона: алгоритм удаления избыточности из оцифрованного сообщения., Конференция по записи видео и данных, Саутгемптон, Великобритания, 24–27 июля 1979 г.
^ «Алгоритмы кодирования исходного кода для быстрого сжатия данных» Ричард Кларк Паско, Стэнфорд, Калифорния, 1976
^ "На накладные расходы кодеров диапазона ", Тимоти Б. Террибери, Техническая записка 2008 г.
^ Патент США 4,122,440 - (IBM) Подана 4 марта 1977 г., предоставлена 24 октября 1978 г. (срок действия истек)

внешние ссылки

[compressconsult-1] а ^б Г. Найджел Н. Мартин, Кодирование диапазона: алгоритм удаления избыточности из оцифрованного сообщения., Конференция по записи видео и данных, Саутгемптон, Великобритания, 24–27 июля 1979 г.

[2] «Алгоритмы кодирования исходного кода для быстрого сжатия данных» Ричард Кларк Паско, Стэнфорд, Калифорния, 1976

[3] "На накладные расходы кодеров диапазона ", Тимоти Б. Террибери, Техническая записка 2008 г.

[4] Патент США 4,122,440 - (IBM) Подана 4 марта 1977 г., предоставлена 24 октября 1978 г. (срок действия истек)

[1]

[2]

[3]

[4]