Dyskusja:Kodowanie Huffmana

Z Wikipedii

Chciałem dodać że algorytm napisany w c++ nie jest do końca poprawny, w warunku

if (tmp1->value > nodes[i].value){

tmp2 = tmp1;

tmp1 = &nodes[i];

}

zamiast tmp1->value powinno być tmp2->value, inaczej nie jest on poprawny.

[edytuj] prawdopodobieństwo

Proponuję wycofać z treści słowo "prawdopodobieństwo", a zastąpić je innym, bo słowo to w statystyce ma dokładnie określone znaczenie i "Prawdopodobieństwa nie muszą w sumie dawać jedynki, muszą jedynie zachować proporcje," jest niepoprawne

Moja propozycja

1. Zliczamy liczbę wystąpień poszczególnych symboli (S)
2. Tworzymy graf (drzewko)
   1. Dla każdego symbolu S tworzymy węzeł o wartości równej liczbie wystąpień tego symbolu S.
   2. Bierzemy 2 wolne węzły z najmniejszymi wartościami (jeśli kilka węzłów ma taką samą wartość bierzemy dowolny z nich) i łączymy je jako 2 podgałęzie nowego węzła. Nowe węzłowi nadajemy wartość równą sumie wartości obu węzłów. Jednej drodze do podwęzła nadajemy wartość 0 a drugiej 1.
   3. Powtarzamy tak długo dopóki jest więcej niż 1 wolny węzeł.
3. Generujemy kod wynikowy (wersja bez tablicy kodów).
   1. Dla każdego znaku informacji tworzymy ciąg zer i jedynek odpowiadający wystąpieniu tej wartości na gałęziach drzewa od korzenia do kodowanego znaku.
   2. Utworzony kod traktujemy całęj wiadomośći trakujemy jako liczbę binarną, dzielimy na bajty i zapisujemy.

Jeśli zaakceptujecie to przerobię poniższy przykład na kodowanie z rysunkiem grafu dla jakiegoś napisu.

Tez sie z tym zgodzę

[edytuj] Przykład

Mamy symbole A,B,C,D o prawdopodobieństwach wystąpienia odpowiednio [0.1, 0.2, 0.3, 0.4].

• Łączymy węzły odpowiadające symbolom (A) i (B). Teraz mamy (A + B) = 0.3, (C) = 0.3, (D) = 0.4
• Łączymy węzły odpowiadające drzewku (A + B) oraz (C). Teraz mamy ((A + B) + C)=0.6 i (D) = 0.4
• Łączymy węzły odpowiadające drzewku ((A + B) + C) oraz (D). Teraz mamy tylko jeden wolny węzeł - drzewko (((A + B) + C) + D) = 1.0
• Obliczamy kody znaków:
  • A = lewo, lewo, lewo = 000
  • B = lewo, lewo, prawo = 001
  • C = lewo, prawo = 01
  • D = prawo = 1

Jak łatwo sprawdzić statystyczny znak zajmie w naszym kodzie:

p[A] * 3 + p[B] * 3 + p[C] * 2 + p[D] * 1 = 0.3 + 0.6 + 0.6 + 0.4 = 1.9 bitów. Jest to mniej niż 2 bity potrzebne w trywialnym kodowaniu o stałej długości znaku.

zauwazylem ze nie dziala link na samym dole, do czegos w c++