Kodowanie zakresu

Kodowanie zakresu (lub kodowanie zakresu ) to metoda kodowania entropijnego zdefiniowana przez G. Nigela N. Martina w artykule z 1979 r., która skutecznie odkryła na nowo kod arytmetyczny FIFO wprowadzony po raz pierwszy przez Richarda Clarka Pasco w 1976 r. Biorąc pod uwagę strumień symboli i ich prawdopodobieństwa, koder zakresu wytwarza oszczędny przestrzennie strumień bitów do reprezentowania tych symboli, a biorąc pod uwagę strumień i prawdopodobieństwa, dekoder zasięgu odwraca ten proces.

Kodowanie zakresowe jest bardzo podobne do kodowania arytmetycznego , z tą różnicą, że kodowanie odbywa się za pomocą cyfr w dowolnej bazie, zamiast za pomocą bitów, więc jest szybsze przy użyciu większych baz (np. bajtu ) przy niewielkim koszcie wydajności kompresji. Po wygaśnięciu pierwszego (1978) patentu na kodowanie arytmetyczne, kodowanie zakresowe wydawało się wyraźnie wolne od obciążeń patentowych. To szczególnie wzbudziło zainteresowanie tą techniką w open source . Od tego czasu wygasły także patenty na różne znane techniki kodowania arytmetycznego.

Jak działa kodowanie zakresu

Graficzne przedstawienie procesu kodowania. Zakodowana tutaj wiadomość to „AABA "

Kodowanie zakresowe koncepcyjnie koduje wszystkie symbole wiadomości w jedną liczbę, w przeciwieństwie do kodowania Huffmana , które przypisuje każdemu symbolowi wzór bitowy i łączy wszystkie wzorce bitowe razem. Zatem kodowanie zakresowe może osiągnąć większe współczynniki kompresji niż dolna granica jeden bit na symbol w kodowaniu Huffmana i nie jest narażone na nieefektywność, jaką ma Huffman w przypadku prawdopodobieństw, które nie są dokładną potęgą dwójki .

Główna koncepcja kodowania zakresów jest następująca: biorąc pod uwagę wystarczająco duży zakres liczb całkowitych i oszacowanie prawdopodobieństwa symboli, początkowy zakres można łatwo podzielić na podzakresy, których rozmiary są proporcjonalne do prawdopodobieństwa symbolu, który reprezentują. Każdy symbol wiadomości można następnie zakodować po kolei, redukując bieżący zakres do tylko tego podzakresu, który odpowiada następnemu symbolowi do zakodowania. Dekoder musi mieć takie samo oszacowanie prawdopodobieństwa jak zastosowany koder, które może zostać przesłane z wyprzedzeniem, wyprowadzone z już przesłanych danych lub stanowić część kompresora i dekompresora.

Kiedy wszystkie symbole zostaną zakodowane, wystarczy zidentyfikować podzakres, aby przekazać całą wiadomość (zakładając oczywiście, że dekoder zostanie w jakiś sposób powiadomiony o wyodrębnieniu całej wiadomości). Do zidentyfikowania podzakresu wystarczy pojedyncza liczba całkowita, a przesyłanie całej liczby całkowitej może nawet nie być konieczne; jeśli istnieje ciąg cyfr taki, że każda liczba całkowita rozpoczynająca się od tego przedrostka mieści się w podzakresie, wówczas sam przedrostek wystarczy do zidentyfikowania podzakresu i w ten sposób przesłania wiadomości.

Przykład

Załóżmy, że chcemy zakodować wiadomość „AABA<EOM>”, gdzie <EOM> jest symbolem końca wiadomości. W tym przykładzie zakłada się, że dekoder wie, że zamierzamy zakodować dokładnie pięć symboli w systemie liczbowym o podstawie 10 (pozwalając na 10 ⁵ różnych kombinacji symboli z zakresu [0, 100000)) przy użyciu rozkładu prawdopodobieństwa {A: . 60; B: 0,20; <EOM>: 0,20}. Enkoder dzieli zakres [0, 100000) na trzy podzakresy:

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

Ponieważ naszym pierwszym symbolem jest A, zmniejsza to nasz początkowy zakres do [0, 60000). Drugi wybór symbolu pozostawia nam trzy podzakresy tego zakresu. Pokazujemy je po już zakodowanym „A”:

AA: [ 0, 36000) AB: [ 36000, 48000) A : [ 48000, 60000)

