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

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

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

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

Графическое представление процесса кодирования. Кодируемое здесь сообщение - "AABA <EOM>"

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

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

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

Пример [ править ]

Предположим, мы хотим закодировать сообщение «AABA <EOM>», где <EOM> - это символ конца сообщения. В этом примере предполагается, что декодер знает, что мы намерены закодировать ровно пять символов в системе счисления с основанием 10 (с учетом 10 ⁵ различных комбинаций символов с диапазоном [0, 100000)) с использованием распределения вероятностей {A:. 60; B: 0,20; <EOM>: .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 () { Кодировать ( 0 ,  6 ,  10 ); // Кодирование ( 0 ,  6 ,  10 ); // Кодирование ( 6 ,  2 ,  10 ); // B Encode ( 0 ,  6 ,  10 ); // Кодирование ( 8 ,  2 ,  10 ); // <EOM>// выводим последние цифры - см. ниже while  ( range  <  10000 ) EmitDigit ();низкий  + =  10000 ; EmitDigit (); }void  EmitDigit () { Консоль . Написать ( низкий  /  10000 ); низкий  =  ( низкий  %  10000 )  *  10 ; диапазон  * =  10 ; }void  Encode ( int  start ,  int  size ,  int  total ) { // настраиваем диапазон на основе интервала символа range  / =  total ; низкий  + =  начало  *  диапазон ; диапазон  * =  размер ;// проверяем, одинакова ли самая левая цифра во всем диапазоне while  ( low  /  10000  ==  ( low  +  range )  /  10000 ) EmitDigit ();// скорректировать диапазон - см. причину ниже if  ( range  <  1000 ) { EmitDigit (); EmitDigit (); range  =  100000  -  низкий ; } }

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

// выводим последние цифры while  ( диапазон  <  10000 ) EmitDigit ();низкий  + =  10000 ; EmitDigit ();

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

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

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

При декодировании используется точно такой же алгоритм с добавлением отслеживания текущего codeзначения, состоящего из цифр, считанных из компрессора. Вместо того, чтобы испускать верхнюю цифру, lowвы просто выбросите ее, но вы также сдвинете верхнюю цифру codeи переместите новую цифру, считанную с компрессора. Используйте 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  -  низкий ; } }

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

void  Run () { int  start  =  0 ; int  size ; int  total  =  10 ; AppendDigit ();  // нужно получить диапазон / всего> 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 ;  Консоль . Написать ( «А» );  перерыв ; case  6 : case  7 :  start = 6 ;  size = 2 ;  Консоль . Написать ( «Б» );  перерыв ; по умолчанию :  start = 8 ; size = 2 ;  Консоль . WriteLine ( "" ); } Декодирование ( начало ,  размер ,  итого ); } }int  GetValue ( int  total ) {  return  ( код  -  низкий )  /  ( диапазон  /  всего ); }

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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