Algorytm Huffmana dla polskich tekstów

Odpowiedz Nowy wątek
2011-10-24 15:26
0

Witam muszę (No dobra nie muszę jest to pewnego rodzaju zadanie dodatkowe, ale w celach nauki chciałbym jednak to zrobić) napisać program kodujący litery polskiego alfabetu - czyli po prostu wpisuję jakiś tam tekst a program zamienia go na kod binarny (Nie chcę by np. przepisywało program z notatnika do innego pliku zmniejszając jego wielkość - za to w ogóle nie miałbym pojęcia jak się zabrać. Starczy mi samo wypisanie zmienionej wersji tekstu) z wykorzystaniem algorytmu Huffmana.

Częstotliwość występowania liter w polskich tekstach jest tutaj http://pl.wikipedia.org/wiki/Alfabet_polski - mam zamiar ominąć litery specjalne typu ż ą (Czyli alfabet łaciński bez Q i X)

Niestety jedynym pomysłem jaki przychodzi mi do głowy to rozpisanie sobie liter na kartce, wczytanie tekstu do tablicy typu char i sprawdzanie pętlą każdej litery i potem odpowiednia zamiana za pomocą if i else if. (Czyli na przykład if(tablica[i]=a) cout<<"01"). Program taki oczywiście (No na 99%?) będzie działać aczkolwiek musiałbym zrobić else if'a dla każdej litery czyli if + 20 pare else if'ow - nie dość, że nie będzie to wyglądało zbyt pięknie to program chyba nie będzie działał zbyt szybko dla większej ilości tekstu.

Jak to zrobić inaczej? Czy może się nie da bez zastosowania jakichś zaawansowanych funkcji? Dla mnie to nie problem wypisanie tego wszystkiego aczkolwiek jak już to robię to chciałbym to zrobić dobrze.

Pozostało 580 znaków

2011-10-24 16:02
1

Może użyj std::map

Pozostało 580 znaków

2011-10-24 16:34
0

Coś popróbuje choć napotkałem na pewne problemy gdy teraz próbowałem coś zrobić, dodatkowo program nadal będzie długi (Może szybszy choć nie jestem pewien), jeszcze jakieś propozycje?

Jedna linijka na każdą literę, to nie jest dużo. - lukasz1235 2011-10-24 16:38

Pozostało 580 znaków

2011-10-24 17:07
0

mam zamiar ominąć litery specjalne typu ż ą

a dlaczego?

Pozostało 580 znaków

2011-10-24 17:33
0

A tak bez powodu.

Jedna linijka na każdą literę, to nie jest dużo

Niby. W każdym razie mam problem z napisaniem tego. Jak do wieczora nie zadziała to dam to co stworzyłem. Chyba, że ktoś byłby chętny napisać kawałek kodu to byłbym wdzięczny ;>

@EDIT
OK już wiem jak to zrobić, żeby działało (No a przynajmniej działa dla dwóch liter potem napisze całość) jednak mam inny problem. Jak wczytać zmienna liczbową zaczynającą się od zera? Tzn jak jest np. 'a' to jej kod binarny powinien byc 01 aczkolwiek gdy to wypisuje to pisze mi tylko 1. Jak sprawić by wypisywał całość (jedno lub wiecej zer na poczatku?). Oczywiscie mogę zapisać to w stringu, ale czy istnieje jakiś sposób, żeby przechować taką zmienna w typie stworzonym do zmiennych liczbowych?

edytowany 2x, ostatnio: rafi94, 2011-10-24 18:27

Pozostało 580 znaków

2011-10-25 11:56
pan kuba
0

W kodowaniu Huffmana, 01 to nie jest liczba, tylko ciąg znaków. Zatem będziesz miał słownik std::map, w którym klucze to będzie typ char, a wartości będą typu string. Tak będzie najlepiej :)

Pozostało 580 znaków

2011-10-25 12:03
pan kuba
0

Spoglądając na drzewko w artukule na wiki: http://pl.wikipedia.org/wiki/Kodowanie_Huffmana teraz już jestem pewny, że nie ma innej opcji, jak to co wyżej przedstawiłem. Masz tam przykładowo takie dwie ścieżki: 001 oraz 0001. Jak odróżnić 001 od 0001? To są dwie takie same liczby, ale dwa różne ciągi znaków :)

Pozostało 580 znaków

2011-10-25 15:22
msm
0

@pan kuba - ale powstałe kody są bezprefiksowe, czyli da się reprezentować jako liczbę:

(zakładając przechowywanie w bajtach)
001  = 001?????
0001 = 0001????

(Gdzie ? to dowolny znak)

edytowany 2x, ostatnio: msm, 2011-10-25 15:23

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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