Інтервальне кодуванняІнтервальне кодування (діапазонне кодування) — ентропійний метод кодування, запропонований Г. Найджелом Мартіном (G. Nigel N. Martin) 1979 року[1]. Різновид арифметичного кодування[2]. ОписІнтервальне кодування кодує всі символи повідомлення в одне число, на відміну від, наприклад, коду Гаффмана, який присвоює кожному символу послідовність біт і об'єднує всі бітові послідовності разом. ПрикладНехай, необхідно зашифрувати повідомлення "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) 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;
}
}
Щоб закінчити, нам може знадобитися виділити кілька зайвих цифр. Старша цифра значення // випускаємо останні цифри
while (range < 10000)
EmitDigit();
low += 10000;
EmitDigit();
Однією з проблем, яка може виникнути із наведеною вище функцією // це відбувається безпосередньо перед кінцем Encode() вище
if (range < 1000)
{
EmitDigit();
EmitDigit();
range = 100000 - low;
}
У цьому прикладі використано основу 10, але в реальній реалізація краще використати двійкову систему із повним діапазоном цілого типу даних. Замість
При декодуванні використовується цей самий алгоритм з додаванням відстеження поточного значення 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;
}
}
Для того, щоб визначити, які інтервали ймовірності застосовувати, декодеру потрібно переглянути поточне значення 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] тоді як арифметичні кодувальники взагалі не називають інтервальними. Часто відмінністю інтервальних кодувальників є побайтове, а не побітове перенормування. Іншими словами, інтервальні кодувальники, як правило, використовують для кодування цифр байти, а не біти. Хоча це й знижує рівень стиснення, але виконується швидше, ніж перенормування для кожного біта. Див. такожПримітки
|
||||||||||||||||||||||||||||||||
Portal di Ensiklopedia Dunia
