Witam, na wstępie chcę zaznaczyć, że jestem tu nowy. Mam do napisania pierwszy w życiu własny program. Treść : "Napisz program, który implementuje kody Huffmana o stałej długości. Program ma umożliwiać wczytywanie pliku tekstowego, kompresję pliku i zapis wyniku kompresji do pliku wyjściowego. Dodatkowo program powinien podawać stopień kompresji." Zacząłem czytać o tym, ale praktycznie wszystko co znalazłem odnosi się do kodów o zmiennej długości. Niby te o stałej długości powinny być łatwiejsze, ale i mniej efektywne, mimo to nigdzie nie ma tego opisanego. Chętnie przyjmę każdą poradę w jaki sposób mógłbym się za to w ogóle zabrać i od czego zacząć. Jakieś podstawy programowania w C++ znam, ale nadal jestem zielony w tym temacie. Z góry dzięki!
Tutaj masz to wyjaśnione.
W kodowaniu Huffmana zakłada się, że kody dla różnych symboli mogą mieć różną długość. Jeśli wszystkie kody mają tą samą długość to nie ma kodowania Huffmana, a zwykły bit packing. Z drugiej strony, kodowanie Huffmana może być:
- statyczne - wtedy dzielimy dane wejściowe na bloki (1 lub więcej bloków) i przy każdym zakodowanym bloku wstawiamy dane z których można wygenerować kody Huffmana użyte do zakodowania bloku
- adaptacyjne - wtedy nie zapisujemy do pliku bezpośrednio statystyk, kodów, itp a zamiast tego używamy historię poprzednio zakodowanych symboli do policzenia kodów dla następnych symboli. W takim przypadku startujemy z jakimś predefiniowanym stanem kodów (przez co na początku kompresja jest słaba, albo nie ma jej wcale), a z czasem uczymy się rozkładu prawdopodobieństw symboli i możemy poprawiać na bieżąco kody (co zwykle poprawia kompresję mniej więcej do poziomu tego statycznego kodowania)
wojtes napisał(a):
Treść : "Napisz program, który implementuje kody Huffmana o stałej długości. Program ma umożliwiać wczytywanie pliku tekstowego, kompresję pliku i zapis wyniku kompresji do pliku wyjściowego. Dodatkowo program powinien podawać** stopień kompresji**."
Mam wrażenie, że autor zadania sam nie wie na czym polega kodowanie Huffmana. Poza tym co wytknął Wibowit, niby na czym miałby polegać stopień kompresji w kodowaniu Huffmana? (coś mi się pochrzaniło i źle zrozumiałem treść).
@MarekR22: stopień kompresji = stosunek rozmiaru pliku wyjściowego do wejściowego