NI-VSM-DU-1

1. Z obou datových souborů načtěte texty k analýze. Pro každý text zvlášť odhadněte pravděpodobnosti znaků (symbolů včetně mezery), které se v textech vyskytují. Výsledné pravděpodobnosti graficky znázorněte.

Data a parametry

Reprezentant - Bogdan Buliakov

Parametry úlohy byly spočtěny následovně:

K = den narození reprezentanta skupiny - 23 L = počet písmen v příjmení reprezentanta - 8 (BULIAKOV)

Podle uvedeného vzorce jsme definovali datový soubor č. 1, jako soubor 013.txt a datový soubor č. 2, jako 014.txt

K = 23 L = 8 X = ((K*L*23) % (20)) + 1 Y = ((X + ((K*5 + L*7) % (19))) % (20)) + 1 print('X =', X) print('Y =', Y)

Nastavení

from scipy import stats import numpy as np from matplotlib import pyplot as plt %matplotlib inline Darnost = 2

Funkce read_text_from_file se používá ke čtení textu ze souboru

Funkce rel_freq se používá k výpočtu pravděpodobnosti znaků

Funkce draw_rel_freq se používá ke grafickému znázornění pravděpodobnosti znaků

Funkce entropy se používá pro výpočet entropie. Použili jsme funkce entropy z knihovny scipy https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.entropy.html Vzhledem k tomu, že pracujeme s bity, musíme výsledné číslo rozdělit na logaritm se základem (base) 2 (Entropie diskrétní náhodné veliciny, Přednáška 5)

class VSM: def __init__(self): super().__init__() self.text = "" self.text_code = [] self.letters_codes = [] self.letters_counts = [] self.letters_rel_freq = [] self.letters = [] def read_text_from_file(self, file_str: str): with open(f"{file_str}", 'r') as f: self.text = f.readlines()[1] self.text_code = list([ord(x) for x in self.text]) def rel_freq(self): self.letters_codes, self.letters_counts = np.unique(self.text_code, return_counts=True) self.letters_rel_freq = self.letters_counts / np.sum(self.letters_counts) self.letters = [chr(int(c)) for c in self.letters_codes] return list(zip(self.letters, self.letters_rel_freq)) def draw_rel_freq(self): fig, ax = plt.subplots() ax.bar(np.arange(len(self.letters)), self.letters_rel_freq) fig.tight_layout() plt.xticks(ticks=np.arange(len(self.letters)), labels=self.letters) plt.title("Pravděpodobnost znaků v textu") plt.xlabel("Znak") plt.ylabel("Pravděpodobnost") #display(fig) def entropy(self, base:int = 2): return stats.entropy(self.letters_rel_freq) / np.log(base)

Pomocí těchto funkcí získáme výsledky.

Výsledky pro první text

print(f"Text 1: soubor {X}") vsm1 = VSM() vsm1.read_text_from_file(f"{str(X).zfill(3)}.txt") vsm1.rel_freq() vsm1.draw_rel_freq()

Nejčastějším znakem, který se objevuje, je samozřejmě ' ' – protože se díváme na text a jako znak bereme v úvahu i mezery.Tady vidíme,že se nejčastěji vyskytující písmeno je 'e'. Následuje 'a', 't' a 'i'.

Nejméně často se vyskytující písmeno je 'z' . Mezi další zřídka se vyskytující písmena patří 'j' a 'q'.

