Przeczytaj

Już wiesz

W roku 1952 David Huffman opracował prefiksową metodę kompresji bezstratnejbezstratna kompresja danychkompresji bezstratnej.

Mówimy, że kodowanie jest prefiksowe, gdy żadne słowo kodowe nie jest początkiem innego słowa.

Słowem kodowym w kontekście kodowania Huffmana określamy ciągi bitów, które jednoznacznie interpretują jakiś znak. Uwaga – dla uproszczenia w implementacji będziemy kodować każdy znak osobno, bez wcześniejszego grupowania.

Problem 1

Załóżmy, że w alfabecie, którym się posługujemy, są trzy znaki zgrupowane w następującej książce kodowejksiążka kodowaksiążce kodowej:

A: 1
B: 01
C: 00

Mamy zakodować wiadomość: „ABBAAAC”.

Spróbuj samodzielnie zakodować wiadomość.

Problem 2

Załóżmy, że wiadomość „ABBAAAC” zakodujemy następującym kodem:

A: 1
B: 0
C: 00

Wiadomość ta przyjęłaby następującą postać: 10011100 – miałaby tym samym jedynie 8 bitów, czyli zaoszczędzilibyśmy więcej pamięci.
Problem jednak polega na tym, że o ile zakodowana wiadomość jest krótsza, to nie da się jej jednoznacznie odkodować.

Spróbuj zdekodować wiadomość na jak najwięcej różnych sposobów, aby przekonać się, że kodowanie z tego przykładu nie jest jednoznaczne.

Ważne!

Książka kodowa przedstawiona w Problemie 2 jest błędna, ponieważ słowo kodowe odpowiadające literze B jest prefiksem słowa kodowego odpowiadającego literze C i z tego powodu nie można jednoznacznie odkodować wiadomości po tym, gdy zostanie ona zakodowana.

Implementacja w języku Java

Problem 3

Zaimplementujmy w języku Java program kodujący podany ciąg znaków za pomocą algorytmu Huffmana. Następnie przetestujemy go dla ciągu znaków "AABBCCDDDDDDDFFFEEER"

Specyfikacja problemu:

Dane:

wiadomosc – łańcuch znaków do zakodowania

Wynik:

zakodowanaWiadomosc – łańcuch znaków; wiadomość zakodowana algorytmem Huffmana

Zaczynamy od zdefiniowania klasy wierzcholek zawierającej konstruktor, który później pomoże szybciej tworzyć nowe wierzchołki. Klasa będzie posiadała pola znak, czestosc, lewy, prawy przechowujące kolejno znak, jego częstość, lewe, a następnie prawe dziecko wierzchołka.

class Wierzcholek {
	char znak;
	int czestosc;
	Wierzcholek lewy = null;
	Wierzcholek prawy = null;
	Wierzcholek(char znak, int czestosc, Wierzcholek lewy, Wierzcholek prawy) {
		this.znak = znak;
		this.czestosc = czestosc;
		this.lewy = lewy;
		this.prawy = prawy;
	}
}

Ponieważ w języku Java każdy symbol zapisywany jest w typie char, który ma długość 2 bajtów (wartości możliwe do zapisania mieszczą się w zakresie od 0000Indeks dolny 16 do FFFFIndeks dolny 16), maksymalna liczba unikalnych symboli, jakie mogą pojawić się w tekście, wynosi 65536Indeks dolny 10, co powoduje potencjalny problem z ich zliczeniem.

Można zrobić to na kilka sposobów. Moglibyśmy utworzyć tablicę ze zmiennymi typu int o długości 65536 i zapisać każde wystąpienie znaku na odpowiadającym mu indeksie. Metoda ta sprawiłaby jednak, że w trakcie kodowania wykorzystalibyśmy dodatkowe 262144 bajty.

Jesteśmy w stanie temu zaradzić, posługując się rozwiązaniem znanym z algorytmów sortujących. Przeszukując najpierw tekst i znajdując znaki o najmniejszej i największej wartości liczbowej, możemy zmniejszyć rozmiar tablicy, analogicznie jak w sortowaniu przez zliczanie czy w sortowaniu kubełkowym. Dokładne omówienie tych zagadnień znajdziesz w e‑materiałach:

Sortowanie przez zliczaniePNx8quWZlSortowanie przez zliczanie,
Sortowanie kubełkowePPpmzST7zSortowanie kubełkowe.

Następnie zliczamy wystąpienia poszczególnych znaków i zapisujemy je do tablicy.

public static int[] zlicz(String wiadomosc) {
	int[] tabZliczajaca;
	char min = Character.MAX_VALUE;
	char max = Character.MIN_VALUE;
	for (int i = 0; i < wiadomosc.length(); i++) {
		if (min > wiadomosc.charAt(i)) min = wiadomosc.charAt(i);
		if (max < wiadomosc.charAt(i)) max = wiadomosc.charAt(i);
	}
	tabZliczajaca = new int[max - min + 1];
	for (int i = 0; i < wiadomosc.length(); i++) {
		tabZliczajaca[wiadomosc.charAt(i) - min]++;
	}
	return tabZliczajaca;
}

Stałe Character.MAX_VALUE i Character.MIN_VALUE dostępne są w klasie Character, której nie musimy importować, ponieważ jest dostępna w ramach pakietu Java.lang. Po zliczeniu częstości występujących w kodzie znaków przechodzimy do tworzenia wierzchołków.

Zaprezentowany fragment kodu implementuje utworzenie wierzchołków dla tych znaków, które występują w kodzie przynajmniej raz. Korzystając z tablicy zwróconej przez funkcję zlicz(), tworzymy tablicę zawierającą nowo utworzone wierzchołki. Aby móc stwierdzić, jaki znak jest zakodowany, pod którym indeksem tablicy, musimy najpierw znaleźć w wiadomości znak o najniższym kodowaniu, a następnie do każdego indeksu z tablicy dodać jego wartość. W ten sposób po przekonwertowaniu na typ char otrzymamy odpowiedni znak.

Linia 1. String wiadomosc znak równości cudzysłów AABBCCDDDDDDDFFFEEER cudzysłów średnik. Linia 2. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca znak równości zlicz otwórz nawias okrągły wiadomosc zamknij nawias okrągły średnik. Linia 3. char minZnak znak równości Character kropka MAX podkreślnik VALUE średnik. Linia 4. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. if otwórz nawias okrągły minZnak zamknij nawias ostrokątny wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły. Linia 6. minZnak znak równości wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 7. zamknij nawias klamrowy. Linia 8. Wierzcholek otwórz nawias kwadratowy zamknij nawias kwadratowy listaWierzcholkow znak równości new Wierzcholek otwórz nawias kwadratowy tabZliczajaca kropka length zamknij nawias kwadratowy średnik. Linia 9. int dlugoscListy znak równości 0 średnik. Linia 10. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny listaWierzcholkow kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. if otwórz nawias okrągły tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. listaWierzcholkow otwórz nawias kwadratowy dlugoscListy zamknij nawias kwadratowy znak równości new Wierzcholek otwórz nawias okrągły otwórz nawias okrągły char zamknij nawias okrągły otwórz nawias okrągły i plus minZnak zamknij nawias okrągły przecinek tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek null przecinek null zamknij nawias okrągły średnik. Linia 13. dlugoscListy plus plus średnik. Linia 14. zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy.

String wiadomosc = "AABBCCDDDDDDDFFFEEER";
int[] tabZliczajaca = zlicz(wiadomosc);
char minZnak = Character.MAX_VALUE;
for (int i = 0; i < wiadomosc.length(); i++) {
	if (minZnak > wiadomosc.charAt(i))
        minZnak = wiadomosc.charAt(i);
}
Wierzcholek[] listaWierzcholkow = new Wierzcholek[tabZliczajaca.length];
int dlugoscListy = 0;
for (int i = 0; i < listaWierzcholkow.length; i++) {
	if (tabZliczajaca[i] != 0) {
		listaWierzcholkow[dlugoscListy] = new Wierzcholek((char) (i + minZnak), tabZliczajaca[i], null, null);
		dlugoscListy++;
	}
}

Następnie, zgodnie z kodowaniem Huffmana, wyszukujemy dwa wierzchołki o najmniejszej liczbie wystąpień i łączymy je w jeden o liczbie wystąpień równej sumie liczb wystąpień złączanych wierzchołków. Robimy tak do momentu, gdy zostanie nam jeden wierzchołek stanowiący korzeń całego drzewa binarnegodrzewo binarnedrzewa binarnego.

Posortujmy na początku wszystkie wierzchołki według liczby wystąpień. Skorzystamy z algorytmu sortowania bąbelkowego (jeśli chcesz przypomnieć sobie wiadomości na ten temat, znajdziesz je w e‑materiale Sortowanie bąbelkowePCfvfjgLkSortowanie bąbelkowe).

Podczas sortowania zawsze bierzemy dwa ostatnie wierzchołki z listy i łączymy je. Następnie wystarczy, że nowo powstały wierzchołek przesuniemy na odpowiednie miejsce w liście, a cała procedura będzie się powtarzać, aż zostanie jeden wierzchołek (czyli korzeń).

