Områdekodning - Range coding
Områdeskodning (eller områdekodning ) er en entropikodningsmetode defineret af G. Nigel N. Martin i et papir fra 1979, som effektivt genopdagede FIFO's aritmetiske kode, der først blev introduceret af Richard Clark Pasco i 1976. I betragtning af en strøm af symboler og deres sandsynligheder, en områdekoder producerer en rumeffektiv strøm af bits til at repræsentere disse symboler, og i betragtning af strømmen og sandsynlighederne vender en rækkedekoder processen.
Områdeskodning ligner meget aritmetisk kodning , bortset fra at kodning udføres med cifre i en hvilken som helst base i stedet for med bits, og det er derfor hurtigere, når man bruger større baser (f.eks. En byte ) til en lille pris i komprimeringseffektivitet. Efter udløbet af det første (1978) aritmetiske kodningspatent syntes områdekodning klart at være fri for patentbehæftelser. Dette drev især interessen for teknikken i open source -samfundet. Siden dengang er patenter på forskellige velkendte aritmetiske kodningsteknikker også udløbet.
Sådan fungerer områdekodning
Områdeskodning koder konceptuelt alle meddelelsens symboler til ét tal, i modsætning til Huffman-kodning, der tildeler hvert symbol et bitmønster og sammenkæder alle bitmønstrene sammen. Således kan områdekodning opnå større komprimeringsforhold end den nederste grænse på et bit pr. Symbol på Huffman-kodning, og den lider ikke over den ineffektivitet, Huffman gør, når han beskæftiger sig med sandsynligheder, der ikke er en nøjagtig effekt på to .
Det centrale koncept bag områdekodning er dette: givet et stort nok område af heltal og en sandsynlighedsestimering for symbolerne, kan det indledende område let opdeles i underområder, hvis størrelser er proportionelle med sandsynligheden for det symbol, de repræsenterer. Hvert symbol i meddelelsen kan derefter kodes efter tur ved at reducere det aktuelle område til netop det underområde, der svarer til det næste symbol, der skal kodes. Dekoderen skal have den samme sandsynlighedsestimering som den anvendte encoder, som enten kan sendes på forhånd, afledt af allerede overførte data eller være en del af kompressoren og dekompressoren.
Når alle symboler er blevet kodet, er det bare at identificere underområdet, der er nok til at kommunikere hele meddelelsen (forudsat naturligvis, at dekoderen på en eller anden måde underrettes, når den har hentet hele meddelelsen). Et enkelt heltal er faktisk tilstrækkeligt til at identificere underområdet, og det er måske ikke engang nødvendigt at transmittere hele heltalet; hvis der er en sekvens af cifre, så hvert helt tal, der begynder med dette præfiks, falder inden for underområdet, så er præfikset alene det eneste, der er nødvendigt for at identificere underområdet og dermed overføre meddelelsen.
Eksempel
Antag, at vi vil kode meddelelsen "AABA <EOM>", hvor <EOM> er symbolet for slutningen af beskeden. I dette eksempel antages det, at dekoderen ved, at vi har til hensigt at kode nøjagtig fem symboler i basissystemet 10 (med mulighed for 10 5 forskellige kombinationer af symboler med området [0, 100000)) ved hjælp af sandsynlighedsfordelingen {A:. 60; B: .20; <EOM>: .20}. Koderen opdeler området [0, 100000) i tre underområder:
A: [ 0, 60000) B: [ 60000, 80000) <EOM>: [ 80000, 100000)
Da vores første symbol er et A, reducerer det vores indledende område ned til [0, 60000). Det andet symbolvalg efterlader os med tre underområder i dette område. Vi viser dem efter det allerede kodede 'A':
AA: [ 0, 36000) AB: [ 36000, 48000) A<EOM>: [ 48000, 60000)
Med to symboler kodet, er vores område nu [0, 36000), og vores tredje symbol fører til følgende valg:
AAA: [ 0, 21600) AAB: [ 21600, 28800) AA<EOM>: [ 28800, 36000)
Denne gang er det det andet af vores tre valg, der repræsenterer det budskab, vi vil kode, og vores område bliver [21600, 28800). Det kan se sværere ud at bestemme vores underområder i dette tilfælde, men det er faktisk ikke: vi kan blot trække den nedre grænse fra den øvre grænse for at bestemme, at der er 7200 tal i vores område; at de første 4320 af dem repræsenterer 0,60 af det samlede antal, de næste 1440 repræsenterer de næste 0,20, og de resterende 1440 repræsenterer de resterende 0,20 af totalen. Tilføjelse af den nedre grænse giver os vores intervaller:
AABA: [21600, 25920) AABB: [25920, 27360) AAB<EOM>: [27360, 28800)
Endelig, med vores rækkevidde indsnævret til [21600, 25920), har vi bare endnu et symbol at kode. Ved at bruge den samme teknik som før til at opdele intervallet mellem den nedre og øvre grænse, finder vi de tre underområder:
AABAA: [21600, 24192) AABAB: [24192, 25056) AABA<EOM>: [25056, 25920)
Og da <EOM> er vores sidste symbol, er vores endelige område [25056, 25920). Fordi alle femcifrede heltal, der starter med "251", falder inden for vores endelige område, er det et af de trecifrede præfikser, vi kunne sende, der utvetydigt ville formidle vores originale budskab. (Det faktum, at der faktisk er otte sådanne præfikser i alt, betyder, at vi stadig har ineffektivitet. De er blevet introduceret ved vores brug af base 10 frem for base 2. )
Det centrale problem kan synes at være at vælge et indledende område, der er stort nok til, at uanset hvor mange symboler vi skal kode, vil vi altid have et aktuelt område, der er stort nok til at opdele i ikke-nul-underområder. I praksis er dette dog ikke et problem, for i stedet for at starte med et meget stort område og gradvist indsnævre det, arbejder encoderen med et mindre talområde til enhver tid. Efter at et antal cifre er blevet kodet, ændres cifrene til venstre ikke. I eksemplet efter at have kodet kun tre symboler, vidste vi allerede, at vores endelige resultat ville starte med "2". Flere cifre flyttes ind til højre, da cifre til venstre sendes. Dette er illustreret i følgende kode:
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;
}
}
For at afslutte skal vi muligvis udsende et par ekstra cifre. Det øverste ciffer på lower sandsynligvis for lille, så vi skal øge det, men vi skal sørge for, at vi ikke øger det forbi low+range. Så først skal vi sikre os, at den rangeer stor nok.
// emit final digits
while (range < 10000)
EmitDigit();
low += 10000;
EmitDigit();
Et problem, der kan opstå med Encodefunktionen ovenfor som rangekan blive meget små, men lowog low+rangestadig har forskellige første cifre. Dette kan resultere i, at intervallet har utilstrækkelig præcision til at skelne mellem alle symbolerne i alfabetet. Når dette sker, skal vi fudge lidt, indtaste de første par cifre, selvom vi måske er slukket et, og justere området igen for at give os så meget plads som muligt. Dekoderen følger de samme trin, så den ved, hvornår den skal gøre dette for at blive synkroniseret.
// this goes just before the end of Encode() above
if (range < 1000)
{
EmitDigit();
EmitDigit();
range = 100000 - low;
}
Base 10 blev brugt i dette eksempel, men en reel implementering ville bare bruge binær, med hele spektret af den native heltal datatype. I stedet for 10000og 1000du sandsynligvis ville bruge hexadecimale konstanter som 0x1000000og 0x10000. I stedet for at udsende et ciffer ad gangen ville du udsende en byte ad gangen og bruge en byte-shift-handling i stedet for at gange med 10.
Dekodning bruger nøjagtig den samme algoritme med tilføjelse af at holde styr på den aktuelle codeværdi bestående af cifrene, der er læst fra kompressoren. I stedet for at udsende det øverste ciffer i lowdig skal du bare smide det væk, men du skifter også det øverste ciffer ud af codeog skifter i et nyt ciffer læst fra kompressoren. Brug AppendDigitnedenfor i stedet for 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;
}
}
For at bestemme hvilke sandsynlighedsintervaller, der skal anvendes, skal dekoderen se på den aktuelle værdi codeinden for intervallet [lav, lav+rækkevidde) og afgøre, hvilket symbol dette repræsenterer.
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);
}
For AABA <EOM> -eksemplet ovenfor ville dette returnere en værdi i området 0 til 9. Værdierne 0 til 5 ville repræsentere A, 6 og 7 ville repræsentere B, og 8 og 9 ville repræsentere <EOM>.
Forholdet til aritmetisk kodning
Aritmetisk kodning er det samme som områdekodning, men med heltalene som tællere af brøker . Disse fraktioner har en implicit fællesnævner, således at alle fraktionerne falder i området [0,1). Følgelig fortolkes den resulterende aritmetiske kode som begyndende med et implicit "0". Da disse bare er forskellige fortolkninger af de samme kodningsmetoder, og da den resulterende aritmetik og områdekoder er identiske, er hver aritmetisk koder dens tilsvarende områdekoder og omvendt. Med andre ord er aritmetisk kodning og områdekodning kun to, lidt forskellige måder at forstå det samme på.
I praksis, selv om, såkaldte range encodere tendens til at blive gennemført stort set som beskrevet i Martins papir, mens aritmetiske kodere mere generelt en tendens til ikke at blive kaldt range encodere. Et ofte bemærket træk ved sådanne områdekodere er tendensen til at udføre renormalisering en byte ad gangen, snarere end en bit ad gangen (som normalt er tilfældet). Med andre ord har områdekodere en tendens til at bruge bytes som kodende cifre frem for bits. Selvom dette reducerer mængden af komprimering, der kan opnås med en meget lille mængde, er det hurtigere end ved renormalisering for hver bit.
Se også
- Aritmetisk kodning
- Asymmetriske numeriske systemer
- Datakomprimering
- Entropi -kodning
- Huffman -kodning
- Multiskala elektrofysiologisk format
- Shannon – Fano kodning
Referencer
- ^ a b G. Nigel N. Martin, Range encoding: En algoritme til fjernelse af redundans fra en digitaliseret meddelelse , Video & Data Recording Conference, Southampton , UK, 24. – 27. juli 1979.
- ^ "Kildekodningsalgoritmer til hurtig datakomprimering" Richard Clark Pasco, Stanford, CA 1976
- ^ " On the Overhead of Range Coders ", Timothy B. Terriberry, teknisk note 2008
- ^ US Patent 4,122,440 - (IBM) Anlagt 4. marts 1977, Bevilget 24. oktober 1978 (Nu udløbet)
