# -*- coding: utf-8 -*-
import codecs,sys
import re, string, random, glob, operator, heapq
from collections import defaultdict
import sys
from collections import Counter
from math import log10
alphabet =[u'\u0901', u'\u0903', u'\u0902', u'\u0905', u'\u0907', u'\u0906', u'\u0909', u'\u0908', u'\u090b', u'\u090a', u'\u090d', u'\u090f', u'\u090e', u'\u0911', u'\u0910', u'\u0913', u'\u0915', u'\u0914', u'\u0917', u'\u0916', u'\u0919', u'\u0918', u'\u091b', u'\u091a', u'\u091d', u'\u091c', u'\u091f', u'\u091e', u'\u0921', u'\u0920', u'\u0923', u'\u0922', u'\u0925', u'\u0924', u'\u0927', u'\u0926', u'\u0929', u'\u0928', u'\u092b', u'\u092a', u'\u092d', u'\u092c', u'\u092f', u'\u092e', u'\u0931', u'\u0930', u'\u0933', u'\u0932', u'\u0935', u'\u0937', u'\u0936', u'\u0939', u'\u0938', u'\u093d', u'\u093c', u'\u093f', u'\u093e', u'\u0941', u'\u0940', u'\u0943', u'\u0942', u'\u0945', u'\u0947', u'\u0949', u'\u0948', u'\u094b', u'\u094a', u'\u094d', u'\u094c', u'\u0950', u'\u0959', u'\u0958', u'\u095b', u'\u095a', u'\u095d', u'\u095c', u'\u095e', u'\u0964', u'\u0970']
writefile2 = 'spellans'
w2 = codecs.open(writefile2,'w','utf-8')


readfile1 = 'final_non-word.txt'
r1 = codecs.open(readfile1,'r','utf-8')

def test(verbose=None):
    """Run some tests, taken from the chapter.
    Since the hillclimbing algorithm is randomized, some tests may fail."""
    import doctest
    print 'Running tests...'
    doctest.testfile('ngrams-test.txt', verbose=verbose)

################ Word Segmentation (p. 223)

#### Support functions (p. 224)



def product(nums):
    "Return the product of a sequence of numbers."
    return reduce(operator.mul, nums, 1)

class Pdist(dict):
    "A probability distribution estimated from counts in datafile."
    def __init__(self, data=[], N=None, missingfn=None):
        for key,count in data:
			key=key.decode('utf-8')
			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): 
		#key=key.decode('utf-8')
		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."
    for line in file(name):
        yield line.split(sep)

def avoid_long_words(key, N):
    "Estimate the probability of an unknown word."
    return 10./(N * 10**len(key))

N = 1024908267229 ## Number of tokens

Pw  = Pdist(datafile('unigram_corpus_pruned.txt'), N, avoid_long_words)
P2w = Pdist(datafile('bigram_corpus_pruned.txt'), N)
print 'Pw computed'
#for p in Pw:
#	print p,Pw[p]
#### segment2: second version, with bigram counts, (p. 226-227)

###### spell corrector ###################33

def corrections(text): 
    "Spell-correct all words in text." 
    return re.sub('[\u0900-\u0970]+', lambda m: correct(m.group(0)), text) 

def correct(w): 
    #"Return the word that is the most likely spell correction of w.",w 
    candidates = edits(w).items()
    if candidates:
		c, edit = max(candidates, key=lambda (c,e): Pedit(e) * (P2w(c)+Pw(c))) 
		return c
    else: 
		return w

def Pedit(edit): 
    "The probability of an edit; can be '' or 'a|b' or 'a|b+c|d'."
    if edit == '': return (1. - p_spell_error) 
    prob =  p_spell_error*product(P1edit(e) for e in edit.split('+'))
    return prob

p_spell_error = 1./20. 

P1edit = Pdist(datafile('confusionmatrix.txt')) ## Probabilities of single edits 

def edits(word, d=2): 
    "Return a dict of {correct: edit} pairs within d edits of word." 
    results = {} 
    def editsR(hd, tl, d, edits):
        def ed(L,R): return edits+[R+'|'+L] 
        C = hd+tl
        
        if C in Pw:
			e = '+'.join(edits)
			if C not in results: results[C] = e
			else: results[C] = max(results[C], e, key=Pedit)
	elif C in P2w:
			e = '+'.join(edits)
			if C not in results: results[C] = e
			else: results[C] = max(results[C], e, key=Pedit)
                    
        if d <= 0: return
        #print edits  
        extensions = [hd+c for c in alphabet if hd+c in PREFIXES]
         
        p = (hd[-1] if hd else '<') ## previous character 
        ## Insertion 
        for h in extensions: 
            editsR(h, tl, d-1, ed(p+h[-1], p)) 
        if not tl: return 
        ## Deletion 
        editsR(hd, tl[1:], d-1, ed(p, p+tl[0])) 
        for h in extensions: 
            if h[-1] == tl[0]: ## Match 
                editsR(h, tl[1:], d, edits) 
            else: ## Replacement 
                editsR(h, tl[1:], d-1, ed(h[-1], tl[0])) 

    ## Body of edits: 
    editsR('', word, d, []) 
    return results 

PREFIXES = set(w[:i] for w in Pw for i in range(len(w) + 1)) 


for w in r1:
	w=w.strip('\n')
	ans = correct(w);
	out=ans
	print>>w2,out
	
