Przeczytaj

Zadanie 1. Fragment Pana Tadeusza

W pewnej elektronicznej bibliotece przechowywane są książki w formie nieskompresowanych plików tekstowych. Biblioteka ta ma jednak problem z magazynowaniem swoich zasobów – ich liczba przyrasta z czasem, a rozbudowa infrastruktury jest zbyt kosztowna. Zarząd e‑biblioteki zdecydował się więc kompresowaćkompresjakompresować te pliki przy użyciu własnoręcznie przygotowanego programu.

W pliku INWOKACJA.txt zapisano treść inwokacji z Pana Tadeusza Adama Mickiewicza. Plik ten zawiera 22 wiersze, które biblioteka udostępniła w ramach testów. W pliku nie ma polskich znaków diakrytycznych, występują jednak znaki interpunkcyjne.

RjKxrnrOKZFwq

Przycisk do pobrania TXT z inwokacją.

Plik TXT o rozmiarze 992.00 B w języku polskim

Napisz program w wybranym języku programowania, który z podanego pliku utworzy plik skompresowany za pomocą algorytmu Huffmana. Wiersze z pliku z danymi powinny zostać zakodowane w taki sposób, by w pliku wynikowym znalazły się w jednym wierszu, ale w kolejności zgodnej z plikiem z danymi.

Znaki spacji, tak pozostałe znaki ASCII, również powinny zostać zakodowane.

Wyniki zapisz w pliku wyniki_1.txt.

Do oceny oddajesz:

plik wyniki_1.txt zawierający odpowiedź (tekst zakodowany za pomocą algorytmu Huffmana),
plik(i) z komputerową realizacją zadania (kodem programu).

Przedstaw rozwiązanie zadania, pisząc program w jednym z trzech języków: C++, Java lub Python. Odpowiedź do zadania dla przykładowych danych znajdziesz w pliku wyniki_1.txt umieszczonym pod rozwiązaniem.

Rozwiązanie

Rozwiązanie zadania przedstawimy w formie pseudokodu.

Ważne!

Zakładamy, że przy kodowaniu za pomocą algorytmu Huffmana cyfra 1 w kodzie oznacza przejście do prawego potomka rozważanego obecnie węzła (o ile węzeł nie jest liściem). Zakładamy, że listę drzew sortujemy niemalejąco względem wartości częstości występowania w korzeniu drzewa. W przypadku tej samej częstości występowania znaków odpowiadające im drzewa (mające ten znak w korzeniu) sortujemy niemalejąco względem kodu ASCII znaku. Sortujemy również tak, żeby w przypadku wystąpienia drzewa ze znakiem w korzeniu i drzewa bez znaku w korzeniu, drzewo ze znakiem (mające zapisane tę samą częstość występowania) było rozpatrzone jako pierwsze (znalazło się wcześniej na liście). Jeżeli dwa drzewa zbiorcze (bez litery) mają tę samą częstość występowania, to zostawiamy je w kolejności, w jakiej trafiły na listę – elementy są dodawane na koniec listy (jak w kolejce).

Zastosujemy algorytm Huffmana zgodnie z poleceniem. Najpierw wczytamy do programu łańcuch znaków, a następnie utworzymy tablicę, w której będziemy sprawdzać liczbę konkretnych liter i znaków. Dzięki niej określimy w naszym kodzie najczęściej pojawiające się znaki. Następnie, korzystając z ustalonych już częstości, użyjemy algorytmu Huffmana. Potem, opierając się na utworzonym drzewie, stworzymy słownik (tablicę asocjacyjną), w którym każdej występującej literze przypiszemy słowo kodowe. Ostatnim krokiem będzie zakodowanie tekstu za pomocą stworzonej tablicy kodów.

Rozpoczynając pracę nad implementacją algorytmu Huffmana, zacznijmy od stworzenia struktury węzła, którą wykorzystamy przy tworzeniu drzewa Huffmana. Powinny się w niej znaleźć: częstość wystąpień przechowywanych w węźle znaków (lub znaków jego poddrzewa), znak oraz prawy i lewy potomek (pola, w które będą wstawiane inne struktury tego typu, tworzące w ten sposób strukturę drzewiastą).

typ DrzewoHuffmana:
	Znak znak
    Liczba liczbaWystapien
    DrzewoHuffmana lewyPotomek
    DrzewoHuffmana prawyPotomek

Kolejnym krokiem jest wczytanie danych z pliku INWOKACJA.txt i stworzenie zmiennych pomocniczych do przechowywania wyznaczonych dla poszczególnych znaków częstości występowania i kodów Huffmana przypisanych poszczególnym znakom.

typ DrzewoHuffmana:
	Znak znak
    Liczba liczbaWystapien
    DrzewoHuffmana lewyPotomek
    DrzewoHuffmana prawyPotomek
    
tekstDoZakodowania ← wczytaj z pliku dane do zakodowania
n ← liczba wczytanych znaków
tablicaCzestosciWystapienia  ← słownik, w którym będziemy przechowywać częstość występowania w tekscie poszczególnych znaków
tablicaKodow ← słownik, w którym przechowamy kody wyznaczone dla poszczególnych znaków tekstu

Następny etap to ustalenie liczby wystąpień poszczególnych znaków w tekście.

typ DrzewoHuffmana:
	Znak znak
    Liczba liczbaWystapien
    DrzewoHuffmana lewyPotomek
    DrzewoHuffmana prawyPotomek
    