Po zakodowaniu dwóch symboli nasz zakres wynosi teraz [0, 36000), a trzeci symbol prowadzi do następujących wyborów:

AAA: [ 0, 21600) AAB: [ 21600, 28800) AA : [28800, 36000)

Tym razem jest to druga z trzech opcji reprezentujących wiadomość, którą chcemy zakodować, a naszym zakresem jest [21600, 28800). W tym przypadku określenie naszych podzakresów może wydawać się trudniejsze, ale w rzeczywistości tak nie jest: możemy po prostu odjąć dolną granicę od górnej granicy, aby ustalić, że w naszym zakresie znajduje się 7200 liczb; że pierwszych 4320 z nich reprezentuje 0,60 całości, kolejnych 1440 reprezentuje kolejne 0,20, a pozostałych 1440 reprezentuje pozostałe 0,20 całości. Dodanie dolnej granicy daje nam nasze zakresy:

AABA: [21600, 25920) AABB: [25920, 27360) AAB : [27360, 28800)

Wreszcie, gdy nasz zakres został zawężony do [21600, 25920), mamy jeszcze tylko jeden symbol do zakodowania. Stosując tę samą technikę co poprzednio przy podziale zakresu pomiędzy dolną i górną granicę, stwierdzamy, że trzy podzakresy to:

AABAA: [21600, 24192) AABAB: [24192, 25056) AABA : [25056, 25920)

A ponieważ <EOM> jest naszym ostatnim symbolem, nasz ostateczny zakres to [25056, 25920). Ponieważ wszystkie pięciocyfrowe liczby całkowite zaczynające się od „251” mieszczą się w naszym ostatecznym zakresie, jest to jeden z trzycyfrowych przedrostków, które mogliśmy przesłać, i który jednoznacznie przekazywałby naszą oryginalną wiadomość. (Fakt, że w sumie jest osiem takich przedrostków, oznacza, że nadal mamy do czynienia z niedociągnięciami. Zostały one wprowadzone przez użycie podstawy 10 , a nie podstawy 2 ).

Głównym problemem może się wydawać wybór początkowego zakresu na tyle dużego, że niezależnie od tego, ile symboli musimy zakodować, zawsze będziemy mieli bieżący zakres wystarczająco duży, aby podzielić go na niezerowe podzakresy. W praktyce nie stanowi to jednak problemu, gdyż zamiast zaczynać od bardzo dużego zakresu i stopniowo go zawężać, koder w danym momencie pracuje z mniejszym zakresem liczb. Po zakodowaniu pewnej liczby cyfr cyfry znajdujące się najbardziej na lewo nie ulegną zmianie. W przykładzie po zakodowaniu zaledwie trzech symboli wiedzieliśmy już, że nasz końcowy wynik zacznie się od „2”. Więcej cyfr jest przesuniętych w prawo, gdy cyfry po lewej stronie są wysyłane. Ilustruje to następujący kod:

   0
   

 

	0  	
	0  	
	  	
	0  	
	 int  niski  =  ;  int  zakres  =  100000  ;  void  Uruchom  ()  {  Zakoduj  (  ,  6  ,  10  );  //  Kodowanie  (  ,  6  ,  10  );  //  Kodowanie  (  6  ,  2  ,  10  );  // B  Zakoduj  (  ,  6  ,  10  );  //  Kodowanie  (   	

	
	   
		

	  
	


 

	  
	       8  ,  2  ,  10  );  // <EOM>  // emituje ostatnie cyfry - patrz poniżej  while  (  zakres  <  10000  )  EmitDigit  ();  niski  +=  10000  ;  EmitCyfra  ();  }  void  EmitDigit  ()  {  Konsola  .  Zapis  (  niski  /  10000  );  niski  =  (  niski  %  10000  )  *  10 
	  


      

	
	  
	    
	  

	
	    ;  zakres  *=  10  ;  }  void  Encode  (  int  start  ,  int  size  ,  int  total  )  {  // dostosuj zakres w oparciu o  zakres interwału symboli   /=  total  ;  niski  +=  początek  *  zakres  ;  zakres  *=  rozmiar  ;  // sprawdź, czy cyfra znajdująca się najbardziej na lewo jest taka sama w całym zakresie  while  (  low  /  10000       
		

	
	   
	
		
		
		    
	
 ==  (  niski  +  zakres  )  /  10000  )  EmitDigit  ();  // ponownie dostosuj zakres — zobacz przyczynę poniżej  if  (  range  <  1000  )  {  EmitDigit  ();  EmitCyfra  ();  zakres  =  100000  -  niski  ;  }  }

