Кодирование диапазона

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

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

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

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

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

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

Пример

Предположим, мы хотим закодировать сообщение «AABA<EOM>», где <EOM> — это символ конца сообщения. В этом примере предполагается, что декодер знает, что мы намерены закодировать ровно пять символов в десятичной системе счисления (с учетом 10 символов). ⁵ различные комбинации символов в диапазоне [0, 100000)) с использованием распределения вероятностей {A: .60; Б: 0,20; <МНВ>: .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», попадают в наш конечный диапазон, это один из трехзначных префиксов, которые мы можем передать, и которые однозначно передают наше исходное сообщение. (Тот факт, что на самом деле таких префиксов восемь, означает, что у нас все еще есть недостатки. Они возникли из-за того, что мы использовали базу 10, а не систему 2. )

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

int low = 0;
int range = 100000;

void Run()
{
	Encode(0, 6, 10);	// A
	Encode(0, 6, 10);	// A
	Encode(6, 2, 10);	// B
	Encode(0, 6, 10);	// A
	Encode(8, 2, 10);	// <EOM>

	// emit final digits - see below
	while (range < 10000)
		EmitDigit();

	low += 10000;
	EmitDigit();
}

void EmitDigit()
{
	Console.Write(low / 10000);
	low = (low % 10000) * 10;
	range *= 10;
}

void Encode(int start, int size, int total)
{
	// adjust the range based on the symbol interval
	range /= total;
	low += start * range;
	range *= size;

	// check if left-most digit is same throughout range
	while (low / 10000 == (low + range) / 10000)
		EmitDigit();

	// readjust range - see reason for this below
	if (range < 1000)
	{
		EmitDigit();
		EmitDigit();
		range = 100000 - low;
	}
}

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

// emit final digits
while (range < 10000)
	EmitDigit();

low += 10000;
EmitDigit();

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

Например, представьте, что входной поток привел кодер к правому открытому интервалу [59888, 60188), то есть low = 59888 и range = 300. Хитрость заключается в том, чтобы сузить интервал до [59888, 60000) = [ 59 888, 59 999], что позволяет кодировщику выдавать две самые левые цифры числа. low, и измените интервал на [88800, 99999] = [88800, 100000), то есть low = 88800 и range = 100000 - low.

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

// this goes just before the end of Encode() above
if (range < 1000)
{
	EmitDigit();
	EmitDigit();
	range = 100000 - low;
}

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

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

int code = 0;
int low = 0;
int range = 1;

void InitializeDecoder()
{
        AppendDigit();  // with this example code, only 1 of these is actually needed
        AppendDigit();
        AppendDigit();
        AppendDigit();
        AppendDigit();
}

void AppendDigit()
{
	code = (code % 10000) * 10 + ReadNextDigit();
	low = (low % 10000) * 10;
	range *= 10;
}

void Decode(int start, int size, int total)  // Decode is same as Encode with EmitDigit replaced by AppendDigit
{
	// adjust the range based on the symbol interval
	range /= total;
	low += start * range;
	range *= size;

	// check if left-most digit is same throughout range
	while (low / 10000 == (low + range) / 10000)
		AppendDigit();

	// readjust range - see reason for this below
	if (range < 1000)
	{
		AppendDigit();
		AppendDigit();
		range = 100000 - low;
	}
}

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

void Run()
{
	int start = 0;
	int size;
	int total = 10;
	InitializeDecoder();          // need to get range/total >0
	while (start < 8)             // stop when receive EOM
	{
		int v = GetValue(total);  // code is in what symbol range?
		switch (v)                // convert value to symbol
		{
			case 0:
			case 1:
			case 2:
			case 3:
			case 4:
			case 5: start=0; size=6; Console.Write("A"); break;
			case 6:
			case 7: start=6; size=2; Console.Write("B"); break;
			default: start=8; size=2; Console.WriteLine("");
		}
		Decode(start, size, total);
	}
}

int GetValue(int total)
{
	return (code - low) / (range / total);
}

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

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

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

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

См. также

Ссылки

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

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

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

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

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

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

[1]

[2]

[3]

[4]