tekstDoZakodowania ← wczytaj z pliku dane do zakodowania
n ← liczba wczytanych znaków
tablicaCzestosciWystapienia  ← słownik, w którym będziemy przechowywać częstość występowania w tekscie poszczególnych znaków
tablicaKodow ← słownik, w którym przechowamy kody wyznaczone dla poszczególnych znaków tekstu

dla i = 0, 1, 2 ... n - 1 wykonuj
	tablicaCzestosciWystapienia [tekstDoZakodowania[i]] ← tablicaCzestosciWystapienia [tekstDoZakodowania[i]] + 1

Następnie konieczne jest stworzenie listy jednowęzłowych drzew. Każdy z nowo stworzonych węzłów zawiera znak występujący w tekście i liczbę jego wystąpień. Będziemy z nich potem tworzyć coraz to większe drzewa, aż zostanie nam tylko jedno drzewo, na podstawie którego zakodujemy tekst.

typ DrzewoHuffmana:
	Znak znak
    Liczba liczbaWystapien
    DrzewoHuffmana lewyPotomek
    DrzewoHuffmana prawyPotomek
    
tekstDoZakodowania ← wczytaj z pliku dane do zakodowania
n ← liczba wczytanych znaków
tablicaCzestosciWystapienia  ← słownik, w którym będziemy przechowywać częstość występowania w tekscie poszczególnych znaków
tablicaKodow ← słownik, w którym przechowamy kody wyznaczone dla poszczególnych znaków tekstu

dla i = 0, 1, 2 ... n - 1 wykonuj
	tablicaCzestosciWystapienia [tekstDoZakodowania[i]] ← tablicaCzestosciWystapienia [tekstDoZakodowania[i]] + 1

listaDrzew ← lista drzew binarnych typu DrzewoHuffmana złożonych jedynie z korzenia zawierającego znak i liczbę jego wystąpień (zakładamy dostęp sowobodny do elementów)

dla i = 1, 2, ..., 255 wykonuj
	jeżeli tablicaCzestosciWystapienia [znak(i)] istnieje
    	noweDrzewo ← DrzewoHuffmana (o polach znak ← znak(i) i liczbaWystapien ← tablicaCzestosciWystapienia [znak(i)], pola potomków zostawiamy puste)
		dodaj noweDrzewo na koniec listy listaDrzew

Do dalszego przetwarzania potrzebna będzie funkcja sortująca drzewa, zgodnie z wytycznymi podanymi wcześniej, czyli niemalejąco względem częstości wystąpień. Drzewa o tej samej częstości ze znakami przed drzewami o tej samej częstości bez znaku, a drzewa o tej samej częstości bez znaków – w kolejności dodania na listę. Funkcja kod() zwraca kod ASCII znaku, funkcja znak() zmienia kod ASCII na znak.

Ważne!

Znak \17, widoczny w funkcji sortującej, został wprowadzony w celu ułatwienia przełożenia pseudokodu na istniejące języki programowania i uproszczenia zrozumienia działania algorytmu. Decyzja o jego wprowadzeniu została dokładnie opisana przy opisie kolejnego kroku algorytmu.

typ DrzewoHuffmana:
	Znak znak
    Liczba liczbaWystapien
    DrzewoHuffmana lewyPotomek
    DrzewoHuffmana prawyPotomek

funkcja sortuj(listaDrzew)
	dla i = 0, 1, 2, ..., listaDrzew.długość() - 1 wykonuj
    	dla j = 1, 2, 3, ..., listaDrzew.długość() - i wykonuj
			jeżeli listaDrzew[j - 1].liczbaWystapien > listaDrzew[j].liczbaWystapien
                x ← listaDrzew[j - 1]
                listaDrzew[j - 1] ← listaDrzew[j]
                listaDrzew[j] ← x
            w przeciwnym razie jeżeli listaDrzew[j - 1].liczbaWystapien = listaDrzew[j].liczbaWystapien
				jeżeli listaDrzew[j - 1].znak ≠ '\17' i listaDrzew[j].znak ≠ '\17'
                	jeżeli kod(listaDrzew[j - 1].znak) > kod(listaDrzew[j].znak)
                    	x ← listaDrzew[j - 1]
                		listaDrzew[j - 1] ← listaDrzew[j]
                		listaDrzew[j] ← x
                jeżeli listaDrzew[j - 1].znak = '\17' i listaDrzew[j].znak ≠ '\17'
                	x = listaDrzew[j - 1]
                    listaDrzew[j - 1] ← listaDrzew[j]
                    listaDrzew[j] ← x

tekstDoZakodowania ← wczytaj z pliku dane do zakodowania
n ← liczba wczytanych znaków
tablicaCzestosciWystapienia  ← słownik, w którym będziemy przechowywać częstość występowania w tekscie poszczególnych znaków
tablicaKodow ← słownik, w którym przechowamy kody wyznaczone dla poszczególnych znaków tekstu

dla i = 0, 1, 2 ... n - 1 wykonuj
	tablicaCzestosciWystapienia [tekstDoZakodowania[i]] ← tablicaCzestosciWystapienia [tekstDoZakodowania[i]] + 1

listaDrzew ← lista drzew binarnych typu DrzewoHuffmana złożonych jedynie z korzenia zawierającego znak i liczbę jego wystąpień (zakładamy dostęp sowobodny do elementów)

