Infografika

Polecenie 1

Zapoznaj się z infografiką przedstawiającą przebieg działania algorytmu Huffmana dla przykładowego ciągu znaków. Zdekoduj podaną wiadomość.

Nad infografiką znajdują się przyciski odnoszące się do kolejnych kroków.

Algorytm Huffmana dla przykładowego ciągu znaków

R1BMJrrVjf2DW1
Mapa interaktywna: Opisy kroków. Infografika przedstawia przebieg działania algorytmu Huffmana dla przykładowego ciągu znaków. Przedstawiono siedem kroków. Krok 1: Zliczamy wystąpienia każdego znaku dla ciągu AAABBCABCDC. Ilustracja ukazuje krok pierwszy. W okręgach znajdują się wartości: A-4, B-3, C-3, D-1. Krok 2: Tworzymy cztery wierzchołki – każdy zawierający znak i częstość. Ilustracja przedstawia Krok drugi. Jest rząd czterech okręgów. W pierwszym okręgu napis: Znak A częstość 4, w drugim Znak B częstość 3, w trzecim Znak C częstość 3, w czwartym Znak D częstość 1. Krok 3: Zgodnie z algorytmem Huffmana wybieramy dwa wierzchołki o najmniejszych częstościach. W omawianym przypadku będzie to wierzchołek ze znakiem D, a także ze znakiem B lub C. Na ilustracji jest Krok trzeci. W jednym rzędzie są trzy okręgi. W pierwszym jest napis: Znak B częstość 3, w drugim Znak C częstość 3, w trzecim Znak D częstość 1. Krok 4: Nie bez przyczyny umieściliśmy wierzchołki w kolejności od największej częstości do najmniejszej. Wystarczy wybrać dwa wierzchołki znajdujące się na końcu, a potem umieścić je w takim miejscu listy, by częstości wciąż były malejące. Idąc tym tokiem rozumowania, wybieramy wierzchołki z C i D. Na ilustracji jest przedstawiony Krok czwarty. W okręgach znajdują się wartości: znak A częstość 4, znak brak częstość 4, znak B częstość 3, znak C częstość 3, znak D częstość 1. Od okręgu z znakiem brak częstość cztery prowadzą linie proste w dół do okręgów z napisami: znak C częstość 3 oraz znak D częstość 1. Krok 5: Wierzchołki ze znakiem C i D połączyliśmy w nowy wierzchołek, którego częstość stanowi sumę częstości jego potomków. W nowym wierzchołku znak oznaczyliśmy jako „brak” (zauważmy, że wierzchołki ze znakami nie mogą mieć żadnego potomka, zatem każdy wierzchołek posiadający choć jednego potomka nie będzie miał swojego znaku). Kontynuując algorytm, wybieramy kolejne dwa wierzchołki z najmniejszymi częstościami znajdującymi się w liście. Warto zwrócić uwagę, że wierzchołek o większej częstości umieszczamy z lewej strony (można to zrobić również z prawej, jednak należy postępować w sposób konsekwentny, tzn. umieszczać wierzchołki z większą częstością po konkretnej stronie). Ilustracja przedstawia Krok piąty. W górnej części ilustracji są dwa okręgi. W pierwszym jest napis: Znak brak częstość 7 oraz Znak A częstość 4. Od okręgu Znak brak częstość 7 dwie kreski w dół do dwóch okręgów. W jednym z nich jest napis: Znak brak częstość 4, w drugim Znak B częstość 3. Od okręgu Znak brak częstość 4 dwie kreski w dół do dwóch okręgów. W pierwszym napis: Znak C częstość 3, w drugim Znak D częstość 1. Krok 6: Wybieramy dwa ostatnie wierzchołki, kończąc tym samym algorytm. Ilustracja przedstawia Krok szósty. W górnej części ilustracji jest jeden okrąg. W nim napis: Znak brak częstość 11. Od okręgu w dół dwie kreski do dwóch okręgów. W jednym z nich napis: Znak brak częstość 7, w drugim Znak A częstość 4. Od okręgu Znak brak częstość 7 dwie kreski w dół do dwóch okręgów. W pierwszym napis: Znak brak częstość 4, w drugim: Znak B częstość 3. Od okręgu z napisem: Znak brak częstość 4 dwie kreski w dół do dwóch okręgów. W jednym z nich napis: Znak C częstość 3, w drugim Znak C częstość 1. Krok 7: Na podstawie tego drzewa tworzymy słownik kodowy. Każdą odnogę w lewo oznaczymy jako 0, a każdą odnogę w prawo jako 1. Tym samym otrzymamy graf. Książka kodowa: A: 1, B: 01, C: 000, D: 001. Spróbuj zdekodować następującą wiadomość: 01000001011, odczytując kolejne znaki prosto z grafu. Zacznij od korzenia grafu z częstością 11. Następnie, jeśli napotkasz 0, przejdź do wierzchołka z lewej, a jeśli 1 – do wierzchołka z prawej. Jeżeli wierzchołek jest korzeniem, odczytaj z niego literę i wróć do korzenia. Jeżeli nim nie jest, odczytaj kolejną liczbę i kontynuuj zgodnie ze sposobem opisanym w poprzednich krokach. Ilustracja przedstawia Krok siódmy. W górnej części ilustracji jest jeden okrąg. W nim napis: Znak brak częstość 11. Od okręgu w dół dwie kreski do dwóch okręgów. W jednym napis: Znak brak częstość 7, nad okręgiem cyfra 0; w drugim okręgu napis: Znak A częstość 4, nad okręgiem cyfra 1. Od okręgu z napisem: Znak brak częstość 7 dwie kreski w dół do dwóch okręgów. W jednym napis: Znak brak częstość 4, nad okręgiem cyfra 0, w drugim okręgu napis: Znak B częstość 3, nad okręgiem cyfra 1. Od okręgu z napisem: Znak brak częstość 4 dwie kreski w dół do dwóch okręgów. W jednym napis: Znak C częstość 3, nad okręgiem cyfra 0, w drugim Znak D częstość 1 - nad okręgiem cyfra 1.
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
1
Ćwiczenie 1

Zaimplementuj w języku C++ algorytm Huffmana służący do kodowania ciągu znaków. Podczas łączenia wierzchołków upewnij się, że prawy potomek będzie wierzchołkiem z mniejszą częstością niż lewy. Jeśli wierzchołki mają tę samą częstość, za mniejszy uznajemy ten o znaku z niższą wartością w kodowaniu ASCII. Nie musisz uwzględniać sytuacji, w której porównywane wierzchołki mają takie same częstości, a nie mają znaku (nie są liśćmi) – dane testowe ją wykluczają. Podczas poruszania się po drzewie kodowym zakładamy, że przejściu na lewo odpowiada cyfra 1, a przejściu na prawo cyfra 0. Do napisania programu możesz wykorzystać zmodyfikowany algorytm przedstawiony w sekcji „Przeczytaj”. Działanie programu przetestuj dla podanej wiadomości:

Linia 1. wiadomosc znak równości cudzysłów AAAADBABCABCDAC cudzysłów.

Specyfikacja problemu:

Dane:

  • wiadomosc – łańcuch znaków do zakodowania

Wynik:

  • zakodowanaWiadomosc – łańcuch znaków (zer i jedynek) reprezentujący zakodowany do postaci binarnej zgodnie z kodowaniem Huffmana łańcuch znaków wiadomosc

R1MuRzteyrJBA1
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Przeczytaj
Sprawdź się