Linia 1. public static Wierzcholek sortowanie otwórz nawias okrągły Wierzcholek otwórz nawias kwadratowy zamknij nawias kwadratowy listaWierzcholkow przecinek int dlugoscListy zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. int j znak równości dlugoscListy średnik. Linia 3. do otwórz nawias klamrowy. Linia 4. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny j minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. if otwórz nawias okrągły listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka czestosc otwórz nawias ostrokątny listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy kropka czestosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. Wierzcholek temp znak równości listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 7. listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy średnik. Linia 8. listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 9. zamknij nawias klamrowy. Linia 10. zamknij nawias klamrowy. Linia 11. j minus minus średnik. Linia 12. zamknij nawias klamrowy while otwórz nawias okrągły j zamknij nawias ostrokątny 1 zamknij nawias okrągły średnik. Linia 14. int k znak równości dlugoscListy średnik. Linia 15. while otwórz nawias okrągły k zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. Wierzcholek pierwszyDoUsuniecia znak równości listaWierzcholkow otwórz nawias kwadratowy k minus 1 zamknij nawias kwadratowy średnik. Linia 17. Wierzcholek drugiDoUsuniecia znak równości listaWierzcholkow otwórz nawias kwadratowy k minus 2 zamknij nawias kwadratowy średnik. Linia 18. Wierzcholek nowyWierzcholek znak równości new Wierzcholek otwórz nawias okrągły apostrof lewy ukośnik 0 apostrof przecinek. Linia 19. pierwszyDoUsuniecia kropka czestosc plus drugiDoUsuniecia kropka czestosc przecinek pierwszyDoUsuniecia przecinek drugiDoUsuniecia zamknij nawias okrągły średnik. Linia 20. System kropka out kropka println otwórz nawias okrągły cudzysłów Usuwam i lacze w jeden następujace wierzcholki dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 21. System kropka out kropka println otwórz nawias okrągły cudzysłów Wierzcholek o znaku dwukropek cudzysłów plus pierwszyDoUsuniecia kropka znak plus cudzysłów cudzysłów plus pierwszyDoUsuniecia kropka czestosc zamknij nawias okrągły średnik. Linia 22. System kropka out kropka println otwórz nawias okrągły cudzysłów Wierzcholek o znaku dwukropek cudzysłów plus drugiDoUsuniecia kropka znak plus cudzysłów cudzysłów plus drugiDoUsuniecia kropka czestosc zamknij nawias okrągły średnik. Linia 23. listaWierzcholkow otwórz nawias kwadratowy k minus 2 zamknij nawias kwadratowy znak równości nowyWierzcholek średnik. Linia 24. listaWierzcholkow otwórz nawias kwadratowy k minus 1 zamknij nawias kwadratowy znak równości null średnik. Linia 25. k minus minus średnik. Linia 26. prawy ukośnik prawy ukośnik umieść nowy wierzchołek w odpowiednim miejscu. Linia 27. for otwórz nawias okrągły int i znak równości k minus 1 średnik i zamknij nawias ostrokątny 0 średnik i minus minus zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. if otwórz nawias okrągły listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy znak równości znak równości null kreska pionowa kreska pionowa listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka czestosc zamknij nawias ostrokątny listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy kropka czestosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. Wierzcholek temp znak równości listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 30. listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy średnik. Linia 31. listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 32. zamknij nawias klamrowy else. Linia 33. break średnik. Linia 34. zamknij nawias klamrowy. Linia 35. zamknij nawias klamrowy. Linia 36. return listaWierzcholkow otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 37. zamknij nawias klamrowy.

public static Wierzcholek sortowanie(Wierzcholek[] listaWierzcholkow, int dlugoscListy) {
	int j = dlugoscListy;
	do {
		for (int i = 0; i < j - 1; i++) {
			if (listaWierzcholkow[i].czestosc < listaWierzcholkow[i + 1].czestosc) {
				Wierzcholek temp = listaWierzcholkow[i];
				listaWierzcholkow[i] = listaWierzcholkow[i + 1];
				listaWierzcholkow[i + 1] = temp; 
			}
		} 
		j--;
	} while (j > 1);

	int k = dlugoscListy;
	while (k > 1) {
		Wierzcholek pierwszyDoUsuniecia = listaWierzcholkow[k - 1];
		Wierzcholek drugiDoUsuniecia = listaWierzcholkow[k - 2];
		Wierzcholek nowyWierzcholek = new Wierzcholek('\0',
					pierwszyDoUsuniecia.czestosc + drugiDoUsuniecia.czestosc, pierwszyDoUsuniecia, drugiDoUsuniecia);
		System.out.println("Usuwam i lacze w jeden następujace wierzcholki:");
		System.out.println("Wierzcholek o znaku: " + pierwszyDoUsuniecia.znak + " " + pierwszyDoUsuniecia.czestosc);
		System.out.println("Wierzcholek o znaku: " + drugiDoUsuniecia.znak + " " + drugiDoUsuniecia.czestosc);
		listaWierzcholkow[k - 2] = nowyWierzcholek;
		listaWierzcholkow[k - 1] = null;
		k--;
		// umieść nowy wierzchołek w odpowiednim miejscu
		for (int i = k - 1; i > 0; i--) {
			if (listaWierzcholkow[i - 1] == null || listaWierzcholkow[i].czestosc > listaWierzcholkow[i - 1].czestosc) {
				Wierzcholek temp = listaWierzcholkow[i];
				listaWierzcholkow[i] = listaWierzcholkow[i - 1];
				listaWierzcholkow[i - 1] = temp;
			} else
				break;
		}
	}
	return listaWierzcholkow[0];
}

Funkcja sortowanie zwróci jeden wierzchołek będący korzeniem.

Wierzcholek korzen = sortowanie(listaWierzcholkow, dlugoscListy);

Napiszemy też funkcję pomocniczą, dzięki której będzie można odczytać, w jaki sposób kodujemy znaki – służy ona jedynie do sprawdzania poprawności drzewa. W tym celu przejdziemy rekurencyjnie po drzewie i wypiszemy wartości każdego ze znalezionych liści.

public static void wypiszKod(Wierzcholek doPrzeszukania, String dotychczasowyKod) {
	if (doPrzeszukania.lewy == null && doPrzeszukania.prawy == null) {
		System.out.println("Znak: " + doPrzeszukania.znak + 
							" czestosc: " + doPrzeszukania.czestosc + 
							" slowo kodowe: " + dotychczasowyKod);
	}
	if (doPrzeszukania.lewy != null) {
		wypiszKod(doPrzeszukania.lewy, dotychczasowyKod + "0");
	}
	if (doPrzeszukania.prawy != null) {
		wypiszKod(doPrzeszukania.prawy, dotychczasowyKod + "1");
	}
}

Tworzymy dodatkową klasę Slowo, która będzie przechowywała słowo kodowe oraz kodowany znak pod tym słowem.

class Slowo {
	char znak;
	int czestosc;
	String slowoKodowe;
    
	Slowo(char znak, int czestosc, String slowoKodowe) {
		this.znak = znak;
		this.czestosc = czestosc;
		this.slowoKodowe = slowoKodowe;
	}
}

W kolejnym kroku implementujemy funkcję tworzącą tablicę słów kodowych. W tym celu przejdziemy rekurencyjnie po drzewie Huffmana i wartość każdego liścia zapiszemy w obiekcie klasy Słowo, który umieścimy w tablicy.

static int obecnyElementTablicySlow = 0;
 
private static Slowo[] zapiszKod(Wierzcholek doPrzeszukania, String dotychczasowyKod, Slowo[] listaSlow) {
	if (doPrzeszukania.lewy == null && doPrzeszukania.prawy == null) {
		listaSlow[obecnyElementTablicySlow] = new Slowo(doPrzeszukania.znak, doPrzeszukania.czestosc,dotychczasowyKod);
		obecnyElementTablicySlow++;
	}
	if (doPrzeszukania.lewy != null) {
		zapiszKod(doPrzeszukania.lewy, dotychczasowyKod + "0", listaSlow);
	}
	if (doPrzeszukania.prawy != null) {
		zapiszKod(doPrzeszukania.prawy, dotychczasowyKod + "1", listaSlow);
	}
	return listaSlow;
}

Implementujemy odnajdywanie odpowiedniego słowa kodowego dla odpowiedniego znaku. Iterując po książce słów, szukamy odpowiedniego znaku, a następnie go zwracamy.

static String zakodujZnak(char znak, Slowo[] ksiazkaSlow) {
	for (int i = 0; i < ksiazkaSlow.length; i++) {
		if (ksiazkaSlow[i].znak == znak)
			return ksiazkaSlow[i].slowoKodowe;
	}
	return "";// jeśli korzystamy z odpowiedniej funkcji kodowej, ta instrukcja się nie wykona
}

Gdy mamy już zaimplementowane kodowanie znaku, pora na wdrożenie kodowania całej wiadomości z użyciem gotowej książki kodowej. Dla każdego znaku wywołujemy metodę zakodujZnak(), a następnie wszystkie zakodowane znaki łączymy w jedną zakodowaną wiadomość.

static String zakodujWiadomosc(String wiadomosc, Slowo[] ksiazkaSlow) {
	String zakodowanaWiadomosc = "";
	for (int i = 0; i < wiadomosc.length(); i++) {
		zakodowanaWiadomosc += zakodujZnak(wiadomosc.charAt(i), ksiazkaSlow);
	}
	return zakodowanaWiadomosc;
}

Funkcja main połączy poszczególne omówione powyżej fragmenty kodu. Poza tym dodajemy wywołanie funkcji tworzącej drzewo i kodującej przykładową wiadomość.

