from collections import Counter
from string import ascii_lowercase
from matplotlib import pyplot as plt
import seaborn as sns
import pandas as pd
import scipy as sp
def read_file_text(filename):
f = open(filename, 'r')
lines = f.readlines()
return lines[-1]
def probability_dict(text):
all_char_count = len(text)
counter = Counter(text)
prob = {}
ascii_lowercase_with_space = list(ascii_lowercase + ' ')
for letter in ascii_lowercase_with_space:
prob[letter] = counter[letter] / all_char_count
return prob
x_filename = './input/017.txt'
y_filename = './input/006.txt'
x_text = read_file_text(x_filename)
y_text = read_file_text(y_filename)
x_prob = probability_dict(x_text)
y_prob = probability_dict(y_text)
fig, ax = plt.subplots(nrows=1, ncols=2, sharex=True, figsize=(20,5))
sns.barplot(x=list(x_prob.keys()), y=list(x_prob.values()), ax=ax[0]).set_title('Pravděpodobnost znaků v textu X')
sns.barplot(x=list(y_prob.keys()), y=list(y_prob.values()), ax=ax[1]).set_title('Pravděpodobnost znaků v textu Y')
x_entropy = sp.stats.entropy(list(x_prob.values()), base=2)
y_entropy = sp.stats.entropy(list(y_prob.values()), base=2)
print(f'Entropie rozdělení znaků v textu X je {round(x_entropy, 5)}')
print(f'Entropie rozdělení znaků v textu Y je {round(y_entropy, 5)}.')
Entropie rozdělení znaků v textu X je 4.07772
Entropie rozdělení znaků v textu Y je 4.08502.
# algorithm source: https://www.programiz.com/dsa/huffman-coding
def huffman_code_tree(node, binString):
if type(node) is str:
return {node: binString}
d = {}
d.update(huffman_code_tree(node[0], binString + '0'))
d.update(huffman_code_tree(node[1], binString + '1'))
return d
def create_huffman_code(prob_dict):
nodes = sorted(x_prob.items(), key=lambda x: x[1], reverse=True)
while len(nodes) > 1:
(ch1, c1) = nodes[-1]
(ch2, c2) = nodes[-2]
nodes = nodes[:-2]
node = (ch1, ch2)
nodes.append((node, c1 + c2))
nodes = sorted(nodes, key=lambda x: x[1], reverse=True)
return huffman_code_tree(nodes[0][0], '')
def print_huffman_code(huffman_code):
sorted_huffman_code = sorted(huffman_code.items(), key=lambda x: len(x[1]))
print(' Písmeno | Kódové slovo ')
print('--------------------------')
for (char, frequency) in sorted_huffman_code:
print(' %-7r |%15s' % (char, huffman_code[char]))
x_huffman_code = create_huffman_code(x_prob)
print_huffman_code(x_huffman_code)
Písmeno | Kódové slovo
--------------------------
'e' | 001
' ' | 111
'r' | 0001
'h' | 0100
'n' | 0110
's' | 0111
'i' | 1000
'o' | 1001
'a' | 1010
't' | 1100
'm' | 00000
'd' | 01010
'u' | 01011
'l' | 11010
'p' | 000010
'b' | 000011
'g' | 101100
'w' | 101110
'y' | 101111
'c' | 110110
'f' | 110111
'v' | 1011010
'k' | 10110111
'x' | 101101101
'j' | 1011011001
'z' | 10110110000
'q' | 10110110001
def expected_code_length(code, prob):
lenght = 0
for ch, code in code.items():
lenght += len(code) * prob[ch]
return lenght
x_length = expected_code_length(x_huffman_code, x_prob)
y_length = expected_code_length(x_huffman_code, y_prob)
print(f'Srovnání dolní a horní meze pro dokument X: {round(x_entropy, 4)} <= {round(x_length, 4)} < {round(x_entropy + 1, 4)} (splňuje podmínku optimálního kódu)')
print(f'Srovnání dolní a horní meze pro dokument Y: {round(y_entropy, 4)} <= {round(y_length, 4)} < {round(y_entropy + 1, 4)} (splňuje podmínku optimálního kódu)')
Srovnání dolní a horní meze pro dokument X: 4.0777 <= 4.1213 < 5.0777 (splňuje podmínku optimálního kódu)
Srovnání dolní a horní meze pro dokument Y: 4.085 <= 4.1355 < 5.085 (splňuje podmínku optimálního kódu)