Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Інтервальне кодування (діапазонне кодування) — ентропійний метод кодування, запропонований Г. Найджелом Мартіном (G. Nigel N. Martin) 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)
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.». Оскільки це просто різні інтерпретації одного методу кодування, то будь-який арифметичний кодувальник є інтервальним кодувальником, і навпаки.
На практиці, однак, так звані інтервальні кодувальники здебільшого реалізують так, як описано в статті Мартіна, тоді як арифметичні кодувальники взагалі не називають інтервальними. Часто відмінністю інтервальних кодувальників є побайтове, а не побітове перенормування. Іншими словами, інтервальні кодувальники, як правило, використовують для кодування цифр байти, а не біти. Хоча це й знижує рівень стиснення, але виконується швидше, ніж перенормування для кожного біта.
Див. також
Примітки
- 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Intervalne koduvannya diapazonne koduvannya entropijnij metod koduvannya zaproponovanij G Najdzhelom Martinom G Nigel N Martin 1979 roku Riznovid arifmetichnogo koduvannya OpisIntervalne koduvannya koduye vsi simvoli povidomlennya v odne chislo na vidminu vid napriklad kodu Gaffmana yakij prisvoyuye kozhnomu simvolu poslidovnist bit i ob yednuye vsi bitovi poslidovnosti razom Priklad Nehaj neobhidno zashifruvati povidomlennya AABA lt EOM gt de lt EOM gt ce simvol kincya povidomlennya angl end of message Dlya cogo prikladu peredbachayetsya sho dekoduvalnik znaye sho mi mayemo namir zakoduvati rivno p yat simvoliv u desyatkovij sistemi chislennya algoritm u danomu vipadku pidtrimuye 105 riznih kombinacij simvoliv v diapazoni 0 100000 vikoristovuyuchi rozpodil jmovirnostej A 0 60 B 0 20 lt EOM gt 0 20 Koduvalnik dilit diapazon 0 100000 na tri piddiapazoni A 0 60000 B 60000 80000 lt EOM gt 80000 100000 Oskilki pershij simvol A ce znizhuye nash pochatkovij diapazon do 0 60000 Drugij simvol dilit cej diapazon she na tri chastini AA 0 36000 AB 36000 48000 A lt EOM gt 48000 60000 AAA 0 21600 AAB 21600 28800 AA lt EOM gt 28800 36000 Na cej raz vibir padaye na drugij z troh variantiv yaki yavlyayut soboyu povidomlennya yake mi hochemo zakoduvati i nash diapazon staye 21600 28800 Mozhe zdatisya sho stalo skladnishe viznachiti nashi piddiapazoni v danomu vipadku ale naspravdi ce ne tak mi mozhemo prosto vidnyati nizhnyu mezhu z verhnoyi mezhi shob viznachiti sho v nashomu diapazoni dostupno 7200 chisel pershi 4320 z nih predstavlyayut 0 60 vid zagalnogo chisla nastupni 1440 predstavlyayut nastupni 0 20 a reshtu 1440 predstavlyayut 0 20 sho zalishilisya vid zagalnogo diapazonu Zbilshennya nizhnoyi mezhi daye nam nashi diapazoni AABA 21600 25920 AABB 25920 27360 AAB lt EOM gt 27360 28800 Nareshti nash diapazon zvuzivsya do 21600 25920 u nas zalishivsya tilki odin simvol dlya koduvannya Vikoristovuyuchi tu zh tehniku yak i ranishe dlya podilu diapazon mizh nizhnoyu ta verhnoyu mezheyu mi znahodimo tri piddiapazoni AABAA 21600 24192 AABAB 24192 25056 AABA lt EOM gt 25056 25920 I oskilki lt EOM gt ce nash ostannij simvol nash kincevij diapazon 25056 25920 Oskilki vsi p yatiznachni chisla sho pochinayutsya z 251 potraplyayut v nash ostannij ryad to ce ye odin z triznachnih prefiksiv yakij odnoznachno peredaye pochatkove povidomlennya toj fakt sho naspravdi isnuye visim takih prefiksiv oznachaye sho mozhna optimizuvati algoritm Voni vinikli vnaslidok vikoristannya desyatkovoyi sistemi chislennya a ne dvijkovoyi Osnovnoyu problemoyu mozhe viyavitis vibir pochatkovogo diapazonu dostatno velikogo shob nezalezhno vid togo skilki simvoliv nam potribno zakoduvati mi zavzhdi mali potochnij diapazon dostatno velikij shob rozdiliti jogo na nenulovi piddiapazoni Na praktici odnak ce ne problema oskilki zamist togo shob pochinati z duzhe velikogo diapazonu i postupovo zvuzhuvati jogo koduvalnik pracyuye z menshim diapazonom chisel u bud yakij moment chasu Pislya koduvannya deyakoyi kilkosti cifr krajni livi cifri ne zminyuvatimutsya U prikladi pislya koduvannya lishe troh simvoliv mi vzhe znali sho nash kincevij rezultat pochnetsya z 2 Ce pokazano v takomu kodi 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 lt EOM gt vipuskayemo kincevi cifri div nizhche while range lt 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 koriguyemo diapazon na osnovi intervalu simvoliv range total low start range range size pereviryayemo chi liva cifra odnakova po vsomu diapazonu while low 10000 low range 10000 EmitDigit koriguyemo diapazon prichinu cogo div nizhche if range lt 1000 EmitDigit EmitDigit range 100000 low Shob zakinchiti nam mozhe znadobitisya vidiliti kilka zajvih cifr Starsha cifra znachennya low mabut zanadto mala tomu nam potribno zbilshiti yiyi ale slid perekonatisya sho pri comu ne vijdemo za low range Otzhe spochatku potribno perekonatisya sho range dostatno velikij vipuskayemo ostanni cifri while range lt 10000 EmitDigit low 10000 EmitDigit Odniyeyu z problem yaka mozhe viniknuti iz navedenoyu vishe funkciyeyu Encode ye te sho range mozhe stati duzhe malim a low ta low range vse odno matimut rizni pershi cifri Ce mozhe sprichiniti nedostatnyu tochnist intervalu dlya rozriznennya vsih simvoliv alfavitu Koli ce traplyayetsya nam potribno shitruvati vivesti pershi dekilka cifr hocha mi mozhemo pomilitis v odnij utochniti i povtorno vidregulyuvati diapazon shob otrimati yakomoga bilshe miscya Dekoder vikonuvatime ci diyi zavdyaki chomu znatime koli jomu potribno sinhronizuvatis ce vidbuvayetsya bezposeredno pered kincem Encode vishe if range lt 1000 EmitDigit EmitDigit range 100000 low U comu prikladi vikoristano osnovu 10 ale v realnij realizaciya krashe vikoristati dvijkovu sistemu iz povnim diapazonom cilogo tipu danih Zamist 10000 ta 1000 najpevnishe bude vikoristano shistnadcyatkovi konstanti taki yak 0x1000000 ta 0x10000 Zamist togo shob vipuskati cifru za raz bude vipuskatis bajt za raz i zamist mnozhennya na 10 bude vikoristano operaciyu zsuvu bajtiv Pri dekoduvanni vikoristovuyetsya cej samij algoritm z dodavannyam vidstezhennya potochnogo znachennya code sho skladayetsya z cifr prochitanih z kompresora Zamist togo shob vipuskati verhnyu cifru z low yiyi prosto vidkidayut ale takozh zsuvayut verhnyu cifru code i perenosyat novu cifru prochitanu z kompresora Dali zamist EmitDigit vikoristano AppendDigit int code 0 int low 0 int range 1 void InitializeDecoder AppendDigit u comu prikladi kodu naspravdi potriben lishe 1 z nih 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 taka zh yak Encode tilki EmitDigit zamineno na AppendDigit koriguyemo diapazon na osnovi intervalu simvoliv range total low start range range size pereviryayemo chi liva cifra odnakova po vsomu diapazonu while low 10000 low range 10000 AppendDigit koriguyemo diapazon prichinu cogo div nizhche if range lt 1000 AppendDigit AppendDigit range 100000 low Dlya togo shob viznachiti yaki intervali jmovirnosti zastosovuvati dekoderu potribno pereglyanuti potochne znachennya code v intervali low low range i virishiti yakij simvol vono predstavlyaye void Run int start 0 int size int total 10 AppendDigit potribno otrimati range total gt 0 while start lt 8 zupiniti yaksho dosyagnuto EOM int v GetValue total kod v yakomu diapazoni simvoliv switch v peretvoryuyemo znachennya na simvol 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 Dlya navedenogo vishe prikladu AABA lt EOM gt ce poverne znachennya v diapazoni vid 0 do 9 Znachennya vid 0 do 5 predstavlyatimut A 6 i 7 B a 8 i 9 lt EOM gt Zv yazok z arifmetichnim koduvannyamArifmetichne koduvannya analogichne intervalnomu ale vikoristovuye drobovi chisla v diapazoni 0 1 Vidpovidno kincevij arifmetichnij kod interpretuyetsya yak takij sho neyavno pochinayetsya z 0 Oskilki ce prosto rizni interpretaciyi odnogo metodu koduvannya to bud yakij arifmetichnij koduvalnik ye intervalnim koduvalnikom i navpaki Na praktici odnak tak zvani intervalni koduvalniki zdebilshogo realizuyut tak yak opisano v statti Martina todi yak arifmetichni koduvalniki vzagali ne nazivayut intervalnimi Chasto vidminnistyu intervalnih koduvalnikiv ye pobajtove a ne pobitove perenormuvannya Inshimi slovami intervalni koduvalniki yak pravilo vikoristovuyut dlya koduvannya cifr bajti a ne biti Hocha ce j znizhuye riven stisnennya ale vikonuyetsya shvidshe nizh perenormuvannya dlya kozhnogo bita Div takozhKoduvannya Shennona FanoPrimitkiG Nigel N Martin Range encoding An algorithm for removing redundancy from a digitized message 14 zhovtnya 2004 u Wayback Machine Video amp Data Recording Conference Southampton UK July 24 27 1979 Source coding algorithms for fast data compression Richard Clark Pasco Stanford CA 1976