# -*- coding: iso-8859-2 -*-
def LZ78_encode(data):
D = {}
n = 1
c = ''
result = []
for s in data:
if c + s not in D:
if c == '':
# specjalny przypadek: symbol 's'
# nie występuje jeszcze w słowniku
result.append( (0, s) )
D[s] = n
else:
# ciąg 'c' jest w słowniku
result.append( (D[c], s) )
D[c + s] = n
n = n + 1
c = ''
else:
c = c + s
return result
def LZ78_decode(data):
D = {}
n = 1
result = []
for i, s in data:
if i == 0:
result.append(s)
D[n] = s
n = n + 1
else:
result.append(D[i] + s)
D[n] = D[i] + s
n = n + 1
return ''.join(result)
if __name__ == '__main__':
import sys
from math import log, ceil
if len(sys.argv) < 2:
print "Podaj nazwę pliku"
sys.exit(1)
data = open(sys.argv[1]).read()
comp = LZ78_encode(data)
decomp = LZ78_decode(comp)
if data == decomp:
k = len(comp)
n = int(ceil(log(max(index for index, symbol in comp), 2.0)))
l1 = len(data)
l2 = (k*(n+8) + 7)/8
print "Liczba par: %d" % k
print "Maks. liczba bitów potrzebna do zapisania kodu: %d" % n
print "Maks. liczba bitów potrzebna do zapisania pary: %d + %d = %d" % (n, 8, n+8)
print "Rozmiar danych wejściowych: %d bajtów" % l1
print "Rozmiar danych skompresowanych: %d bajtów" % l2
print "Stopień kompresji: %.2f%%" % (100.0*(l1-l2)/l1)
# print data
# print decomp
else:
print "Wystąpił jakiś błąd!"