Linia 1. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. String wiadomosc znak równości cudzysłów AABBCCDDDDDDDFFFEEER cudzysłów średnik. Linia 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca znak równości zlicz otwórz nawias okrągły wiadomosc zamknij nawias okrągły średnik. Linia 4. char minZnak znak równości Character kropka MAX podkreślnik VALUE średnik. Linia 5. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. if otwórz nawias okrągły minZnak zamknij nawias ostrokątny wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły. Linia 7. minZnak znak równości wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 8. zamknij nawias klamrowy. Linia 9. Wierzcholek otwórz nawias kwadratowy zamknij nawias kwadratowy listaWierzcholkow znak równości new Wierzcholek otwórz nawias kwadratowy tabZliczajaca kropka length zamknij nawias kwadratowy średnik. Linia 10. int dlugoscListy znak równości 0 średnik. Linia 11. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny listaWierzcholkow kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. if otwórz nawias okrągły tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. listaWierzcholkow otwórz nawias kwadratowy dlugoscListy zamknij nawias kwadratowy znak równości new Wierzcholek otwórz nawias okrągły otwórz nawias okrągły char zamknij nawias okrągły otwórz nawias okrągły i plus minZnak zamknij nawias okrągły przecinek tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek null przecinek null zamknij nawias okrągły średnik. Linia 14. dlugoscListy plus plus średnik. Linia 15. zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy. Linia 17. Wierzcholek korzen znak równości sortowanie otwórz nawias okrągły listaWierzcholkow przecinek dlugoscListy zamknij nawias okrągły średnik. Linia 18. prawy ukośnik prawy ukośnik w przypadku przecinek gdy w tekście znajduje się tylko jeden unikalny znak przecinek musimy. Linia 19. prawy ukośnik prawy ukośnik obsłużyć ten wyjątek przecinek ponieważ drzewo się nie zbuduje. Linia 20. if otwórz nawias okrągły dlugoscListy znak równości znak równości 1 zamknij nawias okrągły. Linia 21. korzen znak równości new Wierzcholek otwórz nawias okrągły apostrof lewy ukośnik 0 apostrof przecinek 1 przecinek null przecinek listaWierzcholkow otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 22. Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazkaSlow znak równości new Slowo otwórz nawias kwadratowy dlugoscListy zamknij nawias kwadratowy średnik. Linia 23. wypiszKod otwórz nawias okrągły korzen przecinek cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 24. prawy ukośnik prawy ukośnik zapisujemy kodowanie w książce słów. Linia 25. ksiazkaSlow znak równości zapiszKod otwórz nawias okrągły korzen przecinek cudzysłów cudzysłów przecinek ksiazkaSlow zamknij nawias okrągły średnik. Linia 26. prawy ukośnik prawy ukośnik kodujemy wiadomość. Linia 27. String wiadomoscZakodowana znak równości zakodujWiadomosc otwórz nawias okrągły wiadomosc przecinek ksiazkaSlow zamknij nawias okrągły średnik. Linia 28. System kropka out kropka println otwórz nawias okrągły cudzysłów Wiadomosc do zakodowania dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 29. System kropka out kropka println otwórz nawias okrągły wiadomosc zamknij nawias okrągły średnik. Linia 30. System kropka out kropka println otwórz nawias okrągły cudzysłów Wiadomosc zakodowana dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 31. System kropka out kropka println otwórz nawias okrągły wiadomoscZakodowana zamknij nawias okrągły średnik. Linia 32. zamknij nawias klamrowy.

public static void main(String[] args) {
	String wiadomosc = "AABBCCDDDDDDDFFFEEER";
	int[] tabZliczajaca = zlicz(wiadomosc);
	char minZnak = Character.MAX_VALUE;
	for (int i = 0; i < wiadomosc.length(); i++) {
		if (minZnak > wiadomosc.charAt(i))
			minZnak = wiadomosc.charAt(i);
	}
	Wierzcholek[] listaWierzcholkow = new Wierzcholek[tabZliczajaca.length];
	int dlugoscListy = 0;
	for (int i = 0; i < listaWierzcholkow.length; i++) {
		if (tabZliczajaca[i] != 0) {
			listaWierzcholkow[dlugoscListy] = new Wierzcholek((char) (i + minZnak), tabZliczajaca[i], null, null);
			dlugoscListy++;
		}
	}
	Wierzcholek korzen = sortowanie(listaWierzcholkow, dlugoscListy);
	// w przypadku, gdy w tekście znajduje się tylko jeden unikalny znak, musimy
	// obsłużyć ten wyjątek, ponieważ drzewo się nie zbuduje
	if (dlugoscListy == 1)
		korzen = new Wierzcholek('\0', 1, null, listaWierzcholkow[0]);
	Slowo[] ksiazkaSlow = new Slowo[dlugoscListy];
	wypiszKod(korzen, "");
    // zapisujemy kodowanie w książce słów
	ksiazkaSlow = zapiszKod(korzen, "", ksiazkaSlow);
    // kodujemy wiadomość
	String wiadomoscZakodowana = zakodujWiadomosc(wiadomosc, ksiazkaSlow);
	System.out.println("Wiadomosc do zakodowania: ");
	System.out.println(wiadomosc);
	System.out.println("Wiadomosc zakodowana: ");
	System.out.println(wiadomoscZakodowana);
}

Teraz możemy przetestować działanie kodowania.