dla i = 1, 2, ..., 255 wykonuj
	jeżeli tablicaCzestosciWystapienia [znak(i)] istnieje
    	noweDrzewo ← DrzewoHuffmana (o polach znak ← znak(i) i liczbaWystapien ← tablicaCzestosciWystapienia [znak(i)], pola potomków zostawiamy puste)
		dodaj noweDrzewo na koniec listy listaDrzew

Po stworzeniu funkcji sortującej kolejnym krokiem będzie łączenie drzew złożonych z pojedynczych węzłów w coraz większe struktury, aż zostaniemy z jednym drzewem, na podstawie którego wyznaczymy kody poszczególnych znaków. Zrobimy to poprzez tworzenie drzew, do których dołączać będziemy istniejące drzewa (położone jako pierwsze na liście) do niewykorzystywanych na razie pól lewyPotomek i prawyPotomek (w językach programowania pola te będą zwykle wskaźnikami lub referencjami na pole typu DrzewoHuffmana).

Ważne!

W powstających w ten sposób coraz bardziej złożonych drzewach, część węzłów nie będzie przechowywać żadnego znaku znajdującego się w tekście (ich pola znak będą puste). Ze względu na fakt, że w takich językach programowania jak np. C++ i Java typ znakowy nie może być pusty, przyjmijmy, że w takich przypadkach do pola znak będziemy przypisywać wybrany przez nas znak, który nie znajdzie się w przetwarzanych przez algorytm tekstach. Znakiem takim może być wybrany znak sterujący (znaki o kodach ASCII 0‑31 i 127). Do prezentacji działania algorytmu wybrany został znak o kodzie ASCII 17 (w języku programowania takie użycie znaku sterującego wymaga podania jego kodu poprzedzonego ukośnikiem lewym [z j. ang. backslash], zapisanego w pojedynczym cudzysłowie – np. '\17').

Linia 1. typ DrzewoHuffmana dwukropek. Linia 2. Znak znak. Linia 3. Liczba liczbaWystapien. Linia 4. DrzewoHuffmana lewyPotomek. Linia 5. DrzewoHuffmana prawyPotomek. Linia 7. funkcja sortuj otwórz nawias okrągły listaDrzew zamknij nawias okrągły. Linia 8. dla i znak równości 0 przecinek 1 przecinek 2 przecinek kropka kropka kropka przecinek listaDrzew kropka długość otwórz nawias okrągły zamknij nawias okrągły minus 1 wykonuj. Linia 9. dla j znak równości 1 przecinek 2 przecinek 3 przecinek kropka kropka kropka przecinek listaDrzew kropka długość otwórz nawias okrągły zamknij nawias okrągły minus i wykonuj. Linia 10. jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka liczbaWystapien zamknij nawias ostrokątny listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka liczbaWystapien. Linia 11. x ← listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy. Linia 12. listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy ← listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 13. listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy ← x. Linia 14. w przeciwnym razie jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka liczbaWystapien znak równości listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka liczbaWystapien. Linia 15. jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka znak ≠ apostrof lewy ukośnik 17 apostrof i listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka znak ≠ apostrof lewy ukośnik 17 apostrof. Linia 16. jeżeli kod otwórz nawias okrągły listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka znak zamknij nawias okrągły zamknij nawias ostrokątny kod otwórz nawias okrągły listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka znak zamknij nawias okrągły. Linia 17. x ← listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy. Linia 18. listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy ← listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 19. listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy ← x. Linia 20. jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka znak znak równości apostrof lewy ukośnik 17 apostrof i listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka znak ≠ apostrof lewy ukośnik 17 apostrof. Linia 21. x znak równości listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy. Linia 22. listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy ← listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 23. listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy ← x. Linia 25. tekstDoZakodowania ← wczytaj z pliku dane do zakodowania. Linia 26. n ← liczba wczytanych znaków. Linia 27. tablicaCzestosciWystapienia ← słownik przecinek w którym będziemy przechowywać częstość występowania w tekscie poszczególnych znaków. Linia 28. tablicaKodow ← słownik przecinek w którym przechowamy kody wyznaczone dla poszczególnych znaków tekstu. Linia 30. dla i znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka n minus 1 wykonuj. Linia 31. tablicaCzestosciWystapienia otwórz nawias kwadratowy tekstDoZakodowania otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy ← tablicaCzestosciWystapienia otwórz nawias kwadratowy tekstDoZakodowania otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus 1. Linia 33. listaDrzew ← lista drzew binarnych typu DrzewoHuffmana złożonych jedynie z korzenia zawierającego znak i liczbę jego wystąpień otwórz nawias okrągły zakładamy dostęp sowobodny do elementów zamknij nawias okrągły. Linia 35. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek 255 wykonuj. Linia 36. jeżeli tablicaCzestosciWystapienia otwórz nawias kwadratowy znak otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias kwadratowy istnieje. Linia 37. noweDrzewo ← DrzewoHuffmana otwórz nawias okrągły o polach znak ← znak otwórz nawias okrągły i zamknij nawias okrągły i liczbaWystapien ← tablicaCzestosciWystapienia otwórz nawias kwadratowy znak otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias kwadratowy przecinek pola potomków zostawiamy puste zamknij nawias okrągły. Linia 38. dodaj noweDrzewo na koniec listy listaDrzew. Linia 40. dopóki listaDrzew kropka długość zamknij nawias ostrokątny 1 wykonaj. Linia 41. sortuj otwórz nawias okrągły liczbaDrzew zamknij nawias okrągły. Linia 42. drzewoSkladowe ← drzewo z najmniejszą liczbą wystąpień znaku. Linia 43. drugieDrzewoSkladowe ← drzewo z drugą najmniejszą liczbą wystąpień znaku. Linia 44. noweDrzewo ← DrzewoHuffmana otwórz nawias okrągły liczbaWystapien ← drzewoSkladowe kropka liczbaWystapien plus drugieDrzewoSkladowe kropka liczbaWystapien przecinek lewyPotomek ← drugieDrzewoSkladowe przecinek prawyPotomek ← drzewoSkladowe przecinek znak ← apostrof lewy ukośnik 17 apostrof zamknij nawias okrągły. Linia 45. usuń pobrane powyżej węzły drzewoSkladowe i drugieDrzewoSkladowe z listy. Linia 46. dodaj tak utworzone drzewo noweDrzewo na koniec listy listaDrzew.

