Aritmetik Kodlama'nın Gizli Sorunları: Sıkıştırmanız Neden Verimli Değil?

Aritmetik kodlamayı kendine uyguladıysan, muhtemelen harika bir iş çıkardığını düşünmüşsündür. Bit dizilerini olasılık aralıklarına eşleyen zarif bir algoritma, değil mi? Ama işte asıl sorun şu: çoğu yerde bulabileceğin temel uygulamalar sessizce düşük performans gösteriyor.

Buradan CPU işlem hızından bahsetmiyorum (tabii ki o da önemli). Bahsettiğim sıkıştırma oranı—yani entropy kodlaması kullanmanın temeli. Binlerce dosyada birkaç yüzde fark, milyonlarca işlemde ciddi kayıplara dönüşebiliyor.

Kitaplardan Öğrenilen Yöntem Aslında Eksik

Çoğu kaynakta görüceğin şey böyle bir yapıya benziyor:

let mut left: u32 = 0;
let mut right: u32 = u32::MAX;

fn encode_bit(bit: bool, probability: f32) {
    let mid = left + ((right - left) as f32 * probability) as u32;
    if !bit {
        right = mid;
    } else {
        left = mid + 1;
    }
    
    // Değer kesinleşince baytları yolla
    while left >> 24 == right >> 24 {
        output_byte((left >> 24) as u8);
        left <<= 8;
        right = (right << 8) | 0xff;
    }
}

Mantıklı görünüyor. Mevcut değer aralığını temsil eden [left, right] aralığını koruyorsun. Her bit bu aralığı olasılığa göre daralttıyor. Baytların değeri kesinleşince onları çıkışa yazıp, kalan bitler için yer açıyorsun.

Sorun nerede? Bu yaklaşımda matematiksel olarak olmaması gereken bir asimetri var.

Bayt Sınırlarında Kaybolan Verimlilik

Burada işler garip hale geliyor. Sonsuz kesinlikli ideal bir aritmetik kodlama dünyasında, aynı uzunluktaki aralıklar tamamen özdeş davranır. Ama 32-bitlik tamsayılarla uygulanınca değil.

İki durumu düşün:

1. left = 0 ile başlayan aralık hiçbir zaman 2^24 bitle daha küçük olamaz
2. left = 2^31 - 1 gibi bir yerden başlayan aralık sadece 2 bite kadar daralabilir

Neden? Çünkü bayt çıkartma koşulu while left >> 24 == right >> 24 aralığın konumuna bağlı. Uzunluğuna değil.

Aralık bayt sınırında sallanırsa—mesela [2^31 - 1, 2^31]—tehlikeli ölçüde daralmış olur. Böyle sıkışık bir alanda olasılık değerleri kaba bir şekilde nicelenir. 0.95 olasılıkla kodlamak istediğin kesin bir bit, aralık çok kısa olduğu için zorla 50/50 bölüne giriyor.

Sonuç? Daha fazla bit yazıyorsun. Entropi teorisine göre gerekli olmayan ekstra veriler.

Çözmede Saklı Karmaşıklık

Ama sorun sadece kodlamada değil. Çözmede de ortaya çıkıyor:

fn decode_bit(probability: f32) -> bool {
    let mid = left + ((right - left) as f32 * probability) as u32;
    if x <= mid {
        right = mid;
        bit = false;
    } else {
        left = mid + 1;
        bit = true;
    }
    
    while left >> 24 == right >> 24 {
        left <<= 8;
        right = (right << 8) | 0xff;
        x = (x << 8) | (bytes.next().unwrap() as u32);
    }
    
    bit
}

Çözücü üç değişkeni takip ediyor: left, right ve x (kodlanmış değer). Oysa matematiksel olarak sadece iki bilgiye ihtiyacın var: aralığın uzunluğu (right - left) ve kodlanmış noktanın bu aralık içindeki konumu (x - left).

Çözücü üçünü de tutuyor çünkü kesinlik artırma döngüsü bu şekilde çalışıyor. left ve right'ı ayrı tutmasının tek sebebi üst baytlarının eşit olup olmadığını kontrol etmek. Bu da çözücüyü mutlak konuma bağlı hale getiriyor. Oysa aralığın büyüklüğü yeterli olurdu.

Bu bağımlılık demek:

• Daha fazla bellek işlemi
• Derleyici optimizasyonları engelleme
• Anlaması zor kod

Hepsi de aslında yalnızca aralığın boyutu hakkında bilgi vermeleri gereken bir koşul yüzünden.

Gerçek Çözüm

Aritmetik kodlamada kesinlik mantığını yeniden düşünmek gerekiyor. Bayt çıkartmayı üst baytların eşitliğine göre yapmak yerine (konuma bağlı), aralığın uzunluğuna göre yapmak (konumdan bağımsız).

Basit görünse de, kodlamadan çözmeve kadar tüm döngüyü yeniden ayarlamanız gerekiyor. Karşılığında? Sıkıştırıcın kayıp biti kalmıyor ve çözücü daha basit ve hızlı oluyor.

Neden Önemli?

Domain ve hosting dünyasında çalışan geliştiriciler gün içinde binlerce dosya işleyebilir. Veritabanı yedeklemeleri, API yanıtları, bulut depolamada verilerin sıkıştırılması—her yerde bu tür optimizasyonlar devreye giriyor.

Çoğu geliştirici aldığı hazır kütüphanelerin gerçek yeteneğini bilmez. %5-10 sıkıştırma oranı iyileştirmesi, milyonlarca işleme vurulduğunda büyük tasarruf demektir. Özellikle yüksek trafikli uygulamalarda kullanılan altyapıda.

Asıl ders şu: "ders kitabında yazanlar" her zaman tam değil. Derinlere in. Varsayımları sorgula. Garip davrananları araştır. İyi mühendisler sadece algoritma kullanmaz—sınırlarını anlayarak kullanır.

Performans kritik sistemler inşa ediyorsan, her küçük iyileştirmenin kümülatif etkisini düşün. Milyonlarca sorgu başına birkaç milisaniye fark, yılda saatlerce tasarruf olur. İşin detayları önemlidir.