Added logging, removed additional implementation of bombe from engima.py
[cipher-training.git] / norms.py
1 import collections
2 from math import log10
3
4 def normalise(frequencies):
5 """Scale a set of frequencies so they sum to one
6
7 >>> sorted(normalise({1: 1, 2: 0}).items())
8 [(1, 1.0), (2, 0.0)]
9 >>> sorted(normalise({1: 1, 2: 1}).items())
10 [(1, 0.5), (2, 0.5)]
11 >>> sorted(normalise({1: 1, 2: 1, 3: 1}).items()) # doctest: +ELLIPSIS
12 [(1, 0.333...), (2, 0.333...), (3, 0.333...)]
13 >>> sorted(normalise({1: 1, 2: 2, 3: 1}).items())
14 [(1, 0.25), (2, 0.5), (3, 0.25)]
15 """
16 length = sum(f for f in frequencies.values())
17 return collections.defaultdict(int, ((k, v / length)
18 for (k, v) in frequencies.items()))
19
20 def euclidean_scale(frequencies):
21 """Scale a set of frequencies so they have a unit euclidean length
22
23 >>> sorted(euclidean_scale({1: 1, 2: 0}).items())
24 [(1, 1.0), (2, 0.0)]
25 >>> sorted(euclidean_scale({1: 1, 2: 1}).items()) # doctest: +ELLIPSIS
26 [(1, 0.7071067...), (2, 0.7071067...)]
27 >>> sorted(euclidean_scale({1: 1, 2: 1, 3: 1}).items()) # doctest: +ELLIPSIS
28 [(1, 0.577350...), (2, 0.577350...), (3, 0.577350...)]
29 >>> sorted(euclidean_scale({1: 1, 2: 2, 3: 1}).items()) # doctest: +ELLIPSIS
30 [(1, 0.408248...), (2, 0.81649658...), (3, 0.408248...)]
31 """
32 length = sum([f ** 2 for f in frequencies.values()]) ** 0.5
33 return collections.defaultdict(int, ((k, v / length)
34 for (k, v) in frequencies.items()))
35
36 def identity_scale(frequencies):
37 return frequencies
38
39
40 def l2(frequencies1, frequencies2):
41 """Finds the distances between two frequency profiles, expressed as dictionaries.
42 Assumes every key in frequencies1 is also in frequencies2
43
44 >>> l2({'a':1, 'b':1, 'c':1}, {'a':1, 'b':1, 'c':1})
45 0.0
46 >>> l2({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1}) # doctest: +ELLIPSIS
47 1.73205080...
48 >>> l2(normalise({'a':2, 'b':2, 'c':2}), normalise({'a':1, 'b':1, 'c':1}))
49 0.0
50 >>> l2({'a':0, 'b':2, 'c':0}, {'a':1, 'b':1, 'c':1}) # doctest: +ELLIPSIS
51 1.732050807...
52 >>> l2(normalise({'a':0, 'b':2, 'c':0}), \
53 normalise({'a':1, 'b':1, 'c':1})) # doctest: +ELLIPSIS
54 0.81649658...
55 >>> l2({'a':0, 'b':1}, {'a':1, 'b':1})
56 1.0
57 """
58 total = 0
59 for k in frequencies1:
60 total += (frequencies1[k] - frequencies2[k]) ** 2
61 return total ** 0.5
62 euclidean_distance = l2
63
64 def l1(frequencies1, frequencies2):
65 """Finds the distances between two frequency profiles, expressed as
66 dictionaries. Assumes every key in frequencies1 is also in frequencies2
67
68 >>> l1({'a':1, 'b':1, 'c':1}, {'a':1, 'b':1, 'c':1})
69 0
70 >>> l1({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1})
71 3
72 >>> l1(normalise({'a':2, 'b':2, 'c':2}), normalise({'a':1, 'b':1, 'c':1}))
73 0.0
74 >>> l1({'a':0, 'b':2, 'c':0}, {'a':1, 'b':1, 'c':1})
75 3
76 >>> l1({'a':0, 'b':1}, {'a':1, 'b':1})
77 1
78 """
79 total = 0
80 for k in frequencies1:
81 total += abs(frequencies1[k] - frequencies2[k])
82 return total
83
84 def l3(frequencies1, frequencies2):
85 """Finds the distances between two frequency profiles, expressed as
86 dictionaries. Assumes every key in frequencies1 is also in frequencies2
87
88 >>> l3({'a':1, 'b':1, 'c':1}, {'a':1, 'b':1, 'c':1})
89 0.0
90 >>> l3({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1}) # doctest: +ELLIPSIS
91 1.44224957...
92 >>> l3({'a':0, 'b':2, 'c':0}, {'a':1, 'b':1, 'c':1}) # doctest: +ELLIPSIS
93 1.4422495703...
94 >>> l3(normalise({'a':0, 'b':2, 'c':0}), \
95 normalise({'a':1, 'b':1, 'c':1})) # doctest: +ELLIPSIS
96 0.718144896...
97 >>> l3({'a':0, 'b':1}, {'a':1, 'b':1})
98 1.0
99 >>> l3(normalise({'a':0, 'b':1}), normalise({'a':1, 'b':1})) # doctest: +ELLIPSIS
100 0.6299605249...
101 """
102 total = 0
103 for k in frequencies1:
104 total += abs(frequencies1[k] - frequencies2[k]) ** 3
105 return total ** (1/3)
106
107 def geometric_mean(frequencies1, frequencies2):
108 """Finds the geometric mean of the absolute differences between two frequency profiles,
109 expressed as dictionaries.
110 Assumes every key in frequencies1 is also in frequencies2
111
112 >>> geometric_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1})
113 1
114 >>> geometric_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1})
115 1
116 >>> geometric_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':5, 'c':1})
117 3
118 >>> geometric_mean(normalise({'a':2, 'b':2, 'c':2}), \
119 normalise({'a':1, 'b':5, 'c':1})) # doctest: +ELLIPSIS
120 0.01382140...
121 >>> geometric_mean(normalise({'a':2, 'b':2, 'c':2}), \
122 normalise({'a':1, 'b':1, 'c':1})) # doctest: +ELLIPSIS
123 0.0
124 >>> geometric_mean(normalise({'a':2, 'b':2, 'c':2}), \
125 normalise({'a':1, 'b':1, 'c':0})) # doctest: +ELLIPSIS
126 0.009259259...
127 """
128 total = 1
129 for k in frequencies1:
130 total *= abs(frequencies1[k] - frequencies2[k])
131 return total
132
133 def harmonic_mean(frequencies1, frequencies2):
134 """Finds the harmonic mean of the absolute differences between two frequency profiles,
135 expressed as dictionaries.
136 Assumes every key in frequencies1 is also in frequencies2
137
138 >>> harmonic_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1})
139 1.0
140 >>> harmonic_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1})
141 1.0
142 >>> harmonic_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':5, 'c':1}) # doctest: +ELLIPSIS
143 1.285714285...
144 >>> harmonic_mean(normalise({'a':2, 'b':2, 'c':2}), \
145 normalise({'a':1, 'b':5, 'c':1})) # doctest: +ELLIPSIS
146 0.228571428571...
147 >>> harmonic_mean(normalise({'a':2, 'b':2, 'c':2}), \
148 normalise({'a':1, 'b':1, 'c':1})) # doctest: +ELLIPSIS
149 0
150 >>> harmonic_mean(normalise({'a':2, 'b':2, 'c':2}), \
151 normalise({'a':1, 'b':1, 'c':0})) # doctest: +ELLIPSIS
152 0.2
153 """
154 total = 0
155 for k in frequencies1:
156 if abs(frequencies1[k] - frequencies2[k]) == 0:
157 return 0
158 total += 1 / abs(frequencies1[k] - frequencies2[k])
159 return len(frequencies1) / total
160
161
162 def cosine_similarity(frequencies1, frequencies2):
163 """Finds the distances between two frequency profiles, expressed as dictionaries.
164 Assumes every key in frequencies1 is also in frequencies2
165
166 >>> cosine_similarity({'a':1, 'b':1, 'c':1}, {'a':1, 'b':1, 'c':1}) # doctest: +ELLIPSIS
167 1.0000000000...
168 >>> cosine_similarity({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1}) # doctest: +ELLIPSIS
169 1.0000000000...
170 >>> cosine_similarity({'a':0, 'b':2, 'c':0}, {'a':1, 'b':1, 'c':1}) # doctest: +ELLIPSIS
171 0.5773502691...
172 >>> cosine_similarity({'a':0, 'b':1}, {'a':1, 'b':1}) # doctest: +ELLIPSIS
173 0.7071067811...
174 """
175 numerator = 0
176 length1 = 0
177 length2 = 0
178 for k in frequencies1:
179 numerator += frequencies1[k] * frequencies2[k]
180 length1 += frequencies1[k]**2
181 for k in frequencies2:
182 length2 += frequencies2[k]**2
183 return numerator / (length1 ** 0.5 * length2 ** 0.5)
184
185
186
187 if __name__ == "__main__":
188 import doctest
189 doctest.testmod()