System Kodowania (Huffman)


(Przemo Mynek) #1

Witam

mam następujący problem , dostałem zadanko pare dni temu ale nie wiem jak sie za to zabrac;)

Dokładniej chodzi o pomysł bo z implementacja sobie poradzę:wink:

Mam wymyslec i zaimplementowac algorytm podobny do kodowania (kompresji) huffmana ale troche bardziej prosty a problem polega na tym że mam sobie go sam wymyślic;)

Na wejściu mam byc tekst ,każda literka ma być zamieniona na ciąg binarny (np nr ASCII zamienic na binarny) ale tu zaczyna sie problem ponieważ litera ktora najczsciej występuje w zdaniu ma mieć najkrótszy kod binarny (i nie ma byc to zrobione za pomoca drzew BST i kolejek;)

i myśle nad tym i myśle i nie moge wymyślic więc stwierdziłe, że ktoś może mnie nakieruje:P

Zalozenie jest takie ze musi to byc bardziej proste niz Huffman jak już pisalem i i kod binarny na wyjściu ma zajmowac mniej bitow niz kod binarny nr ascci danego znaku:)

Z góry Thx za pomoc.


(andhla) #2

Mam taki pomysł aby "ręcznie" zbudować tablicę kodów prefiksowych. Rozmiar tabeli byłby taki jak ilość symboli w dostępnym alfabecie. Tablica byłaby posortowana ze względu na długość kodu. Następnie literze występującej najczęściej należy przypisać najkrótszy kod czyli pierwszą pozycję w tabeli itd. Pewnie "ręczne" przygotowanie takiej tabeli nie będzie proste ale wystarczy zrobić to raz.


(Asterisk) #3

przemo_mynek

Nie wiem czy to widać, ale na forum używamy polskiej pisowni.

Proszę więc edytować własnego posta przy użyciu przycisku icon_edit.gif


(Przemo Mynek) #4

zbudowanie takiej tablicy było by troche pracochłonne bo kod znaku nie moze byc prefiksem innego znaku;)ale może się na to skusze:P