4 <title>Alternative plaintext scoring
</title>
5 <meta http-equiv=
"Content-Type" content=
"text/html; charset=UTF-8"/>
6 <style type=
"text/css">
15 h1 { font-size:
3em; }
16 h2 { font-size:
2em; }
17 h3 { font-size:
1.6em; }
19 text-decoration: none;
22 -moz-border-radius:
5px;
23 -web-border-radius:
5px;
31 text-shadow:
0 0 20px #
333;
37 text-shadow:
0 0 20px #
333;
51 <textarea id=
"source">
53 # Alternative plaintext scoring methods
59 .indexlink[[Index](index.html)]
63 # Back to frequency of letter counts
77 Another way of thinking about this is a
26-dimensional vector.
79 Create a vector of our text, and one of idealised English.
81 The distance between the vectors is how far from English the text is.
87 .float-right[![right-aligned Vector subtraction](vector-subtraction.svg)]
89 Several different distance measures (__metrics__, also called __norms__):
91 * L
<sub>2</sub> norm (Euclidean distance):
92 `\(\|\mathbf{a} - \mathbf{b}\| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^
2} \)`
94 * L
<sub>1</sub> norm (Manhattan distance, taxicab distance):
95 `\(\|\mathbf{a} - \mathbf{b}\| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| \)`
98 `\(\|\mathbf{a} - \mathbf{b}\| = \sqrt[
3]{\sum_i |\mathbf{a}_i - \mathbf{b}_i|^
3} \)`
100 The higher the power used, the more weight is given to the largest differences in components.
104 * L
<sub>0</sub> norm (Hamming distance):
105 `$$\|\mathbf{a} - \mathbf{b}\| = \sum_i \left\{
106 \begin{matrix}
1 &\mbox{if}\ \mathbf{a}_i \neq \mathbf{b}_i , \\
107 0 &\mbox{if}\ \mathbf{a}_i = \mathbf{b}_i \end{matrix} \right. $$`
109 * L
<sub>∞</sub> norm:
110 `\(\|\mathbf{a} - \mathbf{b}\| = \max_i{(\mathbf{a}_i - \mathbf{b}_i)} \)`
112 neither of which will be that useful here, but they keep cropping up.)
115 # Normalisation of vectors
117 Frequency distributions drawn from different sources will have different lengths. For a fair comparison we need to scale them.
119 * Eucliean scaling (vector with unit length): `$$ \hat{\mathbf{x}} = \frac{\mathbf{x}}{\| \mathbf{x} \|} = \frac{\mathbf{x}}{ \sqrt{\mathbf{x}_1^
2 + \mathbf{x}_2^
2 + \mathbf{x}_3^
2 + \dots } }$$`
121 * Normalisation (components of vector sum to
1): `$$ \hat{\mathbf{x}} = \frac{\mathbf{x}}{\| \mathbf{x} \|} = \frac{\mathbf{x}}{ \mathbf{x}_1 + \mathbf{x}_2 + \mathbf{x}_3 + \dots }$$`
125 # Angle, not distance
127 Rather than looking at the distance between the vectors, look at the angle between them.
129 .float-right[![right-aligned Vector dot product](vector-dot-product.svg)]
131 Vector dot product shows how much of one vector lies in the direction of another:
132 `\( \mathbf{A} \bullet \mathbf{B} =
133 \| \mathbf{A} \| \cdot \| \mathbf{B} \| \cos{\theta} \)`
136 `\( \mathbf{A} \bullet \mathbf{B} = \sum_i \mathbf{A}_i \cdot \mathbf{B}_i \)`
137 and `\( \| \mathbf{A} \| = \sum_i \mathbf{A}_i^
2 \)`
139 A bit of rearranging give the cosine simiarity:
140 `$$ \cos{\theta} = \frac{ \mathbf{A} \bullet \mathbf{B} }{ \| \mathbf{A} \| \cdot \| \mathbf{B} \| } =
141 \frac{\sum_i \mathbf{A}_i \cdot \mathbf{B}_i}{\sum_i \mathbf{A}_i^
2 \times \sum_i \mathbf{B}_i^
2} $$`
143 This is independent of vector lengths!
145 Cosine similarity is
1 if in parallel,
0 if perpendicular, -
1 if antiparallel.
151 | Euclidean | Normalised
152 ---|-----------|------------
158 And the probability measure!
160 * Nine different ways of measuring fitness.
162 ## Computing is an empircal science
164 Let's do some experiments to find the best solution!
168 # Experimental harness
170 ## Step
1: build some other scoring functions
172 We need a way of passing the different functions to the keyfinding function.
174 ## Step
2: find the best scoring function
176 Try them all on random ciphertexts, see which one works best.
180 # Functions are values!
184 <function Pletters at
0x7f60e6d9c4d0>
188 def caesar_break(message, fitness=Pletters):
189 """Breaks a Caesar cipher using frequency analysis
191 for shift in range(26):
192 plaintext = caesar_decipher(message, shift)
193 fit = fitness(plaintext)
198 # Changing the comparison function
200 * Must be a function that takes a text and returns a score
201 * Better fit must give higher score, opposite of the vector distance norms
204 def make_frequency_compare_function(target_frequency, frequency_scaling, metric, invert):
205 def frequency_compare(text):
208 return frequency_compare
213 # Data-driven processing
216 metrics = [{'func': norms.l1, 'invert': True, 'name': 'l1'},
217 {'func': norms.l2, 'invert': True, 'name': 'l2'},
218 {'func': norms.l3, 'invert': True, 'name': 'l3'},
219 {'func': norms.cosine_similarity, 'invert': False, 'name': 'cosine_similarity'}]
220 scalings = [{'corpus_frequency': normalised_english_counts,
221 'scaling': norms.normalise,
222 'name': 'normalised'},
223 {'corpus_frequency': euclidean_scaled_english_counts,
224 'scaling': norms.euclidean_scale,
225 'name': 'euclidean_scaled'}]
228 Use this to make all nine scoring functions.
232 <script src="http://gnab.github.io/remark/downloads/remark-
0.6.0.min.js
" type="text/javascript
">
235 <script type="text/javascript
"
236 src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured
"></script>
238 <script type="text/javascript
">
239 var slideshow = remark.create({ ratio: "16:
9" });
244 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
247 MathJax.Hub.Queue(function() {
248 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
249 return(elem.SourceElement());
250 }).parent().addClass('has-jax');
252 MathJax.Hub.Configured();