Linia 1. public class Main otwórz nawias klamrowy. Linia 3. public static int otwórz nawias kwadratowy zamknij nawias kwadratowy zlicz otwórz nawias okrągły String wiadomosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca średnik. Linia 5. char min znak równości Character kropka MAX podkreślnik VALUE średnik. Linia 6. char max znak równości Character kropka MIN podkreślnik VALUE średnik. Linia 7. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły min zamknij nawias ostrokątny wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły. Linia 9. min znak równości wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 10. if otwórz nawias okrągły max otwórz nawias ostrokątny wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły. Linia 11. max znak równości wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 12. zamknij nawias klamrowy. Linia 13. tabZliczajaca znak równości new int otwórz nawias kwadratowy max minus min plus 1 zamknij nawias kwadratowy średnik. Linia 14. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. tabZliczajaca otwórz nawias kwadratowy wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły minus min zamknij nawias kwadratowy plus plus średnik. Linia 16. zamknij nawias klamrowy. Linia 17. return tabZliczajaca średnik. Linia 18. zamknij nawias klamrowy. Linia 20. public static Wierzcholek sortowanie otwórz nawias okrągły Wierzcholek otwórz nawias kwadratowy zamknij nawias kwadratowy listaWierzcholkow przecinek int dlugoscListy zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. int j znak równości dlugoscListy średnik. Linia 22. do otwórz nawias klamrowy. Linia 23. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny j minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. if otwórz nawias okrągły listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka czestosc otwórz nawias ostrokątny listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy kropka czestosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 25. Wierzcholek temp znak równości listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 26. listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy średnik. Linia 27. listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 28. zamknij nawias klamrowy. Linia 29. zamknij nawias klamrowy. Linia 30. j minus minus średnik. Linia 31. zamknij nawias klamrowy while otwórz nawias okrągły j zamknij nawias ostrokątny 1 zamknij nawias okrągły średnik. Linia 33. int k znak równości dlugoscListy średnik. Linia 34. while otwórz nawias okrągły k zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. prawy ukośnik prawy ukośnik wierzchołki o najmniejszej częstości znajdują się na końcu listy. Linia 36. Wierzcholek pierwszyDoUsuniecia znak równości listaWierzcholkow otwórz nawias kwadratowy k minus 1 zamknij nawias kwadratowy średnik. Linia 37. Wierzcholek drugiDoUsuniecia znak równości listaWierzcholkow otwórz nawias kwadratowy k minus 2 zamknij nawias kwadratowy średnik. Linia 38. Wierzcholek nowyWierzcholek znak równości new Wierzcholek otwórz nawias okrągły apostrof lewy ukośnik 0 apostrof przecinek. Linia 39. pierwszyDoUsuniecia kropka czestosc plus drugiDoUsuniecia kropka czestosc przecinek pierwszyDoUsuniecia przecinek drugiDoUsuniecia zamknij nawias okrągły średnik. Linia 40. System kropka out kropka println otwórz nawias okrągły cudzysłów Usuwam i lacze w jeden następujace wierzcholki dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 41. System kropka out kropka println otwórz nawias okrągły cudzysłów Wierzcholek o znaku dwukropek cudzysłów plus pierwszyDoUsuniecia kropka znak plus cudzysłów cudzysłów plus pierwszyDoUsuniecia kropka czestosc zamknij nawias okrągły średnik. Linia 42. System kropka out kropka println otwórz nawias okrągły cudzysłów Wierzcholek o znaku dwukropek cudzysłów plus drugiDoUsuniecia kropka znak plus cudzysłów cudzysłów plus drugiDoUsuniecia kropka czestosc zamknij nawias okrągły średnik. Linia 43. listaWierzcholkow otwórz nawias kwadratowy k minus 2 zamknij nawias kwadratowy znak równości nowyWierzcholek średnik. Linia 44. listaWierzcholkow otwórz nawias kwadratowy k minus 1 zamknij nawias kwadratowy znak równości null średnik. Linia 45. k minus minus średnik. Linia 46. prawy ukośnik prawy ukośnik umieść nowy wierzchołek w odpowiednim miejscu. Linia 47. for otwórz nawias okrągły int i znak równości k minus 1 średnik i zamknij nawias ostrokątny 0 średnik i minus minus zamknij nawias okrągły otwórz nawias klamrowy. Linia 48. if otwórz nawias okrągły listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy znak równości znak równości null. Linia 49. kreska pionowa kreska pionowa listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka czestosc zamknij nawias ostrokątny listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy kropka czestosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 50. Wierzcholek temp znak równości listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 51. listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy średnik. Linia 52. listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 53. zamknij nawias klamrowy else. Linia 54. break średnik. Linia 55. zamknij nawias klamrowy. Linia 56. zamknij nawias klamrowy. Linia 57. return listaWierzcholkow otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 58. zamknij nawias klamrowy. Linia 60. public static void wypiszKod otwórz nawias okrągły Wierzcholek doPrzeszukania przecinek String dotychczasowyKod zamknij nawias okrągły otwórz nawias klamrowy. Linia 61. if otwórz nawias okrągły doPrzeszukania kropka lewy znak równości znak równości null ampersant ampersant doPrzeszukania kropka prawy znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 62. System kropka out kropka println otwórz nawias okrągły cudzysłów Znak dwukropek cudzysłów plus doPrzeszukania kropka znak plus. Linia 63. cudzysłów czestosc dwukropek cudzysłów plus doPrzeszukania kropka czestosc plus. Linia 64. cudzysłów slowo kodowe dwukropek cudzysłów plus dotychczasowyKod zamknij nawias okrągły średnik. Linia 65. zamknij nawias klamrowy. Linia 66. if otwórz nawias okrągły doPrzeszukania kropka lewy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 67. wypiszKod otwórz nawias okrągły doPrzeszukania kropka lewy przecinek dotychczasowyKod plus cudzysłów 0 cudzysłów zamknij nawias okrągły średnik. Linia 68. zamknij nawias klamrowy. Linia 69. if otwórz nawias okrągły doPrzeszukania kropka prawy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 70. wypiszKod otwórz nawias okrągły doPrzeszukania kropka prawy przecinek dotychczasowyKod plus cudzysłów 1 cudzysłów zamknij nawias okrągły średnik. Linia 71. zamknij nawias klamrowy. Linia 72. zamknij nawias klamrowy. Linia 74. static int obecnyElementTablicySlow znak równości 0 średnik. Linia 76. private static Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy zapiszKod otwórz nawias okrągły Wierzcholek doPrzeszukania przecinek String dotychczasowyKod przecinek Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy listaSlow zamknij nawias okrągły otwórz nawias klamrowy. Linia 77. if otwórz nawias okrągły doPrzeszukania kropka lewy znak równości znak równości null ampersant ampersant doPrzeszukania kropka prawy znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 78. listaSlow otwórz nawias kwadratowy obecnyElementTablicySlow zamknij nawias kwadratowy znak równości new Slowo otwórz nawias okrągły doPrzeszukania kropka znak przecinek doPrzeszukania kropka czestosc przecinek. Linia 79. dotychczasowyKod zamknij nawias okrągły średnik. Linia 80. obecnyElementTablicySlow plus plus średnik. Linia 81. zamknij nawias klamrowy. Linia 82. if otwórz nawias okrągły doPrzeszukania kropka lewy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 83. zapiszKod otwórz nawias okrągły doPrzeszukania kropka lewy przecinek dotychczasowyKod plus cudzysłów 0 cudzysłów przecinek listaSlow zamknij nawias okrągły średnik. Linia 84. zamknij nawias klamrowy. Linia 85. if otwórz nawias okrągły doPrzeszukania kropka prawy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 86. zapiszKod otwórz nawias okrągły doPrzeszukania kropka prawy przecinek dotychczasowyKod plus cudzysłów 1 cudzysłów przecinek listaSlow zamknij nawias okrągły średnik. Linia 87. zamknij nawias klamrowy. Linia 88. return listaSlow średnik. Linia 89. zamknij nawias klamrowy. Linia 91. static String zakodujZnak otwórz nawias okrągły char znak przecinek Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazkaSlow zamknij nawias okrągły otwórz nawias klamrowy. Linia 92. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny ksiazkaSlow kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 93. if otwórz nawias okrągły ksiazkaSlow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak znak równości znak równości znak zamknij nawias okrągły. Linia 94. return ksiazkaSlow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowoKodowe średnik. Linia 95. zamknij nawias klamrowy. Linia 96. return cudzysłów cudzysłów średnik prawy ukośnik prawy ukośnik jeśli korzystamy z odpowiedniej funkcji kodowej przecinek ta instrukcja się nie wykona. Linia 97. zamknij nawias klamrowy. Linia 99. static String zakodujWiadomosc otwórz nawias okrągły String wiadomosc przecinek Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazkaSlow zamknij nawias okrągły otwórz nawias klamrowy. Linia 100. String zakodowanaWiadomosc znak równości cudzysłów cudzysłów średnik. Linia 101. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 102. zakodowanaWiadomosc plus znak równości zakodujZnak otwórz nawias okrągły wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły przecinek ksiazkaSlow zamknij nawias okrągły średnik. Linia 103. zamknij nawias klamrowy. Linia 104. return zakodowanaWiadomosc średnik. Linia 105. zamknij nawias klamrowy. Linia 107. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 108. String wiadomosc znak równości cudzysłów AABBCCDDDDDDDFFFEEER cudzysłów średnik. Linia 109. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca znak równości zlicz otwórz nawias okrągły wiadomosc zamknij nawias okrągły średnik. Linia 110. char minZnak znak równości Character kropka MAX podkreślnik VALUE średnik. Linia 111. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 112. if otwórz nawias okrągły minZnak zamknij nawias ostrokątny wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły. Linia 113. minZnak znak równości wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 114. zamknij nawias klamrowy. Linia 115. Wierzcholek otwórz nawias kwadratowy zamknij nawias kwadratowy listaWierzcholkow znak równości new Wierzcholek otwórz nawias kwadratowy tabZliczajaca kropka length zamknij nawias kwadratowy średnik. Linia 116. int dlugoscListy znak równości 0 średnik. Linia 117. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny listaWierzcholkow kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 118. if otwórz nawias okrągły tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 119. listaWierzcholkow otwórz nawias kwadratowy dlugoscListy zamknij nawias kwadratowy znak równości new Wierzcholek otwórz nawias okrągły otwórz nawias okrągły char zamknij nawias okrągły otwórz nawias okrągły i plus minZnak zamknij nawias okrągły przecinek tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek null przecinek null zamknij nawias okrągły średnik. Linia 120. dlugoscListy plus plus średnik. Linia 121. zamknij nawias klamrowy. Linia 122. zamknij nawias klamrowy. Linia 123. Wierzcholek korzen znak równości sortowanie otwórz nawias okrągły listaWierzcholkow przecinek dlugoscListy zamknij nawias okrągły średnik. Linia 124. prawy ukośnik prawy ukośnik w przypadku przecinek gdy w tekście znajduje się tylko jeden unikalny znak przecinek musimy. Linia 125. prawy ukośnik prawy ukośnik obsłużyć ten wyjątek przecinek ponieważ drzewo się nie zbuduje. Linia 126. if otwórz nawias okrągły dlugoscListy znak równości znak równości 1 zamknij nawias okrągły. Linia 127. korzen znak równości new Wierzcholek otwórz nawias okrągły apostrof lewy ukośnik 0 apostrof przecinek 1 przecinek null przecinek listaWierzcholkow otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 128. Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazkaSlow znak równości new Slowo otwórz nawias kwadratowy dlugoscListy zamknij nawias kwadratowy średnik. Linia 129. wypiszKod otwórz nawias okrągły korzen przecinek cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 130. ksiazkaSlow znak równości zapiszKod otwórz nawias okrągły korzen przecinek cudzysłów cudzysłów przecinek ksiazkaSlow zamknij nawias okrągły średnik. Linia 131. String wiadomoscZakodowana znak równości zakodujWiadomosc otwórz nawias okrągły wiadomosc przecinek ksiazkaSlow zamknij nawias okrągły średnik. Linia 132. System kropka out kropka println otwórz nawias okrągły cudzysłów Wiadomosc do zakodowania dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 133. System kropka out kropka println otwórz nawias okrągły wiadomosc zamknij nawias okrągły średnik. Linia 134. System kropka out kropka println otwórz nawias okrągły cudzysłów Wiadomosc zakodowana dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 135. System kropka out kropka println otwórz nawias okrągły wiadomoscZakodowana zamknij nawias okrągły średnik. Linia 136. zamknij nawias klamrowy. Linia 137. zamknij nawias klamrowy. Linia 139. class Wierzcholek otwórz nawias klamrowy. Linia 140. char znak średnik. Linia 141. int czestosc średnik. Linia 142. Wierzcholek lewy znak równości null średnik. Linia 143. Wierzcholek prawy znak równości null średnik. Linia 145. Wierzcholek otwórz nawias okrągły char znak przecinek int czestosc przecinek Wierzcholek lewy przecinek Wierzcholek prawy zamknij nawias okrągły otwórz nawias klamrowy. Linia 146. this kropka znak znak równości znak średnik. Linia 147. this kropka czestosc znak równości czestosc średnik. Linia 148. this kropka lewy znak równości lewy średnik. Linia 149. this kropka prawy znak równości prawy średnik. Linia 150. zamknij nawias klamrowy. Linia 151. zamknij nawias klamrowy. Linia 153. class Slowo otwórz nawias klamrowy. Linia 154. char znak średnik. Linia 155. int czestosc średnik. Linia 156. String slowoKodowe średnik. Linia 158. Slowo otwórz nawias okrągły char znak przecinek int czestosc przecinek String slowoKodowe zamknij nawias okrągły otwórz nawias klamrowy. Linia 159. this kropka znak znak równości znak średnik. Linia 160. this kropka czestosc znak równości czestosc średnik. Linia 161. this kropka slowoKodowe znak równości slowoKodowe średnik. Linia 162. zamknij nawias klamrowy. Linia 163. zamknij nawias klamrowy.

public class Main {

