W praktycznych aplikacjach rozwiązania mogą być inne.
# -*- 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).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.