> shannon | fano | entropia <
// Shannon-Fano – Kodowanie entropijne top-down do kompresji danych
Oparte na entropii
Wykorzystuje teorię informacji do tworzenia wydajnych kodów o zmiennej długości.
Podejście z góry w dół
Rekursywnie dzieli symbole na grupy o podobnym prawdopodobieństwie.
Historyczny algorytm
Pionierska metoda, która wpłynęła na wiele nowoczesnych technik kompresji.
>> informacje techniczne
Jak działa Shannon-Fano:
Kodowanie Shannon-Fano sortuje symbole według częstości, a następnie rekursywnie dzieli je na dwie grupy o jak najbardziej zbliżonym łącznym prawdopodobieństwie. Każdy podział dodaje bit do kodu (0 po lewej, 1 po prawej). Wynikiem jest prefiksowy kod o zmiennej długości.
Przykład kodowania:
Tekst: "AAABBCD" Częstości: A:3, B:2, C:1, D:1 Podział: [A] | [B,C,D] Kody: A: 0 B: 10 C: 110 D: 111 Zakodowany ciąg: 0 0 0 10 10 110 111
Dlaczego warto używać Shannon-Fano:
- >Łatwe do zaimplementowania
- >Dobre współczynniki kompresji
- >Znaczenie historyczne
- >Przydatne w nauczaniu
- >Kody prefiksowe
>> najczęstsze pytania
Czym jest kodowanie Shannon-Fano?
Kodowanie Shannon-Fano to technika kodowania entropijnego opracowana w latach 40. XX wieku przez Claude’a Shannona i Roberta Fano. Był to jeden z pierwszych algorytmów wykorzystujących kody o zmiennej długości oparte na prawdopodobieństwie symboli.
Shannon-Fano czy Huffman?
Oba algorytmy tworzą kody o zmiennej długości, ale Huffman jest optymalny i zapewnia najkrótszą średnią długość kodu. Shannon-Fano jest prostszy, ale może generować nieco dłuższe kody. Huffman buduje drzewo od dołu do góry, Shannon-Fano – od góry do dołu.
Jak działa podział symboli?
Symbole są sortowane według częstości, a następnie dzielone na dwie grupy o jak najbardziej zbliżonym łącznym prawdopodobieństwie. Proces powtarza się rekursywnie, aż każda grupa będzie zawierać tylko jeden symbol.
Czy Shannon-Fano jest nadal używany?
Obecnie Shannon-Fano ma głównie znaczenie historyczne i edukacyjne. W praktyce został w dużej mierze zastąpiony kodowaniem Huffmana, które gwarantuje optymalność. Nadal pozostaje jednak użyteczny do wyjaśniania podstaw kompresji.
// Przykład krok po kroku
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// Przykłady kodu
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
>> Więcej pytań
P: Czym Shannon-Fano różni się od Huffmana?
O: Shannon-Fano dzieli posortowaną listę z góry na dół na dwie części o jak najbardziej zbliżonych sumach częstości; Huffman buduje drzewo od dołu, łącząc najrzadsze symbole. Optymalność Huffmana jest udowodniona, Shannona-Fano nie zawsze.
P: Czy Shannon-Fano jest zawsze optymalny?
O: Nie. W przykładzie potrzebuje 89 bitów wobec 87 u Huffmana. Oba dają kody bez prefiksów, ale reguła podziału Shannona-Fano może wybrać niekorzystne cięcia.
P: Gdzie używa się Shannona-Fano?
O: Głównie jako metodę historyczną i dydaktyczną (Claude Shannon i Robert Fano, 1948/49). Wariant jest w algorytmie IMPLODE formatu ZIP; współczesne kompresory używają Huffmana lub kodowania arytmetycznego.