typ DrzewoHuffmana:
	Znak znak
    Liczba liczbaWystapien
    DrzewoHuffmana lewyPotomek
    DrzewoHuffmana prawyPotomek

funkcja sortuj(listaDrzew)
	dla i = 0, 1, 2, ..., listaDrzew.długość() - 1 wykonuj
    	dla j = 1, 2, 3, ..., listaDrzew.długość() - i wykonuj
			jeżeli listaDrzew[j - 1].liczbaWystapien > listaDrzew[j].liczbaWystapien
                x ← listaDrzew[j - 1]
                listaDrzew[j - 1] ← listaDrzew[j]
                listaDrzew[j] ← x
            w przeciwnym razie jeżeli listaDrzew[j - 1].liczbaWystapien = listaDrzew[j].liczbaWystapien
				jeżeli listaDrzew[j - 1].znak ≠ '\17' i listaDrzew[j].znak ≠ '\17'
                	jeżeli kod(listaDrzew[j - 1].znak) > kod(listaDrzew[j].znak)
                    	x ← listaDrzew[j - 1]
                		listaDrzew[j - 1] ← listaDrzew[j]
                		listaDrzew[j] ← x
                jeżeli listaDrzew[j - 1].znak = '\17' i listaDrzew[j].znak ≠ '\17'
                	x = listaDrzew[j - 1]
                    listaDrzew[j - 1] ← listaDrzew[j]
                    listaDrzew[j] ← x

tekstDoZakodowania ← wczytaj z pliku dane do zakodowania
n ← liczba wczytanych znaków
tablicaCzestosciWystapienia  ← słownik, w którym będziemy przechowywać częstość występowania w tekscie poszczególnych znaków
tablicaKodow ← słownik, w którym przechowamy kody wyznaczone dla poszczególnych znaków tekstu

dla i = 0, 1, 2 ... n - 1 wykonuj
	tablicaCzestosciWystapienia [tekstDoZakodowania[i]] ← tablicaCzestosciWystapienia [tekstDoZakodowania[i]] + 1

listaDrzew ← lista drzew binarnych typu DrzewoHuffmana złożonych jedynie z korzenia zawierającego znak i liczbę jego wystąpień (zakładamy dostęp sowobodny do elementów)

dla i = 1, 2, ..., 255 wykonuj
	jeżeli tablicaCzestosciWystapienia [znak(i)] istnieje
    	noweDrzewo ← DrzewoHuffmana (o polach znak ← znak(i) i liczbaWystapien ← tablicaCzestosciWystapienia [znak(i)], pola potomków zostawiamy puste)
		dodaj noweDrzewo na koniec listy listaDrzew
        
dopóki listaDrzew.długość > 1 wykonaj
	sortuj(liczbaDrzew)
    drzewoSkladowe ← drzewo z najmniejszą liczbą wystąpień znaku
    drugieDrzewoSkladowe ← drzewo z drugą najmniejszą liczbą wystąpień znaku
    noweDrzewo ← DrzewoHuffmana (liczbaWystapien ← drzewoSkladowe.liczbaWystapien + drugieDrzewoSkladowe.liczbaWystapien, lewyPotomek ← drugieDrzewoSkladowe, prawyPotomek ← drzewoSkladowe, znak ← '\17')
    usuń pobrane powyżej węzły drzewoSkladowe i drugieDrzewoSkladowe z listy
    dodaj tak utworzone drzewo noweDrzewo na koniec listy listaDrzew

Po utworzeniu drzewa Huffmana możemy wyznaczyć na jego podstawie kody znaków. Potrzebna będzie funkcja, która rekurencyjnie która rekurencyjnie przejdzie drzewo i na tej podstawie wyznaczy kody znaków.

