# -*- coding: utf-8 -*-
from __future__ import unicode_literals
import unicodedata
import re
import codecs
import  operator
L=20
#longest word length is found to be 132 in corpus
def product(nums):
    "Return the product of a number sequence in the nums."
    return reduce(operator.mul, nums, 1)
def memo(f):
    "Memoize function f."
    table = {}
    def fmemo(*args):
        if args not in table:
            table[args] = f(*args)
        return table[args]
    fmemo.memo = table
    return fmemo
def spliting(text,L=20):
     return [(text[:i+1], text[i+1:]) 
            for i in range(min(len(text), L))]
@memo
def segmentation(text):
    "Return a list of words that is the best segmentation of text."
    if not text: return []
    candidate_set = ([first]+segmentation(rem) for first,rem in spliting(text))
    return max(candidate_set, key=Pwords)
def Pwords(words): 
    "The Naive Bayes probability of a sequence of words."
    return product(Pw(w) for w in words)
###############################################################################
class Pdist(dict):
    "A probability distribution estimated from counts in datafile."
    def __init__(self, data=[], N=None, missingfn=None):
        for key,count in data:
            self[key] = self.get(key, 0) + int(count)
        self.N = float(N or sum(self.itervalues()))
        self.missingfn = missingfn or (lambda k, N: 1./N)
    def __call__(self, key): 
        if key in self: return self[key]/self.N  
        else: return self.missingfn(key, self.N)

def datafile(name, sep='\t'):
    "Read key,value pairs from file."
    wordlist= codecs.open(name, "r", "utf-8")
    vocab=wordlist.readlines()
    for line in vocab:
        yield line.split(sep)
    
def avoid_long_words(key, N):
    "Estimate the probability of an unknown word."
    return 10./(N * 10**len(key))
###########################################################################################
N = 17712719   ## Number of tokens
Pw  = Pdist(datafile('AllignWordFreq_Vishal.txt'), N, avoid_long_words)
#####################################################################
data1 = open('groundtruth3.txt').read()
data1 = data1.decode("utf=8")
data1 = data1.split('\n')
f = open('testDataGt3.txt', 'w')
data = open("groundtruth3Train.txt").read()
data = data.decode("utf=8")
data = data.split('\n')
a=0
for line in data:
	result = segmentation(line)
	for word in result:
		#print word
		word = word.encode("utf=8")
		f.write(word )
		f.write(" ")
	f.write('\t')
	f.write(data1[j].encode("utf=8"))
	f.write("\n")
	a=a+1