ALG04

ALG04



304 Rozdział 13. Kodowanie i kompresja danych

304 Rozdział 13. Kodowanie i kompresja danych


Rys. 13 - 4. Przykład drzewa kodowego (2).

Powstaje naturalne pytanie: które drzewo jest najlepsze? Oczywiście, kryterium jakości drzewa kodowego jest związane z naszym celem głównym: kompresją. Kod, który zapewni nam największy stopień kompresji, będzie uznany za najlepszy. Zwróćmy uwagę, żc długość słowa kodowego nie jest stała (w naszym przykładzie wynosiła 2 lub 3 znaki). Jeśli w jakiś magiczny sposób sprawimy, że znaki występujące w kodowanym tekście najczęściej będą miały najkrótsze słowa kodowe, a znaki występujące sporadycznie - odpowiednio - najdłuższe, to uzyskana reprezentacja bitowa będzie miała najmniejszą długość w porównaniu z innymi kodami binarnymi.

Na tym spostrzeżeniu bazuje kod Iluffmana, który służy do uzyskania optymalnego drzewa kodowego. Jak nietrudno się domyślić, potrzebuje on danych na temat częstotliwości występowania znaków w tekście. Mogą to być wyniki uzyskane od językoznawców, którzy policzyli prawdopodobieństwo występowania określonych znaków w danym języku, lub po prostu, nasze własne w-yliczenia bazujące na wstępnej analizie tekstu, który ma zostać zakodowany. Sposób postępowania zależy od tego. co zamierzamy kodować (i ewentualnie przesyłać): teksty języka mówionego, dla którego prawdopodobieństwa występowania liter są znane, czy też losowe w swojej treści pliki „binarne” (np. obrazy, programy komputerowe...).

Dla zainteresowanych podaję tabelkę zawierającą dane na temat języka polskiego (przytaczam za |CR90]).

Algorytm I luffmana korzysta w bezpośredni sposób z tabelek takich jak 13 - 2. Wyszukuje on i grupuje rzadziej występujące znaki, tak aby w konsekwencji przypisać im najdłuższe słowa binarne, natomiast znakom występującym częściej -odpowiednio najkrótsze. Może on operować prawdopodobieństwami lub częstotliwościami występowania znaków. Poniżej podam klasyczny algorytm konstrukcji kodu Hoffmana, który następnie przeanalizujemy na konkretnym przykładzie obliczeniowym.


Wyszukiwarka

Podobne podstrony:
41690 PA274974 ANALIZA STATYSTYCZNA DANYCH Rys. 7.13. Okno wyboru statystyk obliczanych dla zmiennyc
ALG 6 96 Rozdział 5. Struktury danych Rys. 5 - 3. FCOOh FCI4h FFEEh Przykład listy jedno-kierunk
ALG6 126 Rozdział 5. Struktury danych Rys. 5 - 12. Metoda„ tablic równoległych " (2) DANE L2
Image468 Rozdzielacze zwykle Najprostszym rozdzielaczem zwykłym jest licznik pierścieniowy (rys. 4.5
star266125 Skrzynka rozdzielcza 125 7. Pod obudowę łożyska 2 (rys. 5-30) założyć uszczelkę pokr
18 Rozdział 1 Cele zarządzania produkcją    Zakłócenia (Z) Rys. 7. Rola modeli
skanuj0065 (32) 66 Rozdział 5. ze stożkiem diamentowym przedstawia rys. 5.6, natomiast wgłębnik kulk
Architektura klient - serwer Użytkownicy aplikacji Klienci Serwer Baza danych Rys. 2.4.
Politechnika WrocławskaProblemy dostępności do danych Rys. Model problemów związanych z
45074 skanuj0061 (51) Rozdział 3.3 Przykłady zastosowania terminala przenośnego: Rys. 3-16. Różne za
76 Rozdział 7 Wielomian y = x5 + x2 - 3x - 3 Rys. 7.1. Wykres wielomianu z naniesionymi wartościami
6. ROZDZIELNICE SN I STACJE TRANSFORMATOROWE 82 Rys. 6.8. Rozdzielnica osłonięta jednoczłonowa 10 i
Elementy teletransmisji danych -* t Rys. 1.5. Zasada przetwarzania sygnału analogowego na cyfrowy. a
35 Bazy danych Rys. 2.2 Model wodospadowy Powyższe cechy tego modelu są bardzo korzystne dla małych

więcej podobnych podstron