Linia 1. typ DrzewoHuffmana dwukropek. Linia 2. Znak znak. Linia 3. Liczba liczbaWystapien. Linia 4. DrzewoHuffmana lewyPotomek. Linia 5. DrzewoHuffmana prawyPotomek. Linia 7. funkcja sortuj otwórz nawias okrągły listaDrzew zamknij nawias okrągły. Linia 8. dla i znak równości 0 przecinek 1 przecinek 2 przecinek kropka kropka kropka przecinek listaDrzew kropka długość otwórz nawias okrągły zamknij nawias okrągły minus 1 wykonuj. Linia 9. dla j znak równości 1 przecinek 2 przecinek 3 przecinek kropka kropka kropka przecinek listaDrzew kropka długość otwórz nawias okrągły zamknij nawias okrągły minus i wykonuj. Linia 10. jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka liczbaWystapien zamknij nawias ostrokątny listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka liczbaWystapien. Linia 11. x ← listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy. Linia 12. listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy ← listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 13. listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy ← x. Linia 14. w przeciwnym razie jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka liczbaWystapien znak równości listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka liczbaWystapien. Linia 15. jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka znak ≠ apostrof lewy ukośnik 17 apostrof i listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka znak ≠ apostrof lewy ukośnik 17 apostrof. Linia 16. jeżeli kod otwórz nawias okrągły listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka znak zamknij nawias okrągły zamknij nawias ostrokątny kod otwórz nawias okrągły listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka znak zamknij nawias okrągły. Linia 17. x ← listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy. Linia 18. listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy ← listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 19. listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy ← x. Linia 20. jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka znak znak równości apostrof lewy ukośnik 17 apostrof i listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka znak ≠ apostrof lewy ukośnik 17 apostrof. Linia 21. x znak równości listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy. Linia 22. listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy ← listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 23. listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy ← x. Linia 25. funkcja przypiszKody otwórz nawias okrągły węzełDrzewa przecinek tablicaKodów przecinek kod zamknij nawias okrągły. Linia 26. jeżeli węzełDrzewa kropka lewyPotomek jest przypisany. Linia 27. przypiszKody otwórz nawias okrągły węzełDrzewa kropka lewyPotomek przecinek tablicaKodów przecinek kod plus apostrof 0 apostrof zamknij nawias okrągły. Linia 28. jeżeli węzełDrzewa kropka prawyPotomek jest przypisany. Linia 29. przypiszKody otwórz nawias okrągły węzełDrzewa kropka prawyPotomek przecinek tablicaKodów przecinek kod plus apostrof 1 apostrof zamknij nawias okrągły. Linia 30. jeżeli węzełDrzewa kropka prawyPotomek nie jest przypisany i węzełDrzewa kropka lewyPotomek nie jest przypisany. Linia 31. tablicaKodow otwórz nawias kwadratowy węzełDrzewa kropka znak zamknij nawias kwadratowy ← kod. Linia 32. zakończ. Linia 34. tekstDoZakodowania ← wczytaj z pliku dane do zakodowania. Linia 35. n ← liczba wczytanych znaków. Linia 36. tablicaCzestosciWystapienia ← słownik przecinek w którym będziemy przechowywać częstość występowania w tekscie poszczególnych znaków. Linia 37. tablicaKodow ← słownik przecinek w którym przechowamy kody wyznaczone dla poszczególnych znaków tekstu. Linia 39. dla i znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka n minus 1 wykonuj. Linia 40. tablicaCzestosciWystapienia otwórz nawias kwadratowy tekstDoZakodowania otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy ← tablicaCzestosciWystapienia otwórz nawias kwadratowy tekstDoZakodowania otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus 1. Linia 42. listaDrzew ← lista drzew binarnych typu DrzewoHuffmana złożonych jedynie z korzenia zawierającego znak i liczbę jego wystąpień otwórz nawias okrągły zakładamy dostęp sowobodny do elementów zamknij nawias okrągły. Linia 44. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek 255 wykonuj. Linia 45. jeżeli tablicaCzestosciWystapienia otwórz nawias kwadratowy znak otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias kwadratowy istnieje. Linia 46. noweDrzewo ← DrzewoHuffmana otwórz nawias okrągły o polach znak ← znak otwórz nawias okrągły i zamknij nawias okrągły i liczbaWystapien ← tablicaCzestosciWystapienia otwórz nawias kwadratowy znak otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias kwadratowy przecinek pola potomków zostawiamy puste zamknij nawias okrągły. Linia 47. dodaj noweDrzewo na koniec listy listaDrzew. Linia 49. dopóki listaDrzew kropka długość zamknij nawias ostrokątny 1 wykonaj. Linia 50. sortuj otwórz nawias okrągły liczbaDrzew zamknij nawias okrągły. Linia 51. drzewoSkladowe ← drzewo z najmniejszą liczbą wystąpień znaku. Linia 52. drugieDrzewoSkladowe ← drzewo z drugą najmniejszą liczbą wystąpień znaku. Linia 53. noweDrzewo ← DrzewoHuffmana otwórz nawias okrągły liczbaWystapien ← drzewoSkladowe kropka liczbaWystapien plus drugieDrzewoSkladowe kropka liczbaWystapien przecinek lewyPotomek ← drugieDrzewoSkladowe przecinek prawyPotomek ← drzewoSkladowe przecinek znak ← apostrof lewy ukośnik 17 apostrof zamknij nawias okrągły. Linia 54. usuń pobrane powyżej węzły drzewoSkladowe i drugieDrzewoSkladowe z listy. Linia 55. dodaj tak utworzone drzewo noweDrzewo na koniec listy listaDrzew.

typ DrzewoHuffmana:
	Znak znak
    Liczba liczbaWystapien
    DrzewoHuffmana lewyPotomek
    DrzewoHuffmana prawyPotomek

