Solved 2014 challenges 1 and 2
[cipher-training.git] / language_models.py
1 """Language-specific functions, including models of languages based on data of
2 its use.
3 """
4
5 import string
6 import random
7 import norms
8 import collections
9 import unicodedata
10 import itertools
11 from math import log10
12
13 def letters(text):
14 """Remove all non-alphabetic characters from a text
15 >>> letters('The Quick')
16 'TheQuick'
17 >>> letters('The Quick BROWN fox jumped! over... the (9lazy) DOG')
18 'TheQuickBROWNfoxjumpedoverthelazyDOG'
19 """
20 return ''.join([c for c in text if c in string.ascii_letters])
21
22 def unaccent(text):
23 """Remove all accents from letters.
24 It does this by converting the unicode string to decomposed compatability
25 form, dropping all the combining accents, then re-encoding the bytes.
26
27 >>> unaccent('hello')
28 'hello'
29 >>> unaccent('HELLO')
30 'HELLO'
31 >>> unaccent('héllo')
32 'hello'
33 >>> unaccent('héllö')
34 'hello'
35 >>> unaccent('HÉLLÖ')
36 'HELLO'
37 """
38 return unicodedata.normalize('NFKD', text).\
39 encode('ascii', 'ignore').\
40 decode('utf-8')
41
42 def sanitise(text):
43 """Remove all non-alphabetic characters and convert the text to lowercase
44
45 >>> sanitise('The Quick')
46 'thequick'
47 >>> sanitise('The Quick BROWN fox jumped! over... the (9lazy) DOG')
48 'thequickbrownfoxjumpedoverthelazydog'
49 >>> sanitise('HÉLLÖ')
50 'hello'
51 """
52 # sanitised = [c.lower() for c in text if c in string.ascii_letters]
53 # return ''.join(sanitised)
54 return letters(unaccent(text)).lower()
55
56
57 def datafile(name, sep='\t'):
58 """Read key,value pairs from file.
59 """
60 with open(name, 'r') as f:
61 for line in f:
62 splits = line.split(sep)
63 yield [splits[0], int(splits[1])]
64
65 english_counts = collections.Counter(dict(datafile('count_1l.txt')))
66 normalised_english_counts = norms.normalise(english_counts)
67
68 english_bigram_counts = collections.Counter(dict(datafile('count_2l.txt')))
69 normalised_english_bigram_counts = norms.normalise(english_bigram_counts)
70
71 english_trigram_counts = collections.Counter(dict(datafile('count_3l.txt')))
72 normalised_english_trigram_counts = norms.normalise(english_trigram_counts)
73
74 with open('words.txt', 'r') as f:
75 keywords = [line.rstrip() for line in f]
76
77
78 def weighted_choice(d):
79 """Generate random item from a dictionary of item counts
80 """
81 target = random.uniform(0, sum(d.values()))
82 cuml = 0.0
83 for (l, p) in d.items():
84 cuml += p
85 if cuml > target:
86 return l
87 return None
88
89 def random_english_letter():
90 """Generate a random letter based on English letter counts
91 """
92 return weighted_choice(normalised_english_counts)
93
94
95 def ngrams(text, n):
96 """Returns all n-grams of a text
97
98 >>> ngrams(sanitise('the quick brown fox'), 2) # doctest: +NORMALIZE_WHITESPACE
99 ['th', 'he', 'eq', 'qu', 'ui', 'ic', 'ck', 'kb', 'br', 'ro', 'ow', 'wn',
100 'nf', 'fo', 'ox']
101 >>> ngrams(sanitise('the quick brown fox'), 4) # doctest: +NORMALIZE_WHITESPACE
102 ['theq', 'hequ', 'equi', 'quic', 'uick', 'ickb', 'ckbr', 'kbro', 'brow',
103 'rown', 'ownf', 'wnfo', 'nfox']
104 """
105 return [text[i:i+n] for i in range(len(text)-n+1)]
106
107
108 class Pdist(dict):
109 """A probability distribution estimated from counts in datafile.
110 Values are stored and returned as log probabilities.
111 """
112 def __init__(self, data=[], estimate_of_missing=None):
113 data1, data2 = itertools.tee(data)
114 self.total = sum([d[1] for d in data1])
115 for key, count in data2:
116 self[key] = log10(count / self.total)
117 self.estimate_of_missing = estimate_of_missing or (lambda k, N: 1./N)
118 def __missing__(self, key):
119 return self.estimate_of_missing(key, self.total)
120
121 def log_probability_of_unknown_word(key, N):
122 """Estimate the probability of an unknown word.
123 """
124 return -log10(N * 10**((len(key) - 2) * 1.4))
125
126 Pw = Pdist(datafile('count_1w.txt'), log_probability_of_unknown_word)
127 Pw_wrong = Pdist(datafile('count_1w.txt'), lambda _k, N: log10(1/N))
128 Pl = Pdist(datafile('count_1l.txt'), lambda _k, _N: 0)
129 P2l = Pdist(datafile('count_2l.txt'), lambda _k, _N: 0)
130 P3l = Pdist(datafile('count_3l.txt'), lambda _k, _N: 0)
131
132 def Pwords(words):
133 """The Naive Bayes log probability of a sequence of words.
134 """
135 return sum(Pw[w.lower()] for w in words)
136
137 def Pwords_wrong(words):
138 """The Naive Bayes log probability of a sequence of words.
139 """
140 return sum(Pw_wrong[w.lower()] for w in words)
141
142 def Pletters(letters):
143 """The Naive Bayes log probability of a sequence of letters.
144 """
145 return sum(Pl[l.lower()] for l in letters)
146
147 def Pbigrams(letters):
148 """The Naive Bayes log probability of the bigrams formed from a sequence
149 of letters.
150 """
151 return sum(P2l[p] for p in ngrams(letters, 2))
152
153 def Ptrigrams(letters):
154 """The Naive Bayes log probability of the trigrams formed from a sequence
155 of letters.
156 """
157 return sum(P3l[p] for p in ngrams(letters, 3))
158
159
160 def cosine_similarity_score(text):
161 """Finds the dissimilarity of a text to English, using the cosine distance
162 of the frequency distribution.
163
164 >>> cosine_similarity_score('abcabc') # doctest: +ELLIPSIS
165 0.26228882...
166 """
167 return norms.cosine_similarity(english_counts,
168 collections.Counter(sanitise(text)))
169
170
171 if __name__ == "__main__":
172 import doctest
173 doctest.testmod()