Intervalové kódování (pásmové kódování) je metoda entropického kódování navržená G. N. N. Martinem v roce 1979 [1] . Jedná se o druh aritmetického kódování [2] .
Intervalové kódování zakóduje všechny znaky zprávy do jediného čísla, na rozdíl například od Huffmanova kódu , který každému znaku přiřadí sekvenci bitů a všechny bitové sekvence spojí dohromady.
Řekněme, že chcete zašifrovat zprávu "AABA<EOM>", kde <EOM> je znak konce zprávy . Pro tento příklad se předpokládá, že dekodér ví, že hodláme zakódovat přesně pět znaků v desítkovém zápisu (algoritmus v tomto případě podporuje 10 5 různých kombinací znaků v rozsahu [0, 100000)) pomocí rozdělení pravděpodobnosti {A : 0,60; B: 0,20; <EOM>: 0,20}. Kodér rozdělí rozsah [0, 100000) do tří podrozsahů:
A: [0, 60000) B: [ 60 000, 80 000) <EOM>: [ 80 000, 100 000)Protože naším prvním znakem je A, snižuje se tím náš počáteční rozsah na [0, 60000). Druhý znak rozděluje tento rozsah na další tři části:
AA: [0, 36000) AB: [ 36000, 48000) A<EOM>: [ 48000, 60000)Se dvěma zakódovanými znaky se náš rozsah stane [0, 36000) a náš třetí znak poskytuje následující možnosti:
AAA: [0, 21600) AAB: [ 21600, 28800) AA<EOM>: [28800, 36000)Tentokrát volba padne na druhou ze tří možností, což je zpráva, kterou chceme zakódovat, a náš rozsah bude [21600, 28800). Může se zdát, že je v tomto případě obtížnější určit naše podrozsahy, ale ve skutečnosti tomu tak není: můžeme jednoduše odečíst spodní hranici od horní hranice a určit, že v našem rozsahu je k dispozici 7200 čísel; prvních 4320 z nich představuje 0,60 z celkového počtu, dalších 1440 představuje dalších 0,20 a zbývajících 1440 představuje zbývajících 0,20 z celkového rozsahu. Přidáním spodní hranice získáme naše rozsahy:
AABA: [21600, 25920) AABB: [25920, 27360) AAB<EOM>: [27360, 28800)Nakonec se náš rozsah zúžil na [21600, 25920), zbyl nám pouze jeden znak ke kódování. Pomocí stejné techniky jako dříve k rozdělení rozsahu mezi dolní a horní mez najdeme tři zbývající podrozsahy:
AABAA: [21600, 24192) AABAB: [24192, 25056) AABA<EOM>: [25056, 25920)A protože <EOM> je náš poslední znak, náš konečný rozsah je [25056, 25920). Protože všechna pětimístná čísla začínající na „251“ spadají do našeho posledního řádku, mohli bychom předat jedno z třímístných prefixů, abychom jednoznačně vyjádřili původní zprávu (skutečnost, že takových prefixů je ve skutečnosti osm, naznačuje, že je možné optimalizovat algoritmus. Ale vznikly díky použití desítkové číselné soustavy , nikoli binární ).
Aritmetické kódování je podobné intervalovému kódování, používá zlomková čísla v rozsahu [0,1). V důsledku toho je aritmetický kód interpretován jako začínající implicitní "0.", protože se jedná pouze o různé interpretace stejných metod kódování, pak je jakýkoli aritmetický kodér odpovídajícím intervalovým kodérem a naopak.
V praxi však bývají ve velké míře implementovány tzv. kodéry rozsahu, jak je popsáno v Martinově článku [1] , zatímco aritmetické kodéry se vůbec nenazývají kodéry rozsahu. Často je rozdílem bajtová a bitová renormalizace. Intervalové kodéry mají tendenci používat spíše bajty než bity. Ačkoli to snižuje úroveň komprese, je to rychlejší než renormalizace na bitové bázi.
| Kompresní metody | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Bezztrátový |
| ||||||
| Zvuk |
| ||||||
| snímky |
| ||||||
| Video |
| ||||||