import random, string, sys

def random_word(h):
    words = h.keys();  sum = 0;  cum = []
    for word in words:  sum += h[word];  cum.append(sum)
    num = random.randint(1, cum[-1]); low = 0; high = len(cum)-1
    while low < high:
        mid = (low+high) / 2
        if num <= cum[mid]:  high = mid
        elif num > cum[mid]:  low = mid+1
    return words[low]

def read_words(filename, marker):
  words = []
  f = open(filename, "r")
  start = marker == None
  for line in f.readlines():
    if not start:
      if marker != None and line[:len(marker)] == marker:
        start = True
    else:
      if marker != None and line[:len(marker)] == marker:
        break
      words.extend(line.lower().translate(None, string.punctuation).split())
  return words

def histogram(words):
  d = {}
  for word in words:
    if not word in d:
      d[word] = 0
    d[word] += 1
  return d

def most_common(h):
  t = []
  for key, val in h.items():
    t.append((val, key))
  t.sort(reverse=True)
  return t

def print_most_common(hist, num = 10):
    t = most_common(hist)
    print "The most common", num, "words are:"
    for n, word in t[:num]:
        print word, "\t", n

def subtract(d1, d2):
    d = {}
    for key in d1:
        if key not in d2:
            d[key] = None
    return d

def random_word_slow(h):
    t = []
    for word, n in h.items():
        t.extend([word] * n)
    return random.choice(t)

def markov_analysis(words, prefix_length = 2):
  d = {}
  t = []
  for i in range(prefix_length):
    t.append(words[i:])
  for t in zip(*t):
    prefix = t[:-1]
    suffix = t[-1]
    if not prefix in d:
      d[prefix] = {}
    e = d[prefix]
    if not suffix in e:
      e[suffix] = 0
    e[suffix] += 1
  return d

def markov_analysis_ugly(words, prefix_length = 2):
  d = {}
  index = 0
  while index + prefix_length < len(words):
    prefix = tuple(words[index:index+prefix_length])
    suffix = words[index+prefix_length]
    if not prefix in d:
      d[prefix] = {}
    e = d[prefix]
    if not suffix in e:
      e[suffix] = 0
    e[suffix] += 1
    index += 1
  return d

words = read_words(sys.argv[1], "***")
freq = histogram(words)
print "Total words:", len(words)
print "Number of different words:", len(freq)
print_most_common(freq, 20)

wordlist = read_words(sys.argv[2], None)
wh = histogram(wordlist)
for key in subtract(freq, wh):
  print key

for i in range(10):
  print random_word(freq),

markov = markov_analysis(words, 100)

prefix = random.choice(markov.keys())
for i in range(10):
  print prefix[0]
  suffix = random_word(markov[prefix])
  prefix = prefix[1:] + (suffix,)