Film samouczek
Kodowanie Huffmana – drzewo prawdopodobieństw
Napisz program, który dla zadanego łańcucha znaków napis
wygeneruje drzewo Huffmana. Działanie programu przetestuj dla następującego łańcucha znaków „aaaabbccaaaaccbbaddaaaaaaabbbbcccaaaaaabbbb"
.
Specyfikacja problemu:
Dane:
napis
– łańcuch znaków, dla którego należy wygenerować drzewo Huffmana
Wynik:
Program wyświetla częstości znaków w łańcuchu znaków napis
, a także przypisany im kod.
Przykładowe wyjście:
Porównaj swoje rozwiązanie z zaprezentowanym w filmie.
Program zaprezentowany w filmie prezentuje algorytm generowania drzewa Huffmana zrealizowany za pomocą programowania obiektowego. W odróżnieniu od kodu zaprezentowanego w poprzedniej sekcji używane są dodatkowe struktury danych takie jak kolejka priorytetowa (zaimplementowana za pomocą listy) oraz wcześniej wspomniane drzewo. Więcej na temat zasady tworzenia i działania drzew dowiesz się z materiału Binarne drzewo poszukiwańBinarne drzewo poszukiwań.
![](https://static.zpe.gov.pl/portal/f/res-minimized/R1B9SSvPUqfwZ/1689529708/2GGN6JoJmKz5pq5bDymp6vve7rcXQMuG.jpg)
Film dostępny pod adresem /preview/resource/R1B9SSvPUqfwZ
Lekcja poświęcona programowaniu algorytmu Huffmana w języku Python.