Dyskusja:Kodowanie Huffmana

W zdaniu rozpoczynającym się od "Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów bitowych)" wyrażenie "których długość jest odwrotnie proporcjonalna do prawdopodobieństwa" jest niepoprawne. Proporcjonalność odwrotna oznaczałaby, że jeżeli jakiś symbol jest dwa razy mniej prawdopodobny niż inny, to jego kod powinien być dokładnie dwa razy dłuższy. (Zob. Proporcjonalność odwrotna.) W rzeczywistości mamy tylko zależność malejącą: kod symboli rzadkich jest dłuższy (a dokładniej nie krótszy), tak jak to jest wyjaśnione w następnym zdaniu artykułu. Jednak zależność malejąca to nie to samo co odwrotna proporcjonalność (tak samo jak nie każda zależność rosnąca jest proporcjonalnością).

Proponuję następującą poprawkę:

Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów bitowych) w ten sposób, że im częściej dany symbol występuje (może wystąpić) w ciągu danych, tym mniej zajmie bitów.

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.

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ę

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++

JAK TO JEST ŻE NIEPRAWIDŁOWY KOD JEST TU TYLE CZASU? WSZYSTKIE LEWE I PRAWE WĘZŁY TO NULLE (przeniósł z arta McMonster (相談) 19:11, 16 sty 2009 (CET))[odpowiedz]

We własnościach kodu Huffmana jest punkt: "dwa słowa kodowe o tej samej długości różnią się tylko jednym, ostatnim bitem", co oczywiście nie jest prawdą. Najprostszym dowodem jest układ z czterema (lub dowolną potęgą dwójki) znakami o identycznej liczbie wystąpień, w którym wszystkie słowa kodowe są równej długości.

Głośno ostatnio o ANS z Krakowa - trochę podobne do arytmetycznego, ale stan jest jedną liczbą naturalną zamiast dwóch - dzięki temu można stablicować całe zachowanie, dostając dekoder bardzo podobny do Huffmana, ale dodatkowo uwzględniający ułamkowe bity.

Przykładowe implementacje: https://github.com/Cyan4973/FiniteStateEntropy https://github.com/rygorous/ryg_rans

Benchmarki: http://encode.ru/threads/1890-Benchmarking-Entropy-Coders

Może warto gdzieś wspomnieć?

Artykuł: "The use of asymmetric numeral systems as an accurate replacement for Huffman coding". Nowy kompresor Apple dla iOS 9 (3x szybszy od standardowego, lepsza kompresja): LZFSE: Lempel-Ziv + Finite State Entropy wskazując implementację tANS Yanna Colleta: https://github.com/Cyan4973/FiniteStateEntropy . CRAM v3 komppresor danych genetycznych (European Bioinformatics Institute) używa rANS ( http://www.htslib.org/benchmarks/CRAM.html ) ... i jeszcze kilka innych kompresorów: http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations

W eksperymentalnym branchu kodeka wideo Google (VP10) też wszystko jest kodowane ANS: https://chromium.googlesource.com/webm/libvpx/+/fb9186d68d498919b290d7f444560f44a1d8d1df

Apple otworzyło źródło swojego kompresora na tANS (LZFSE): https://github.com/lzfse/lzfse/blob/master/src/lzfse_fse.h , https://www.infoq.com/news/2016/07/apple-lzfse-lossless-opensource

Facebook oficjalnie używa kompresora Zstandard na Asymmetric Numeral Systems: https://code.facebook.com/posts/1658392934479273/smaller-and-faster-data-compression-with-zstandard/ Kodek wideo z Alliance for Open Media (m.in. Google, Microsoft, Intel) też jest na ANS: https://aomedia.googlesource.com/aom/+/master/aom_dsp/ans.h 188.146.35.77 (dyskusja) 07:20, 5 paź 2016 (CEST)[odpowiedz]

Dodałem przypis z angielskiej wiki (nekreolog), ale jest w nim tylko że David Huffman był autorem algorytmu, natomiast nie ma informacji kiedy został stworzony.

-- Jcubic (dyskusja) 19:37, 6 lip 2014 (CEST)[odpowiedz]

Cytat: "Algorytm Huffmana nie należy do najefektywniejszych systemów bezstratnej kompresji danych". Nie należy? Nie należy do efektywnych obliczeniowo, zgadzam się. Jednak samo stwierdzenie, że nie należy do najefektywniejszych jest błędne. Algorytm Huffmana zawsze produkuje optymalne rozwiązanie dla znanego zbioru wejściowego. To nie jest efektywne? Moim zdaniem niefortunne stwierdzenie.

Zdecydowanie zabrakłow zdaniu słowa obliczeniowo. Dzięki za zwrócenie uwagi. Doctore_→∞ 00:09, 12 sie 2015 (CEST)[odpowiedz]