funkcja sortuj(listaDrzew)
	dla i = 0, 1, 2, ..., listaDrzew.długość() - 1 wykonuj
    	dla j = 1, 2, 3, ..., listaDrzew.długość() - i wykonuj
			jeżeli listaDrzew[j - 1].liczbaWystapien > listaDrzew[j].liczbaWystapien
                x ← listaDrzew[j - 1]
                listaDrzew[j - 1] ← listaDrzew[j]
                listaDrzew[j] ← x
            w przeciwnym razie jeżeli listaDrzew[j - 1].liczbaWystapien = listaDrzew[j].liczbaWystapien
				jeżeli listaDrzew[j - 1].znak ≠ '\17' i listaDrzew[j].znak ≠ '\17'
                	jeżeli kod(listaDrzew[j - 1].znak) > kod(listaDrzew[j].znak)
                    	x ← listaDrzew[j - 1]
                		listaDrzew[j - 1] ← listaDrzew[j]
                		listaDrzew[j] ← x
                jeżeli listaDrzew[j - 1].znak = '\17' i listaDrzew[j].znak ≠ '\17'
                	x = listaDrzew[j - 1]
                    listaDrzew[j - 1] ← listaDrzew[j]
                    listaDrzew[j] ← x

funkcja przypiszKody(węzełDrzewa, tablicaKodów, kod)
	jeżeli węzełDrzewa.lewyPotomek jest przypisany
    	przypiszKody(węzełDrzewa.lewyPotomek,tablicaKodów,kod+'0')
   	jeżeli węzełDrzewa.prawyPotomek jest przypisany
    	przypiszKody(węzełDrzewa.prawyPotomek,tablicaKodów,kod+'1')
    jeżeli węzełDrzewa.prawyPotomek nie jest przypisany i węzełDrzewa.lewyPotomek nie jest przypisany 
		tablicaKodow[węzełDrzewa.znak] ← kod 
    zakończ

tekstDoZakodowania ← wczytaj z pliku dane do zakodowania
n ← liczba wczytanych znaków
tablicaCzestosciWystapienia  ← słownik, w którym będziemy przechowywać częstość występowania w tekscie poszczególnych znaków
tablicaKodow ← słownik, w którym przechowamy kody wyznaczone dla poszczególnych znaków tekstu

dla i = 0, 1, 2 ... n - 1 wykonuj
	tablicaCzestosciWystapienia [tekstDoZakodowania[i]] ← tablicaCzestosciWystapienia [tekstDoZakodowania[i]] + 1

listaDrzew ← lista drzew binarnych typu DrzewoHuffmana złożonych jedynie z korzenia zawierającego znak i liczbę jego wystąpień (zakładamy dostęp sowobodny do elementów)

dla i = 1, 2, ..., 255 wykonuj
	jeżeli tablicaCzestosciWystapienia [znak(i)] istnieje
    	noweDrzewo ← DrzewoHuffmana (o polach znak ← znak(i) i liczbaWystapien ← tablicaCzestosciWystapienia [znak(i)], pola potomków zostawiamy puste)
		dodaj noweDrzewo na koniec listy listaDrzew
        
dopóki listaDrzew.długość > 1 wykonaj
	sortuj(liczbaDrzew)
    drzewoSkladowe ← drzewo z najmniejszą liczbą wystąpień znaku
    drugieDrzewoSkladowe ← drzewo z drugą najmniejszą liczbą wystąpień znaku
    noweDrzewo ← DrzewoHuffmana (liczbaWystapien ← drzewoSkladowe.liczbaWystapien + drugieDrzewoSkladowe.liczbaWystapien, lewyPotomek ← drugieDrzewoSkladowe, prawyPotomek ← drzewoSkladowe, znak ← '\17')
    usuń pobrane powyżej węzły drzewoSkladowe i drugieDrzewoSkladowe z listy
    dodaj tak utworzone drzewo noweDrzewo na koniec listy listaDrzew

Po stworzeniu tej funkcji wystarczy ją wywołać, a następnie wykorzystując wyznaczone kody, zapisać zakodowany tekst.