Celkově se distribuce zdá být poněkud podobná typické distribuci písmen v anglickém textu (https://en.wikipedia.org/wiki/Letter_frequency).

Výsledky pro druhý text

print(f"Text 2: soubor {Y}") vsm2 = VSM() vsm2.read_text_from_file(f"{str(Y).zfill(3)}.txt") vsm2.rel_freq() vsm2.draw_rel_freq()

Distribuce znaků ve druhém textu se příliš neliší od distribuce znaků v prvním textu. Zde můžeme říci, že k těm nejčastějším přibyla písmena 'o' a 'n'.

Můžeme si taky všimnout, že v obou textech se vyskytuje každý znak anglické abecedy,takže nemusíme provádět žádné úpravy.

2. Pro každý text zvlášť spočtěte entropii odhadnutého rozdělení znaků.

Pomocí výše uvedené funkce (entropy) se podívejme na výsledky.

Výsledky pro první text

print(f"Entropy: {vsm1.entropy(Darnost)}")

Můžeme si to ověřit i pomocí původního vzorce uvedeného na přednáškách. (Entropie diskrétní náhodné veliciny, Přednáška 5)

np.sum([- p*np.log2(p) for p in vsm1.letters_rel_freq])

Výsledky pro druhý text

print(f"Entropy: {vsm2.entropy(Darnost)}")

Ověřim i pomocí původního vzorce uvedeného na přednáškách.

np.sum([- p*np.log2(p) for p in vsm2.letters_rel_freq])

3. Nalezněte optimální binární instantní kód C pro kódování znaků prvního z textů.

Jak již víme z přednášek (Věta 6.17, Přednáška 6) Huffmanův kód je optimální, proto použijeme Algoritmus sestrojení binárního Huffmanova kódu (6.6 Huffmanovo kódování, Přednáška 6):

Spojíme dvě nejméně pravděpodobné hodnoty do jedné a uvažujme nové rozdělení náhodné veličiny s o jednu menším počtem hodnot.

Opakujeme tak dlouho, až zůstane jediná hodnota, které přiřadíme prázdný řetězec jako kódové slovo.

Zpětným chodem zkonstrujeme kódová slova všech původních hodnot.

Pro hodnotu x, která vznikla spojením hodnot u a v, vytvoříme kódové slovo méně pravděpodobné hodnoty připojením symbolu 1 za kódové slovo C(x) a analogicky kódové slovo více pravděpodobné hodnoty připojením symbolu 0 za C(x),

Realizace

Vytvořme si Huffmanovu třídu, která bude obsahovat všechny potřebné funkce pro splnění našeho úkolu.

class Huffman: def __init__(self, Darnost): super().__init__() self.Darnost = Darnost self.Code_dict = list([str(d) for d in range(Darnost)[::-1]]) def create_code(self, vsm): probabilities = np.array(list(zip(range(len(vsm.letters_rel_freq)), vsm.letters_rel_freq))) letters_dict = dict(zip(vsm.letters, [[int(i), p, [], ''] for i, p in enumerate(vsm.letters_rel_freq)])) self.letters_count = len(letters_dict) step = 0 while len(probabilities) != 1: step += 1 indices_for_union = np.argsort(probabilities[:, 1])[:Darnost] letters_indices_for_union = list(np.array(probabilities[indices_for_union][:, 0], dtype=int)) letters_for_union = [list(letters_dict)[int(i)] for i in letters_indices_for_union] new_letter = ''.join(letters_for_union) new_probability = [len(letters_dict), np.sum([letters_dict[l][1] for l in letters_for_union]), letters_indices_for_union, ''] letters_dict[new_letter] = new_probability probabilities = np.concatenate([np.delete(probabilities, indices_for_union, axis = 0), [new_probability[:2]]]) print(f"New letter {new_letter:27}, letter number {new_probability[0]}, indices united {letters_indices_for_union}, probability {new_probability[1]}") self.probabilities = probabilities self.letters_dict = letters_dict self._fill_code(int(self.probabilities[0, 0]), '') self.Code = dict([]) for letter in list(self.letters_dict)[:self.letters_count]: self.Code[letter] = self.letters_dict[letter][3] def _fill_code(self, ind, code): self.letters_dict[list(self.letters_dict)[int(ind)]][3] = code slozky = self.letters_dict[list(self.letters_dict)[int(ind)]][2] if len(slozky) == 0: return sl_probs = [] for s in slozky: slozka = self.letters_dict[list(self.letters_dict)[s]] sl_probs.append(slozka[:2]) sl_probs = np.array(sl_probs) for i, s in enumerate(sl_probs[np.argsort(sl_probs[:, 1])]): self._fill_code(s[0], code + self.Code_dict[i])

Zde můžeme vidět, jak tvoříme nová slova (new letter) z kombinací existujících slov, jejich indexy (letter number) , indexy slov, která tvoří nové slovo(indices united), a jak se sčítají jejich pravděpodobnosti (probability).

hf = Huffman(Darnost) hf.create_code(vsm1)

K implementaci výše uvedeného algoritmu budeme potřebovat: array - probabilities ve funkci create_code s číslem písmena (slova) a jeho pravděpodobností, který použijeme k uspořádání jejich pravděpodobností a hledání nejméně pravděpodobných slov.

probabilities = np.array(list(zip(range(len(vsm1.letters_rel_freq)), vsm1.letters_rel_freq))) print(probabilities)

letters_dict ve funkci create_code toto je struktura (dictionary) pro uložení stromu, kam budeme přidávat nové uzly (prvky): key tady bude písmeno (slovo), které jsme měli předtím a pak tam přidáme slova, která byla získána, jako výsledek vytváření nových uzlů jak value uložíme číslo slova, jeho pravděpodobnost (v případě nového slova součet pravděpodobností, ze kterých se skládá), сísla slov, ze kterých nové slovo bylo složeno, a kod, který bude vygenerován v _fill_code indices_for_union používáme pro uspořádání a výběru 2 (Darnost = 2, protože potřebujeme binární kod) nejméně pravděpodobných prvků (slov) v probabilities.

hf.letters_dict

_fill_code funkce funguje tak, že vytvořený strom uvažujeme od konce. V kořeni máme prvek s pravděpodobností 1 a to je slovo sestávající ze všech slov, která jsme měli. Toto slovo "hrcmseovpwgnildatjxzqkbufy" bude mít kódové slovo prázdný řetězec= " ". Dále začneme zvažovat, jak ze kterých prvků byl získán a jejich pravděpodobnosti, prvku s nejvyšší pravděpodobností bude přiřazeno kódové slovo "0", s menší pravděpodobností"1".

Například, jak můžete vidět výše, slovo - "hrcmseovpwgnildatjxzqkbufy" bylo získáno kombinací 50 = "hrcmseovpwg" a 51 = "nildatjxzqkbufy " slov, jejich pravděpodobnosti jsou rovna ''hrcmseovpwg" - 0.41634397115769795, "nildatjxzqkbufy " - 0.583656028842302

Proto dáme slovu 'hrcmseovpwg" kód "1" a slovu "nildatjxzqkbufy" - "0" provedeme stejnou operaci pro každého potomka a vytvoříme jeho kódová slova, jak jsme to udělali nyní (přidáním "0" nebo "1" k předchozímu kódovému slovu, v závislosti na jejich pravděpodobnosti)

Binární Huffmanův kód

Takto vypadá náš kód získaný použitím Huffmanova algoritmu.

hf.Code

4. Pro každý text zvlášť spočtěte střední délku kódu C a porovnejte ji s entropií rozdělení znaků. Je kód C optimální i pro druhý text?

Střední délka kódu C s rozdělením p(x) definujeme jako, kde l (x) je délka kódového slova příslušejícího prvku x ∈ X .

Nutná podmínka pro optimalitu (entropie <= střední délka kódu < entropie +1)

Code_delky = dict() for c in hf.Code: Code_delky[c] = len(hf.Code[c]) st_delka_1 = 0 for letter, p in zip(vsm1.letters, vsm1.letters_rel_freq): st_delka_1 += p * Code_delky[letter] st_delka_2 = 0 for letter, p in zip(vsm2.letters, vsm2.letters_rel_freq): st_delka_2 += p * Code_delky[letter] print(f"Stredni delka kodu pro soubor 1 je {st_delka_1}") print(f"Srovnání s enropií pro první text: {vsm1.entropy(Darnost)} <= {st_delka_1} < {vsm1.entropy(Darnost) +1} ") print(f"Stredni delka kodu pro soubor 2 je {st_delka_2}") print(f"Srovnání s enropií pro druhý text: {vsm2.entropy(Darnost)} <= {st_delka_2} < {vsm2.entropy(Darnost) +1} ")

Podíváme se na náš kód pro první text. Můžeme si všimnout, že délka kódu je řazena podle pravděpodobností.

np.array(list(zip(vsm1.letters, vsm1.letters_rel_freq, Code_delky.values(), hf.Code.values())))[np.argsort(vsm1.letters_rel_freq)[::-1]]

Podíváme se ted' na druhý text. Vidíme, že u druhého textu tomu tak není.

np.array(list(zip(vsm2.letters, vsm2.letters_rel_freq, Code_delky.values(), hf.Code.values())))[np.argsort(vsm2.letters_rel_freq)[::-1]]

Zkusme seřadit a nahradít navzájem odpovídající kódy a uvidíme, co se stane se střední délkou kódu.

"c" ('0.019375500400320256') -"f" (0.02145716573258607)

"m" (0.01809447558046437) -"u" (0.021297037630104085)

"b" (0.012489991993594875) -"v" (0.008006405124099279)

"q" (0.0006405124099279424) -"x" (0.0006405124099279424)

Pak dostaneme:

Code_text_2 = hf.Code.copy() Code_text_2["b"] = hf.Code["v"] Code_text_2["v"] = hf.Code["b"] Code_text_2["m"] = hf.Code["u"] Code_text_2["u"] = hf.Code["m"] Code_text_2["c"] = hf.Code["f"] Code_text_2["f"] = hf.Code["c"] Code_text_2["q"] = hf.Code["x"] Code_text_2["x"] = hf.Code["q"] Code_text_2

Code_delky_2 = dict() for c in hf.Code: Code_delky_2[c] = len(Code_text_2[c]) st_delka_2_2 = 0 for letter, p in zip(vsm2.letters, vsm2.letters_rel_freq): st_delka_2_2 += p * Code_delky_2[letter] print(f"Stredni delka kodu pro soubor 2, kterou jsme získali aplikací Huffmanova algoritmu na první text, je {st_delka_2}") print(f"Stredni delka kodu pro soubor 2, kterou jsme získali po vzájemném nahrazení kódů, jak je uvedeno výše {st_delka_2_2}")

Vidíme, že jsme dostali nižší hodnotu, než byla. Můžeme tedy usoudit, že předchozí kód С nebyl pro druhý text optimální.

Můžeme se také podivat, jakou střední délku kódu získáme, pokud pro druhý text, jestli použijeme Huffmanův algoritmus.

hf_2 = Huffman(Darnost) hf_2.create_code(vsm2)

hf_2.Code

Code_delky_2_hf = dict() for c in hf_2.Code: Code_delky_2_hf[c] = len(hf_2.Code[c]) st_delka_2_2_hf = 0 for letter, p in zip(vsm2.letters, vsm2.letters_rel_freq): st_delka_2_2_hf+= p * Code_delky_2_hf[letter] print(f"Stredni delka kodu pro soubor 2 (Huffman pro soubor 1) {st_delka_2}") print(f"Stredni delka kodu pro soubor 2 (Huffman pro soubor 2) {st_delka_2_2_hf}")

Vidíme, že se střední délka kódu zmenšila, což může opět potvrdit, že předchozí kód C nebyl pro druhý text optimální.

.css-hdxizt{color:var(--chakra-colors-fg-neutral-primary);font-weight:var(--chakra-fontWeights-bold);letter-spacing:-0.09px;}Data a parametry

Nastavení

Výsledky pro první text

Výsledky pro druhý text

2. Pro každý text zvlášť spočtěte entropii odhadnutého rozdělení znaků.

Výsledky pro první text

Výsledky pro druhý text

3. Nalezněte optimální binární instantní kód .css-1oyr43u{color:var(--chakra-colors-fg-neutral-primary);font-style:italic;font-weight:inherit;letter-spacing:-0.09px;}C pro kódování znaků prvního z textů.

Realizace

Binární Huffmanův kód

4. Pro každý text zvlášť spočtěte střední délku kódu C a porovnejte ji s entropií rozdělení znaků. Je kód C optimální i pro druhý text?

Data a parametry

3. Nalezněte optimální binární instantní kód C pro kódování znaků prvního z textů.