Kodowanie Huffmana – drzewo prawdopodobieństw

1
Polecenie 1

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:

Linia 1. Znak dwukropek a czestosc dwukropek 22 kod dwukropek 0. Linia 2. Znak dwukropek b czestosc dwukropek 12 kod dwukropek 10. Linia 3. Znak dwukropek c czestosc dwukropek 7 kod dwukropek 110. Linia 4. Znak dwukropek d czestosc dwukropek 2 kod dwukropek 111.
Rm8bgSRBOfjJg
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Polecenie 2

Porównaj swoje rozwiązanie z zaprezentowanym w filmie.

Uwaga!

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ńDDX2pnfbbBinarne drzewo poszukiwań.

R1B9SSvPUqfwZ
Lekcja poświęcona programowaniu algorytmu Huffmana w języku Python.