{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "![Logo 1](https://git.wmi.amu.edu.pl/AITech/Szablon/raw/branch/master/Logotyp_AITech1.jpg)\n", "
\n", "

Modelowanie Języka

\n", "

3. Entropia [ćwiczenia]

\n", "

Jakub Pokrywka (2022)

\n", "
\n", "\n", "![Logo 2](https://git.wmi.amu.edu.pl/AITech/Szablon/raw/branch/master/Logotyp_AITech2.jpg)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Zadanie 1 ( 15 punktów)\n", "\n", "Weź teksty:\n", "- z poprzednich zajęć (lub dowolny inny) w języku naturalnym i obetnij do długości 100_000 znaków\n", "- wygenerowany losowo zgodnie z rozkładem jednostajnym dyskretnym z klasy [a-zA-Z0-9 ] o długości 100_000 znaków\n", "- 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\n", "- wygenerowany losowo zgodnie z rozkładem jednostajnym dwupunktowym p=0.5 z klasy [01] o długości 100_000 znaków\n", "- wygenerowany losowo zgodnie z rozkładem jednostajnym dwupunktowym p=0.9 z klasy [01] o długości 100_000 znaków\n", "\n", "Następnie dla każdego z tekstów trakując je po znakach:\n", "- skompresuj plik za pomocą dowolnego progrmu (zip, tar lub inny)\n", "- policz entropię\n", "- wytrenuj kodek huffmana i zakoduj cały tekst\n", "- zdekoduj pierwsze 3 znaki (jako zera i jedynki) wypisz je (z oddzieleniem na znaki)\n", "- zakodowany tekst zapisz do pliku binarnego, zapisz również tablicę kodową\n", "- porównaj wielkość pliku tekstowego, skompresowanego pliku tekstowego (zip, ...) oraz pliku skompresowanego hofmmanem (wraz z kodekiem)\n", "\n", "Uzupełnij poniższe tabelki oraz wnioski (conajmniej 5 zdań).\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### START ZADANIA" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Entropia\n", " \n", "| | Entropia |\n", "| ----------- | ----------- |\n", "| tekst w jęz. naturalnym | 4.490477053022786 |\n", "| losowy tekst (jednostajny) | 5.976797776033915 |\n", "| losowy tekst (geometryczny)| 2.9384661505927614 |\n", "| losowy tekst (dwupunktowy 0.5) | 0.9999992786523595 |\n", "| losowy tekst (dwupunktowy 0.9) | 0.4672814931728006 |\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Wielkości w bitach:\n", " \n", "| | Plik nieskompresowany | Plik skompresowany (zip, tar,.. ) | Plik skompresowany + tablica kodowa) |\n", "| ----------- | ----------- |-----------|----------- |\n", "| tekst w jęz. naturalnym | 100766 *8 | 36084 *8 | (56413 + 1131) *8 |\n", "| losowy tekst (jednostajny) | 100000 *8 | 76560 *8 | (74976 + 790) *8 |\n", "| losowy tekst (geometryczny)| 100000 *8 | 38744 *8 | (36964 + 491) *8 |\n", "| losowy tekst (dwupunktowy 0.5)| 100000 *8 | 14292 *8 | (18740 + 180) *8 |\n", "| losowy tekst (dwupunktowy 0.9)| 100000 *8 | 7764 *8 | (13750 + 180) *8 |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Wnioski:\n", "\n", "1. W tekście w języku naturalnym wystąpiły znaki o ponad przeciętnej długosci bitowej\n", "2. W tekście w języku naturalnym skompresowanie narzędziem `xz` bardziej się opłaciło \n", "3. Korpusy z mniejszą entropią jest łatwiej kompresować.\n", "4. Losowy tekst (jednostajny) ma większą entropię niż tekst w języku naturalnym\n", "5. Czym większy alfabet tym większa tablica kodowa" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### KONIEC ZADANIA" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Zadanie 2 (10 punktów)\n", "\n", "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.\n", " \n", "Do wniosków dopisz koniecznie porównanie między kodowaniem hoffmana znaków i słów.\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### START ZADANIA" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Entropia\n", " \n", "| | Entropia |\n", "| ----------- | ----------- |\n", "| tekst w jęz. naturalnym | 10.188508379298268 |\n", "| losowy tekst (dyskretny) | 10.629740889027198 |\n", "| losowy tekst (geometryczny)| 0 |\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Wielkości w bitach:\n", " \n", "| | Plik nieskompresowany | Plik skompresowany (zip, tar,.. ) | Plik skompresowany + tablica kodowa) |\n", "| ----------- | ----------- |-----------|----------- |\n", "| tekst w jęz. naturalnym | 100766 *8 | 36084 *8 | (20495 + 91497) *8 |\n", "| losowy tekst (jednostajny) | 100000 *8 | 76560 *8 | (2130 + 114214) *8 |\n", "| losowy tekst (geometryczny)| 100000 *8 | 38744 *8 | (1 + 100164) *8 |\n", "| losowy tekst (dwupunktowy 0.5)| 100000 *8 | 14292 *8 | (1 + 100164) *8 |\n", "| losowy tekst (dwupunktowy 0.9)| 100000 *8 | 7764 *8 | (1 + 100164) *8 |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Wnioski:\n", "\n", "1. korpusy bez spacji mają tylko jeden bajt\n", "2. Korpusy bez spacji mają większą tablice kodową niż nieskompresowany plik\n", "3. Kompresowanie huffmanem na słowach dla plików z jednym wyrazem nie ma sesnu\n", "4. Kompresowanie na wyrazach wydaję się być gorsze niż na znakach z powodu ogromnej tablicy kodowej\n", "5. W jęzuku naturalbym częściej występują te same wyrazy niż w losowym tekście (jednostajnym)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### KONIEC ZADANIA" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Zadanie 3 (20 punktów)\n", "\n", "stwórz ręcznie drzewo Huffmana (zrób rysunki na kartce i załącz je jako obrazek) oraz zakoduj poniższy tekst " ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'kkehsoaefokjsnodjoj'" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random.seed(444463) # <- Mój numer indeksu\n", "\n", "tekst = list('abcdefghijklmnoprst')\n", "\n", "random.shuffle(tekst)\n", "\n", "tekst = tekst[: 5 + random.randint(1,5)]\n", "\n", "tekst = [a*random.randint(1,4) for a in tekst]\n", "\n", "tekst = [item for sublist in tekst for item in sublist]\n", "\n", "''.join(tekst)\n", "\n", "random.shuffle(tekst)\n", "\n", "tekst = ''.join(tekst)\n", "tekst" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "19" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(list('abcdefghijklmnoprst'))" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Counter({'k': 3,\n", " 'e': 2,\n", " 'h': 1,\n", " 's': 2,\n", " 'o': 4,\n", " 'a': 1,\n", " 'f': 1,\n", " 'j': 3,\n", " 'n': 1,\n", " 'd': 1})" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Counter('kkehsoaefokjsnodjoj')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Start zadania" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Koniec zadania" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## WYKONANIE ZADAŃ\n", "Zgodnie z instrukcją 01_Kodowanie_tekstu.ipynb" ] } ], "metadata": { "author": "Jakub Pokrywka", "email": "kubapok@wmi.amu.edu.pl", "kernelspec": { "display_name": "Python 3.8.12 64-bit", "language": "python", "name": "python3" }, "lang": "pl", "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.12" }, "subtitle": "0.Informacje na temat przedmiotu[ćwiczenia]", "title": "Ekstrakcja informacji", "vscode": { "interpreter": { "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6" } }, "year": "2021" }, "nbformat": 4, "nbformat_minor": 4 }