Кодирование диапазона (или кодирование диапазона ) — это метод энтропийного кодирования, определенный Г. Найджелом Н. Мартином в статье 1979 года [1], который фактически переоткрыл арифметический код FIFO, впервые представленный Ричардом Кларком Паско в 1976 году [2]. При наличии потока символов и их вероятностей кодер диапазона создает эффективный по пространству поток битов для представления этих символов, а при наличии потока и вероятностей декодер диапазона выполняет обратный процесс.
Кодирование диапазонов очень похоже на арифметическое кодирование , за исключением того, что кодирование выполняется с помощью цифр в любой базе, а не битов, и поэтому оно быстрее при использовании больших баз (например, байта ) при небольших затратах на эффективность сжатия. [3] После истечения срока действия первого (1978) патента на арифметическое кодирование [4] кодирование диапазонов, по-видимому, было явно свободно от патентных обременений. Это особенно подогрело интерес к этой технике в сообществе разработчиков программного обеспечения с открытым исходным кодом . С того времени также истекли патенты на различные известные методы арифметического кодирования.
Кодирование диапазона концептуально кодирует все символы сообщения в одно число, в отличие от кодирования Хаффмана , которое назначает каждому символу битовый шаблон и объединяет все битовые шаблоны вместе. Таким образом, кодирование диапазона может достигать больших коэффициентов сжатия, чем нижняя граница кодирования Хаффмана «один бит на символ», и оно не страдает неэффективностью, которая свойственна Хаффману при работе с вероятностями, которые не являются точной степенью двойки .
Центральная концепция кодирования диапазона заключается в следующем: при наличии достаточно большого диапазона целых чисел и оценки вероятности для символов начальный диапазон можно легко разделить на поддиапазоны, размеры которых пропорциональны вероятности символа, который они представляют. Затем каждый символ сообщения может быть закодирован по очереди, уменьшая текущий диапазон до того поддиапазона, который соответствует следующему символу, который должен быть закодирован. Декодер должен иметь ту же оценку вероятности, что и используемый кодер, которая может быть либо отправлена заранее, либо получена из уже переданных данных, либо быть частью компрессора и декомпрессора.
Когда все символы закодированы, простого указания поддиапазона достаточно для передачи всего сообщения (конечно, предполагая, что декодер каким-то образом уведомлен, когда он извлек все сообщение). Одного целого числа на самом деле достаточно для определения поддиапазона, и может даже не потребоваться передавать все целое число; если есть последовательность цифр, такая, что каждое целое число, начинающееся с этого префикса, попадает в поддиапазон, то для определения поддиапазона и, таким образом, передачи сообщения достаточно одного префикса.
Предположим, мы хотим закодировать сообщение "AABA<EOM>", где <EOM> — символ конца сообщения. Для этого примера предполагается, что декодер знает, что мы намерены закодировать ровно пять символов в десятичной системе счисления (что допускает 10 5 различных комбинаций символов с диапазоном [0, 100000)), используя распределение вероятностей {A: .60; B: .20; <EOM>: .20}. Кодер разбивает диапазон [0, 100000) на три поддиапазона:
А: [ 0, 60000)Б: [ 60000, 80000)<ЭОМ>: [ 80000, 100000)
Поскольку наш первый символ — A, он сокращает наш начальный диапазон до [0, 60000). Второй выбор символа оставляет нам три поддиапазона этого диапазона. Мы показываем их после уже закодированного 'A':
АА: [ 0, 36000)АБ: [36000, 48000)А<ЭОМ>: [ 48000, 60000)
При кодировании двух символов наш диапазон теперь равен [0, 36000), а наш третий символ приводит к следующим вариантам:
ААА: [ 0, 21600)ААБ: [ 21600, 28800)АА<ЭОМ>: [ 28800, 36000)
На этот раз это второй из трех вариантов, представляющий сообщение, которое мы хотим закодировать, и наш диапазон становится [21600, 28800). Может показаться, что определить наши поддиапазоны в этом случае сложнее, но на самом деле это не так: мы можем просто вычесть нижнюю границу из верхней границы, чтобы определить, что в нашем диапазоне 7200 чисел; что первые 4320 из них представляют 0,60 от общего числа, следующие 1440 представляют следующие 0,20, а оставшиеся 1440 представляют оставшиеся 0,20 от общего числа. Возвращая нижнюю границу, мы получаем наши диапазоны:
ААБА: [21600, 25920)ААББ: [25920, 27360)ААБ<ЭОМ>: [27360, 28800)
Наконец, сузив наш диапазон до [21600, 25920), нам осталось закодировать еще один символ. Используя ту же технику, что и раньше для разделения диапазона между нижней и верхней границей, мы находим три поддиапазона:
ААБАА: [21600, 24192)ААБАБ: [24192, 25056)ААБА<ЭОМ>: [25056, 25920)
И поскольку <EOM> — наш последний символ, наш последний диапазон — [25056, 25920]. Поскольку все пятизначные целые числа, начинающиеся с «251», попадают в наш последний диапазон, это один из трехзначных префиксов, который мы могли бы передать, чтобы однозначно передать наше исходное сообщение. (Тот факт, что на самом деле существует восемь таких префиксов, подразумевает, что у нас все еще есть неэффективности. Они были введены из-за того, что мы использовали основание 10 вместо основания 2. )
Центральная проблема может показаться в выборе начального диапазона достаточно большого, чтобы независимо от того, сколько символов нам нужно закодировать, у нас всегда был текущий диапазон, достаточно большой для разделения на ненулевые поддиапазоны. Однако на практике это не проблема, потому что вместо того, чтобы начинать с очень большого диапазона и постепенно его сужать, кодер работает с меньшим диапазоном чисел в любой момент времени. После того, как некоторое количество цифр будет закодировано, самые левые цифры не изменятся. В примере после кодирования всего трех символов мы уже знали, что наш конечный результат начнется с «2». Больше цифр смещается вправо по мере отправки цифр слева. Это проиллюстрировано в следующем коде:
int low = 0 ; int range = 100000 ; void Run () { Кодировать ( 0 , 6 , 10 ); // Кодировать A ( 0 , 6 , 10 ) ; // Кодировать A ( 6 , 2 , 10 ); // Кодировать B ( 0 , 6 , 10 ); // Кодировать A ( 8 , 2 , 10 ); // <EOM> // выдаем последние цифры - см. ниже while ( range < 10000 ) EmitDigit (); низкий += 10000 ; ИзлучаемаяЦифра (); } 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иметь отличающиеся первые цифры. Это может привести к тому, что интервал будет иметь недостаточную точность для различения всех символов в алфавите. Когда это происходит, нам нужно немного подтасовать, вывести первые пару цифр, даже если мы можем ошибиться на одну, и перенастроить диапазон, чтобы дать нам как можно больше места.
Например, представьте, что входной поток привел кодер к правому открытому интервалу [59888, 60188), то есть low = 59888и range = 300. Хитрость заключается в том, чтобы сузить интервал до [59888, 60000) = [ 59 888, 59 999], что позволяет кодеру выдать две самые левые цифры lowи перенастроить интервал до [88800, 99999] = [88800, 100000), то есть low = 88800и range = 100000 - low.
Декодер будет выполнять те же шаги, чтобы знать, когда это необходимо сделать для синхронизации.
// это происходит непосредственно перед концом Encode() выше if ( range < 1000 ) { EmitDigit (); EmitDigit (); range = 100000 - low ; } В этом примере использовалось основание 10, но реальная реализация использовала бы просто двоичный код с полным диапазоном собственного целочисленного типа данных. Вместо 10000and 1000вы, скорее всего, использовали бы шестнадцатеричные константы, такие как 0x1000000and 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 () { code = ( code % 10000 ) * 10 + ReadNextDigit (); low = ( low % 10000 ) * 10 ; range *= 10 ; } void Decode ( int start , int size , int total ) // Декодирование аналогично 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в интервале [низкий, низкий+диапазон) и решить, какой символ оно представляет.
void Run () { int start = 0 ; int size ; int total = 10 ; InitializeDecoder (); // необходимо получить 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], в то время как арифметические кодеры в целом не называются кодерами диапазона. Часто отмечаемой особенностью таких кодеров диапазона является тенденция выполнять перенормировку по байту за раз, а не по одному биту за раз (как это обычно бывает). Другими словами, кодеры диапазона, как правило, используют байты в качестве кодирующих цифр, а не биты. Хотя это и уменьшает объем сжатия, который может быть достигнут, на очень небольшую величину, это быстрее, чем при выполнении перенормировки для каждого бита.