	public static int[] zlicz(String wiadomosc) {
		int[] tabZliczajaca;
		char min = Character.MAX_VALUE;
		char max = Character.MIN_VALUE;
		for (int i = 0; i < wiadomosc.length(); i++) {
			if (min > wiadomosc.charAt(i))
				min = wiadomosc.charAt(i);
			if (max < wiadomosc.charAt(i))
				max = wiadomosc.charAt(i);
		}
		tabZliczajaca = new int[max - min + 1];
		for (int i = 0; i < wiadomosc.length(); i++) {
			tabZliczajaca[wiadomosc.charAt(i) - min]++;
		}
		return tabZliczajaca;
	}

	public static Wierzcholek sortowanie(Wierzcholek[] listaWierzcholkow, int dlugoscListy) {
		int j = dlugoscListy;
		do {
			for (int i = 0; i < j - 1; i++) {
				if (listaWierzcholkow[i].czestosc < listaWierzcholkow[i + 1].czestosc) {
					Wierzcholek temp = listaWierzcholkow[i];
					listaWierzcholkow[i] = listaWierzcholkow[i + 1];
					listaWierzcholkow[i + 1] = temp;
				}
			}
			j--;
		} while (j > 1);

		int k = dlugoscListy;
		while (k > 1) {
			// wierzchołki o najmniejszej częstości znajdują się na końcu listy
			Wierzcholek pierwszyDoUsuniecia = listaWierzcholkow[k - 1];
			Wierzcholek drugiDoUsuniecia = listaWierzcholkow[k - 2];
			Wierzcholek nowyWierzcholek = new Wierzcholek('\0',
					pierwszyDoUsuniecia.czestosc + drugiDoUsuniecia.czestosc, pierwszyDoUsuniecia, drugiDoUsuniecia);
			System.out.println("Usuwam i lacze w jeden następujace wierzcholki:");
			System.out.println("Wierzcholek o znaku: " + pierwszyDoUsuniecia.znak + " " + pierwszyDoUsuniecia.czestosc);
			System.out.println("Wierzcholek o znaku: " + drugiDoUsuniecia.znak + " " + drugiDoUsuniecia.czestosc);
			listaWierzcholkow[k - 2] = nowyWierzcholek;
			listaWierzcholkow[k - 1] = null;
			k--;
			// umieść nowy wierzchołek w odpowiednim miejscu
			for (int i = k - 1; i > 0; i--) {
				if (listaWierzcholkow[i - 1] == null
						|| listaWierzcholkow[i].czestosc > listaWierzcholkow[i - 1].czestosc) {
					Wierzcholek temp = listaWierzcholkow[i];
					listaWierzcholkow[i] = listaWierzcholkow[i - 1];
					listaWierzcholkow[i - 1] = temp;
				} else
					break;
			}
		}
		return listaWierzcholkow[0];
	}
    
    public static void wypiszKod(Wierzcholek doPrzeszukania, String dotychczasowyKod) {
		if (doPrzeszukania.lewy == null && doPrzeszukania.prawy == null) {
			System.out.println("Znak: " + doPrzeszukania.znak +
					" czestosc: " + doPrzeszukania.czestosc +
					" slowo kodowe: " + dotychczasowyKod);
		}
		if (doPrzeszukania.lewy != null) {
			wypiszKod(doPrzeszukania.lewy, dotychczasowyKod + "0");
		}
		if (doPrzeszukania.prawy != null) {
			wypiszKod(doPrzeszukania.prawy, dotychczasowyKod + "1");
		}
	}

	static int obecnyElementTablicySlow = 0;

	private static Slowo[] zapiszKod(Wierzcholek doPrzeszukania, String dotychczasowyKod, Slowo[] listaSlow) {
		if (doPrzeszukania.lewy == null && doPrzeszukania.prawy == null) {
			listaSlow[obecnyElementTablicySlow] = new Slowo(doPrzeszukania.znak, doPrzeszukania.czestosc,
					dotychczasowyKod);
			obecnyElementTablicySlow++;
		}
		if (doPrzeszukania.lewy != null) {
			zapiszKod(doPrzeszukania.lewy, dotychczasowyKod + "0", listaSlow);
		}
		if (doPrzeszukania.prawy != null) {
			zapiszKod(doPrzeszukania.prawy, dotychczasowyKod + "1", listaSlow);
		}
		return listaSlow;
	}

	static String zakodujZnak(char znak, Slowo[] ksiazkaSlow) {
		for (int i = 0; i < ksiazkaSlow.length; i++) {
			if (ksiazkaSlow[i].znak == znak)
				return ksiazkaSlow[i].slowoKodowe;
		}
		return "";// jeśli korzystamy z odpowiedniej funkcji kodowej, ta instrukcja się nie wykona
	}

	static String zakodujWiadomosc(String wiadomosc, Slowo[] ksiazkaSlow) {
		String zakodowanaWiadomosc = "";
		for (int i = 0; i < wiadomosc.length(); i++) {
			zakodowanaWiadomosc += zakodujZnak(wiadomosc.charAt(i), ksiazkaSlow);
		}
		return zakodowanaWiadomosc;
	}

	public static void main(String[] args) {
		String wiadomosc = "AABBCCDDDDDDDFFFEEER";
		int[] tabZliczajaca = zlicz(wiadomosc);
		char minZnak = Character.MAX_VALUE;
		for (int i = 0; i < wiadomosc.length(); i++) {
			if (minZnak > wiadomosc.charAt(i))
				minZnak = wiadomosc.charAt(i);
		}
		Wierzcholek[] listaWierzcholkow = new Wierzcholek[tabZliczajaca.length];
		int dlugoscListy = 0;
		for (int i = 0; i < listaWierzcholkow.length; i++) {
			if (tabZliczajaca[i] != 0) {
				listaWierzcholkow[dlugoscListy] = new Wierzcholek((char) (i + minZnak), tabZliczajaca[i], null, null);
				dlugoscListy++;
			}
		}
		Wierzcholek korzen = sortowanie(listaWierzcholkow, dlugoscListy);
		// w przypadku, gdy w tekście znajduje się tylko jeden unikalny znak, musimy
		// obsłużyć ten wyjątek, ponieważ drzewo się nie zbuduje
		if (dlugoscListy == 1)
			korzen = new Wierzcholek('\0', 1, null, listaWierzcholkow[0]);
		Slowo[] ksiazkaSlow = new Slowo[dlugoscListy];
		wypiszKod(korzen, "");
		ksiazkaSlow = zapiszKod(korzen, "", ksiazkaSlow);
		String wiadomoscZakodowana = zakodujWiadomosc(wiadomosc, ksiazkaSlow);
		System.out.println("Wiadomosc do zakodowania: ");
		System.out.println(wiadomosc);
		System.out.println("Wiadomosc zakodowana: ");
		System.out.println(wiadomoscZakodowana);
	}
}

class Wierzcholek {
	char znak;
	int czestosc;
	Wierzcholek lewy = null;
	Wierzcholek prawy = null;

	Wierzcholek(char znak, int czestosc, Wierzcholek lewy, Wierzcholek prawy) {
		this.znak = znak;
		this.czestosc = czestosc;
		this.lewy = lewy;
		this.prawy = prawy;
	}
}

class Slowo {
	char znak;
	int czestosc;
	String slowoKodowe;

	Slowo(char znak, int czestosc, String slowoKodowe) {
		this.znak = znak;
		this.czestosc = czestosc;
		this.slowoKodowe = slowoKodowe;
	}
}

Program wypisuje:

Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku: R 1
Wierzcholek o znaku: C 2
Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku: B 2
Wierzcholek o znaku: A 2
Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku:  3
Wierzcholek o znaku: F 3
Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku: E 3
Wierzcholek o znaku:  4
Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku:  6
Wierzcholek o znaku:  7
Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku: D 7
Wierzcholek o znaku:  13
Znak: D czestosc: 7 slowo kodowe: 0
Znak: R czestosc: 1 slowo kodowe: 1000
Znak: C czestosc: 2 slowo kodowe: 1001
Znak: F czestosc: 3 slowo kodowe: 101
Znak: E czestosc: 3 slowo kodowe: 110
Znak: B czestosc: 2 slowo kodowe: 1110
Znak: A czestosc: 2 slowo kodowe: 1111
Wiadomosc do zakodowania:
AABBCCDDDDDDDFFFEEER
Wiadomosc zakodowana:
11111111111011101001100100000001011011011101101101000

Problem 4

W kolejnym kroku implementujemy odkodowywanie na podstawie utworzonego drzewa. Odkodowanie wiadomości na podstawie książki kodowej jest możliwe, ale nieefektywne. Informacje na temat algorytmów zachłannych, stosowanych przy przeszukiwaniu wszystkich możliwości, znajdziesz w e‑materiale Algorytmy zachłanneP1Ed8GL2MAlgorytmy zachłanne.

Specyfikacja problemu:

Dane:

zakodowanaWiadomosc – łańcuch znaków do odkodowania
korzen – korzeń drzewa binarnego użytego do zakodowania wiadomości

Wynik:

zdekodowanaWiadomosc – łańcuch znaków

Aby odkodować wiadomość, skorzystamy z drzewa binarnego, którego używaliśmy do kodowania. Zagłębiamy się rekurencyjnie w drzewo aż do odnalezienia liścia zawierającego znak. Powtarzamy tę procedurę do momentu, w którym skończy się łańcuch znaków:

static String odkodujWiadomosc(String wiadomosc, Wierzcholek korzen) {
	Wierzcholek doPrzeszukania = korzen;
	String wiadomoscOdkodowana = "";
	for (int i = 0; i < wiadomosc.length(); i++) {
		if (wiadomosc.charAt(i) == '0')
			doPrzeszukania = doPrzeszukania.lewy;
		else
			doPrzeszukania = doPrzeszukania.prawy;
		if (doPrzeszukania.lewy == null || doPrzeszukania.prawy == null) {
			wiadomoscOdkodowana += doPrzeszukania.znak;
			doPrzeszukania = korzen;
		}
	}
	return wiadomoscOdkodowana;
}

Aby przetestować działanie funkcji odkodowującej, potrzebujemy najpierw stworzyć drzewo binarne. Użyjemy w tym celu implementacji z poprzedniego zadania i połączymy kodowanie z odkodowywaniem.

Linia 1. public class Main otwórz nawias klamrowy. Linia 3. public static int otwórz nawias kwadratowy zamknij nawias kwadratowy zlicz otwórz nawias okrągły String wiadomosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca średnik. Linia 5. char min znak równości Character kropka MAX podkreślnik VALUE średnik. Linia 6. char max znak równości Character kropka MIN podkreślnik VALUE średnik. Linia 7. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły min zamknij nawias ostrokątny wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły. Linia 9. min znak równości wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 10. if otwórz nawias okrągły max otwórz nawias ostrokątny wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły. Linia 11. max znak równości wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 12. zamknij nawias klamrowy. Linia 13. tabZliczajaca znak równości new int otwórz nawias kwadratowy max minus min plus 1 zamknij nawias kwadratowy średnik. Linia 14. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. tabZliczajaca otwórz nawias kwadratowy wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły minus min zamknij nawias kwadratowy plus plus średnik. Linia 16. zamknij nawias klamrowy. Linia 17. return tabZliczajaca średnik. Linia 18. zamknij nawias klamrowy. Linia 20. public static Wierzcholek sortowanie otwórz nawias okrągły Wierzcholek otwórz nawias kwadratowy zamknij nawias kwadratowy listaWierzcholkow przecinek int dlugoscListy zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. int j znak równości dlugoscListy średnik. Linia 23. do otwórz nawias klamrowy. Linia 24. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny j minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 25. if otwórz nawias okrągły listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka czestosc otwórz nawias ostrokątny listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy kropka czestosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. Wierzcholek temp znak równości listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 27. listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy średnik. Linia 28. listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy. Linia 31. j minus minus średnik. Linia 32. zamknij nawias klamrowy while otwórz nawias okrągły j zamknij nawias ostrokątny 1 zamknij nawias okrągły średnik. Linia 34. int k znak równości dlugoscListy średnik. Linia 35. while otwórz nawias okrągły k zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. prawy ukośnik prawy ukośnik wierzchołki o najmniejszej częstości znajdują się na końcu listy. Linia 37. Wierzcholek pierwszyDoUsuniecia znak równości listaWierzcholkow otwórz nawias kwadratowy k minus 1 zamknij nawias kwadratowy średnik. Linia 38. Wierzcholek drugiDoUsuniecia znak równości listaWierzcholkow otwórz nawias kwadratowy k minus 2 zamknij nawias kwadratowy średnik. Linia 39. Wierzcholek nowyWierzcholek znak równości new Wierzcholek otwórz nawias okrągły apostrof lewy ukośnik 0 apostrof przecinek. Linia 40. pierwszyDoUsuniecia kropka czestosc plus drugiDoUsuniecia kropka czestosc przecinek pierwszyDoUsuniecia przecinek drugiDoUsuniecia zamknij nawias okrągły średnik. Linia 41. System kropka out kropka println otwórz nawias okrągły cudzysłów Usuwam i lacze w jeden następujace wierzcholki dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 42. System kropka out kropka println otwórz nawias okrągły cudzysłów Wierzcholek o znaku dwukropek cudzysłów plus pierwszyDoUsuniecia kropka znak plus cudzysłów cudzysłów plus pierwszyDoUsuniecia kropka czestosc zamknij nawias okrągły średnik. Linia 43. System kropka out kropka println otwórz nawias okrągły cudzysłów Wierzcholek o znaku dwukropek cudzysłów plus drugiDoUsuniecia kropka znak plus cudzysłów cudzysłów plus drugiDoUsuniecia kropka czestosc zamknij nawias okrągły średnik. Linia 44. listaWierzcholkow otwórz nawias kwadratowy k minus 2 zamknij nawias kwadratowy znak równości nowyWierzcholek średnik. Linia 45. listaWierzcholkow otwórz nawias kwadratowy k minus 1 zamknij nawias kwadratowy znak równości null średnik. Linia 46. k minus minus średnik. Linia 47. prawy ukośnik prawy ukośnik umieść nowy wierzchołek w odpowiednim miejscu. Linia 48. for otwórz nawias okrągły int i znak równości k minus 1 średnik i zamknij nawias ostrokątny 0 średnik i minus minus zamknij nawias okrągły otwórz nawias klamrowy. Linia 49. if otwórz nawias okrągły listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy znak równości znak równości null. Linia 50. kreska pionowa kreska pionowa listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka czestosc zamknij nawias ostrokątny listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy kropka czestosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 51. Wierzcholek temp znak równości listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 52. listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy średnik. Linia 53. listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 54. zamknij nawias klamrowy else break średnik. Linia 55. zamknij nawias klamrowy. Linia 56. zamknij nawias klamrowy. Linia 57. return listaWierzcholkow otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 58. zamknij nawias klamrowy. Linia 60. public static void wypiszKod otwórz nawias okrągły Wierzcholek doPrzeszukania przecinek String dotychczasowyKod zamknij nawias okrągły otwórz nawias klamrowy. Linia 61. if otwórz nawias okrągły doPrzeszukania kropka lewy znak równości znak równości null ampersant ampersant doPrzeszukania kropka prawy znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 62. System kropka out kropka println otwórz nawias okrągły cudzysłów Znak dwukropek cudzysłów plus doPrzeszukania kropka znak plus. Linia 63. cudzysłów czestosc dwukropek cudzysłów plus doPrzeszukania kropka czestosc plus. Linia 64. cudzysłów slowo kodowe dwukropek cudzysłów plus dotychczasowyKod zamknij nawias okrągły średnik. Linia 65. zamknij nawias klamrowy. Linia 66. if otwórz nawias okrągły doPrzeszukania kropka lewy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 67. wypiszKod otwórz nawias okrągły doPrzeszukania kropka lewy przecinek dotychczasowyKod plus cudzysłów 0 cudzysłów zamknij nawias okrągły średnik. Linia 68. zamknij nawias klamrowy. Linia 69. if otwórz nawias okrągły doPrzeszukania kropka prawy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 70. wypiszKod otwórz nawias okrągły doPrzeszukania kropka prawy przecinek dotychczasowyKod plus cudzysłów 1 cudzysłów zamknij nawias okrągły średnik. Linia 71. zamknij nawias klamrowy. Linia 72. zamknij nawias klamrowy. Linia 74. static int obecnyElementTablicySlow znak równości 0 średnik. Linia 76. private static Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy zapiszKod otwórz nawias okrągły Wierzcholek doPrzeszukania przecinek String dotychczasowyKod przecinek Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy listaSlow zamknij nawias okrągły otwórz nawias klamrowy. Linia 77. if otwórz nawias okrągły doPrzeszukania kropka lewy znak równości znak równości null ampersant ampersant doPrzeszukania kropka prawy znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 78. listaSlow otwórz nawias kwadratowy obecnyElementTablicySlow zamknij nawias kwadratowy znak równości new Slowo otwórz nawias okrągły doPrzeszukania kropka znak przecinek doPrzeszukania kropka czestosc przecinek. Linia 79. dotychczasowyKod zamknij nawias okrągły średnik. Linia 80. obecnyElementTablicySlow plus plus średnik. Linia 81. zamknij nawias klamrowy. Linia 82. if otwórz nawias okrągły doPrzeszukania kropka lewy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 83. zapiszKod otwórz nawias okrągły doPrzeszukania kropka lewy przecinek dotychczasowyKod plus cudzysłów 0 cudzysłów przecinek listaSlow zamknij nawias okrągły średnik. Linia 84. zamknij nawias klamrowy. Linia 85. if otwórz nawias okrągły doPrzeszukania kropka prawy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 86. zapiszKod otwórz nawias okrągły doPrzeszukania kropka prawy przecinek dotychczasowyKod plus cudzysłów 1 cudzysłów przecinek listaSlow zamknij nawias okrągły średnik. Linia 87. zamknij nawias klamrowy. Linia 88. return listaSlow średnik. Linia 89. zamknij nawias klamrowy. Linia 91. static String zakodujZnak otwórz nawias okrągły char znak przecinek Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazkaSlow zamknij nawias okrągły otwórz nawias klamrowy. Linia 92. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny ksiazkaSlow kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 93. if otwórz nawias okrągły ksiazkaSlow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak znak równości znak równości znak zamknij nawias okrągły. Linia 94. return ksiazkaSlow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowoKodowe średnik. Linia 95. zamknij nawias klamrowy. Linia 96. return cudzysłów cudzysłów średnik prawy ukośnik prawy ukośnik jeśli korzystamy z odpowiedniej funkcji kodowej przecinek ta instrukcja się nie wykona. Linia 97. zamknij nawias klamrowy. Linia 99. static String zakodujWiadomosc otwórz nawias okrągły String wiadomosc przecinek Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazkaSlow zamknij nawias okrągły otwórz nawias klamrowy. Linia 100. String zakodowanaWiadomosc znak równości cudzysłów cudzysłów średnik. Linia 101. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 102. zakodowanaWiadomosc plus znak równości zakodujZnak otwórz nawias okrągły wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły przecinek ksiazkaSlow zamknij nawias okrągły średnik. Linia 103. zamknij nawias klamrowy. Linia 104. return zakodowanaWiadomosc średnik. Linia 105. zamknij nawias klamrowy. Linia 107. static String odkodujWiadomosc otwórz nawias okrągły String wiadomosc przecinek Wierzcholek korzen zamknij nawias okrągły otwórz nawias klamrowy. Linia 108. Wierzcholek doPrzeszukania znak równości korzen średnik. Linia 109. String wiadomoscOdkodowana znak równości cudzysłów cudzysłów średnik. Linia 110. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 111. if otwórz nawias okrągły wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły znak równości znak równości apostrof 0 apostrof zamknij nawias okrągły. Linia 112. doPrzeszukania znak równości doPrzeszukania kropka lewy średnik. Linia 113. else. Linia 114. doPrzeszukania znak równości doPrzeszukania kropka prawy średnik. Linia 115. if otwórz nawias okrągły doPrzeszukania kropka lewy znak równości znak równości null kreska pionowa kreska pionowa doPrzeszukania kropka prawy znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 116. wiadomoscOdkodowana plus znak równości doPrzeszukania kropka znak średnik. Linia 117. doPrzeszukania znak równości korzen średnik. Linia 118. zamknij nawias klamrowy. Linia 119. zamknij nawias klamrowy. Linia 120. return wiadomoscOdkodowana średnik. Linia 121. zamknij nawias klamrowy. Linia 123. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 124. String wiadomosc znak równości cudzysłów AABBCCDDDDDDDFFFEEER cudzysłów średnik. Linia 125. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca znak równości zlicz otwórz nawias okrągły wiadomosc zamknij nawias okrągły średnik. Linia 126. char minZnak znak równości Character kropka MAX podkreślnik VALUE średnik. Linia 127. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 128. if otwórz nawias okrągły minZnak zamknij nawias ostrokątny wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły. Linia 129. minZnak znak równości wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 130. zamknij nawias klamrowy. Linia 131. Wierzcholek otwórz nawias kwadratowy zamknij nawias kwadratowy listaWierzcholkow znak równości new Wierzcholek otwórz nawias kwadratowy tabZliczajaca kropka length zamknij nawias kwadratowy średnik. Linia 132. int dlugoscListy znak równości 0 średnik. Linia 133. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny listaWierzcholkow kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 134. if otwórz nawias okrągły tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 135. listaWierzcholkow otwórz nawias kwadratowy dlugoscListy zamknij nawias kwadratowy znak równości new Wierzcholek otwórz nawias okrągły otwórz nawias okrągły char zamknij nawias okrągły otwórz nawias okrągły i plus minZnak zamknij nawias okrągły przecinek tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek null przecinek null zamknij nawias okrągły średnik. Linia 136. dlugoscListy plus plus średnik. Linia 137. zamknij nawias klamrowy. Linia 138. zamknij nawias klamrowy. Linia 139. Wierzcholek korzen znak równości sortowanie otwórz nawias okrągły listaWierzcholkow przecinek dlugoscListy zamknij nawias okrągły średnik. Linia 140. prawy ukośnik prawy ukośnik w przypadku przecinek gdy w tekście znajduje się tylko jeden unikalny znak przecinek musimy. Linia 141. prawy ukośnik prawy ukośnik obsłużyć ten wyjątek przecinek ponieważ drzewo się nie zbuduje. Linia 142. if otwórz nawias okrągły dlugoscListy znak równości znak równości 1 zamknij nawias okrągły. Linia 143. korzen znak równości new Wierzcholek otwórz nawias okrągły apostrof lewy ukośnik 0 apostrof przecinek 1 przecinek null przecinek listaWierzcholkow otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 144. Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazkaSlow znak równości new Slowo otwórz nawias kwadratowy dlugoscListy zamknij nawias kwadratowy średnik. Linia 145. wypiszKod otwórz nawias okrągły korzen przecinek cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 146. ksiazkaSlow znak równości zapiszKod otwórz nawias okrągły korzen przecinek cudzysłów cudzysłów przecinek ksiazkaSlow zamknij nawias okrągły średnik. Linia 147. String wiadomoscZakodowana znak równości zakodujWiadomosc otwórz nawias okrągły wiadomosc przecinek ksiazkaSlow zamknij nawias okrągły średnik. Linia 148. String wiadomoscOdkodowana znak równości odkodujWiadomosc otwórz nawias okrągły wiadomoscZakodowana przecinek korzen zamknij nawias okrągły średnik. Linia 149. System kropka out kropka println otwórz nawias okrągły cudzysłów Wiadomosc do zakodowania dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 150. System kropka out kropka println otwórz nawias okrągły wiadomosc zamknij nawias okrągły średnik. Linia 151. System kropka out kropka println otwórz nawias okrągły cudzysłów Wiadomosc zakodowana dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 152. System kropka out kropka println otwórz nawias okrągły wiadomoscZakodowana zamknij nawias okrągły średnik. Linia 153. System kropka out kropka println otwórz nawias okrągły cudzysłów Wiadomosc odkodowana dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 154. System kropka out kropka println otwórz nawias okrągły wiadomoscOdkodowana zamknij nawias okrągły średnik. Linia 155. System kropka out kropka println otwórz nawias okrągły cudzysłów Oryginalna wiadomosc zajmuje w pamięci dwukropek cudzysłów plus wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły asterysk 2. Linia 156. plus cudzysłów bajtow przecinek a po zakodowaniu zajmowalaby jedynie dwukropek cudzysłów plus wiadomoscZakodowana kropka length otwórz nawias okrągły zamknij nawias okrągły plus cudzysłów bitow przecinek czyli cudzysłów. Linia 157. plus otwórz nawias okrągły wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły plus otwórz nawias okrągły wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły procent 8 zamknij nawias ostrokątny 0 znak zapytania 0 dwukropek 1 zamknij nawias okrągły zamknij nawias okrągły plus cudzysłów bajtow po zaokragleniu w gore kropka cudzysłów zamknij nawias okrągły średnik. Linia 158. zamknij nawias klamrowy. Linia 159. zamknij nawias klamrowy. Linia 161. class Wierzcholek otwórz nawias klamrowy. Linia 162. char znak średnik. Linia 163. int czestosc średnik. Linia 164. Wierzcholek lewy znak równości null średnik. Linia 165. Wierzcholek prawy znak równości null średnik. Linia 167. Wierzcholek otwórz nawias okrągły char znak przecinek int czestosc przecinek Wierzcholek lewy przecinek Wierzcholek prawy zamknij nawias okrągły otwórz nawias klamrowy. Linia 168. this kropka znak znak równości znak średnik. Linia 169. this kropka czestosc znak równości czestosc średnik. Linia 170. this kropka lewy znak równości lewy średnik. Linia 171. this kropka prawy znak równości prawy średnik. Linia 172. zamknij nawias klamrowy. Linia 173. zamknij nawias klamrowy. Linia 175. class Slowo otwórz nawias klamrowy. Linia 176. char znak średnik. Linia 177. int czestosc średnik. Linia 178. String slowoKodowe średnik. Linia 180. Slowo otwórz nawias okrągły char znak przecinek int czestosc przecinek String slowoKodowe zamknij nawias okrągły otwórz nawias klamrowy. Linia 181. this kropka znak znak równości znak średnik. Linia 182. this kropka czestosc znak równości czestosc średnik. Linia 183. this kropka slowoKodowe znak równości slowoKodowe średnik. Linia 184. zamknij nawias klamrowy. Linia 185. zamknij nawias klamrowy.