Linia 1. typ DrzewoHuffmana dwukropek. Linia 2. Znak znak. Linia 3. Liczba liczbaWystapien. Linia 4. DrzewoHuffmana lewyPotomek. Linia 5. DrzewoHuffmana prawyPotomek. Linia 7. funkcja sortuj otwórz nawias okrągły listaDrzew zamknij nawias okrągły. Linia 8. dla i znak równości 0 przecinek 1 przecinek 2 przecinek kropka kropka kropka przecinek listaDrzew kropka długość otwórz nawias okrągły zamknij nawias okrągły minus 1 wykonuj. Linia 9. dla j znak równości 1 przecinek 2 przecinek 3 przecinek kropka kropka kropka przecinek listaDrzew kropka długość otwórz nawias okrągły zamknij nawias okrągły minus i wykonuj. Linia 10. jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka liczbaWystapien zamknij nawias ostrokątny listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka liczbaWystapien. Linia 11. x ← listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy. Linia 12. listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy ← listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 13. listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy ← x. Linia 14. w przeciwnym razie jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka liczbaWystapien znak równości listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka liczbaWystapien. Linia 15. jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka znak ≠ apostrof lewy ukośnik 17 apostrof i listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka znak ≠ apostrof lewy ukośnik 17 apostrof. Linia 16. jeżeli kod otwórz nawias okrągły listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka znak zamknij nawias okrągły zamknij nawias ostrokątny kod otwórz nawias okrągły listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka znak zamknij nawias okrągły. Linia 17. x ← listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy. Linia 18. listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy ← listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 19. listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy ← x. Linia 20. jeżeli listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy kropka znak znak równości apostrof lewy ukośnik 17 apostrof i listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka znak ≠ apostrof lewy ukośnik 17 apostrof. Linia 21. x znak równości listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy. Linia 22. listaDrzew otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy ← listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 23. listaDrzew otwórz nawias kwadratowy j zamknij nawias kwadratowy ← x. Linia 25. funkcja przypiszKody otwórz nawias okrągły węzełDrzewa przecinek tablicaKodów przecinek kod zamknij nawias okrągły. Linia 26. jeżeli węzełDrzewa kropka lewyPotomek jest przypisany. Linia 27. przypiszKody otwórz nawias okrągły węzełDrzewa kropka lewyPotomek przecinek tablicaKodów przecinek kod plus apostrof 0 apostrof zamknij nawias okrągły. Linia 28. jeżeli węzełDrzewa kropka prawyPotomek jest przypisany. Linia 29. przypiszKody otwórz nawias okrągły węzełDrzewa kropka prawyPotomek przecinek tablicaKodów przecinek kod plus apostrof 1 apostrof zamknij nawias okrągły. Linia 30. jeżeli węzełDrzewa kropka prawyPotomek nie jest przypisany i węzełDrzewa kropka lewyPotomek nie jest przypisany. Linia 31. tablicaKodow otwórz nawias kwadratowy węzełDrzewa kropka znak zamknij nawias kwadratowy ← kod. Linia 32. zakończ. Linia 34. tekstDoZakodowania ← wczytaj z pliku dane do zakodowania. Linia 35. n ← liczba wczytanych znaków. Linia 36. tablicaCzestosciWystapienia ← słownik przecinek w którym będziemy przechowywać częstość występowania w tekscie poszczególnych znaków. Linia 37. tablicaKodow ← słownik przecinek w którym przechowamy kody wyznaczone dla poszczególnych znaków tekstu. Linia 39. dla i znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka n minus 1 wykonuj. Linia 40. tablicaCzestosciWystapienia otwórz nawias kwadratowy tekstDoZakodowania otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy ← tablicaCzestosciWystapienia otwórz nawias kwadratowy tekstDoZakodowania otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus 1. Linia 42. listaDrzew ← lista drzew binarnych typu DrzewoHuffmana złożonych jedynie z korzenia zawierającego znak i liczbę jego wystąpień otwórz nawias okrągły zakładamy dostęp sowobodny do elementów zamknij nawias okrągły. Linia 44. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek 255 wykonuj. Linia 45. jeżeli tablicaCzestosciWystapienia otwórz nawias kwadratowy znak otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias kwadratowy istnieje. Linia 46. noweDrzewo ← DrzewoHuffmana otwórz nawias okrągły o polach znak ← znak otwórz nawias okrągły i zamknij nawias okrągły i liczbaWystapien ← tablicaCzestosciWystapienia otwórz nawias kwadratowy znak otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias kwadratowy przecinek pola potomków zostawiamy puste zamknij nawias okrągły. Linia 47. dodaj noweDrzewo na koniec listy listaDrzew. Linia 49. dopóki listaDrzew kropka długość zamknij nawias ostrokątny 1 wykonaj. Linia 50. sortuj otwórz nawias okrągły liczbaDrzew zamknij nawias okrągły. Linia 51. drzewoSkladowe ← drzewo z najmniejszą liczbą wystąpień znaku. Linia 52. drugieDrzewoSkladowe ← drzewo z drugą najmniejszą liczbą wystąpień znaku. Linia 53. noweDrzewo ← DrzewoHuffmana otwórz nawias okrągły liczbaWystapien ← drzewoSkladowe kropka liczbaWystapien plus drugieDrzewoSkladowe kropka liczbaWystapien przecinek lewyPotomek ← drugieDrzewoSkladowe przecinek prawyPotomek ← drzewoSkladowe przecinek znak ← apostrof lewy ukośnik 17 apostrof zamknij nawias okrągły. Linia 54. usuń pobrane powyżej węzły drzewoSkladowe i drugieDrzewoSkladowe z listy. Linia 55. dodaj tak utworzone drzewo noweDrzewo na koniec listy listaDrzew. Linia 57. przypiszKody otwórz nawias okrągły listaDrzew otwórz nawias kwadratowy 0 zamknij nawias kwadratowy przecinek tablicaKodów przecinek cudzysłów cudzysłów zamknij nawias okrągły. Linia 59. wynik ← cudzysłów cudzysłów. Linia 61. dla i znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka n minus 1 wykonuj. Linia 62. wynik ← wynik plus tablicaKodow otwórz nawias kwadratowy tekstDoZakodowania otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy. Linia 64. zapisz wynik do pliku wyniki kropka txt.

typ DrzewoHuffmana:
	Znak znak
    Liczba liczbaWystapien
    DrzewoHuffmana lewyPotomek
    DrzewoHuffmana prawyPotomek

