> aritmetik kodlama | kesirli bitler | optimal <
// Aritmetik kodlama - entropi sınırına yaklaşan kesirli bit kodlama
Neredeyse optimal
Sıkıştırma verimliliği için teorik entropi sınırına çok yaklaşır.
Kesirli bitler
Sembolleri olasılıklarına göre kesirli bitlerle kodlar.
Akış işleme
Veriler geldikçe artımlı olarak kodlayıp çözebilir.
>> teknik bilgiler
Aritmetik kodlama nasıl çalışır?:
Aritmetik kodlama, tüm mesajı [0,1) aralığındaki tek bir sayı olarak temsil eder. Her sembol, olasılığına bağlı olarak bu aralığı daraltır. Son aralık, ikili bir kesir olarak kodlanır ve entropi sınırına çok yakın bir sıkıştırma sağlar.
Kodlama süreci:
Metin: "AAB" Olasılıklar: A=0.67, B=0.33 1. Başlangıç: [0, 1) 2. 'A': [0, 0.67) 3. 'A': [0, 0.45) 4. 'B': [0.30, 0.45) Çıktı: [0.30, 0.45) aralığındaki herhangi bir sayı İkili: 0.010011...
Neden aritmetik kodlama kullanmalısınız?:
- >Daha iyi sıkıştırma oranları
- >Entropi sınırına yaklaşan performans
- >Her türlü olasılık dağılımını destekler
- >JPEG2000 ve H.264 gibi standartlarda kullanılır
- >Patent süresi doldu (2024)
>> sık sorulan sorular
Aritmetik kodlama nedir?
Aritmetik kodlama, sembol dizisini tek bir kesirli sayıya dönüştüren bir entropi kodlama türüdür. Sadece tam bitler kullanan Huffman kodlamasından farklı olarak, aritmetik kodlama sembol başına kesirli bitler kullanabilir.
Neden Huffman'dan daha iyidir?
Aritmetik kodlama, sıkıştırmayı entropi sınırına keyfi derecede yaklaştırabilir; Huffman ise sembol başına tam bitlerle sınırlıdır. Olasılıkların çok dengesiz olduğu durumlarda aritmetik kodlama oldukça daha verimlidir.
Hassasiyet parametresi nedir?
Hassasiyet, dahili hesaplamalarda kullanılan bit sayısını kontrol eder. Daha yüksek hassasiyet daha uzun mesajların kodlanmasını sağlar ancak daha fazla bellek gerektirir. Kısa metinler için genellikle 16 bit yeterlidir.
Aritmetik kodlama nerelerde kullanılır?
Aritmetik kodlama, H.264/H.265 video, JPEG2000 görüntüler ve ZIP'in DEFLATE64 modu gibi modern sıkıştırma standartlarında kullanılır. Önceden çeşitli patentlerle korunuyordu ancak temel patentler artık sona ermiştir.
// Çözümlü örnek
| Step | Symbol | low | high |
|---|---|---|---|
| 0 | — | 0 | 1 |
| 1 | A | 0 | 0.5 |
| 2 | B | 0.25 | 0.375 |
| 3 | C | 0.34375 | 0.375 |
// Kod örnekleri
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
>> Daha fazla soru
S: Aritmetik kodlama neden çoğu zaman Huffman’dan iyidir?
C: Huffman her sembole tam sayıda bit (en az 1) verir. Aritmetik kodlama tüm mesajı [0, 1) içinde tek bir kesir olarak kodlar ve entropiye yaklaşır; Huffman’da yine 1 bit tutan %50’den olası semboller için bile.
S: ABC aralık örneği nasıl çalışır?
C: A=0,5, B=0,25, C=0,25 ile aralık her sembolde daralır: [0,1) → [0,0,5) → [0,25, 0,375) → [0,34375, 0,375). İçindeki herhangi bir sayı, örneğin ikilide 0,01011 (=0,34375), “ABC”yi 5 bitle, yani tam entropiyle kodlar.
S: Aritmetik kodlama nerelerde kullanılır?
C: H.264/HEVC’deki CABAC, JPEG 2000 ve JBIG2’deki MQ kodlayıcı ile range coding (AV1) ve ANS (zstd, JPEG XL) gibi türevlerde. Erken patentler yaygınlaşmayı yavaşlattı; bugün çoğunun süresi doldu.