public class Main {

	public static int[] zlicz(String wiadomosc) {
		int[] tabZliczajaca;
		char min = Character.MAX_VALUE;
		char max = Character.MIN_VALUE;
		for (int i = 0; i < wiadomosc.length(); i++) {
			if (min > wiadomosc.charAt(i))
				min = wiadomosc.charAt(i);
			if (max < wiadomosc.charAt(i))
				max = wiadomosc.charAt(i);
		}
		tabZliczajaca = new int[max - min + 1];
		for (int i = 0; i < wiadomosc.length(); i++) {
			tabZliczajaca[wiadomosc.charAt(i) - min]++;
		}
		return tabZliczajaca;
	}

	public static Wierzcholek sortowanie(Wierzcholek[] listaWierzcholkow, int dlugoscListy) {

		int j = dlugoscListy;
		do {
			for (int i = 0; i < j - 1; i++) {
				if (listaWierzcholkow[i].czestosc < listaWierzcholkow[i + 1].czestosc) {
					Wierzcholek temp = listaWierzcholkow[i];
					listaWierzcholkow[i] = listaWierzcholkow[i + 1];
					listaWierzcholkow[i + 1] = temp;
				}
			}
			j--;
		} while (j > 1);

		int k = dlugoscListy;
		while (k > 1) {
			// wierzchołki o najmniejszej częstości znajdują się na końcu listy
			Wierzcholek pierwszyDoUsuniecia = listaWierzcholkow[k - 1];
			Wierzcholek drugiDoUsuniecia = listaWierzcholkow[k - 2];
			Wierzcholek nowyWierzcholek = new Wierzcholek('\0',
					pierwszyDoUsuniecia.czestosc + drugiDoUsuniecia.czestosc, pierwszyDoUsuniecia, drugiDoUsuniecia);
			System.out.println("Usuwam i lacze w jeden następujace wierzcholki:");
			System.out.println("Wierzcholek o znaku: " + pierwszyDoUsuniecia.znak + " " + pierwszyDoUsuniecia.czestosc);
			System.out.println("Wierzcholek o znaku: " + drugiDoUsuniecia.znak + " " + drugiDoUsuniecia.czestosc);
			listaWierzcholkow[k - 2] = nowyWierzcholek;
			listaWierzcholkow[k - 1] = null;
			k--;
			// umieść nowy wierzchołek w odpowiednim miejscu
			for (int i = k - 1; i > 0; i--) {
				if (listaWierzcholkow[i - 1] == null
						|| listaWierzcholkow[i].czestosc > listaWierzcholkow[i - 1].czestosc) {
					Wierzcholek temp = listaWierzcholkow[i];
					listaWierzcholkow[i] = listaWierzcholkow[i - 1];
					listaWierzcholkow[i - 1] = temp;
				} else break;
			}
		}
		return listaWierzcholkow[0];
	}

