> 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.