Områdeskodning - Range coding
Områdeskodning (eller intervallkodning ) är en entropikodningsmetod definierad av G. Nigel N. Martin i ett papper från 1979, som effektivt återupptäckte FIFO: s aritmetiska kod som först introducerades av Richard Clark Pasco 1976. Med tanke på en ström av symboler och deras sannolikheter, en avståndskodare producerar en rymdeffektiv ström av bitar för att representera dessa symboler och med tanke på strömmen och sannolikheterna vänder en avståndsavkodare processen.
Områdeskodning är mycket lik aritmetisk kodning , förutom att kodning görs med siffror i valfri bas, istället för med bitar, och så är det snabbare när man använder större baser (t.ex. en byte ) till liten kostnad i komprimeringseffektivitet. Efter utgången av det första (1978) aritmetiska kodningspatentet tycktes områdeskodning helt klart vara fri från patenthämningar. Detta drev särskilt intresset för tekniken i open source -gemenskapen. Sedan dess har också patent på olika välkända aritmetiska kodningstekniker gått ut.
Hur intervallkodning fungerar
Områdeskodning kodar konceptuellt alla meddelandets symboler till ett nummer, till skillnad från Huffman-kodning som tilldelar varje symbol ett bitmönster och sammanfogar alla bitmönster tillsammans. Således kan intervallkodning uppnå större kompressionsförhållanden än en-bit-per-symbolens nedre gräns för Huffman-kodning och den lider inte av ineffektiviteten som Huffman gör när hanterar sannolikheter som inte är en exakt effekt av två .
Det centrala konceptet bakom intervallkodning är detta: med tanke på ett tillräckligt stort intervall av heltal och en sannolikhetsuppskattning för symbolerna kan det initiala intervallet lätt delas in i delområden vars storlekar är proportionella mot sannolikheten för den symbol de representerar. Varje symbol för meddelandet kan sedan kodas i tur och ordning genom att minska det aktuella intervallet till just det delområdet som motsvarar nästa symbol som ska kodas. Avkodaren måste ha samma sannolikhetsuppskattning som kodaren som används, som antingen kan skickas i förväg, härledas från redan överförda data eller vara en del av kompressorn och dekompressorn.
När alla symboler har kodats räcker det bara med att identifiera delområdet för att kommunicera hela meddelandet (förutsatt naturligtvis att avkodaren på något sätt meddelas när den har extraherat hela meddelandet). Ett enda heltal är faktiskt tillräckligt för att identifiera delområdet, och det kanske inte ens är nödvändigt att överföra hela heltalet; om det finns en sekvens av siffror så att varje heltal som börjar med det prefixet faller inom delområdet, så är prefixet ensamt allt som behövs för att identifiera delområdet och därmed överföra meddelandet.
Exempel
Antag att vi vill koda meddelandet "AABA <EOM>", där <EOM> är symbolen för slutet av meddelandet. För detta exempel antas det att avkodaren vet att vi avser att koda exakt fem symboler i bas -10 -nummersystemet (vilket möjliggör 10 5 olika kombinationer av symboler med intervallet [0, 100000)) med hjälp av sannolikhetsfördelningen {A:. 60; B: .20; <EOM>: .20}. Kodaren delar upp intervallet [0, 100000) i tre undergrupper:
A: [ 0, 60000) B: [ 60000, 80000) <EOM>: [ 80000, 100000)
Eftersom vår första symbol är ett A, minskar det vårt initiala område till [0, 60000). Det andra symbolvalet lämnar oss med tre delområden i detta intervall. Vi visar dem efter det redan kodade 'A':
AA: [ 0, 36000) AB: [ 36000, 48000) A<EOM>: [ 48000, 60000)
Med två symboler kodade är vårt sortiment nu [0, 36000) och vår tredje symbol leder till följande val:
AAA: [ 0, 21600) AAB: [ 21600, 28800) AA<EOM>: [ 28800, 36000)
Den här gången är det det andra av våra tre val som representerar det budskap vi vill koda, och vårt intervall blir [21600, 28800). Det kan se svårare ut att bestämma våra delområden i det här fallet, men det är det faktiskt inte: vi kan bara subtrahera den nedre gränsen från den övre gränsen för att bestämma att det finns 7200 nummer i vårt intervall; att de första 4320 av dem representerar 0,60 av totalen, nästa 1440 representerar nästa 0,20, och de återstående 1440 representerar de återstående 0,20 av totalen. Att lägga tillbaka den nedre gränsen ger oss våra intervall:
AABA: [21600, 25920) AABB: [25920, 27360) AAB<EOM>: [27360, 28800)
Slutligen, med vårt intervall minskat till [21600, 25920), har vi bara ytterligare en symbol att koda. Med samma teknik som tidigare för att dela upp intervallet mellan den nedre och övre gränsen finner vi att de tre delområdena är:
AABAA: [21600, 24192) AABAB: [24192, 25056) AABA<EOM>: [25056, 25920)
Och eftersom <EOM> är vår sista symbol är vårt slutintervall [25056, 25920). Eftersom alla femsiffriga heltal som börjar med "251" faller inom vårt slutintervall är det ett av de tresiffriga prefixen vi kan överföra som entydigt skulle förmedla vårt ursprungliga budskap. (Det faktum att det faktiskt finns åtta sådana prefix i alla innebär att vi fortfarande har ineffektivitet. De har införts genom vår användning av bas 10 snarare än bas 2. )
Det centrala problemet kan tyckas vara att välja ett initialt område som är tillräckligt stort för att oavsett hur många symboler vi måste koda, kommer vi alltid att ha ett nuvarande område som är tillräckligt stort för att dela upp oss i delområden som inte är noll. I praktiken är detta dock inget problem, för istället för att börja med ett mycket stort intervall och gradvis minska det, arbetar kodaren med ett mindre antal nummer vid varje given tidpunkt. Efter att ett antal siffror har kodats ändras inte siffrorna längst till vänster. I exemplet efter att ha kodat bara tre symboler visste vi redan att vårt slutresultat skulle börja med "2". Fler siffror flyttas in till höger när siffror till vänster skickas ut. Detta illustreras i följande kod:
int low = 0;
int range = 100000;
void Run()
{
Encode(0, 6, 10); // A
Encode(0, 6, 10); // A
Encode(6, 2, 10); // B
Encode(0, 6, 10); // A
Encode(8, 2, 10); // <EOM>
// emit final digits - see below
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;
}
}
För att avsluta kan vi behöva skriva ut några extra siffror. Den översta siffran på lowär förmodligen för liten så vi måste öka den, men vi måste se till att vi inte ökar den förbi low+range. Så först måste vi se till att den rangeär tillräckligt stor.
// emit final digits
while (range < 10000)
EmitDigit();
low += 10000;
EmitDigit();
Ett problem som kan uppstå med Encodefunktionen ovan är att rangekan bli mycket små men lowoch low+rangeändå ha olika första siffrorna. Detta kan resultera i att intervallet har otillräcklig precision för att skilja mellan alla symboler i alfabetet. När detta händer måste vi fudge lite, mata ut de första två siffrorna trots att vi kanske är avstängda med en och justera intervallet igen för att ge oss så mycket utrymme som möjligt. Avkodaren kommer att följa samma steg så att den vet när den behöver göra detta för att vara synkroniserad.
// this goes just before the end of Encode() above
if (range < 1000)
{
EmitDigit();
EmitDigit();
range = 100000 - low;
}
Bas 10 användes i detta exempel, men en verklig implementering skulle bara använda binär, med hela intervallet av den inbyggda heltalstypen. Istället för 10000och 1000du skulle sannolikt använda hexadecimala konstanter som 0x1000000och 0x10000. Istället för att avge en siffra åt gången skulle du avge en byte i taget och använda en byte-skift-operation istället för att multiplicera med 10.
Avkodning använder exakt samma algoritm med tillägget att hålla koll på det aktuella codevärdet som består av siffrorna som läses från kompressorn. Istället för att avge den översta siffran på lowdig bara kasta bort den, men du flyttar också ut den översta siffran på codeoch skiftar in en ny siffra läst från kompressorn. Använd AppendDigitnedan istället för EmitDigit.
int code = 0;
int low = 0;
int range = 1;
void InitializeDecoder()
{
AppendDigit(); // with this example code, only 1 of these is actually needed
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) // Decode is same as Encode with EmitDigit replaced by AppendDigit
{
// 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)
AppendDigit();
// readjust range - see reason for this below
if (range < 1000)
{
AppendDigit();
AppendDigit();
range = 100000 - low;
}
}
För att bestämma vilka sannolikhetsintervall som ska tillämpas måste avkodaren titta på det aktuella värdet codeinom intervallet [lågt, lågt+intervall) och bestämma vilken symbol detta representerar.
void Run()
{
int start = 0;
int size;
int total = 10;
InitializeDecoder(); // need to get range/total >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);
}
För AABA <EOM> -exemplet ovan skulle detta returnera ett värde i intervallet 0 till 9. Värden 0 till 5 skulle representera A, 6 och 7 skulle representera B och 8 och 9 skulle representera <EOM>.
Förhållande till aritmetisk kodning
Aritmetisk kodning är detsamma som intervallkodning, men med heltal som räknare av fraktioner . Dessa fraktioner har en implicit gemensam nämnare, så att alla fraktioner faller i intervallet [0,1). Följaktligen tolkas den resulterande aritmetiska koden som att börja med ett implicit "0". Eftersom dessa bara är olika tolkningar av samma kodningsmetoder, och eftersom den resulterande aritmetiken och intervallkoderna är identiska, är varje aritmetisk kodare dess motsvarande intervallkodare, och vice versa. Med andra ord är aritmetisk kodning och intervallkodning bara två, lite olika sätt att förstå samma sak.
I praktiken är dock så kallade områdes givare tenderar att genomföras ganska mycket som beskrivs i Martin papper, medan aritmetiska kodare tenderar mer allmänt inte kallas avståndsgivare. En ofta noterad egenskap hos sådana områdeskodare är tendensen att utföra renormalisering en byte i taget, snarare än en bit i taget (som vanligtvis är fallet). Med andra ord, intervallkodare tenderar att använda byte som kodande siffror, snarare än bitar. Även om detta minskar mängden komprimering som kan uppnås med en mycket liten mängd, är det snabbare än vid renormalisering för varje bit.
Se även
- Aritmetisk kodning
- Asymmetriska numeriska system
- Datakomprimering
- Entropikodning
- Huffman -kodning
- Multiskala elektrofysiologiska format
- Shannon – Fano kodning
Referenser
- ^ a b G. Nigel N. Martin, Range encoding: En algoritm för att ta bort redundans från ett digitaliserat meddelande , Video & Data Recording Conference, Southampton , UK, 24–27 juli 1979.
- ^ "Källkodningsalgoritmer för snabb datakomprimering" Richard Clark Pasco, Stanford, CA 1976
- ^ " On the Overhead of Range Coders ", Timothy B. Terriberry, teknisk not 2008
- ^ US Patent 4,122,440 - (IBM) Inlämnad 4 mars 1977, beviljad 24 oktober 1978 (nu utgången)
