319 lines
9.5 KiB
Plaintext
319 lines
9.5 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"\n",
|
|
"<div class=\"alert alert-block alert-info\">\n",
|
|
"<h1> Modelowanie Języka </h1>\n",
|
|
"<h2> 3. <i>Entropia</i> [ćwiczenia]</h2> \n",
|
|
"<h3> Jakub Pokrywka (2022)</h3>\n",
|
|
"</div>\n",
|
|
"\n",
|
|
""
|
|
]
|
|
},
|
|
{
|
|
"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
|
|
}
|