import string
import collections
from math import log10
+import itertools
+import sys
+from functools import lru_cache
+sys.setrecursionlimit(1000000)
-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
-
-@memo
+@lru_cache()
def segment(text):
"""Return a list of words that is the best segmentation of text.
"""
if not text: return []
- candidates = ([first]+segment(rem) for first,rem in splits(text))
+ candidates = ([first]+segment(rest) for first,rest in splits(text))
return max(candidates, key=Pwords)
def splits(text, L=20):
def Pwords(words):
"""The Naive Bayes log probability of a sequence of words.
"""
- return sum(Pw(w) for w in words)
+ return sum(Pw[w.lower()] for w in words)
class Pdist(dict):
"""A probability distribution estimated from counts in datafile.
Values are stored and returned as log probabilities.
"""
def __init__(self, data=[], estimate_of_missing=None):
- self.total = sum([int(d[1]) for d in data])
- for key, count in data:
+ data1, data2 = itertools.tee(data)
+ self.total = sum([int(d[1]) for d in data1])
+ for key, count in data2:
self[key] = log10(int(count) / self.total)
self.estimate_of_missing = estimate_of_missing or (lambda k, N: 1./N)
- def __call__(self, key):
- if key in self:
- return self[key]
- else:
- return self.estimate_of_missing(key, self.total)
+ def __missing__(self, key):
+ return self.estimate_of_missing(key, self.total)
def datafile(name, sep='\t'):
"""Read key,value pairs from file.
"""
return -log10((N * 10**(len(key) - 2)))
-N = 1024908267229 ## Number of tokens
-
Pw = Pdist(datafile('count_1w.txt'), avoid_long_words)
+