Multimediální technologie – Cvičení 6

Zadání

  1. Vytvořte algoritmus pro RLE kódování a dekódování znaků v datovém souboru Cv06_RLE_data.bin, kde jsou jednotlivá čísla uložena jako uint8. Slovník dat je 5 čísel: 1, 2, 3, 4, 5.
  2. Naprogramujte kompresní a dekompresní metodu pomocí algoritmu Huffmanova kódování a komprimujte a dekomprimujte její pomocí data (čísla) v souboru Cv05_LZW_data.bin, kde jsou jednotlivá čísla uložena jako uint8. Slovník dat je 5 čísel: 1, 2, 3, 4, 5.

Soubory


Řešení

RLE kódování

# -*- coding: utf-8 -*-
import os
import numpy as np
import matplotlib.pyplot as plt

clear = lambda: os.system('cls')
clear()
plt.close('all')

def compress(data):
    result = []
    count = 1
    prev = ''

    for char in data:
        if char != prev:
            if prev:
                entry = (prev, count)
                result.append(entry)
            count = 1
            prev = char
        else:
            count += 1

    entry = (char, count)
    result.append(entry)

    return result

def decompress(data):
    result = ''

    for char, count in data:
        result += char * count

    return result

def readFile(file_name):
    data = np.zeros

    with open(file_name,'rb') as file:
        data = np.fromfile(file, dtype=np.uint8)

    return data

def getStringData(fileData):
    result = ''

    for c in fileData:
        result += str(c)

    result = "".join(result)

    return result

def main():
    fileData = readFile('Cv06_RLE_data.bin')

    stringData = getStringData(fileData)
    print 'Original data: {0}'.format(stringData)

    compressed = compress(stringData)
    print 'Komprimovaná data: {0}'.format(compressed)

    decompressed = decompress(compressed)
    print 'Dekomprimovaná data: {0}'.format(decompressed)

if __name__ == "__main__":
    main()

Huffmanovo kódování

# -*- coding: utf-8 -*-
import os
import numpy as np
import matplotlib.pyplot as plt

clear = lambda: os.system('cls')
clear()
plt.close('all')

class Tree:
    def __init__(self, char, freq, left, right):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right

    def __gt__(self, node):
        return self.freq > node.freq

    def dictionary(self):
        codes = {}

        def traversal(item, code):
            if item != None:
                traversal(item.left, code + '0')

                if item.char != None:
                    codes[item.char] = code

                traversal(item.right, code + '1')

        traversal(self, '')

        return codes

class Queue:
    def __init__(self):
        self.queue = []

    def put(self, item):
        self.queue.append(item)
        self.queue.sort(reverse=True)

    def get(self):
        return self.queue.pop()

def Huffman(freqs):
    queue = Queue()
    items = {Tree(freq, freqs[freq], None, None) for freq in freqs}

    for item in items:
        queue.put(item)

    for i in range(len(freqs)-1):
        left = queue.get()
        right = queue.get()
        newNode = Tree(None, left.freq + right.freq, left, right)
        queue.put(newNode)

    return queue.get().dictionary()

def compress(data, dictionary):
    return ''.join(dictionary[char] for char in data)

def decompress(data, decodeDictionary):
    codeword = ''
    result = ''

    for i in range(len(data)):
        codeword += data[i]
        if codeword in decodeDictionary:
            result += decodeDictionary[codeword]
            codeword = ''

    return result

def getDecodeDictionary(dictionary):
    return {v:k for k, v in dictionary.items()}

def readFile(file_name):
    data = np.zeros

    with open(file_name,'rb') as file:
        data = np.fromfile(file, dtype=np.uint8)

    return data

def getStringData(fileData):
    result = ''

    for c in fileData:
        result += str(c)

    result = "".join(result)

    return result

def getCountOfUnique(text):
    from collections import OrderedDict
    unique  = "".join(OrderedDict.fromkeys(text))

    num = 0

    for c in unique:
        num += 1

    return num+1

def main():
    fileData = readFile('Cv05_LZW_data.bin')

    stringData = getStringData(fileData)
    print 'Original data: {0}'.format(stringData)

    uniqueChars = getCountOfUnique(stringData)
    print 'Počet unikátních zaků: {0}'.format(uniqueChars)

    freqs = {'1' : 001, '2' : 010, '3' : 011, '4' : 100, '5' : 101}
    dictionary = Huffman(freqs)

    compressed = compress(stringData, dictionary)
    print 'Komprimovaná data: {0}'.format(compressed)

    decompressed = decompress(compressed, getDecodeDictionary(dictionary))
    print 'Dekomprimovaná data: {0}'.format(decompressed)

if __name__ == "__main__":
    main()

You may also like...

Napsat komentář

Vaše emailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *