Po angielsku Huffman Encoding, jest to sposób zapisu symboli informacji w taki sposób, by zawatość zajęła mniej mniejsca niż początkowo.
Wydaje mi sie, że kodowanie to moze mieć jeszcze jedno zastosowanie w grach RPG bez przemocy. Mianowicie częstostliwość występowania symbolu może być uznana za koszt użytego... powiedzmy sobie -- czaru, ataku... którym nokautuje, pomaga się oponentowi, by przejść dalej.
Portal geeksforgeeks podaje algorytm zachłanny wyznaczania tego kodu. Proponuje kopce lub kolejki priorytetowe. Spróbowałem 'po swojemu', i teraz podam, że wystarczą listy oraz drzewa zapisane jako tablice. Najgorszy moment - w ostatniej fazie chciałem przenumerować węzły, ale okazało się to niepotrzebne. Odpowiednie drzewo było niemal gotowe.
Opis algorytmu, który jest taki sam we wszystkich podejsciach.
Mamy tablice symboli oraz ich częstotliwość występowania. Sortujemy je rosnąco. Wybieramy dwa najmniejsze, i tworzymy z nich nowy węzeł, w którym częstotliwość jest sumą składowych. Powtarzamy tak długo, aż zostanie jeden węzeł, w którym częstotliwość jest równa sumie częstotliwości wszystkich symboli.
W drugiej fazie, dane te umieszczamy na drzewie. Przechodząc po tym drzewie prefiksowym po dotarciu do liścia uzyskujemy symbol zapisany tym kodem.
W moim kodzie od razu generuję węzły drzewa, choć częstotliwość jako ostatecznie zbędna wprowadzam do drugiej pomocniczej tablicy węzłów wsp.
Zatem tworzę węzły z pary (symbol, częstotliwość, pozycja), gdzie pozycja to indeks węzła w tablicy, niezbędny, by dobrze je łączyć. Umieszczam je na liście tree. Kopiuję je do pomocniczej tablicy wsp. Warunek, nie mogę mieć symbolu 0 służącego jako flaga separująca liście od węzłów drzewa binarnego.
Wyszukuję wskaźnikami dwa węzły a, b o dwu najmniejszych częstotliwościach w tablicy wsp, tworzę z nich nowy węzeł o budowie (0, suma_częstotliwości, indeks), który dołączam do tablicy wsp, zaś równocześnie do tree dołączam węzeł o budowie (0, a, b), gdzie a i b są wyszukanymi indeksami węzłów. Z tablicy wsp usuwam węzły o indeksach a oraz b. Tak długość wsp w każdej iteracji maleje o 1.
Kontynuuję, dopóki we wsp nie zostanie tylko jeden węzeł, dołączany na końcu. Węzeł ten jest korzeniem drzewa, które już mam zaszyte w tablicy tree!
Druga faza to u mnie kosmetyka. We wszystkich węzłach z symbolami zeruję pola inne niż nazwa symbolu, przez co węzeł staje się liściem (symbol, 0,0), i drzewo gotowe!
Korzeń jest w ostatnim wężle wsp postaci np. (0,x,y). Na pozycji x jest węzeł tree.left, na pozycji y węzeł tree.right, liście mają wyzerowane te odsyłacze. Odczyt preOrder(tree, len(tree)-1, s="") schodzi rekursywnie s+'0' dla left, s+'1' dla right.
