'''
PPM-C
'''
import math
import sys
import requests

username = sys.argv[-1]
k = 3


address ="http://multi6.aladdin.cs.cmu.edu:3001/algoreal"
response = requests.get(address, params={"andrew": username})
str = response.text
emissions = []

tables = [{} for i in range(0, k + 1)]

tables[0] = {'': {}}

def incr_count(c, context):
	ctxlength = len(context)
	if context not in tables[ctxlength]:
		tables[ctxlength][context] = {}
	if c in tables[ctxlength][context]:
		count = tables[ctxlength][context][c] + 1
	else:
		count = 1
	tables[ctxlength][context][c] = count

def update_tables(c, context):
	for i in xrange(0, len(context) + 1):
		incr_count(c, context[i:])


def prob(c, table, omits):
	modtable = table.copy()
	for o in omits:
		modtable.pop(o, None)
	escapecount = len(modtable.keys())
	fullcount = sum(modtable.values()) + escapecount
	if c != None:
		charcount = modtable[c]
	else:
		charcount = escapecount  # Escape is when c=None
	if charcount == fullcount:
		return 1    # Implicit
	return float(charcount) / fullcount

def emit(c, p):
	if c == None:
		c = "<$>"
	if p < 1:
		emissions.append((c, p))

def encode(c, fullcontext):
	omits = set([])
	success = False
	for j in xrange(0, len(fullcontext) + 1):
		context = fullcontext[j:]
		ctxlength = len(context)
		if context in tables[ctxlength]:
			if c in tables[ctxlength][context]:
				emit(c, prob(c, tables[ctxlength][context], omits))
				success = True
				break
			else:
				# escape
				emit(None, prob(None, tables[ctxlength][context], omits))
				omits = omits.union(tables[ctxlength][context].keys())  # Include to omits
		else:
			# Context not found - so no need to emit anything
			continue
	if not success:
		# Previously unseen key
		emit(c, 1.0 / (256 - len(tables[0][''].keys())))

	update_tables(c, fullcontext)




for i in xrange(0, len(str)):
	encode(str[i], str[max(i - k, 0): i])


if k == 3:
    print "-----beginning-----"
    for e in emissions[:12]:
        print "%s,%f" % (e[0], e[1])
    
    print "-----from the end----"
    for e in emissions[-12:]:
        print "%s,%f" % (e[0], e[1])
	
#print "k=%d: Total bits %f" % (k, sum(-math.log(e[1])/math.log(2) for e in emissions))


# With spaces removes
for k in xrange(1, 6):
    emissions = []
    tables = [{} for i in range(0, k + 1)]
    
    tables[0] = {'': {}}
    for i in xrange(0, len(str)):
        encode(str[i], str[max(i - k, 0): i])
    print "k=%d Total bits  %f" % (k, sum(-math.log(e[1])/math.log(2) for e in emissions))