Intervallkodning (bandkodning) är en entropikodningsmetod som föreslagits av G. N. N. Martin 1979 [1] . Detta är en sorts aritmetisk kodning [2] .
Intervallkodning kodar alla tecken i ett meddelande till ett enda nummer, till skillnad från till exempel Huffman-kod , som tilldelar varje tecken en bitsekvens och sammanfogar alla bitsekvenser.
Låt oss säga att du vill kryptera meddelandet "AABA<EOM>", där <EOM> är slutet av meddelandetecknet . För detta exempel antas det att avkodaren vet att vi avser att koda exakt fem tecken i decimalnotation (algoritmen i detta fall stöder 10 5 olika kombinationer av tecken i intervallet [0, 100000)) med hjälp av sannolikhetsfördelningen {A : 0,60; B: 0,20; <EOM>: 0,20}. Kodaren delar upp området [0, 100000) i tre delområden:
A: [ 0, 60000) B: [ 60 000, 80 000) <EOM>: [ 80000, 100000)Eftersom vårt första tecken är A, minskar detta vårt initiala intervall till [0, 60000). Det andra tecknet delar upp detta intervall i ytterligare tre delar:
AA: [ 0, 36000) AB: [ 36000, 48000) A<EOM>: [ 48000, 60000)Med två tecken kodade blir vårt intervall [0, 36000) och vårt tredje tecken ger följande alternativ:
AAA: [ 0, 21600) AAB: [ 21600, 28800) AA<EOM>: [ 28800, 36000)Den här gången faller valet på det andra av de tre alternativen, vilket är meddelandet vi vill koda, och vårt utbud blir [21600, 28800). Det kan tyckas att det har blivit svårare att bestämma våra delområden i det här fallet, men det är det faktiskt inte: vi kan helt enkelt subtrahera den nedre gränsen från den övre gränsen för att fastställa att 7200 nummer finns tillgängliga i vårt sortiment; de första 4320 av dessa representerar 0,60 av det totala, nästa 1440 representerar nästa 0,20 och de återstående 1440 representerar de återstående 0,20 av det totala intervallet. Genom att lägga till den nedre gränsen får vi våra intervall:
AABA: [21600, 25920) AABB: [25920, 27360) AAB<EOM>: [27360, 28800)Slutligen, vårt sortiment minskade till [21600, 25920), vi fick bara ett tecken att koda. Med samma teknik som tidigare för att dela intervallet mellan de nedre och övre gränserna, hittar vi de tre återstående underområdena:
AABAA: [21600, 24192) AABAB: [24192, 25056) AABA<EOM>: [25056, 25920)Och eftersom <EOM> är vår sista karaktär är vårt slutliga intervall [25056, 25920). Eftersom alla femsiffriga nummer som börjar med "251" hamnar på vår sista rad, kan vi skicka ett av de tresiffriga prefixen för att unikt uttrycka det ursprungliga meddelandet (det faktum att det faktiskt finns åtta sådana prefix tyder på att det är möjligt att optimera algoritmen. Men de uppstod på grund av användningen av decimaltalssystemet , inte binärt ).
Aritmetisk kodning liknar intervallkodning, använder bråktal i intervallet [0,1). Följaktligen, som ett resultat, tolkas den aritmetiska koden som att den börjar med en implicit "0.", eftersom dessa bara är olika tolkningar av samma kodningsmetoder, då är vilken aritmetisk kodare som helst motsvarande intervallkodare, och vice versa.
I praktiken tenderar dock så kallade avståndskodare att implementeras i stor utsträckning, vilket beskrivs i Martins artikel, [1] medan aritmetiska kodare inte alls kallas för avståndskodare. Ofta är skillnaden byte- och bitrenormalisering. Intervallkodare tenderar att använda bytes snarare än bitar. Även om detta minskar komprimeringsnivån är det snabbare än att göra omnormalisering per bit.
| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Förlust mindre |
| ||||||
| Audio |
| ||||||
| Bilder |
| ||||||
| Video |
| ||||||