Інтервальне кодування

Інтервальне кодування (діапазонне кодування) — ентропійний метод кодування, запропонований Г. Найджелом Мартіном (G. Nigel N. Martin) 1979 року^[1]. Різновид арифметичного кодування^[2].

Опис

Інтервальне кодування кодує всі символи повідомлення в одне число, на відміну від, наприклад, коду Гаффмана, який присвоює кожному символу послідовність біт і об'єднує всі бітові послідовності разом.

Приклад

Нехай, необхідно зашифрувати повідомлення "AABA<EOM>, де <EOM> — це символ кінця повідомлення (англ. end of message). Для цього прикладу передбачається, що декодувальник знає, що ми маємо намір закодувати рівно п'ять символів у десятковій системі числення (алгоритм у даному випадку підтримує 10⁵ різних комбінацій символів в діапазоні [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)

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», потрапляють в наш останній ряд, то це є один з тризначних префіксів, який однозначно передає початкове повідомлення (той факт, що насправді існує вісім таких префіксів, означає, що можна оптимізувати алгоритм. Вони виникли внаслідок використання десяткової системи числення, а не двійкової).

Основною проблемою може виявитись вибір початкового діапазону, достатньо великого, щоб незалежно від того, скільки символів нам потрібно закодувати, ми завжди мали поточний діапазон, достатньо великий, щоб розділити його на ненульові піддіапазони. На практиці, однак, це не проблема, оскільки замість того, щоб починати з дуже великого діапазону і поступово звужувати його, кодувальник працює з меншим діапазоном чисел у будь-який момент часу. Після кодування деякої кількості цифр крайні ліві цифри не змінюватимуться. У прикладі після кодування лише трьох символів ми вже знали, що наш кінцевий результат почнеться з "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>

	// випускаємо кінцеві цифри - див. нижче
	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)
{
	// коригуємо діапазон на основі інтервалу символів
	range /= total;
	low += start * range;
	range *= size;

	// перевіряємо, чи ліва цифра однакова по всьому діапазону
	while (low / 10000 == (low + range) / 10000)
		EmitDigit();

	// коригуємо діапазон - причину цього див. нижче
	if (range < 1000)
	{
		EmitDigit();
		EmitDigit();
		range = 100000 - low;
	}
}

Щоб закінчити, нам може знадобитися виділити кілька зайвих цифр. Старша цифра значення low, мабуть, занадто мала, тому нам потрібно збільшити її, але слід переконатися, що при цьому не вийдемо за low+range. Отже, спочатку потрібно переконатися, що range достатньо великий.

// випускаємо останні цифри
while (range < 10000)
	EmitDigit();

low += 10000;
EmitDigit();

Однією з проблем, яка може виникнути із наведеною вище функцією Encode є те, що range може стати дуже малим, а low та low+range все одно матимуть різні перші цифри. Це може спричинити недостатню точність інтервалу для розрізнення всіх символів алфавіту. Коли це трапляється, нам потрібно схитрувати: вивести перші декілька цифр, хоча ми можемо помилитись в одній^{[уточнити]}, і повторно відрегулювати діапазон, щоб отримати якомога більше місця. Декодер виконуватиме ці дії, завдяки чому знатиме, коли йому потрібно синхронізуватись.

// це відбувається безпосередньо перед кінцем Encode() вище
if (range < 1000)
{
	EmitDigit();
	EmitDigit();
	range = 100000 - low;
}

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

При декодуванні використовується цей самий алгоритм з додаванням відстеження поточного значення code, що складається з цифр, прочитаних з компресора. Замість того, щоб випускати верхню цифру з low її просто відкидають, але також зсувають верхню цифру code і переносять нову цифру, прочитану з компресора. Далі замість EmitDigit використано AppendDigit.

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

void InitializeDecoder()
{
        AppendDigit();  // у цьому прикладі коду насправді потрібен лише 1 з них
        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 така ж, як Encode, тільки EmitDigit замінено на AppendDigit
{
	// коригуємо діапазон на основі інтервалу символів
	range /= total;
	low += start * range;
	range *= size;

	// перевіряємо, чи ліва цифра однакова по всьому діапазону
	while (low / 10000 == (low + range) / 10000)
		AppendDigit();

	// коригуємо діапазон - причину цього див. нижче
	if (range < 1000)
	{
		AppendDigit();
		AppendDigit();
		range = 100000 - low;
	}
}

Для того, щоб визначити, які інтервали ймовірності застосовувати, декодеру потрібно переглянути поточне значення code в інтервалі [low, low+range) і вирішити, який символ воно представляє.

void Run()
{
	int start = 0;
	int size;
	int total = 10;
	AppendDigit();            // потрібно отримати range/total >0
	while (start < 8)         // зупинити, якщо досягнуто EOM
	{
		int v = GetValue(total);  // код в якому діапазоні символів?
		switch (v)                // перетворюємо значення на символ
		{
			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] тоді як арифметичні кодувальники взагалі не називають інтервальними. Часто відмінністю інтервальних кодувальників є побайтове, а не побітове перенормування. Іншими словами, інтервальні кодувальники, як правило, використовують для кодування цифр байти, а не біти. Хоча це й знижує рівень стиснення, але виконується швидше, ніж перенормування для кожного біта.

Див. також

Кодування Шеннона-Фано

Примітки

↑ ^а ^б G. Nigel N. Martin, Range encoding: An algorithm for removing redundancy from a digitized message [Архівовано 14 жовтня 2004 у Wayback Machine.], Video & Data Recording Conference, Southampton, UK, July 24-27, 1979.
↑ «Source coding algorithms for fast data compression» Richard Clark Pasco, Stanford, CA 1976

[compressconsult-1] а ^б G. Nigel N. Martin, Range encoding: An algorithm for removing redundancy from a digitized message [Архівовано 14 жовтня 2004 у Wayback Machine.], Video & Data Recording Conference, Southampton, UK, July 24-27, 1979.

[2] «Source coding algorithms for fast data compression» Richard Clark Pasco, Stanford, CA 1976

[1]