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

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

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

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

Пример

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

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

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

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», попадают в наш последний диапазон, это один из трехзначных префиксов, которые мы могли бы передать, что однозначно передало бы наше исходное сообщение. (Тот факт, что на самом деле существует восемь таких префиксов, означает, что у нас все еще есть недостатки. Они появились благодаря использованию base 10 вместо base 2.)

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

int low = 0; int range = 100000; void Run () {Кодировать (0, 6, 10); // Кодирование (0, 6, 10); // Кодирование (6, 2, 10); // B Encode (0, 6, 10); // Кодирование (8, 2, 10); // // выводим последние цифры - см. Ниже 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достаточно велик.

// испускать последние цифры while (диапазон < 10000) EmitDigit(); low += 10000; EmitDigit();

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

// это происходит непосредственно перед концом Encode () ab ove if (range < 1000) { EmitDigit(); EmitDigit(); range = 100000 - low; }

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

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

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

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

void Run () {int start = 0; int size; int total = 10; AppendDigit (); // нужно получить диапазон / всего>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 это вернет значение в диапазоне от 0 до 9. Значения от 0 до 5 будут представлять A, 6 и 7 будут представлять B и 8 и 9 будут представлять .

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

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

• Арифметическое кодирование
• Асимметричные системы счисления
• Сжатие данных
• Энтропийное кодирование
• Кодирование Хаффмана
• Формат многомасштабной электрофизиологии
• Кодирование Шеннона – Фано

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

• Кодировщик диапазона
• «Кодировщик диапазона» от Артуро Кампоса
• «Анатомия кодировщика диапазона» от Эндрю Поляра
• Быстрая реализация кодирования диапазона и RANS Джеймса К. Бонфилда