W informatyce każdą informację możemy przedstawić na wiele sposobów. Przykładem może być prosta konwersja z typu całkowitego int na typ tekstowy string. Zabieg taki jest czasem wymagany, aby mieć łatwiejszą kontrolę nad programem lub, po prostu, aby wyświetlić użytkownikowi dane w odpowiedniej formie. Zamiana sposobu zapisu informacji jest również powszechnie wykorzystywana w procesie kompresji danych. Dzisiaj omówimy więc wspólnie jeden z ważniejszych algorytmów kompresji bezstratnej, jakim jest kodowanie Hoffmana.
Czym jest kompresja danych?
Krótko mówiąc kompresja danych ma na celu zminimalizowanie redundancji i tym samym zmniejszenie rozmiaru pliku.
Za przykład weźmy 12-elementowy zbiór. Łatwo zauważyć, że składa się on z 3 rodzajów figur geometrycznych. Z pozoru może wydawać się mało rozbudowany, jednak gdyby go powtórzyć 1000-krotnie mielibyśmy już 12000 elementów. Taką ilość elementów ciężej już sobie wyobrazić. Co można zrobić, by uprościć przedstawienie zbioru? Zamiast wypisywać tą samą figurę wielokrotnie pod rząd, wystarczy zapisać ją raz i dopisać ilość jej wystąpień. Powyższy zbiór możemy więc uprościć do:
W ten sposób zredukowaliśmy ilość elementów do sześciu i mimo, że nadal trudno by było sobie wyobrazić sześciotysięczny ciąg elementów, to jednak byłoby ich dwukrotnie mniej, niż przed "kompresją". Podsumowując kompresją możemy nazwać proces, którego celem jest zredukowanie wielkości zbioru danych, poprzez zastępowanie powtarzających się ciągów prostszymi symbolami.
Algorytmy kompresji danych możemy podzielić na stratne i bezstratne. Kompresja bezstratna oznacza, że po dekompresji (procesie odwrotnym do kompresji) stan pliku będzie identyczny, jak przed kompresją. Stosowana jest np. w formatach GIF, PNG, czy wszędzie tam, gdzie ważne jest, aby każdy szczegół pliku był zachowany. Kodowanie Hoffmana, o którym będziemy dzisiaj mówić, jest przykładem kompresji bezstratnej.
Kompresja stratna oznacza, że po kompresji pewne szczegóły pliku są nieodwracalnie tracone i po dekompresji zostaną one pominięte. Kompresję stratną spotyka się np. w plikach JPEG, MP3, czy MPEG.
Kodowanie Huffmana - zasada działania
Kodowanie Huffmana polega na zastępowaniu złożonych partii danych pojedynczymi, prostymi kodami (ciągami bitów). W efekcie dane wyjściowe są znacznie krótsze od wejściowych.
By zrozumieć istotę kodowania Huffmana, przejdźmy do przykładu. Weźmy ciąg znaków "programowanie". Jak pewnie dobrze wiecie, w klasycznym kodowaniu ASCII każdy znak reprezentowany jest przez jeden bajt danych, czyli 8 bitów. Za pomocą ośmiu bitów można zapisać 256 znaków. W powyższym słowie zapisanym w formacie ASCII nie wykorzystaliśmy jednak ich wszystkich, a mimo to zajęliśmy łącznie 13 bajtów. Nie potrzebujemy więc aż 256 znaków. Nasz ciąg składa się z liter z podanego zbioru : {p, r, o, g, a, m, w, n, i, e}. Wykorzystujemy więc jedynie 10 znaków z 256. Oznacza to, że na pojedynczy znak wystarczą nam 4 bity (24 = 16 > 10), zamiast ośmiu. Zauważ jednak, że im więcej liter wykorzystamy w tekście, tym mniej efektywny będzie ten algorytm. Gdyby wykorzystać w pliku wszystkie 256 znaków, to jego działanie nie miałoby żadnego efektu.
Kodowanie Huffmana - algorytm
Jak działa kodowanie Huffmana? W przypadku zbiorów znaków w pierwszej kolejności sprawdzana jest ilość wystąpień każdej litery ze zbioru, a następnie przypisywane jest im odpowiednia wartość. Znaki występujące najczęściej dostają najkrótsze kody, zaś te występujące rzadziej - dłuższe. W tym celu wykorzystuje się drzewo binarne, w które wpisywane są znaki i ich częstotliwości wystąpień. Jeżeli nie wiesz czym jest drzewo binarne, to odsyłam Cię do tego wpisu.
Działanie algorytmu możemy rozpisać następująco:
- Pobierz tekst od użytkownika;
- Zlicz ilość wystąpień dla każdego znaku;
- Dla każdego znaku utwórz liście drzewa binarnego; wartością liścia jest ilość wystąpień dla danego znaku
- Wybierz dwa liście o najmniejszych wartościach
- Utwórz nowy liść, który będzie kontenerem dla wybranych liści; jego wartość jest sumą ich wartości; mniejszy element będzie dzieckiem po lewo, większy dzieckiem po prawo
- Powtarzaj kroki 4-5, aż nie pozostanie jeden element - korzeń drzewa.
Na poniższej animacji prześledzisz działanie kodowania Huffmana, dla słowa "banany":
Kodowanie Huffmana - implementacja C++ Java Python
Mając schemat działania pozostało nam już tylko wcielić go w życie :) Zanim przejdziemy do faktycznego kodowania, musimy najpierw przygotować sobie odpowiednie obiekty i funkcje.
Na początek utwórzmy obiekt liścia - będzie on budulcem naszego drzewa. Musimy w nim zawrzeć jego wartość, wskaźniki na potomne liście oraz znak jaki reprezentuje. Dobrze jest również stworzyć przyjmujący wszystkie te wartości jako argumenty. Dzięki temu zaoszczędzimy sobie nieco wysiłku. Proponuję również dodać metodę typu logicznego, która zwróci, czy dany liść nie jest kontenerem dla innych liści.
C++
//Tworzymy strukturę liścia, który będzie podstawowym budulcem drzewa kodowania.
//Definiujemy w niej wskaźniki na lewe dziecko i prawe dziecko,
//jej wartość(ilość wystąpień/ich sumę), znak do kodowania, a także zakodowany znak.
struct Node{
Node *left;
Node *right;
char character;
int value;
Node(char c, int v, Node* l=nullptr, Node* r=nullptr){ //tworzymy konstruktor struktury
left = l;
right = r;
character = c;
value = v;
}
~Node(){ //pamiętajmy, że zawsze powinno się wyczyścić wszelkie zmienne
delete right; //dlatego zwalniamy pamięc zajętą przez dwójkę dzieci
delete left; //z racji, iż jest to ten sam destruktor, funkcja ta wywoła się również u usuniętych dzieci
}
bool isLeaf(){
return character != '\0'; //tworzymy funkcję pomocniczą, która wskażę, czy jest to liść zawierający jakiś znak
}
};Java
class Node { //tworzymy pomocniczą klasę, która przyda nam się przy tworzeniu drzewa binarnego
private int value; //przechowywana wartość
private Character character = null; //przechowywany znak
public Node left = null; //lewe dziecko danego liścia
public Node right = null; //prawe dziecko danego liścia
public Node(char letter, int val) { //tworzymy konstruktor liścia dla znaków
value = val;
character = letter;
}
public Node(int val) { //tworzymy konstruktor dla liści będących sumą dzieci
value = val;
}
public int getValue() { //funkcja zwracająca wartość liścia
return value;
}
public Character getCharacter() {//funkcja zwracająca znak liścia
return character;
}
public boolean isLeaf() { //funkcja zwracająca, czy liść nie jest kontenerem
return character != null;
}
}Python
class Node:
value = 0
right = None
left = None
character = ""
def isLeaf(self): #pomocnicza metoda, która pozwoli określić, czy liść przechowuje znak
return self.character != ""
def __init__(self, val, ch): #definiujemy konstruktor
self.value = val
self.character = chGdy mamy już obiekt-liść, to musimy stworzyć kolejny obiekt, który będzie efektywnie te liście porównywać. Obiekt ten będzie miał znaczący wpływ na strukturę drzewa:
C++
//Tworzymy strukturę, która pomoże nam przy tworzeniu drzewa kodowania.
//Będzie ona porównywać dwa liście z drzewa/
struct comparator{
bool operator() (Node *a, Node *b){
if(a->value != b->value) //jeżeli liście są różnej wartości
return a->value > b->value; //wykonaj zwykłe porównanie
if(!a->isLeaf() && b->isLeaf()) //jeżeli są równe i drugi jest kontenerem, to zawsze będzie on uznawany jako większy
return false;
if(!b->isLeaf() && a->isLeaf()) //jeżeli są równe i drugi jest kontenerem, to zawsze będzie on uznawany jako większy
return true;
if(a->isLeaf() && b->isLeaf()) //jeżeli oba są liściami
return a->character > b->character; //to decyduje kolejność alfabetyczna
return true; // jeżeli żaden z powyższych warunków nie zostanie spełniony, zwracamy true
}
};Java
class NodeComparator implements Comparator < Node > { //tworzymy pomocniczą klasę, która przyda się przy porównywaniu liści drzewa; korzystamy z interfejsu Comparator
@Override
public int compare(Node n1, Node n2) {
if(n1.getValue() != n2.getValue()) //jeżeli liście są różnej wartości
return n1.getValue() - n2.getValue(); //wykonaj zwykłe porównanie
if(n1.isLeaf() && !n2.isLeaf()) //jeżeli są równe i drugi jest kontenerem, to zawsze będzie on uznawany jako większy
return 1;
if(n2.isLeaf() && !n1.isLeaf()) //jeżeli są równe i drugi jest kontenerem, to zawsze będzie on uznawany jako większy
return -1;
if(n1.isLeaf() && n2.isLeaf()) //jeżeli oba są liściami
return n1.getCharacter() - n2.getCharacter(); //to decyduje kolejność alfabetyczna
return -1; // jeżeli żaden z powyższych warunków nie zostanie spełniony, zwracamy -1 - mniejszość
}
}Python
W Pythonie poniższą funkcję należy dodać do ciała klasy Node:
#funkcja __lt__ pomoże nam przy tworzeniu priority_queue
def __lt__(self, other):
if self.value != other.value: #wykonujemy normalne porównanie, jeżeli liście są różne;
return self.value < other.value
if not self.isLeaf() and other.isLeaf(): # w przeciwnym wypadku ważniejsze są liście mające znak
return True
if self.isLeaf() and not other.isLeaf(): # w przeciwnym wypadku ważniejsze są liście mające znak
return False
if self.isLeaf() and other.isLeaf(): #jeżeli jednak oba maja znak, to decyduje kolejność alfabetyczna
return ord(self.character[0]) < ord(other.character[0])
return TrueMając już potrzebne obiekty możemy przystąpić do tworzenia drzewa. Stworzymy więc funkcję o argumencie tekstowym, która zwróci obiekt Node będący korzeniem drzewa. Zanim jednak w ogóle zaczniemy je budować, musimy najpierw zliczyć znaki i stworzyć na ich podstawie liście drzewa. Utworzone liście dodamy do obiektu typu Priority Queue, który będzie porównywać je przy pomocy przygotowanej wyżej funkcji. Priority Queue jest obiektem o podobnej zasadzie działania, co stos, z tą róznicą, że dane nie zawsze są wrzucane na "wierzch". Zamiast tego przy dodawaniu dokonuje się porównania i na podstawie jego wyniku element jest umieszczany na odpowiedniej pozycji.
C++
//Definiujemy metodę, która stworzy drzewo kodowania Huffmana, a następnie zwróci jego korzeń
//Argumentem jest tekst, który chcemy zakodować
Node * createHuffmanTree(string line){
map<char, int> counter; //korzystamy z obiektu map, aby zliczyć wystąpienia dla każdego znaku
for(char c : line){
if(counter.find(c) == counter.end()){ //jeżeli znaku nie ma w mapie
counter[c] = 1; //dodajemy go
}
else{
counter[c]++; //jeżeli jest, zwiększamy jego ilość wystąpień
}
}
//Tworzymy obiekt priority_queue, który będzie przechowywać nieprzypisane elementy drzewa.
//Obiekt priority_queue pozwoli nam stworzyć uporządkowaną listę liści drzewa - najmniejsze będą najwyżej.
//Do porównywania elementów wykorzystujemy wcześniej zdefiniowaną strukturę comparator.
priority_queue<Node*, vector<Node*>, comparator> nodes;
for(auto entry : counter){
nodes.push(new Node(entry.first, entry.second)); //tworzymy liście drzewa, bazując na znakach i ich ilości wystąpień
}
}Java
private static Node createHuffmanTree(String line) {
HashMap < Character, Integer > occurences = new HashMap < Character, Integer > (); //tworzymy mapę, która przechowa ilość wystąpień dla każdego znaku
for (char c: line.toCharArray()) { //następnie zliczamy je w pętli
if (occurences.containsKey(c)) {
occurences.put(c, occurences.get(c) + 1);
} else {
occurences.put(c, 1);
}
}
NodeComparator nc = new NodeComparator(); //tworzymy instancję pomocniczej klasy
PriorityQueue < Node > nodes = new PriorityQueue < Node > (occurences.size(), nc); //korzystamy z PriorityQueue - w uproszczeniu jest to lista, która zadba, aby nasze elementy były zawsze posortowane; korzysta ona z naszego Comparatora
for (Entry < Character, Integer > entry: occurences.entrySet()) { //zamieniamy znaki i ich ilość wystąpień na liście, a następnie dodajemy je do utworzonej listy
Node n = new Node(entry.getKey(), entry.getValue());
nodes.add(n);
}
}Python
#Definiujemy metodę, która stworzy drzewo kodowania Huffmana, a następnie zwróci jego korzeń
#Argumentem jest tekst, który chcemy zakodować
def createTree(text):
occurences = {}
for c in text: #zliczamy wystąpienia każdego znaku w tekście
if occurences.__contains__(c):
occurences[c] += 1
else:
occurences[c] = 1
# Tworzymy obiekt PriorityQueue(), który będzie przechowywać nieprzypisane elementy drzewa.
# Obiekt priority_queue pozwoli nam stworzyć uporządkowaną listę liści drzewa - najmniejsze będą najwyżej.
nodes = PriorityQueue()
for c in occurences.keys(): #tworzymy liście drzewa, bazując na znakach i ich ilości wystąpień, a następnei dodajmy do listy
node = Node(occurences[c], c)
nodes.put(node)Następnie łączymy dwa liście o najmniejszej wartości, tworząc tym samym liść-kontener, którego wartością będzie suma wartości tych dwóch liści. Następnie dodajemy go do listy pozostałych liści. Kroki te powtarzamy, aż na liście nie zostanie jeden element - korzeń naszego drzewa. Wtedy to możemy zwrócić go jako wynik naszej funkcji - drzewo jest już wtedy zbudowane.
C++
//Definiujemy metodę, która stworzy drzewo kodowania Huffmana, a następnie zwróci jego korzeń
//Argumentem jest tekst, który chcemy zakodować
Node * createHuffmanTree(string line){
map<char, int> counter; //korzystamy z obiektu map, aby zliczyć wystąpienia dla każdego znaku
for(char c : line){
if(counter.find(c) == counter.end()){ //jeżeli znaku nie ma w mapie
counter[c] = 1; //dodajemy go
}
else{
counter[c]++; //jeżeli jest, zwiększamy jego ilość wystąpień
}
}
//Tworzymy obiekt priority_queue, który będzie przechowywać nieprzypisane elementy drzewa.
//Obiekt priority_queue pozwoli nam stworzyć uporządkowaną listę liści drzewa - najmniejsze będą najwyżej.
//Do porównywania elementów wykorzystujemy wcześniej zdefiniowaną strukturę comparator.
priority_queue<Node*, vector<Node*>, comparator> nodes;
for(auto entry : counter){
nodes.push(new Node(entry.first, entry.second)); //tworzymy liście drzewa, bazując na znakach i ich ilości wystąpień
}
Node *root; //definiujemy zmienną, która docelowo będzie korzeniem naszego drzewa
while(nodes.size() > 1){ //następnie iterujemy, dopóki w nodes nie zostanie ostatni element - korzeń drzewa
Node *n1 = nodes.top(); //pobieramy pierwszy, najmniejszy element z priority queue
nodes.pop(); //a następnie go usuwamy
Node *n2 = nodes.top(); //ponawiamy powyższe kroki, aby uzyskać drugi, najmniejszy element
nodes.pop();
if(n1->value == n2->value && !n1->isLeaf()){ //jeżeli oba liście mają tą samą wartość, a jeden z nich jest kontenerem, to powinien on być traktowany jako większy element
Node *pom = n1; //dlatego w takiej sytuacji podmieniamy wskaźniki
n1 = n2;
n2 = pom;
}
root = new Node('\0', n1->value + n2->value, n1, n2); //tworzymy liść-kontener, który będzie przechowywać dwa powyższe elementy i sumę ich wartości
nodes.push(root); //a następnie dodajemy go do priority queue
}
return root; //gdy w priority queue zostanie tylko jeden wyraz, to oznacza, że drzewo zostało zbudowane, a wyraz ten jest jego korzeniem; zwracamy go
}Java
private static Node createHuffmanTree(String line) {
HashMap < Character, Integer > occurences = new HashMap < Character, Integer > (); //tworzymy mapę, która przechowa ilość wystąpień dla każdego znaku
for (char c: line.toCharArray()) { //następnie zliczamy je w pętli
if (occurences.containsKey(c)) {
occurences.put(c, occurences.get(c) + 1);
} else {
occurences.put(c, 1);
}
}
NodeComparator nc = new NodeComparator(); //tworzymy instancję pomocniczej klasy
PriorityQueue < Node > nodes = new PriorityQueue < Node > (occurences.size(), nc); //korzystamy z PriorityQueue - w uproszczeniu jest to lista, która zadba, aby nasze elementy były zawsze posortowane; korzysta ona z naszego Comparatora
for (Entry < Character, Integer > entry: occurences.entrySet()) { //zamieniamy znaki i ich ilość wystąpień na liście, a następnie dodajemy je do utworzonej listy
Node n = new Node(entry.getKey(), entry.getValue());
nodes.add(n);
}
Node rootNode = null; //zmienna pomocnicza przechowująca korzeń drzewa - finalnie ma być on liściem przechowującym wartość równą długości wpisanego wyrazu
while (nodes.size() > 1) { //dopóki na liście nie pozostał jeden element(korzeń)
Node n1 = nodes.peek(); //pobieramy najmniejszy element z listy
nodes.poll(); //a następnie go usuwamy
Node n2 = nodes.peek(); //ponownie pobieramy najmniejszy element z listy
nodes.poll(); //i ponownie go usuwamy; w ten sposób pobraliśmy dwa najmniejsze elementy z listy
Node parent = new Node(n1.getValue() + n2.getValue()); //tworzymy liść, który będzie przechowywał powyższe elementy
if(n1.getValue() == n2.getValue() && !n1.isLeaf()) { /jeżeli oba liście mają tą samą wartość, a jeden z nich jest kontenerem, to powinien on być traktowany jako większy element
Node pom = n1; //dlatego w takiej sytuacji podmieniamy wartości
n1 = n2;
n2 = pom;
}
rootNode = parent; // ustawiamy go tymczasowo jako korzeń
parent.left = n1; // mniejszy element ustawamy jako jego lewe dziecko
parent.right = n2;// większy jako jego prawe dziecko
nodes.add(parent); //następnie dodajemy rodzica jako samodzielny element do listy
}
return rootNode;
}Python
#Definiujemy metodę, która stworzy drzewo kodowania Huffmana, a następnie zwróci jego korzeń
#Argumentem jest tekst, który chcemy zakodować
def createTree(text):
occurences = {}
for c in text: #zliczamy wystąpienia każdego znaku w tekście
if occurences.__contains__(c):
occurences[c] += 1
else:
occurences[c] = 1
# Tworzymy obiekt PriorityQueue(), który będzie przechowywać nieprzypisane elementy drzewa.
# Obiekt priority_queue pozwoli nam stworzyć uporządkowaną listę liści drzewa - najmniejsze będą najwyżej.
nodes = PriorityQueue()
for c in occurences.keys(): #tworzymy liście drzewa, bazując na znakach i ich ilości wystąpień, a następnei dodajmy do listy
node = Node(occurences[c], c)
nodes.put(node)
rootNode = None #tworzymy zmienna przechowujaca docelowo korzen drzewa
while nodes.qsize() > 1: #następnie iterujemy, dopóki w nodes nie zostanie ostatni element - korzeń drzewa
n1 = nodes.get() #pobieramy pierwszy, najmniejszy element z PriorityQueue
n2 = nodes.get() #pobieramy kolejny, najmniejszy element z PriorityQueue
#jeżeli oba liście mają tą samą wartość, a jeden z nich jest kontenerem, to powinien on być traktowany jako większy element
if n1.value == n2.value and not n1.isLeaf():
pom = n1 #dlatego w takiej sytuacji podmieniamy wskaźniki
n1 = n2
n2 = pom
parent = Node(n1.value + n2.value, "") #tworzymy liść-kontener, który będzie przechowywać dwa powyższe elementy i sumę ich wartości
rootNode = parent #ustawiamy go na aktualny korzen
parent.left = n1 #i dodajemy mu dzieci
parent.right = n2
nodes.put(parent) #a następnie dodajemy go do PriorityQueue
return rootNode #nasze drzewo jest gotowe - zwracamy korzeńMamy już utworzone nasze drzewo. Możemy teraz zakodować jego wartości i stworzyć tablicę kodowania. W tym celu stworzymy funkcję rekurencyjną, która wykona się dla wszystkich elementów po lewo i po prawo dla każdego elementu. Jeżeli natrafimy na koniec drzewa, przerywamy rekurencję. Jeżeli temat rekurencji nie jest Ci do końca znany, rzuć okiem na wpis, w którym go wytłumaczyliśmy.
C++
//Tworzymy rekurencyjną funkcję, która zakoduje elementy zależnie od ich pozycji w drzewie.
//Jako argumenty podajemy korzeń drzewa, tekst pomocniczy przy rekurencji, a także mapę kodowania
void encodeNodes(Node *node, string val, map<char, string> *map) {
if(node == nullptr){ //warunek STOP funkcji rekurencyjnej:
return; //jeżeli trafimy na koniec drzewa, przerywamy działanie
}
if(node->isLeaf()){ //jeżeli jest to liść przechowujący znak
cout << node->character << " : " + val << endl; //to drukujemy go i jego zakodowaną wartość
map->insert({node->character, val}); //a następnie dodajemy obie wartości do mapy
}
encodeNodes(node->left, val + '0', map); //wywołujemy jeszcze raz funkcję dla lewej strony drzewa - rekurencja
encodeNodes(node->right, val + '1', map); //wywołujemy jeszcze raz funkcję dla prawej strony drzewa - rekurencja
}Java
private static void encodeValues(Node node, String txt, HashMap < Character, String > encodedValues) { //tworzymy rekurencyjną funkcję, która nada liścią odpowiednie wartości
if (node == null) {
return;
}
if (node.getCharacter() != null) { //jeżeli liść posiada swój znak
System.out.println(node.getCharacter() + ":" + txt);
encodedValues.put(node.getCharacter(), txt); //dodajemy jego zakodowaną wartość do tablicy
}
encodeValues(node.left, txt + "0", encodedValues); //wywołujemy funkcję rekurencyjnie
encodeValues(node.right,txt + "1", encodedValues); //dla obu dzieci; w ten sposób całemu drzewu zostanie przypisana wartość
}Python
#tworzymy funkcję, która zakoduje drzewo
#jednocześnie zakoduje ona podany przez użytkownika tekst
def encodeValues(n, str, txt):
if n is None: #jeżeli trafimy na koniec drzewa
return txt #przerywamy rekurencję
if n.isLeaf(): #jeżeli przechowuje on znak
print(n.character + " : " + str) #to drukujemy go wraz z zakodowaną wartością
txt = txt.replace(n.character, str) #a następnie podmieniamy znak w tekście z zakodowaną wartościa
txt = encodeValues(n.left, str + "0", txt) #wykonujemy te same działania dla lewej części drzewa - rekurencja
txt = encodeValues(n.right, str + "1", txt) #wykonujemy te same działania dla prawej części drzewa - rekurencja
return txt #na koniec zwracamy zakodowany tekstNa sam koniec pozostało nam już tylko zakodowanie tekstu, przy użyciu utworzonej tablicy kodowania:
C++
int main(){
//pobieramy najpierw tekst od użytkownika
cout << "Kodowanie Huffmana. Podaj tekst, który chcesz zakodować:" << endl;
string line;
getline(cin, line);
//tworzymy drzewo bazując na tekście
Node *root = createHuffmanTree(line);
//kodujemy wartości w drzewie, drukujemy je i dodajemy do nowej mapy, która powiąże znaki z ich zakodowanymi wartościami
cout<< "Oto tablica kodowania Huffmana:" << endl;
map<char, string> encodedValues;
encodeNodes(root, "", &encodedValues);
//kodujemy tekst, bazując na utworzonej mapie kodowania
string encodedLine = "";
for(char c : line){
encodedLine += encodedValues[c];
}
cout << "Oto twoj tekst po zakodowaniu: " << encodedLine << endl;
}Java
public static void main(String[] args) {
System.out.println("Kodowanie Huffmana. Podaj tekst, który chcesz zakodować:");
Scanner sc = new Scanner(System.in);
String line = sc.nextLine(); //pobieramy wiersz od użytkownika
sc.close(); //pamiętając o zwalnianiu zasobów
Node rootNode = createHuffmanTree(line);
HashMap < Character, String > encodedValues = new HashMap < Character, String > (); //inicjalizujemy mapę, która przechowa tablicę kodowania
System.out.println("Oto tablica kodowania:");
encodeValues(rootNode, "", encodedValues); //przypisujemy odpowiednie wartości gałęziom i liściom
String output = "";
for (char c: line.toCharArray()) {
output += encodedValues.get(c); //następnie kodujemy wyraz, korzystając z utworzonej tablicy kodowania
}
System.out.println();
System.out.println("Oto twój tekst zakodowany metodą Huffmana: " + output);
}Python
word = input("Kodowanie Huffmana. Podaj tekst, który chcesz zakodować:").rstrip()
rootNode = createTree(word)
print("Oto tablica kodowania:")
word = encodeValues(rootNode, "", word)
print ("Oto tekst po zakodowaniu: " + word)Kodowanie Huffmana - odkodowanie
Powyższa procedura kodowania jest całkowicie odwracalna, o ile nadal mamy dostęp do drzewa lub tablicy kodowania. W pierwszym przypadku procedura jest prosta. Iterujemy poprzez każdy bit w kodzie. Jeżeli natrafimy na zero, idziemy w lewą stronę drzewa, jeżeli natomiast trafimy na jeden - wybieramy prawy liść. Gdy posiada on swój znak, to wstawiamy go w zmienną pomocniczą i wracamy na początek drzewa. Jeżeli jednak jest to kontener, to idziemy dalej, dopóki nie trafimy na liść zawierający znak. Czynności te powtarzamy do samego końca zakodowanego tekstu. W ich wyniku w zmiennej pomocniczej będzie znajdować się odkodowany tekst.
C++
//Tworzymy funkcję, która odkoduje zakodowany tekst bazując na zbudowanym drzewie.
string decode(Node *root, string encoded){
string decoded = ""; //zmienna pomocnicza
Node *currentNode = root; //wskaźnik na aktualnie sprawdzany liść
for(char c : encoded){ //iterujemy poprzez zakodowany tekst
if(c == '0'){ //jeżeli iterowany znak jest zerem, to oznacza, że musimy iść w lewo
if(currentNode->left->isLeaf()){ //jeżeli dziecko po lewo jest liściem przechowującym znak
decoded += currentNode->left->character; //dodajemy ten znak do zmiennej pomocniczej
currentNode = root; //a następnie wracamy na początek drzewa
}
else{
currentNode = currentNode->left; //jeżeli trafiliśmy na kontener, ustawiamy na niego wskaźnik
}
}
else{ //jeżeli jest to inny znak (1), to przechodzimy na prawą stronę
if(currentNode->right->isLeaf()){ //jeżeli dziecko po prawo jest liściem przechowującym znak
decoded += currentNode->right->character;//dodajemy ten znak do zmiennej pomocniczej
currentNode = root;//a następnie wracamy na początek drzewa
}
else{
currentNode = currentNode->right;//jeżeli trafiliśmy na kontener, ustawiamy na niego wskaźnik
}
}
}
return decoded; //na koniec zwracamy odkodowany tekst
}Java
private static String decode(Node root, String encoded){
String decoded = ""; //zmienna pomocnicza
Node currentNode = root; //aktualnie sprawdzany liść
for(char c : encoded.toCharArray()){ //iterujemy poprzez zakodowany tekst
if(c == '0'){ //jeżeli iterowany znak jest zerem, to oznacza, że musimy iść w lewo
if(currentNode.left.isLeaf()){ //jeżeli dziecko po lewo jest liściem przechowującym znak
decoded += currentNode.left.getCharacter(); //dodajemy ten znak do zmiennej pomocniczej
currentNode = root; //a następnie wracamy na początek drzewa
}
else{
currentNode = currentNode.left; //jeżeli trafiliśmy na kontener, ustawiamy go jako aktualny
}
}
else{ //jeżeli jest to inny znak (1), to przechodzimy na prawą stronę
if(currentNode.right.isLeaf()){ //jeżeli dziecko po prawo jest liściem przechowującym znak
decoded += currentNode.right.getCharacter();//dodajemy ten znak do zmiennej pomocniczej
currentNode = root;//a następnie wracamy na początek drzewa
}
else{
currentNode = currentNode.right;//jeżeli trafiliśmy na kontener, ustawiamy go jako aktualny
}
}
}
return decoded; //na koniec zwracamy odkodowany tekst
}Python
#definiujemy funkcję, która odkoduje tekst na bazie utworzonego drzewa
def decode(root, text):
decoded = "" #zmienna pomocnicza
currNode = root #aktualnie rozważany element drzewa
for char in text: #iterujemy poprzez znaki zakodowanego tekstu
if char == '0': #jeżeli jest to 0, to oznacza, że musimy iśc na lewą stronę
if currNode.left.isLeaf(): #jeżeli element po lewo jest liściem
decoded += currNode.left.character #to dodajemy jego znak do zmiennej pomocniczej
currNode = root #a następnie wracamy na początek drzewa
else:
currNode = currNode.left #jeżeli trafiliśmy na kontener, to od niego zaczniemy nast. iterację
else: #jeżeli jest to 1, to oznacza, że musimy iśc na prawą stronę
if currNode.right.isLeaf(): #jeżeli element po prawo jest liściem
decoded += currNode.right.character #to dodajemy jego znak do zmiennej pomocniczej
currNode = root #a następnie wracamy na początek drzewa
else:
currNode = currNode.right #jeżeli trafiliśmy na kontener, to od niego zaczniemy nast. iterację
return decoded #zwracamy odkodowana wartosc
Podsumowanie
W ten oto sposób udało nam się wspólnie zaimplementować kodowanie Huffmana. Z racji na swoją niską wydajność, praktycznie wcale nie korzysta się z niego samodzielnie. Wykorzystywany jest on jednak jako ostatni etap kompresji, najczęściej w połączeniu z kilkoma innymi metodami. Niemniej jednak jest to algorytm warty poznania i zrozumienia. Kto wie, może spotkacie się z nim na maturze? Poniżej znajdziecie pełną implementację kodowania Huffmana:
C++
#include <iostream>
#include <queue>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
//Tworzymy strukturę liścia, który będzie podstawowym budulcem drzewa kodowania.
//Definiujemy w niej wskaźniki na lewe dziecko i prawe dziecko,
//jej wartość(ilość wystąpień/ich sumę), znak do kodowania, a także zakodowany znak.
struct Node{
Node *left;
Node *right;
char character;
int value;
Node(char c, int v, Node* l=nullptr, Node* r=nullptr){ //tworzymy konstruktor struktury
left = l;
right = r;
character = c;
value = v;
}
~Node(){ //pamiętajmy, że zawsze powinno się wyczyścić wszelkie zmienne
delete right; //dlatego zwalniamy pamięc zajętą przez dwójkę dzieci
delete left; //z racji, iż jest to destruktor, funkcja ta wywoła się również u usuniętych dzieci
}
bool isLeaf(){
return character != '\0'; //tworzymy funkcję pomocniczą, która wskażę, czy jest to liść zawierający jakiś znak
}
};
//Tworzymy strukturę, która pomoże nam przy tworzeniu drzewa kodowania.
//Będzie ona porównywać dwa liście z drzewa/
struct comparator{
bool operator() (Node *a, Node *b){
if(a->value != b->value) //jeżeli liście są różnej wartości
return a->value > b->value; //wykonaj zwykłe porównanie
if(!a->isLeaf() && b->isLeaf()) //jeżeli są równe i drugi jest kontenerem, to zawsze będzie on uznawany jako większy
return false;
if(!b->isLeaf() && a->isLeaf()) //jeżeli są równe i drugi jest kontenerem, to zawsze będzie on uznawany jako większy
return true;
if(a->isLeaf() && b->isLeaf()) //jeżeli oba są liściami
return a->character > b->character; //to decyduje kolejność alfabetyczna
return true; // jeżeli żaden z powyższych warunków nie zostanie spełniony, zwracamy true
}
};
//Definiujemy metodę, która stworzy drzewo kodowania Huffmana, a następnie zwróci jego korzeń
//Argumentem jest tekst, który chcemy zakodować
Node * createHuffmanTree(string line){
map<char, int> counter; //korzystamy z obiektu map, aby zliczyć wystąpienia dla każdego znaku
for(char c : line){
if(counter.find(c) == counter.end()){ //jeżeli znaku nie ma w mapie
counter[c] = 1; //dodajemy go
}
else{
counter[c]++; //jeżeli jest, zwiększamy jego ilość wystąpień
}
}
//Tworzymy obiekt priority_queue, który będzie przechowywać nieprzypisane elementy drzewa.
//Obiekt priority_queue pozwoli nam stworzyć uporządkowaną listę liści drzewa - najmniejsze będą najwyżej.
//Do porównywania elementów wykorzystujemy wcześniej zdefiniowaną strukturę comparator.
priority_queue<Node*, vector<Node*>, comparator> nodes;
for(auto entry : counter){
nodes.push(new Node(entry.first, entry.second)); //tworzymy liście drzewa, bazując na znakach i ich ilości wystąpień
}
Node *root; //definiujemy zmienną, która docelowo będzie korzeniem naszego drzewa
while(nodes.size() > 1){ //następnie iterujemy, dopóki w nodes nie zostanie ostatni element - korzeń drzewa
Node *n1 = nodes.top(); //pobieramy pierwszy, najmniejszy element z priority queue
nodes.pop(); //a następnie go usuwamy
Node *n2 = nodes.top(); //ponawiamy powyższe kroki, aby uzyskać drugi, najmniejszy element
nodes.pop();
if(n1->value == n2->value && !n1->isLeaf()){ //jeżeli oba liście mają tą samą wartość, a jeden z nich jest kontenerem, to powinien on być traktowany jako większy element
Node *pom = n1; //dlatego w takiej sytuacji podmieniamy wskaźniki
n1 = n2;
n2 = pom;
}
root = new Node('\0', n1->value + n2->value, n1, n2); //tworzymy liść-kontener, który będzie przechowywać dwa powyższe elementy i sumę ich wartości
nodes.push(root); //a następnie dodajemy go do priority queue
}
return root; //gdy w priority queue zostanie tylko jeden wyraz, to oznacza, że drzewo zostało zbudowane, a wyraz ten jest jego korzeniem; zwracamy go
}
//Tworzymy rekurencyjną funkcję, która zakoduje elementy zależnie od ich pozycji w drzewie.
//Jako argumenty podajemy korzeń drzewa, tekst pomocniczy przy rekurencji, a także mapę kodowania
void encodeNodes(Node *node, string val, map<char, string> *map) {
if(node == nullptr){ //warunek STOP funkcji rekurencyjnej:
return; //jeżeli trafimy na koniec drzewa, przerywamy działanie
}
if(node->isLeaf()){ //jeżeli jest to liść przechowujący znak
cout << node->character << " : " + val << endl; //to drukujemy go i jego zakodowaną wartość
map->insert({node->character, val}); //a następnie dodajemy obie wartości do mapy
}
encodeNodes(node->left, val + '0', map); //wywołujemy jeszcze raz funkcję dla lewej strony drzewa - rekurencja
encodeNodes(node->right, val + '1', map); //wywołujemy jeszcze raz funkcję dla prawej strony drzewa - rekurencja
}
//Tworzymy funkcję, która odkoduje zakodowany tekst bazując na zbudowanym drzewie.
string decode(Node *root, string encoded){
string decoded = ""; //zmienna pomocnicza
Node *currentNode = root; //wskaźnik na aktualnie sprawdzany liść
for(char c : encoded){ //iterujemy poprzez zakodowany tekst
if(c == '0'){ //jeżeli iterowany znak jest zerem, to oznacza, że musimy iść w lewo
if(currentNode->left->isLeaf()){ //jeżeli dziecko po lewo jest liściem przechowującym znak
decoded += currentNode->left->character; //dodajemy ten znak do zmiennej pomocniczej
currentNode = root; //a następnie wracamy na początek drzewa
}
else{
currentNode = currentNode->left; //jeżeli trafiliśmy na kontener, ustawiamy na niego wskaźnik
}
}
else{ //jeżeli jest to inny znak (1), to przechodzimy na prawą stronę
if(currentNode->right->isLeaf()){ //jeżeli dziecko po prawo jest liściem przechowującym znak
decoded += currentNode->right->character;//dodajemy ten znak do zmiennej pomocniczej
currentNode = root;//a następnie wracamy na początek drzewa
}
else{
currentNode = currentNode->right;//jeżeli trafiliśmy na kontener, ustawiamy na niego wskaźnik
}
}
}
return decoded; //na koniec zwracamy odkodowany tekst
}
int main(){
//pobieramy najpierw tekst od użytkownika
cout << "Kodowanie Huffmana. Podaj tekst, który chcesz zakodować:" << endl;
string line;
getline(cin, line);
//tworzymy drzewo bazując na tekście
Node *root = createHuffmanTree(line);
//kodujemy wartości w drzewie, drukujemy je i dodajemy do nowej mapy, która powiąże znaki z ich zakodowanymi wartościami
cout<< "Oto tablica kodowania Huffmana:" << endl;
map<char, string> encodedValues;
encodeNodes(root, "", &encodedValues);
//kodujemy tekst, bazując na utworzonej mapie kodowania
string encodedLine = "";
for(char c : line){
encodedLine += encodedValues[c];
}
cout << "Oto twoj tekst po zakodowaniu: " << encodedLine << endl;
//odkodowujemy tekst, aby sprawdzić działanie
cout << "Oto tekst po odkodowaniu: " << decode(root, encodedLine) << endl;
//sprzątamy po sobie :)
delete root;
return 0;
}Java
package matura;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;
class Node { //tworzymy kolejną, pomocniczą klasę, która przyda nam się przy tworzeniu drzewa binarnego
private int value; //przechowywana wartość
private Character character = null; //przechowywany znak
public Node left = null; //lewe dziecko danego liścia
public Node right = null; //prawe dziecko danego liścia
public Node(char letter, int val) { //tworzymy konstruktor liścia dla znaków
value = val;
character = letter;
}
public Node(int val) { //tworzymy konstruktor liścia dla liści będących sumą dzieci
value = val;
}
public int getValue() { //funkcja zwracająca wartość liścia
return value;
}
public Character getCharacter() {//funkcja zwracająca znak liścia
return character;
}
public boolean isLeaf() {
return character != null;
}
}
class NodeComparator implements Comparator < Node > { //tworzymy pomocniczą klasę, która przyda się przy porównywaniu liści drzewa; korzystamy z interfejsu Comparator
@Override
public int compare(Node n1, Node n2) {
if(n1.getValue() != n2.getValue()) //jeżeli liście są różnej wartości
return n1.getValue() - n2.getValue(); //wykonaj zwykłe porównanie
if(n1.isLeaf() && !n2.isLeaf()) //jeżeli są równe i drugi jest kontenerem, to zawsze będzie on uznawany jako większy
return 1;
if(n2.isLeaf() && !n1.isLeaf()) //jeżeli są równe i drugi jest kontenerem, to zawsze będzie on uznawany jako większy
return -1;
if(n1.isLeaf() && n2.isLeaf()) //jeżeli oba są liściami
return n1.getCharacter() - n2.getCharacter(); //to decyduje kolejność alfabetyczna
return -1; // jeżeli żaden z powyższych warunków nie zostanie spełniony, zwracamy -1 - mniejszość
}
}
public class Kodowanie_Huffman {
private static Node createHuffmanTree(String line) {
HashMap < Character, Integer > occurences = new HashMap < Character, Integer > (); //tworzymy mapę, która przechowa ilość wystąpień dla każdego znaku
for (char c: line.toCharArray()) { //następnie zliczamy je w pętli
if (occurences.containsKey(c)) {
occurences.put(c, occurences.get(c) + 1);
} else {
occurences.put(c, 1);
}
}
NodeComparator nc = new NodeComparator(); //tworzymy instancję pomocniczej klasy
PriorityQueue < Node > nodes = new PriorityQueue < Node > (occurences.size(), nc); //korzystamy z PriorityQueue - w uproszczeniu jest to lista, która zadba, aby nasze elementy były zawsze posortowane; korzysta ona z naszego Comparatora
for (Entry < Character, Integer > entry: occurences.entrySet()) { //zamieniamy znaki i ich ilość wystąpień na liście, a następnie dodajemy je do utworzonej listy
Node n = new Node(entry.getKey(), entry.getValue());
nodes.add(n);
}
Node rootNode = null; //zmienna pomocnicza przechowująca korzeń drzewa - finalnie ma być on liściem przechowującym wartość równą długości wpisanego wyrazu
while (nodes.size() > 1) { //dopóki na liście nie pozostał jeden element(korzeń)
Node n1 = nodes.peek(); //pobieramy najmniejszy element z listy
nodes.poll(); //a następnie go usuwamy
Node n2 = nodes.peek(); //ponownie pobieramy najmniejszy element z listy
nodes.poll(); //i ponownie go usuwamy; w ten sposób pobraliśmy dwa najmniejsze elementy z listy
Node parent = new Node(n1.getValue() + n2.getValue()); //tworzymy liść, który będzie przechowywał powyższe elementy
if(n1.getValue() == n2.getValue() && !n1.isLeaf()) {
Node pom = n1;
n1 = n2;
n2 = pom;
}
rootNode = parent; // ustawiamy go tymczasowo jako korzeń
parent.left = n1; // mniejszy element ustawamy jako jego lewe dziecko
parent.right = n2;// większy jako jego prawe dziecko
nodes.add(parent); //następnie dodajemy rodzica jako samodzielny element do listy
}
return rootNode;
}
private static void encodeValues(Node node, String txt, HashMap < Character, String > encodedValues) { //tworzymy rekurencyjną funkcję, która nada liścią odpowiednie wartości
if (node == null) {
return;
}
if (node.getCharacter() != null) { //jeżeli liść posiada swój znak
System.out.println(node.getCharacter() + ":" + txt);
encodedValues.put(node.getCharacter(), txt); //dodajemy jego zakodowaną wartość do tablicy
}
encodeValues(node.left, txt + "0", encodedValues); //wywołujemy funkcję rekurencyjnie
encodeValues(node.right,txt + "1", encodedValues); //dla obu dzieci; w ten sposób całemu drzewu zostanie przypisana wartość
}
private static String decode(Node root, String encoded){
String decoded = ""; //zmienna pomocnicza
Node currentNode = root; //aktualnie sprawdzany liść
for(char c : encoded.toCharArray()){ //iterujemy poprzez zakodowany tekst
if(c == '0'){ //jeżeli iterowany znak jest zerem, to oznacza, że musimy iść w lewo
if(currentNode.left.isLeaf()){ //jeżeli dziecko po lewo jest liściem przechowującym znak
decoded += currentNode.left.getCharacter(); //dodajemy ten znak do zmiennej pomocniczej
currentNode = root; //a następnie wracamy na początek drzewa
}
else{
currentNode = currentNode.left; //jeżeli trafiliśmy na kontener, ustawiamy go jako aktualny
}
}
else{ //jeżeli jest to inny znak (1), to przechodzimy na prawą stronę
if(currentNode.right.isLeaf()){ //jeżeli dziecko po prawo jest liściem przechowującym znak
decoded += currentNode.right.getCharacter();//dodajemy ten znak do zmiennej pomocniczej
currentNode = root;//a następnie wracamy na początek drzewa
}
else{
currentNode = currentNode.right;//jeżeli trafiliśmy na kontener, ustawiamy go jako aktualny
}
}
}
return decoded; //na koniec zwracamy odkodowany tekst
}
public static void main(String[] args) {
System.out.println("Kodowanie Huffmana. Podaj tekst, który chcesz zakodować:");
Scanner sc = new Scanner(System.in);
String line = sc.nextLine(); //pobieramy wiersz od użytkownika
sc.close(); //pamiętając o zwalnianiu zasobów
Node rootNode = createHuffmanTree(line);
HashMap < Character, String > encodedValues = new HashMap < Character, String > (); //inicjalizujemy mapę, która przechowa tablicę kodowania
System.out.println("Oto tablica kodowania:");
encodeValues(rootNode, "", encodedValues); //przypisujemy odpowiednie wartości gałęziom i liściom
String output = "";
for (char c: line.toCharArray()) {
output += encodedValues.get(c); //następnie kodujemy wyraz, korzystając z utworzonej tablicy kodowania
}
System.out.println();
System.out.println("Oto twój tekst zakodowany metodą Huffmana: " + output);
System.out.println();
System.out.println("Oto odkodowany tekst: " + decode(rootNode, output));
}
}Python
from queue import PriorityQueue #importujemy PriorityQueue
#tworzymy klasę Node, która będzie podstaowym budulcem drzewa kodowania
#będzie ona przechowywać wartość, lewe i prawe dziecko, zakodowaną wartość, a także znak
class Node:
value = 0
right = None
left = None
character = ""
def isLeaf(self): #pomocnicza metoda, która pozwoli określić, czy liść przechowuje znak
return self.character != ""
def __init__(self, val, ch): #definiujemy konstruktor
self.value = val
self.character = ch
#funkcja __lt__ pomoże nam przy tworzeniu priority_queue
def __lt__(self, other):
if self.value != other.value: #wykonujemy normalne porównanie, jeżeli liście są różne;
return self.value < other.value
if not self.isLeaf() and other.isLeaf(): # w przeciwnym wypadku ważniejsze są liście mające znak
return True
if self.isLeaf() and not other.isLeaf(): # w przeciwnym wypadku ważniejsze są liście mające znak
return False
if self.isLeaf() and other.isLeaf(): #jeżeli jednak oba maja znak, to decyduje kolejność alfabetyczna
return ord(self.character[0]) < ord(other.character[0])
return True
#Definiujemy metodę, która stworzy drzewo kodowania Huffmana, a następnie zwróci jego korzeń
#Argumentem jest tekst, który chcemy zakodować
def createTree(text):
occurences = {}
for c in text: #zliczamy wystąpienia każdego znaku w tekście
if occurences.__contains__(c):
occurences[c] += 1
else:
occurences[c] = 1
# Tworzymy obiekt PriorityQueue(), który będzie przechowywać nieprzypisane elementy drzewa.
# Obiekt priority_queue pozwoli nam stworzyć uporządkowaną listę liści drzewa - najmniejsze będą najwyżej.
nodes = PriorityQueue()
for c in occurences.keys(): #tworzymy liście drzewa, bazując na znakach i ich ilości wystąpień, a następnei dodajmy do listy
node = Node(occurences[c], c)
nodes.put(node)
rootNode = None #tworzymy zmienna przechowujaca docelowo korzen drzewa
while nodes.qsize() > 1: #następnie iterujemy, dopóki w nodes nie zostanie ostatni element - korzeń drzewa
n1 = nodes.get() #pobieramy pierwszy, najmniejszy element z PriorityQueue
n2 = nodes.get() #pobieramy kolejny, najmniejszy element z PriorityQueue
#jeżeli oba liście mają tą samą wartość, a jeden z nich jest kontenerem, to powinien on być traktowany jako większy element
if n1.value == n2.value and not n1.isLeaf():
pom = n1 #dlatego w takiej sytuacji podmieniamy wskaźniki
n1 = n2
n2 = pom
parent = Node(n1.value + n2.value, "") #tworzymy liść-kontener, który będzie przechowywać dwa powyższe elementy i sumę ich wartości
rootNode = parent #ustawiamy go na aktualny korzen
parent.left = n1 #i dodajemy mu dzieci
parent.right = n2
nodes.put(parent) #a następnie dodajemy go do PriorityQueue
return rootNode #nasze drzewo jest gotowe - zwracamy korzeń
#tworzymy funkcję, która zakoduje drzewo
#jednocześnie zakoduje ona podany przez użytkownika tekst
def encodeValues(n, str, txt):
if n is None: #jeżeli trafimy na koniec drzewa
return txt #przerywamy rekurencję
if n.isLeaf(): #jeżeli przechowuje on znak
print(n.character + " : " + str) #to drukujemy go wraz z zakodowaną wartością
txt = txt.replace(n.character, str) #a następnie podmieniamy znak w tekście z zakodowaną wartościa
txt = encodeValues(n.left, str + "0", txt) #wykonujemy te same działania dla lewej części drzewa - rekurencja
txt = encodeValues(n.right, str + "1", txt) #wykonujemy te same działania dla prawej części drzewa - rekurencja
return txt #na koniec zwracamy zakodowany tekst
#definiujemy funkcję, która odkoduje tekst na bazie utworzonego drzewa
def decode(root, text):
decoded = "" #zmienna pomocnicza
currNode = root #aktualnie rozważany element drzewa
for char in text: #iterujemy poprzez znaki zakodowanego tekstu
if char == '0': #jeżeli jest to 0, to oznacza, że musimy iśc na lewą stronę
if currNode.left.isLeaf(): #jeżeli element po lewo jest liściem
decoded += currNode.left.character #to dodajemy jego znak do zmiennej pomocniczej
currNode = root #a następnie wracamy na początek drzewa
else:
currNode = currNode.left #jeżeli trafiliśmy na kontener, to od niego zaczniemy nast. iterację
else: #jeżeli jest to 1, to oznacza, że musimy iśc na prawą stronę
if currNode.right.isLeaf(): #jeżeli element po prawo jest liściem
decoded += currNode.right.character #to dodajemy jego znak do zmiennej pomocniczej
currNode = root #a następnie wracamy na początek drzewa
else:
currNode = currNode.right #jeżeli trafiliśmy na kontener, to od niego zaczniemy nast. iterację
return decoded #zwracamy odkodowana wartosc
word = input("Kodowanie Huffmana. Podaj tekst, który chcesz zakodować:").rstrip()
rootNode = createTree(word)
print("Oto tablica kodowania:")
word = encodeValues(rootNode, "", word)
print ("Oto tekst po zakodowaniu: " + word)
word = decode(rootNode, word)
print("Oto odkodowany tekst: " + word)
Super artykuł ;) Fajnie ze masz czas robić coś takiego.