Kompresja pliku przy pomocy algorytmu Huffmana

0

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!

1

Tutaj masz to wyjaśnione.

3

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)
1
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ść).

0

@MarekR22: @Wibowit: Czyli dobrze rozumiem, że treść tego zadania nie ma za bardzo sensu? Jest to zadanie zaliczeniowe na studia, więc chyba będę musiał napisać do prowadzącego co właściwie miał na myśli. Jeszcze jakieś rady o co mogę zapytać ?

0

@MarekR22: stopień kompresji = stosunek rozmiaru pliku wyjściowego do wejściowego

1 użytkowników online, w tym zalogowanych: 0, gości: 1