moj_zad_3/tabele_wnioski.ipynb

Modelowanie Języka

3. Entropia [ćwiczenia]

Jakub Pokrywka (2022)

Zadanie 1 ( 15 punktów)

Weź teksty:

• z poprzednich zajęć (lub dowolny inny) w języku naturalnym i obetnij do długości 100_000 znaków
• wygenerowany losowo zgodnie z rozkładem jednostajnym dyskretnym z klasy [a-zA-Z0-9 ] o długości 100_000 znaków
• wygenerowany losowo zgodnie z rozkładem geometrycznym (wybierz p między 0.2 a 0.8) z klasy [a-zA-Z0-9 ] o długości 100_000 znaków
• wygenerowany losowo zgodnie z rozkładem jednostajnym dwupunktowym p=0.5 z klasy [01] o długości 100_000 znaków
• wygenerowany losowo zgodnie z rozkładem jednostajnym dwupunktowym p=0.9 z klasy [01] o długości 100_000 znaków

Następnie dla każdego z tekstów trakując je po znakach:

• skompresuj plik za pomocą dowolnego progrmu (zip, tar lub inny)
• policz entropię
• wytrenuj kodek huffmana i zakoduj cały tekst
• zdekoduj pierwsze 3 znaki (jako zera i jedynki) wypisz je (z oddzieleniem na znaki)
• zakodowany tekst zapisz do pliku binarnego, zapisz również tablicę kodową
• porównaj wielkość pliku tekstowego, skompresowanego pliku tekstowego (zip, ...) oraz pliku skompresowanego hofmmanem (wraz z kodekiem)

Uzupełnij poniższe tabelki oraz wnioski (conajmniej 5 zdań).

START ZADANIA

Entropia

	Entropia
tekst w jęz. naturalnym	4.490477053022786
losowy tekst (jednostajny)	5.976797776033915
losowy tekst (geometryczny)	2.9384661505927614
losowy tekst (dwupunktowy 0.5)	0.9999992786523595
losowy tekst (dwupunktowy 0.9)	0.4672814931728006

Wielkości w bitach:

	Plik nieskompresowany	Plik skompresowany (zip, tar,.. )	Plik skompresowany + tablica kodowa)
tekst w jęz. naturalnym	100766 *8	36084 *8	(56413 + 1131) *8
losowy tekst (jednostajny)	100000 *8	76560 *8	(74976 + 790) *8
losowy tekst (geometryczny)	100000 *8	38744 *8	(36964 + 491) *8
losowy tekst (dwupunktowy 0.5)	100000 *8	14292 *8	(18740 + 180) *8
losowy tekst (dwupunktowy 0.9)	100000 *8	7764 *8	(13750 + 180) *8

Wnioski:

1. W tekście w języku naturalnym wystąpiły znaki o ponad przeciętnej długosci bitowej
2. W tekście w języku naturalnym skompresowanie narzędziem xz bardziej się opłaciło
3. Korpusy z mniejszą entropią jest łatwiej kompresować.
4. Losowy tekst (jednostajny) ma większą entropię niż tekst w języku naturalnym
5. Czym większy alfabet tym większa tablica kodowa

KONIEC ZADANIA

Zadanie 2 (10 punktów)

Powtórz kroki z zadania 1, tylko potraktuje wiadomości jako słowa (oddzielone spacją). Jeżeli występują więcej niż jedna spacja równocześnie- usuń je.

Do wniosków dopisz koniecznie porównanie między kodowaniem hoffmana znaków i słów.

START ZADANIA

Entropia

	Entropia
tekst w jęz. naturalnym	10.188508379298268
losowy tekst (dyskretny)	10.629740889027198
losowy tekst (geometryczny)	0

Wielkości w bitach:

	Plik nieskompresowany	Plik skompresowany (zip, tar,.. )	Plik skompresowany + tablica kodowa)
tekst w jęz. naturalnym	100766 *8	36084 *8	(20495 + 91497) *8
losowy tekst (jednostajny)	100000 *8	76560 *8	(2130 + 114214) *8
losowy tekst (geometryczny)	100000 *8	38744 *8	(1 + 100164) *8
losowy tekst (dwupunktowy 0.5)	100000 *8	14292 *8	(1 + 100164) *8
losowy tekst (dwupunktowy 0.9)	100000 *8	7764 *8	(1 + 100164) *8

Wnioski:

1. korpusy bez spacji mają tylko jeden bajt
2. Korpusy bez spacji mają większą tablice kodową niż nieskompresowany plik
3. Kompresowanie huffmanem na słowach dla plików z jednym wyrazem nie ma sesnu
4. Kompresowanie na wyrazach wydaję się być gorsze niż na znakach z powodu ogromnej tablicy kodowej
5. W jęzuku naturalbym częściej występują te same wyrazy niż w losowym tekście (jednostajnym)

KONIEC ZADANIA

Zadanie 3 (20 punktów)

stwórz ręcznie drzewo Huffmana (zrób rysunki na kartce i załącz je jako obrazek) oraz zakoduj poniższy tekst

random.seed(444463) # <- Mój numer indeksu

tekst = list('abcdefghijklmnoprst')

random.shuffle(tekst)

tekst = tekst[: 5 + random.randint(1,5)]

tekst = [a*random.randint(1,4) for a in tekst]

tekst = [item for sublist in tekst for item in sublist]

''.join(tekst)

random.shuffle(tekst)

tekst = ''.join(tekst)
tekst

'kkehsoaefokjsnodjoj'

len(list('abcdefghijklmnoprst'))

19

Counter('kkehsoaefokjsnodjoj')

Counter({'k': 3,
         'e': 2,
         'h': 1,
         's': 2,
         'o': 4,
         'a': 1,
         'f': 1,
         'j': 3,
         'n': 1,
         'd': 1})

Start zadania

Koniec zadania

WYKONANIE ZADAŃ

Zgodnie z instrukcją 01_Kodowanie_tekstu.ipynb