# -*- coding: iso-8859-2 -*- 
# wm, 01.02.2007

db = 13
bb = 16-db
nd = 2**db	# rozmiar słownika
nb = 2**bb	# rozmiar bufora (wejściowego/wyjściowego)

def best_match(dictionary, buffer):
	n = len(buffer)
	assert n > 0

	for k in xrange(n-1, 0, -1):
		tmp   = buffer[:k]
		index = dictionary.find(tmp)
		if -1 < index:
			return (index, k)
	return (0, 0)


def LZ77_encode(data):
	assert len(data) > nb

	a = data[0]

	data       = data[1:]
	dictionary = a*nd
	result     = []
	while data:
		(P, C) = best_match(dictionary, data[:nb])
		result.append( (P, C, data[C]) )
		
		S = min(C + 1, len(data))
	
		dictionary = dictionary[C+1:] + data[:S]
		data   = data[S:]

	return (a, result)


def LZ77_decode(fs, data):
	result = [fs]
	buffer = fs*nd
	for P, C, S in data:
		assert P+C <= nd, (P+C, nd)
		tmp = buffer[P:P+C] + S
		result.append(tmp)

		buffer = buffer[C+1:] + tmp

	return ''.join(result)

def compare(s1, s2):
	for i in xrange(min(len(s1), len(s2))):
		if s1[i] != s2[i]:
			break
	return i

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   = LZ77_encode(data)
	decomp = LZ77_decode(*comp)

	if data == decomp:
		k  = len(comp[1])
		n  = bb + db + 8

		l1 = len(data)
		l2 = (k*n + 7)/8 + 8

		print "Liczba trójek: %d" % k
		print "Liczba bitów potrzebna do zapisania trójki: %d" % n
		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!"