> kodowanie arytmetyczne | bity ułamkowe | optymalne <
// Kodowanie arytmetyczne – kodowanie z użyciem bitów ułamkowych zbliżone do granicy entropii
Bliskie optimum
Osiąga współczynniki kompresji bardzo bliskie teoretycznej granicy entropii.
Bity ułamkowe
Koduje symbole przy użyciu bitów ułamkowych zależnych od prawdopodobieństwa.
Przetwarzanie strumieniowe
Może kodować i dekodować dane stopniowo, w miarę ich napływu.
>> informacje techniczne
Jak działa kodowanie arytmetyczne:
Kodowanie arytmetyczne reprezentuje całą wiadomość jako jedną liczbę z przedziału [0,1). Każdy symbol zawęża ten przedział w zależności od swojego prawdopodobieństwa. Końcowy przedział jest kodowany jako ułamkowa liczba binarna, co daje kompresję bardzo bliską granicy entropii.
Proces kodowania:
Tekst: "AAB" Prawdopodobieństwa: A=0.67, B=0.33 1. Start: [0, 1) 2. 'A': [0, 0.67) 3. 'A': [0, 0.45) 4. 'B': [0.30, 0.45) Wynik: dowolna liczba z przedziału [0.30, 0.45) Binarnie: 0.010011...
Dlaczego używać kodowania arytmetycznego:
- >Bardzo dobre współczynniki kompresji
- >Zbliża się do granicy entropii
- >Obsługuje dowolne rozkłady prawdopodobieństwa
- >Wykorzystywane w JPEG2000/H.264
- >Wygasłe patenty (2024)
>> najczęstsze pytania
Czym jest kodowanie arytmetyczne?
Kodowanie arytmetyczne to rodzaj kodowania entropijnego, który zamienia sekwencję symboli w jedną liczbę ułamkową. W przeciwieństwie do kodowania Huffmana, które używa całych bitów, kodowanie arytmetyczne może używać bitów ułamkowych na symbol.
Dlaczego jest lepsze od Huffmana?
Kodowanie arytmetyczne może osiągnąć kompresję dowolnie bliską granicy entropii, podczas gdy Huffman jest ograniczony do całych bitów na symbol. Przy silnie skośnych rozkładach prawdopodobieństwa kodowanie arytmetyczne może być znacznie skuteczniejsze.
Czym jest parametr precyzji?
Precyzja określa liczbę bitów używanych w obliczeniach wewnętrznych. Wyższa precyzja pozwala kodować dłuższe wiadomości, ale wymaga więcej pamięci. Dla krótkich tekstów zwykle wystarcza 16 bitów.
Gdzie stosuje się kodowanie arytmetyczne?
Kodowanie arytmetyczne jest używane w nowoczesnych standardach kompresji, takich jak wideo H.264/H.265, obrazy JPEG2000 oraz tryb DEFLATE64 w ZIP. Wcześniej było objęte patentami, lecz kluczowe patenty wygasły.
// Przykład krok po kroku
| Step | Symbol | low | high |
|---|---|---|---|
| 0 | — | 0 | 1 |
| 1 | A | 0 | 0.5 |
| 2 | B | 0.25 | 0.375 |
| 3 | C | 0.34375 | 0.375 |
// Przykłady kodu
Model P(A)=0.5 P(B)=0.25 P(C)=0.25 -> A:[0,0.5) B:[0.5,0.75) C:[0.75,1)
Update width = high - low
high = low + width * cum_high(symbol)
low = low + width * cum_low(symbol)
Output any value in [0.34375, 0.375) e.g. 0.34375 = 0.01011b (5 bits = 1 + 2 + 2)
Entropy -log2 P(A) - log2 P(B) - log2 P(C) = 1 + 2 + 2 = 5 bits
>> Więcej pytań
P: Dlaczego kodowanie arytmetyczne bywa lepsze od Huffmana?
O: Huffman przypisuje każdemu symbolowi całkowitą liczbę bitów (co najmniej 1). Kodowanie arytmetyczne koduje cały komunikat jako jeden ułamek z [0, 1) i zbliża się do entropii, także dla symboli o prawdopodobieństwie powyżej 50%, które w Huffmanie i tak kosztują 1 bit.
P: Jak działa przykład przedziałów ABC?
O: Przy A=0,5, B=0,25, C=0,25 przedział zawęża się z każdym symbolem: [0,1) → [0,0,5) → [0,25, 0,375) → [0,34375, 0,375). Każda liczba w nim, np. 0,34375 = 0,01011 binarnie, koduje „ABC” w 5 bitach, dokładnie tyle co entropia.
P: Gdzie stosuje się kodowanie arytmetyczne?
O: W CABAC (H.264/HEVC), koderze MQ w JPEG 2000 i JBIG2 oraz wariantach takich jak range coding (AV1) i ANS (zstd, JPEG XL). Wczesne patenty hamowały rozpowszechnienie; dziś w większości wygasły.