> shannon | fano | entropi <
// Shannon-Fano – Veri sıkıştırma için yukarıdan-aşağıya entropi kodlama
Entropi tabanlı
Bilgi teorisini kullanarak verimli, değişken uzunluklu kodlar üretir.
Yukarıdan-aşağıya yaklaşım
Sembolleri benzer olasılıklı gruplara özyinelemeli olarak böler.
Tarihsel algoritma
Modern sıkıştırma tekniklerini etkileyen öncü bir yöntemdir.
>> teknik bilgiler
Shannon-Fano nasıl çalışır?:
Shannon-Fano kodlama, sembolleri frekanslarına göre sıralar ve ardından toplam olasılıkları mümkün olduğunca yakın olacak şekilde bunları iki gruba böler. Her bölme koda bir bit ekler (sol için 0, sağ için 1). Sonuç, değişken uzunluklu önek kodlarından oluşan bir kümedir.
Kodlama süreci:
Metin: "AAABBCD" Frekanslar: A:3, B:2, C:1, D:1 Bölme: [A] | [B,C,D] Kodlar: A: 0 B: 10 C: 110 D: 111 Kodlanmış: 0 0 0 10 10 110 111
Neden Shannon-Fano kullanmalı?:
- >Uygulaması kolaydır
- >İyi sıkıştırma oranları sunar
- >Tarihsel açıdan önemlidir
- >Öğretim ve eğitim için idealdir
- >Önek kodları üretir
>> sık sorulan sorular
Shannon-Fano kodlama nedir?
Shannon-Fano kodlama, 1940’larda Claude Shannon ve Robert Fano tarafından geliştirilen bir entropi kodlama tekniğidir. Sembol olasılıklarına dayalı değişken uzunluklu kodlar kullanan ilk algoritmalardan biridir.
Shannon-Fano mu, Huffman mı?
Her ikisi de değişken uzunluklu kodlar üretir, ancak Huffman algoritması ortalama kod uzunluğunu en aza indiren en iyi çözümdür. Shannon-Fano daha basittir, ancak biraz daha uzun kodlar üretebilir. Huffman ağacı aşağıdan yukarıya, Shannon-Fano ise yukarıdan aşağıya kurar.
Semboller nasıl bölünür?
Semboller frekansa göre sıralanır ve toplam olasılıkları olabildiğince yakın olacak şekilde iki gruba ayrılır. Bu işlem, her grupta yalnızca bir sembol kalana kadar özyinelemeli olarak devam eder.
Shannon-Fano hâlâ kullanılıyor mu?
Shannon-Fano günümüzde çoğunlukla tarihsel ve eğitim amaçlı kullanılır. Pratikte, optimal kodlar garantilediği için büyük ölçüde Huffman kodlamasıyla değiştirilmiştir. Yine de sıkıştırma kavramlarını anlamak için çok faydalıdır.
// Çözümlü örnek
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// Kod örnekleri
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> Daha fazla soru
S: Shannon-Fano, Huffman’dan nasıl farklıdır?
C: Shannon-Fano sıralı listeyi yukarıdan aşağı, toplam sıklıkları mümkün olduğunca eşit iki yarıya böler; Huffman en seyrek simgeleri birleştirerek ağacı aşağıdan yukarı kurar. Huffman’ın en iyi olduğu kanıtlanmıştır, Shannon-Fano’nun her zaman değil.
S: Shannon-Fano her zaman en iyi midir?
C: Hayır. Örnekte Huffman’ın 87 bitine karşılık 89 bit gerekir. İkisi de önek içermeyen kod üretir, ancak Shannon-Fano’nun bölme kuralı elverişsiz kesimler seçebilir.
S: Shannon-Fano nerede kullanılır?
C: Çoğunlukla tarihsel ve öğretici bir yöntem olarak (Claude Shannon ve Robert Fano, 1948/49). ZIP’in IMPLODE algoritmasında bir türevi vardır; modern sıkıştırıcılar Huffman veya aritmetik kodlama kullanır.