Na koniec być może będziemy musieli wyemitować kilka dodatkowych cyfr. Górna cyfra wartości low jest prawdopodobnie za mała, więc musimy ją zwiększyć, ale musimy się upewnić, że nie zwiększymy jej powyżej wartości low+range . Najpierw musimy się upewnić, że zasięg jest wystarczająco duży.


   
	

  
 // wyemituj ostatnie cyfry  while  (  zakres  <  10000  )  EmitDigit  ();  niski  +=  10000  ;  EmitCyfra  ();

Jednym z problemów, który może wystąpić w przypadku powyższej funkcji Encode , jest to, że zakres może stać się bardzo mały, ale niskie i niskie+zakresy nadal mają różne pierwsze cyfry. Może to skutkować niewystarczającą precyzją przedziału, aby rozróżnić wszystkie symbole w alfabecie. Kiedy tak się stanie, musimy trochę pokręcić, wypisać kilka pierwszych cyfr, nawet jeśli możemy różnić się o jedną, i ponownie dostosować zakres, aby zapewnić nam jak najwięcej miejsca. Dekoder będzie wykonywał te same kroki, więc będzie wiedział, kiedy musi to zrobić, aby zachować synchronizację.


   

	
	
	    
 // dzieje się to tuż przed końcem powyższej funkcji Encode()  if  (  range  <  1000  )  {  EmitDigit  ();  EmitCyfra  ();  zakres  =  100000  -  niski  ;  }

W tym przykładzie użyto podstawy 10, ale w prawdziwej implementacji użytoby po prostu danych binarnych z pełnym zakresem natywnego typu danych całkowitych. Zamiast 10000 i 1000 prawdopodobnie użyłbyś stałych szesnastkowych, takich jak 0x1000000 i 0x10000 . Zamiast emitować cyfrę na raz, emitowałbyś bajt na raz i używał operacji przesunięcia bajtów zamiast mnożenia przez 10.

Dekodowanie wykorzystuje dokładnie ten sam algorytm z dodatkiem śledzenia aktualnej wartości kodu składającej się z cyfr odczytanych z kompresora. Zamiast emitować górną cyfrę niskiego poziomu , po prostu ją wyrzucasz, ale przesuwasz także górną cyfrę kodu i przesuwasz nową cyfrę odczytaną z kompresora. Użyj AppendDigit poniżej zamiast EmitDigit .

   0
   0
   

 

          
        
        
        
        


 

	     kod  int  =  ;  int  niski  =  ;  int  zakres  =  1  ;  void  ZainicjujDekoder  ()  {  AppendDigit  ();  // w tym przykładowym kodzie potrzebny jest tylko 1 z nich.  AppendDigit  ();  Dołącz cyfrę  ();  Dołącz cyfrę  ();  Dołącz cyfrę  ();  }  void  AppendDigit  ()  {  kod  =  (  kod  %  10000  )     
	      
	  


        

	
	  
	 *  10  +  Przeczytaj następną cyfrę  ();  niski  =  (  niski  %  10000  )  *  10  ;  zakres  *=  10  ;  }  void  Decode  (  int  start  ,  int  size  ,  int  total  )  // Dekodowanie jest takie samo jak Encode z EmitDigit zastąpionym przez AppendDigit  {  // dostosuj zakres w oparciu o  zakres interwału symboli   /=  total  ;  Niski     
	  

	
	         
		

	
	   
	
		
		
		 +=  początek  *  zakres  ;  zakres  *=  rozmiar  ;  // sprawdza, czy cyfra znajdująca się najbardziej na lewo jest taka sama w całym zakresie  while  (  low  /  10000  ==  (  low  +  range  )  /  10000  )  AppendDigit  ();  // ponownie dostosuj zakres — zobacz przyczynę poniżej  if  (  range  <  1000  )  {  AppendDigit  ();  Dołącz cyfrę  ();  zakres     
	
 =  100000  -  niski  ;  }  }

Aby określić, które przedziały prawdopodobieństwa zastosować, dekoder musi sprawdzić aktualną wartość kodu w przedziale [dolny, dolny+zakres) i zdecydować, który symbol reprezentuje.

 

	   0
	 
	   
	          
	                
	
		     
		  void  Uruchom  ()  {  int  start  =  ;  rozmiar  int  ;  całkowita  całkowita  =  10  ;  ZainicjujDekoder  ();  // trzeba uzyskać zakres/suma > 0  podczas  (  start  <  8  )  // zatrzymać po otrzymaniu EOM  {  int  v  =  GetValue  (  total  );  //kod należy do jakiego zakresu symboli?  przełącznik  (  v  )                 
		
			 0
			 
			 
			 
			 
			  0   
			 
			    // konwertuj wartość na symbol  {  case  :  case  1  :  case  2  :  case  3  :  case  4  :  case  5  :  start  =  ;  rozmiar  =  6  ;  Konsola  .  Napisz  (  „A”  );  przerwa  ;  przypadek  6  :  przypadek  7  :  początek  =  6  ;  rozmiar  =   
			   
		
		  
	


  

	 2  ;  Konsola  .  Napisz  (  „B”  );  przerwa  ;  domyślnie  :  początek  =  8  ;  rozmiar  =  2  ;  Konsola  .  WriteLine  (  ""  );  }  Dekoduj  (  początek  ,  rozmiar  ,  suma  );  }  }  int  GetValue  (  int  total  )  {  return        
 (  kod  -  niski  )  /  (  zakres  /  suma  );  }

Dla AABA powyższym przykładzie zwróci wartość z zakresu od 0 do 9. Wartości od 0 do 5 będą reprezentować A, 6 i 7 będą reprezentować B, a 8 i 9 będą reprezentować .

Związek z kodowaniem arytmetycznym

Kodowanie arytmetyczne jest takie samo jak kodowanie zakresu, ale z liczbami całkowitymi traktowanymi jako liczniki ułamków . Ułamki te mają ukryty wspólny mianownik, tak że wszystkie ułamki mieszczą się w przedziale [0,1). W związku z tym powstały kod arytmetyczny jest interpretowany jako rozpoczynający się od ukrytego „0”. Ponieważ są to po prostu różne interpretacje tych samych metod kodowania i ponieważ wynikowe kody arytmetyczne i kody zakresu są identyczne, każdy koder arytmetyczny jest odpowiadającym mu koderem zakresu i odwrotnie. Innymi słowy, kodowanie arytmetyczne i kodowanie zakresowe to tylko dwa, nieco różne sposoby rozumienia tej samej rzeczy.

Jednak w praktyce tak zwane kodery zakresu są zwykle implementowane mniej więcej tak, jak opisano w artykule Martina, podczas gdy kodery arytmetyczne, ogólniej, nie są nazywane koderami zakresu. Często zauważaną cechą takich koderów zakresu jest tendencja do przeprowadzania renormalizacji bajt po bajcie zamiast jednego bitu na raz (jak to zwykle ma miejsce). Innymi słowy, kodery zakresu mają tendencję do używania bajtów jako cyfr kodujących, a nie bitów. Chociaż zmniejsza to stopień kompresji, jaki można osiągnąć o bardzo małą wartość, jest to szybsze niż w przypadku wykonywania renormalizacji dla każdego bitu.

Zobacz też

^ ^a ^b G. Nigel N. Martin, Kodowanie zakresu: algorytm usuwania nadmiarowości z wiadomości cyfrowej , Konferencja dotycząca nagrywania wideo i danych, Southampton , Wielka Brytania, 24–27 lipca 1979.
^ „Algorytmy kodowania źródłowego do szybkiej kompresji danych” Richard Clark Pasco, Stanford, Kalifornia 1976
^ „ O narzutie koderów zasięgu ”, Timothy B. Terriberry, uwaga techniczna 2008
^ Patent USA 4122440 - (IBM) złożony 4 marca 1977, przyznany 24 października 1978 (obecnie wygasł)

Linki zewnętrzne

[compressconsult-1] G. Nigel N. Martin, Kodowanie zakresu: algorytm usuwania nadmiarowości z wiadomości cyfrowej , Konferencja dotycząca nagrywania wideo i danych, Southampton , Wielka Brytania, 24–27 lipca 1979.

[2] „Algorytmy kodowania źródłowego do szybkiej kompresji danych” Richard Clark Pasco, Stanford, Kalifornia 1976

[3] „ O narzutie koderów zasięgu ”, Timothy B. Terriberry, uwaga techniczna 2008

[4] Patent USA 4122440 - (IBM) złożony 4 marca 1977, przyznany 24 października 1978 (obecnie wygasł)