	public static void wypiszKod(Wierzcholek doPrzeszukania, String dotychczasowyKod) {
		if (doPrzeszukania.lewy == null && doPrzeszukania.prawy == null) {
			System.out.println("Znak: " + doPrzeszukania.znak +
					" czestosc: " + doPrzeszukania.czestosc +
					" slowo kodowe: " + dotychczasowyKod);
		}
		if (doPrzeszukania.lewy != null) {
			wypiszKod(doPrzeszukania.lewy, dotychczasowyKod + "0");
		}
		if (doPrzeszukania.prawy != null) {
			wypiszKod(doPrzeszukania.prawy, dotychczasowyKod + "1");
		}
	}

	static int obecnyElementTablicySlow = 0;

	private static Slowo[] zapiszKod(Wierzcholek doPrzeszukania, String dotychczasowyKod, Slowo[] listaSlow) {
		if (doPrzeszukania.lewy == null && doPrzeszukania.prawy == null) {
			listaSlow[obecnyElementTablicySlow] = new Slowo(doPrzeszukania.znak, doPrzeszukania.czestosc,
					dotychczasowyKod);
			obecnyElementTablicySlow++;
		}
		if (doPrzeszukania.lewy != null) {
			zapiszKod(doPrzeszukania.lewy, dotychczasowyKod + "0", listaSlow);
		}
		if (doPrzeszukania.prawy != null) {
			zapiszKod(doPrzeszukania.prawy, dotychczasowyKod + "1", listaSlow);
		}
		return listaSlow;
	}

	static String zakodujZnak(char znak, Slowo[] ksiazkaSlow) {
		for (int i = 0; i < ksiazkaSlow.length; i++) {
			if (ksiazkaSlow[i].znak == znak)
				return ksiazkaSlow[i].slowoKodowe;
		}
		return "";// jeśli korzystamy z odpowiedniej funkcji kodowej, ta instrukcja się nie wykona
	}

	static String zakodujWiadomosc(String wiadomosc, Slowo[] ksiazkaSlow) {
		String zakodowanaWiadomosc = "";
		for (int i = 0; i < wiadomosc.length(); i++) {
			zakodowanaWiadomosc += zakodujZnak(wiadomosc.charAt(i), ksiazkaSlow);
		}
		return zakodowanaWiadomosc;
	}

	static String odkodujWiadomosc(String wiadomosc, Wierzcholek korzen) {
		Wierzcholek doPrzeszukania = korzen;
		String wiadomoscOdkodowana = "";
		for (int i = 0; i < wiadomosc.length(); i++) {
			if (wiadomosc.charAt(i) == '0')
				doPrzeszukania = doPrzeszukania.lewy;
			else
				doPrzeszukania = doPrzeszukania.prawy;
			if (doPrzeszukania.lewy == null || doPrzeszukania.prawy == null) {
				wiadomoscOdkodowana += doPrzeszukania.znak;
				doPrzeszukania = korzen;
			}
		}
		return wiadomoscOdkodowana;
	}

	public static void main(String[] args) {
		String wiadomosc = "AABBCCDDDDDDDFFFEEER";
		int[] tabZliczajaca = zlicz(wiadomosc);
		char minZnak = Character.MAX_VALUE;
		for (int i = 0; i < wiadomosc.length(); i++) {
			if (minZnak > wiadomosc.charAt(i))
				minZnak = wiadomosc.charAt(i);
		}
		Wierzcholek[] listaWierzcholkow = new Wierzcholek[tabZliczajaca.length];
		int dlugoscListy = 0;
		for (int i = 0; i < listaWierzcholkow.length; i++) {
			if (tabZliczajaca[i] != 0) {
				listaWierzcholkow[dlugoscListy] = new Wierzcholek((char) (i + minZnak), tabZliczajaca[i], null, null);
				dlugoscListy++;
			}
		}
		Wierzcholek korzen = sortowanie(listaWierzcholkow, dlugoscListy);
		// w przypadku, gdy w tekście znajduje się tylko jeden unikalny znak, musimy
		// obsłużyć ten wyjątek, ponieważ drzewo się nie zbuduje
		if (dlugoscListy == 1)
			korzen = new Wierzcholek('\0', 1, null, listaWierzcholkow[0]);
		Slowo[] ksiazkaSlow = new Slowo[dlugoscListy];
		wypiszKod(korzen, "");
		ksiazkaSlow = zapiszKod(korzen, "", ksiazkaSlow);
		String wiadomoscZakodowana = zakodujWiadomosc(wiadomosc, ksiazkaSlow);
		String wiadomoscOdkodowana = odkodujWiadomosc(wiadomoscZakodowana, korzen);
		System.out.println("Wiadomosc do zakodowania: ");
		System.out.println(wiadomosc);
		System.out.println("Wiadomosc zakodowana: ");
		System.out.println(wiadomoscZakodowana);
		System.out.println("Wiadomosc odkodowana: ");
		System.out.println(wiadomoscOdkodowana);
		System.out.println("Oryginalna wiadomosc zajmuje w pamięci: " + wiadomosc.length() * 2
				+ " bajtow, a po zakodowaniu zajmowalaby jedynie: " + wiadomoscZakodowana.length() + " bitow, czyli "
				+ (wiadomosc.length() + (wiadomosc.length() % 8 > 0 ? 0 : 1)) + " bajtow po zaokragleniu w gore.");
	}
}

class Wierzcholek {
	char znak;
	int czestosc;
	Wierzcholek lewy = null;
	Wierzcholek prawy = null;

	Wierzcholek(char znak, int czestosc, Wierzcholek lewy, Wierzcholek prawy) {
		this.znak = znak;
		this.czestosc = czestosc;
		this.lewy = lewy;
		this.prawy = prawy;
	}
}

class Slowo {
	char znak;
	int czestosc;
	String slowoKodowe;

	Slowo(char znak, int czestosc, String slowoKodowe) {
		this.znak = znak;
		this.czestosc = czestosc;
		this.slowoKodowe = slowoKodowe;
	}
}

Program podaje na wyjście następujące wiadomości:

Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku: R 1
Wierzcholek o znaku: C 2
Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku: B 2
Wierzcholek o znaku: A 2
Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku:  3
Wierzcholek o znaku: F 3
Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku: E 3
Wierzcholek o znaku:  4
Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku:  6
Wierzcholek o znaku:  7
Usuwam i lacze w jeden następujace wierzcholki:
Wierzcholek o znaku: D 7
Wierzcholek o znaku:  13
Znak: D czestosc: 7 slowo kodowe: 0
Znak: R czestosc: 1 slowo kodowe: 1000
Znak: C czestosc: 2 slowo kodowe: 1001
Znak: F czestosc: 3 slowo kodowe: 101
Znak: E czestosc: 3 slowo kodowe: 110
Znak: B czestosc: 2 slowo kodowe: 1110
Znak: A czestosc: 2 slowo kodowe: 1111
Wiadomosc do zakodowania:
AABBCCDDDDDDDFFFEEER
Wiadomosc zakodowana:
11111111111011101001100100000001011011011101101101000
Wiadomosc odkodowana:
AABBCCDDDDDDDFFFEEER
Oryginalna wiadomosc zajmuje w pamięci: 40 bajtow, a po zakodowaniu zajmowalaby jedynie: 53 bitow, czyli 20 bajtow po zaokragleniu w gore.

Już wiesz

Podsumujmy najważniejsze informacje:

algorytm Huffmana generuje kod zero‑jedynkowy;
kod każdego znaku nie jest początkowym fragmentem kodu innego znaku;
generowany kod jest tzw. kodem prefiksowym (żaden kod nie jest prefiksem innej litery), który pozwala na jednoznaczne dekodowanie zapisanego znaku;
kod jest tworzony w taki sposób, aby średnia długość kodu znaku była najkrótsza.

Słownik

bezstratna kompresja danych

metoda zmniejszania objętości danych, w której informacja po skompresowaniu jest dekompresowalna do postaci początkowej

drzewo binarne

rodzaj drzewa (struktury danych), w którym każdy wierzchołek ma tylko dwóch potomków (lewego i prawego) oraz tylko jeden początek, czyli korzeń; wierzchołki bez potomków określane są jako liście

książka kodowa

zbiór słów kodowych, który służy do kodowania wiadomości; może służyć również do dekodowania, jednak w algorytmie Huffmana unika się tego, gdyż jest to nieefektywne

stratna kompresja danych

metoda zmniejszania objętości danych, w wyniku której traci się część informacji (dane po zdekompresowaniu nie mają takiej samej postaci, mogą być zniekształcone)

Wprowadzenie

Symulacja interaktywna

Implementacja w języku Java

Słownik