funkcja sortuj(listaDrzew)
	dla i = 0, 1, 2, ..., listaDrzew.długość() - 1 wykonuj
    	dla j = 1, 2, 3, ..., listaDrzew.długość() - i wykonuj
			jeżeli listaDrzew[j - 1].liczbaWystapien > listaDrzew[j].liczbaWystapien
                x ← listaDrzew[j - 1]
                listaDrzew[j - 1] ← listaDrzew[j]
                listaDrzew[j] ← x
            w przeciwnym razie jeżeli listaDrzew[j - 1].liczbaWystapien = listaDrzew[j].liczbaWystapien
				jeżeli listaDrzew[j - 1].znak ≠ '\17' i listaDrzew[j].znak ≠ '\17'
                	jeżeli kod(listaDrzew[j - 1].znak) > kod(listaDrzew[j].znak)
                    	x ← listaDrzew[j - 1]
                		listaDrzew[j - 1] ← listaDrzew[j]
                		listaDrzew[j] ← x
                jeżeli listaDrzew[j - 1].znak = '\17' i listaDrzew[j].znak ≠ '\17'
                	x = listaDrzew[j - 1]
                    listaDrzew[j - 1] ← listaDrzew[j]
                    listaDrzew[j] ← x

funkcja przypiszKody(węzełDrzewa, tablicaKodów, kod)
	jeżeli węzełDrzewa.lewyPotomek jest przypisany
    	przypiszKody(węzełDrzewa.lewyPotomek,tablicaKodów,kod+'0')
   	jeżeli węzełDrzewa.prawyPotomek jest przypisany
    	przypiszKody(węzełDrzewa.prawyPotomek,tablicaKodów,kod+'1')
    jeżeli węzełDrzewa.prawyPotomek nie jest przypisany i węzełDrzewa.lewyPotomek nie jest przypisany 
		tablicaKodow[węzełDrzewa.znak] ← kod 
    zakończ

tekstDoZakodowania ← wczytaj z pliku dane do zakodowania
n ← liczba wczytanych znaków
tablicaCzestosciWystapienia  ← słownik, w którym będziemy przechowywać częstość występowania w tekscie poszczególnych znaków
tablicaKodow ← słownik, w którym przechowamy kody wyznaczone dla poszczególnych znaków tekstu

dla i = 0, 1, 2 ... n - 1 wykonuj
	tablicaCzestosciWystapienia [tekstDoZakodowania[i]] ← tablicaCzestosciWystapienia [tekstDoZakodowania[i]] + 1

listaDrzew ← lista drzew binarnych typu DrzewoHuffmana złożonych jedynie z korzenia zawierającego znak i liczbę jego wystąpień (zakładamy dostęp sowobodny do elementów)

dla i = 1, 2, ..., 255 wykonuj
	jeżeli tablicaCzestosciWystapienia [znak(i)] istnieje
    	noweDrzewo ← DrzewoHuffmana (o polach znak ← znak(i) i liczbaWystapien ← tablicaCzestosciWystapienia [znak(i)], pola potomków zostawiamy puste)
		dodaj noweDrzewo na koniec listy listaDrzew
        
dopóki listaDrzew.długość > 1 wykonaj
	sortuj(liczbaDrzew)
    drzewoSkladowe ← drzewo z najmniejszą liczbą wystąpień znaku
    drugieDrzewoSkladowe ← drzewo z drugą najmniejszą liczbą wystąpień znaku
    noweDrzewo ← DrzewoHuffmana (liczbaWystapien ← drzewoSkladowe.liczbaWystapien + drugieDrzewoSkladowe.liczbaWystapien, lewyPotomek ← drugieDrzewoSkladowe, prawyPotomek ← drzewoSkladowe, znak ← '\17')
    usuń pobrane powyżej węzły drzewoSkladowe i drugieDrzewoSkladowe z listy
    dodaj tak utworzone drzewo noweDrzewo na koniec listy listaDrzew

przypiszKody(listaDrzew[0], tablicaKodów, "")

wynik ← ""

dla i = 0, 1, 2 ... n - 1 wykonuj
	wynik ← wynik + tablicaKodow[tekstDoZakodowania[i]]

zapisz wynik do pliku wyniki.txt

Odpowiedź

Docelowy rezultat, jaki powinniśmy uzyskać po wykonaniu tego zadania, przedstawiono w pliku wyniki_1.txt.

R1dYelkoIRVrm

Przycisk do pobrania TXT z odpowiedzią do zadania.

Plik TXT o rozmiarze 4.55 KB w języku polskim

Słownik

drzewo Huffmana

drzewo binarne stosowane w kodowaniu Huffmana; jego węzły składają się z dwóch węzłów potomnych, prawdopodobieństwa wystąpienia kodowanego znaku (w przypadku liściliśćliści drzewa) lub jednego ze znaków zawartych w potomkach węzła (w przypadku pozostałych węzłów), słowa kodowego znaku (nie występuje we wszystkich implementacjach, słowo kodowe znaku może być wyznaczane na podstawie przebytych gałęzi przy przeszukiwaniu drzewa pod kątem danego znaku)

kompresja

zmiana zapisu danych, której celem jest zmniejszenie ich objętości

korzeń

wierzchołekwierzchołekwierzchołek w drzewie, który nie ma żadnego rodzica

liść

węzeł (element) w drzewie, który nie ma żadnych następników (potomków); często liśćmiliśćliśćmi są węzły najbardziej oddalone od korzeniakorzeńkorzenia

wierzchołek

w teorii grafów, gdzie drzewo jest pewnym rodzajem grafu, definiowany jest jako punkt będący elementem zbioru innych punktów

Wprowadzenie

Prezentacja multimedialna

Zadanie 1. Fragment Pana Tadeusza

Rozwiązanie

Odpowiedź

Słownik