2022¶

Ανισότητα Kraft¶

Ανισότητα Kraft για αντιστρέψιμους κώδικες: $$\sum_{i=1}^n 2^{-\ell_i} \le 1,$$όπου $\ell_i$ το μήκος (πλήθος δυαδικών ψηφίων) της λέξης $c_i$ του κώδικα $C = \{c_1, c_2, \ldots, c_n\}$. Δείτε την απόδειξη στο [MacK 5.2].
Αντίστροφα: αν έχουμε φυσικούς αριθμούς $\ell_1, \ldots, \ell_n$ τέτοιυς ώστε να ισχύει η ανισότητα του Kraft τότε μπορούμε να βρούμε έναν prefix κώδικα $C$ με αυτά τα μήκη. Στο μάθημα είδαμε με ένα παράδειγμα πώς κατασκευάζουμε ένα τέτοιο prefix κώδικα $C$ με δοσμένα τα $\ell_i$. Μπορείτε να δείτε τη μέθοδο και στο [MacK 5.2].
Το μέσο μήκος ενο κώδικα $C$, που το συμβολίζουμε με $L(C)$ είναι η ποσότητα $$L(C) = \sum_{j=1}^n p_j \ell_j,$$ και είναι ίσο με το $\mathbb{E}(c(X))$ όπου $X$ είναι μια ΤΜ που παίρνει ως τιμές τα σύμβολα του αλφαβήτου (που κωδικοποιείται με τον κώδικα $C$) με τις αντίστοιχες πιθανότητες. Αντιπροσωπεύει το μέσο κόστος σε δυαδικά bits ενός συμβόλου του αλφαβήτου όταν αυτό κωδικοποιείται με τον $C$.

Source coding theorem¶

Source coding theorem: Για κάθε αντιστρέψιμο κώδικα $C$ ισχύει $L(C) \ge H(X)$, όπου $X$ είναι μια ΤΜ που παίρνει ως τιμές τα γράμματα του αλφαβήτου που κωδικοποιούμε με τις αντίστοιχες πιθανότητες $p_j$. Επίσης μπορούμε πάντα να βρούμε ένα prefix κώδικα $C$ για τον οποίο ισχύει $L(C) \le H(X)+1$.
Δείξαμε μόνο το κάτω φράγμα για το $L(C)$, χρησιμοποιώντας τις ανισότητες Gibbs και Kraft. Διαβάστε από [MacK 5.3].
Είδαμε την κατασκευή των Huffman codes όπως περιγράφεται στο [MacK 5.5]. Επίσης είδαμε την περιγραφή της μεθόδου εδώ. Πήραμε τον κώδικα σε python (δείτε παρακάτω) από τη σελίδα αυτή και τον συμπληρώσαμε με τις συναρτήσεις encode και decode, που κωδικοποιούν μια λέξη με το δεδομένα Huffman κώδικα και την αποκωδικοποιούν.

# Huffman Coding in python -- code from https://www.programiz.com/dsa/huffman-coding

string = 'BCAADDDCCACACACEEFFFGGGGGCCCCCCCCCCCCCCCCCCCCCC' # από εδώ παίρνουμε τις συχνότητες των γραμμάτων


# Creating tree nodes
class NodeTree(object):

    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def children(self):
        return (self.left, self.right)

    def nodes(self):
        return (self.left, self.right)

    def __str__(self):
        return '%s_%s' % (self.left, self.right)


# Main function implementing huffman coding
def huffman_code_tree(node, left=True, binString=''):
    if type(node) is str:
        return {node: binString}
    (l, r) = node.children()
    d = dict()
    d.update(huffman_code_tree(l, True, binString + '0'))
    d.update(huffman_code_tree(r, False, binString + '1'))
    return d


# Calculating frequency
freq = {}
for c in string:
    if c in freq:
        freq[c] += 1
    else:
        freq[c] = 1

freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)

nodes = freq

while len(nodes) > 1:
    (key1, c1) = nodes[-1]
    (key2, c2) = nodes[-2]
    nodes = nodes[:-2]
    node = NodeTree(key1, key2)
    nodes.append((node, c1 + c2))

    nodes = sorted(nodes, key=lambda x: x[1], reverse=True)

huffmanCode = huffman_code_tree(nodes[0][0])

print(' Char | Huffman code ')
print('----------------------')
for (char, frequency) in freq:
    print(' %-4r |%12s' % (char, huffmanCode[char]))

 Char | Huffman code 
----------------------
 'C'  |           1
 'A'  |         010
 'G'  |         001
 'D'  |         000
 'F'  |        0111
 'E'  |       01101
 'B'  |       01100

Ακολουθούν οι δύο συναρτήσεις encode και decode που γράψαμε στο μάθημα για την κωδικοποίηση και αποκωδικοποίηση μιας λέξης. Σημειωτέον ότι κατά κανόνα κωδικοποιούμε μια λέξη με τον κώδικα Huffman που φτιάξαμε από την ίδια τη λέξη αυτή. Δεν κάνουμε δηλ. αυτό που κάναμε παρακάτω το οποίο ως μόνο σκοπό του έχει να ελέγξει ότι οι δύο συναρτήσεις δουλεύουν σωστά.

def encode(word, hc): # Κωδικοποιούμε μια λέξη με τον κώδικα Huffman hc (σε μορφή dictionary όπως παραπάνω)
    s=''
    for a in word:
        s += hc[a]
    return s


def decode(codeword, hc): # Αποκωδικοποιούμε τη λέξη. Λειτουργεί αναδρομικά.
    if codeword=='': return ''
    for i in range(len(codeword)):
        c = codeword[:i+1]
        for symbol in hc.keys():
            if hc[symbol] == c:
                return symbol + decode(codeword[i+1:], hc)
        continue


# Δοκιμάζουμε τις συναρτήσεις encode και decode. Βεβαιωνόμαστε ότι η λέξη που προκύπτει από το decode
# είναι η αρχική
ee = encode('ABCDDBADDEFFFFFF', huffmanCode) 
print(ee)
print(decode(ee, huffmanCode))

0100110010000000110001000000001101011101110111011101110111
ABCDDBADDEFFFFFF