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

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

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

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

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

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

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

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

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

А: [0, 60000)
 Б: [60000, 80000)
 <EOM>: [ 80000, 100000)

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

АА: [ 0, 36000)
 АБ: [ 36000, 48000)
 A<EOM>: [ 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)
 AAB<EOM>: [27360, 28800)

Наконец, когда наш диапазон сузился до [21600, 25920), нам нужно закодировать еще один символ. Используя ту же технику, что и раньше, для разделения диапазона между нижней и верхней границей, мы находим три поддиапазона:

ОТЕЦ: [21600, 24192)
 ААБАБ: [24192, 25056)
 ОТЕЦ<ЭОМ>: [25056, 25920)

А поскольку <EOM> — наш последний символ, наш окончательный диапазон — [25056, 25920). Поскольку все пятизначные целые числа, начинающиеся с «251», попадают в наш конечный диапазон, это один из трехзначных префиксов, которые мы можем передать, и которые однозначно передают наше исходное сообщение. (Тот факт, что на самом деле таких префиксов восемь, означает, что у нас все еще есть недостатки. Они возникли из-за того, что мы использовали систему счисления по основанию 10 , а не по основанию 2. )

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

интервал   низкий   =   0  ; 
  интервал   интервала   =   100000  ; 

  void   Run  () 
 { 
	 Закодировать  (  0  ,   6  ,   10  ); 	  // 
	 Кодирование  (  0  ,   6  ,   10  ); 	  // 
	 Кодирование  (  6  ,   2  ,   10  ); 	  // B 
	 -кодирование  (  0  ,   6  ,   10  ); 	  // 
	 Кодирование  (  8  ,   2  ,   10  ); 	  // <EOM> 

	 // выводим последние цифры - см. ниже 
	 while   (  диапазон   <   10000  ) 
		 EmitDigit  (); 

	  низкий   +=   10000  ; 
	  ЭмитЦифра  (); 
  } 

 void   EmitDigit  () 
 { 
	 Console  .   Запись  (  низкий   /   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  (); 
		  ЭмитЦифра  (); 
		  диапазон   =   100000   –   низкий  ; 
	  } 
 }

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

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

  низкий   +=   10000  ; 
  ЭмитЦифра  ();

Одна из проблем, которая может возникнуть при 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  (); 
	  ЭмитЦифра  (); 
	  диапазон   =   100000   –   низкий  ; 
  }

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

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

международный   код   =   0  ; 
  интервал   низкий   =   0  ; 
  интервал   диапазона   =   1  ; 

  void   InitializeDecoder  () 
 { 
         AppendDigit  ();     // в этом примере кода действительно необходим только 1 из них 
         AppendDigit  (); 
          ДобавитьЦифру  (); 
          ДобавитьЦифру  (); 
          ДобавитьЦифру  (); 
  } 

 void   AppendDigit  () 
 { 
	 код   =   (  код   %   10000  )   *   10   +   ReadNextDigit  (); 
	  низкий   =   (  низкий   %   10000  )   *   10  ; 
	  диапазон   *=   10  ; 
  } 

 void   Decode  (  int   start  ,   int   size  ,   int   total  )    // Декодирование аналогично кодированию с заменой EmitDigit на AppendDigit 
 { 
	 // корректировка диапазона на основе интервала символа 
	 range   /=   total  ; 
	  низкий   +=   начало   *   диапазон  ; 
	  диапазон   *=   размер  ; 

	  // проверяем, одинакова ли самая левая цифра во всем диапазоне 
	 while   (  low   /   10000   ==   (  low   +   range  )   /   10000  ) 
		 AppendDigit  (); 

	  // корректировка диапазона — см. причину ниже 
	 if   (  range   <   1000  ) 
	 { 
		 AppendDigit  (); 
		  ДобавитьЦифру  (); 
		  диапазон   =   100000   –   низкий  ; 
	  } 
 }

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

void   Run  () 
 { 
	 int   start   =   0  ; 
	  внутренний   размер  ; 
	  целое   число   =   10  ; 
	  ИнициализироватьДекодер  ();             // нужно получить диапазон/общее количество >0 
	 while   (  start   <   8  )               // остановиться при получении EOM 
	 { 
		 int   v   =   GetValue  (  total  );     // в каком диапазоне символов находится код? 
		  переключатель   (  v  )                  // преобразуем значение в символ 
		 { 
			 случай   0  : 
			 случай   1  : 
			 случай   2  : 
			 случай   3  : 
			 случай   4  : 
			 случай   5  :   start  =  0  ;    размер  =  6  ;    Консоль  .   Написать  "  )  ;    перерыв  ; 
			  случай   6  : 
			 случай   7  :   начало  =  6  ;    размер  =  2  ;    Консоль  .   Напишите  (  «Б»  );    перерыв  ; 
			  по умолчанию  :   начало  =  8  ;    размер  =  2  ;    Консоль  .   WriteLine  (  ""  ); 
		  } 
		 Декодировать  (  начало  ,   размер  ,   итог  ); 
	  } 
 } 

 int   GetValue  (  int   total  ) 
 { 
	 return   (  code   -   low  )   /   (  диапазон   /   всего  ); 
  }

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

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

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

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

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

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

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

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

[compressconsult-1] Перейти обратно: ^а ^б Дж. Найджел Н. Мартин, Кодирование диапазона: алгоритм устранения избыточности из оцифрованного сообщения , Конференция по записи видео и данных, Саутгемптон , Великобритания, 24–27 июля 1979 г.

[2] «Алгоритмы исходного кодирования для быстрого сжатия данных» Ричард Кларк Паско, Стэнфорд, Калифорния, 1976 г.

[3] « О накладных расходах кодеров диапазона », Тимоти Б. Терриберри, Техническая заметка, 2008 г.

[4] Патент США 4 122 440 - (IBM) подан 4 марта 1977 г., выдан 24 октября 1978 г. (срок действия истек)

[1]

[2]

[3]

[4]