Merged slides from presentation-slides branch

author Neil Smith <neil.git@njae.me.uk>

Thu, 3 Jul 2014 19:44:02 +0000 (20:44 +0100)

committer Neil Smith <neil.git@njae.me.uk>

Thu, 3 Jul 2014 19:44:02 +0000 (20:44 +0100)
author Neil Smith <neil.git@njae.me.uk>
Thu, 3 Jul 2014 19:44:02 +0000 (20:44 +0100)
committer Neil Smith <neil.git@njae.me.uk>
Thu, 3 Jul 2014 19:44:02 +0000 (20:44 +0100)
diff --git a/slides/affine-break.html b/slides/affine-break.html

new file mode 100644 (file)

index 0000000..58b27f6
--- /dev/null
+++ b/slides/affine-break.html
@@ -0,0 +1,91 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title>Affine ciphers</title>
+    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
+    <style type="text/css">
+      /* Slideshow styles */
+      body {
+        font-size: 20px;
+      }
+      h1, h2, h3 {
+        font-weight: 400;
+        margin-bottom: 0;
+      }
+      h1 { font-size: 3em; }
+      h2 { font-size: 2em; }
+      h3 { font-size: 1.6em; }
+      a, a > code {
+        text-decoration: none;
+      }
+      code {
+        -moz-border-radius: 5px;
+        -web-border-radius: 5px;
+        background: #e7e8e2;
+        border-radius: 5px;
+        font-size: 16px;
+      }
+      .plaintext {
+        background: #272822;
+        color: #80ff80;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+      .ciphertext {
+        background: #272822;
+        color: #ff6666;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+       .float-right {
+        float: right;
+      }
+    </style>
+  </head>
+  <body>
+    <textarea id="source">
+
+# Breaking affine ciphers
+
+a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
+--|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--
+b | e | h | k | n | q | t | w | z | c | f | i | l | o | r | u | x | a | d | g | j | m | p | s | v | y
+
+---
+
+# Duplicate and extend your `caesar_break()` function
+
+* How to cycle through all the keys?
+
+---
+
+# Test it. 
+
+* `2013/2a.ciphertext`
+* `2013/3a.ciphertext`
+
+    </textarea>
+    <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
+    </script>
+
+    <script type="text/javascript"
+      src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
+
+    <script type="text/javascript">
+      var slideshow = remark.create({ ratio: "16:9" });
+
+      // Setup MathJax
+      MathJax.Hub.Config({
+        tex2jax: {
+        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
+        }
+      });
+      MathJax.Hub.Queue(function() {
+        $(MathJax.Hub.getAllJax()).map(function(index, elem) {
+            return(elem.SourceElement());
+        }).parent().addClass('has-jax');
+      });
+      MathJax.Hub.Configured();
+    </script>
+  </body>
+</html>
diff --git a/slides/affine-encipher.html b/slides/affine-encipher.html

new file mode 100644 (file)

index 0000000..30f3900
--- /dev/null
+++ b/slides/affine-encipher.html
@@ -0,0 +1,236 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title>Affine ciphers</title>
+    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
+    <style type="text/css">
+      /* Slideshow styles */
+      body {
+        font-size: 20px;
+      }
+      h1, h2, h3 {
+        font-weight: 400;
+        margin-bottom: 0;
+      }
+      h1 { font-size: 3em; }
+      h2 { font-size: 2em; }
+      h3 { font-size: 1.6em; }
+      a, a > code {
+        text-decoration: none;
+      }
+      code {
+        -moz-border-radius: 5px;
+        -web-border-radius: 5px;
+        background: #e7e8e2;
+        border-radius: 5px;
+        font-size: 16px;
+      }
+      .plaintext {
+        background: #272822;
+        color: #80ff80;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+      .ciphertext {
+        background: #272822;
+        color: #ff6666;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+       .float-right {
+        float: right;
+      }
+    </style>
+  </head>
+  <body>
+    <textarea id="source">
+
+# Affine ciphers
+
+a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
+--|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--
+b | e | h | k | n | q | t | w | z | c | f | i | l | o | r | u | x | a | d | g | j | m | p | s | v | y
+
+An extension of Caesar ciphers
+
+* Count the gaps in the letters.
+
+---
+# How affine ciphers work
+
+_ciphertext_letter_ =_plaintext_letter_ × a + b
+
+* Convert letters to numbers
+* Take the total modulus 26
+
+# Enciphering is easy
+
+* Build the `affine_encipher()` function
+
+---
+
+# Deciphering affine ciphers is harder
+
+`$$p = \frac{c - b}{a} \mod 26$$`
+
+But modular division is hard!
+
+Define division as mutiplication by the inverse: `\(\frac{x}{y} = x \times \frac{1}{y} = x \times y^{-1}\)`
+
+A number _x_, when multiplied by its inverse _x_<sup>-1</sup>, gives result of 1.
+
+This is not always defined in modular arithmetic. For instance, 7 × 4 = 28 = 2 mod 26, but 20 × 4 = 80 = 2 mod 26. Therefore, 4 doesn't have a multiplicative inverse (and therefore makes a bad key for affine ciphers).
+
+Result from number theory: only numbers coprime with _n_ have multiplicative inverses in arithmetic mod _n_.
+
+Another result from number theory: for non-negative integers _a_ and _n_, and there exist unique integers _x_ and _y_ such that _ax_ + _ny_ = gcd(_a_, _b_)
+
+Coprime numbers have gcd of 1.
+
+_ax_ + _ny_ = 1 mod _n_. But _ny_ mod _n_ = 0, so _ax_ = 1 mod _n_, so _a_ = _x_<sup>-1</sup>.
+
+Perhaps the algorithm for finding gcds could be useful?
+
+---
+
+# Euclid's algorithm
+
+.float-right[![right-aligned GCD](gcd.svg)]
+
+World's oldest algorithm.
+
+_a_ = _qb_ + _r_ ; gcd(_a_, _b_) = gcd(_qb_ + _r_, _b_) = gcd(_r_, _b_) = gcd(_b_, _r_)
+
+Repeatedly apply these steps until _r_ = 0, when the other number = gcd(_a_, _b_). For instance, _a_ = 81, _b_ = 57
+
+* 81 = 1 × 57 + 24
+* 57 = 2 × 24 + 9
+* 24 = 2 × 9 + 6
+* 9 = 1 × 6 + 3
+* 6 = 2 × 3 + 0
+
+Therefore, gcd(81, 57) = 3 and 81_x_ + 57_y_ = 3
+
+Now unfold the derivation to find _x_ and _y_
+
+* 3 = 9 × 1 + 6 × -1
+* 3 = 9 × 1 + (24 - 2 × 9) × -1 = 9 × 3 + 24 × -1
+* 3 = (57 - 2 × 24) × 3 + 24 × -1 = 57 × 3 + 24 × -7
+* 3 = 57 × 3 + (81 - 57 × 1) × -7 = 57 × 10 + 81 × -7 
+
+Can we do this in one pass?
+
+---
+
+# Hands up if you're lost
+
+## (Be honest)
+
+---
+
+# Triple constraints
+
+.float-right[![right-aligned GCD](fast-good-cheap.gif)]
+
+## Fast, cheap, good: pick two
+
+## Programmer time, execution time, space: pick one, get some of another.
+
+(Scripting languages like Python are popular because they reduce programmer time. Contrast with Java and Pascal.)
+
+Extended Euclid's algorithm has lots of programmer time (and risk of bugs), but will take virtually no space (6 numbers).
+
+Can we trade space for ease?
+
+A standard technique is memoisation: store the results somewhere, then just look them up.
+
+---
+
+# Modular multiplication table for 7
+
+(7) | 0 | 1 | 2 | 3 | 4 | 5 | 6
+----|---|---|---|---|---|---|---
+  0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
+  1 | 0 | 1 | 2 | 3 | 4 | 5 | 6
+  2 | 0 | 2 | 4 | 6 | 1 | 3 | 5
+  3 | 0 | 3 | 6 | 2 | 5 | 1 | 4
+  4 | 0 | 4 | 1 | 5 | 2 | 6 | 3
+  5 | 0 | 5 | 3 | 1 | 6 | 4 | 2
+  6 | 0 | 6 | 5 | 4 | 3 | 2 | 1
+
+Can use this to find the multiplicative inverses.
+
+(7) | 1 | 2 | 3 | 4 | 5 | 6
+----|---|---|---|---|---|---
+    | 1 | 4 | 5 | 2 | 3 | 6
+
+How much to store?
+
+---
+
+# How much to store?
+
+1. The inverses for this modular base.
+2. The inverses for all bases (12 of them)
+3. All the _x_ ÷ _y_ = _z_ mod _n_ triples...
+4. ...for all _n_
+5. The decipherment table for this key
+6. The decipherment table for all keys
+
+The choice is a design decision, taking into account space needed, time to create and use, expected use patterns, etc. 
+
+## Thoughts?
+
+---
+
+# How much to store?
+
+Keeping the decipherment close to encipherment seems aesthetically better to me. 
+
+Giving the ability to do division is the most obvious (to me).
+
+As there are only a few possible modular bases, might as well calculate the whole table at startup.
+
+## Now implement affine decipherment.
+
+Check both enciphering and deciphering work. Round-trip some text. 
+---
+
+# Counting from 0 or 1
+
+When converting letters to numbers, we're using the range 0-25.
+
+Another convention is to use numbers in range 1-26.
+
+Implement this.
+
+* You'll need another parameter:
+```python
+affine_encipher_letter(letter, multiplier, adder, one_based=False)
+```
+
+    </textarea>
+    <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
+    </script>
+
+    <script type="text/javascript"
+      src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
+
+    <script type="text/javascript">
+      var slideshow = remark.create({ ratio: "16:9" });
+
+      // Setup MathJax
+      MathJax.Hub.Config({
+        tex2jax: {
+        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
+        }
+      });
+      MathJax.Hub.Queue(function() {
+        $(MathJax.Hub.getAllJax()).map(function(index, elem) {
+            return(elem.SourceElement());
+        }).parent().addClass('has-jax');
+      });
+      MathJax.Hub.Configured();
+    </script>
+  </body>
+</html>
diff --git a/slides/alternative-plaintext-scoring.html b/slides/alternative-plaintext-scoring.html

new file mode 100644 (file)

index 0000000..d6f4aa1
--- /dev/null
+++ b/slides/alternative-plaintext-scoring.html
@@ -0,0 +1,244 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title>Alternative plaintext scoring</title>
+    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
+    <style type="text/css">
+      /* Slideshow styles */
+      body {
+        font-size: 20px;
+      }
+      h1, h2, h3 {
+        font-weight: 400;
+        margin-bottom: 0;
+      }
+      h1 { font-size: 3em; }
+      h2 { font-size: 2em; }
+      h3 { font-size: 1.6em; }
+      a, a > code {
+        text-decoration: none;
+      }
+      code {
+        -moz-border-radius: 5px;
+        -web-border-radius: 5px;
+        background: #e7e8e2;
+        border-radius: 5px;
+        font-size: 16px;
+      }
+      .plaintext {
+        background: #272822;
+        color: #80ff80;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+      .ciphertext {
+        background: #272822;
+        color: #ff6666;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+       .float-right {
+        float: right;
+      }
+    </style>
+  </head>
+  <body>
+    <textarea id="source">
+
+# Alternative plaintext scoring methods
+
+---
+
+# Back to frequency of letter counts
+
+Letter | Count
+-------|------
+a | 489107
+b | 92647
+c | 140497
+d | 267381
+e | 756288
+. | .
+. | .
+. | .
+z | 3575
+
+Another way of thinking about this is a 26-dimensional vector. 
+
+Create a vector of our text, and one of idealised English. 
+
+The distance between the vectors is how far from English the text is.
+
+---
+
+# Vector distances
+
+.float-right[![right-aligned Vector subtraction](vector-subtraction.svg)]
+
+Several different distance measures (__metrics__, also called __norms__):
+
+* L<sub>2</sub> norm (Euclidean distance): 
+`\(\|\mathbf{a} - \mathbf{b}\| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^2} \)`
+
+* L<sub>1</sub> norm (Manhattan distance, taxicab distance): 
+`\(\|\mathbf{a} - \mathbf{b}\| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| \)`
+
+* L<sub>3</sub> norm: 
+`\(\|\mathbf{a} - \mathbf{b}\| = \sqrt[3]{\sum_i |\mathbf{a}_i - \mathbf{b}_i|^3} \)`
+
+The higher the power used, the more weight is given to the largest differences in components.
+
+(Extends out to:
+
+* L<sub>0</sub> norm (Hamming distance): 
+`$$\|\mathbf{a} - \mathbf{b}\| = \sum_i \left\{
+\begin{matrix} 1 &amp;\mbox{if}\ \mathbf{a}_i \neq \mathbf{b}_i , \\
+ 0 &amp;\mbox{if}\ \mathbf{a}_i = \mathbf{b}_i \end{matrix} \right. $$`
+
+* L<sub>&infin;</sub> norm: 
+`\(\|\mathbf{a} - \mathbf{b}\| = \max_i{(\mathbf{a}_i - \mathbf{b}_i)} \)`
+
+neither of which will be that useful here, but they keep cropping up.)
+---
+
+# Normalisation of vectors
+
+Frequency distributions drawn from different sources will have different lengths. For a fair comparison we need to scale them. 
+
+* 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 } }$$`
+
+* 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 }$$`
+
+---
+
+# Angle, not distance
+
+Rather than looking at the distance between the vectors, look at the angle between them.
+
+.float-right[![right-aligned Vector dot product](vector-dot-product.svg)]
+
+Vector dot product shows how much of one vector lies in the direction of another: 
+`\( \mathbf{A} \bullet \mathbf{B} = 
+\| \mathbf{A} \| \cdot \| \mathbf{B} \| \cos{\theta} \)`
+
+But, 
+`\( \mathbf{A} \bullet \mathbf{B} = \sum_i \mathbf{A}_i \cdot \mathbf{B}_i \)`
+and `\( \| \mathbf{A} \| = \sum_i \mathbf{A}_i^2 \)`
+
+A bit of rearranging give the cosine simiarity:
+`$$ \cos{\theta} = \frac{ \mathbf{A} \bullet \mathbf{B} }{ \| \mathbf{A} \| \cdot \| \mathbf{B} \| } = 
+\frac{\sum_i \mathbf{A}_i \cdot \mathbf{B}_i}{\sum_i \mathbf{A}_i^2 \times \sum_i \mathbf{B}_i^2} $$`
+
+This is independent of vector lengths!
+
+Cosine similarity is 1 if in parallel, 0 if perpendicular, -1 if antiparallel.
+
+---
+
+# Which is best?
+
+   | Euclidean | Normalised
+---|-----------|------------  
+L1 |     x     |      x
+L2 |     x     |      x
+L3 |     x     |      x
+Cosine |     x     |      x
+
+And the probability measure!
+
+* Nine different ways of measuring fitness.
+
+## Computing is an empircal science
+
+Let's do some experiments to find the best solution!
+
+---
+
+# Experimental harness
+
+## Step 1: build some other scoring functions
+
+We need a way of passing the different functions to the keyfinding function.
+
+## Step 2: find the best scoring function
+
+Try them all on random ciphertexts, see which one works best.
+
+---
+
+# Functions are values!
+
+```python
+>>> Pletters
+<function Pletters at 0x7f60e6d9c4d0>
+```
+
+```python
+def caesar_break(message, fitness=Pletters):
+    """Breaks a Caesar cipher using frequency analysis
+...
+    for shift in range(26):
+        plaintext = caesar_decipher(message, shift)
+        fit = fitness(plaintext)
+```
+
+---
+
+# Changing the comparison function
+
+* Must be a function that takes a text and returns a score
+    * Better fit must give higher score, opposite of the vector distance norms
+
+```python
+def make_frequency_compare_function(target_frequency, frequency_scaling, metric, invert):
+    def frequency_compare(text):
+        ...
+        return score
+    return frequency_compare
+```
+
+---
+
+# Data-driven processing
+
+```python
+metrics = [{'func': norms.l1, 'invert': True, 'name': 'l1'}, 
+    {'func': norms.l2, 'invert': True, 'name': 'l2'},
+    {'func': norms.l3, 'invert': True, 'name': 'l3'},
+    {'func': norms.cosine_similarity, 'invert': False, 'name': 'cosine_similarity'}]
+scalings = [{'corpus_frequency': normalised_english_counts, 
+         'scaling': norms.normalise,
+         'name': 'normalised'},
+        {'corpus_frequency': euclidean_scaled_english_counts, 
+         'scaling': norms.euclidean_scale,
+         'name': 'euclidean_scaled'}]
+```
+
+Use this to make all nine scoring functions.
+
+
+    </textarea>
+    <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
+    </script>
+
+    <script type="text/javascript"
+      src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
+
+    <script type="text/javascript">
+      var slideshow = remark.create({ ratio: "16:9" });
+
+      // Setup MathJax
+      MathJax.Hub.Config({
+        tex2jax: {
+        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
+        }
+      });
+      MathJax.Hub.Queue(function() {
+        $(MathJax.Hub.getAllJax()).map(function(index, elem) {
+            return(elem.SourceElement());
+        }).parent().addClass('has-jax');
+      });
+      MathJax.Hub.Configured();
+    </script>
+  </body>
+</html>
diff --git a/slides/caesar-break.html b/slides/caesar-break.html

index 187719da5f81e687adcac89c30c90646663df232..5ea77b9ffb208baa62eb1c4437cad26a6ef19b55 100644 (file)
--- a/slides/caesar-break.html
+++ b/slides/caesar-break.html
@@ -111,11 +111,34 @@ e | 756288
  . | .
  z | 3575
  
-One way of thinking about this is a 26-dimensional vector. 
+Use this to predict the probability of each letter, and hence the probability of a sequence of letters. 
  
-Create a vector of our text, and one of idealised English. 
+---
+
+# An infinite number of monkeys
+
+What is the probability that this string of letters is a sample of English?
+
+## Naive Bayes, or the bag of letters
+
+Ignore letter order, just treat each letter individually.
+
+Probability of a text is `\( \prod_i p_i \)`
+
+Letter      | h       | e       | l       | l       | o       | hello
+------------|---------|---------|---------|---------|---------|-------
+Probability | 0.06645 | 0.12099 | 0.04134 | 0.04134 | 0.08052 | 1.10648239 × 10<sup>-6</sup>
+
+Letter      | i       | f       | m       | m       | p       | ifmmp
+------------|---------|---------|---------|---------|---------|-------
+Probability | 0.06723 | 0.02159 | 0.02748 | 0.02748 | 0.01607 | 1.76244520 × 10<sup>-8</sup>
+
+(Implmentation issue: this can often underflow, so get in the habit of rephrasing it as `\( \sum_i \log p_i \)`)
+
+Letter      | h       | e       | l       | l       | o       | hello
+------------|---------|---------|---------|---------|---------|-------
+Probability | -1.1774 | -0.9172 | -1.3836 | -1.3836 | -1.0940 | -5.956055
  
-The distance between the vectors is how far from English the text is.
  
  ---
  
@@ -126,13 +149,15 @@ But before then how do we count the letters?
  * Read a file into a string
  ```python
  open()
-read()
+.read()
  ```
  * Count them
  ```python
  import collections
  ```
  
+Create the `language_models.py` file for this.
+
  ---
  
  # Canonical forms
@@ -146,20 +171,21 @@ Counting letters in _War and Peace_ gives all manner of junk.
  ```
  ---
  
-
  # Accents
  
  ```python
->>> caesar_encipher_letter('é', 1)
+>>> 'é' in string.ascii_letters
+>>> 'e' in string.ascii_letters
  ```
-What does it produce?
-
-What should it produce?
  
  ## Unicode, combining codepoints, and normal forms
  
  Text encodings will bite you when you least expect it.
  
+- **é** : LATIN SMALL LETTER E WITH ACUTE (U+00E9)
+
+- **e** + **&nbsp;&#x301;** : LATIN SMALL LETTER E (U+0065) + COMBINING ACUTE ACCENT (U+0301)
+
  * urlencoding is the other pain point.
  
  ---
@@ -190,101 +216,78 @@ def unaccent(text):
  
  ---
  
-# Vector distances
-
-.float-right[![right-aligned Vector subtraction](vector-subtraction.svg)]
-
-Several different distance measures (__metrics__, also called __norms__):
+# Find the frequencies of letters in English
  
-* L<sub>2</sub> norm (Euclidean distance): 
-`\(\|\mathbf{a} - \mathbf{b}\| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^2} \)`
+1. Read from `shakespeare.txt`, `sherlock-holmes.txt`, and `war-and-peace.txt`.
+2. Find the frequencies (`.update()`)
+3. Sort by count 
+4. Write counts to `count_1l.txt` (`'text{}\n'.format()`)
  
-* L<sub>1</sub> norm (Manhattan distance, taxicab distance): 
-`\(\|\mathbf{a} - \mathbf{b}\| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| \)`
+---
  
-* L<sub>3</sub> norm: 
-`\(\|\mathbf{a} - \mathbf{b}\| = \sqrt[3]{\sum_i |\mathbf{a}_i - \mathbf{b}_i|^3} \)`
+# Reading letter probabilities
  
-The higher the power used, the more weight is given to the largest differences in components.
+1. Load the file `count_1l.txt` into a dict, with letters as keys.
  
-(Extends out to:
+2. Normalise the counts (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 }$$`
+    * Return a new dict
+    * Remember the doctest!
  
-* L<sub>0</sub> norm (Hamming distance): 
-`$$\|\mathbf{a} - \mathbf{b}\| = \sum_i \left\{
-\begin{matrix} 1 &amp;\mbox{if}\ \mathbf{a}_i \neq \mathbf{b}_i , \\
- 0 &amp;\mbox{if}\ \mathbf{a}_i = \mathbf{b}_i \end{matrix} \right. $$`
+3. Create a dict `Pl` that gives the log probability of a letter
  
-* L<sub>&infin;</sub> norm: 
-`\(\|\mathbf{a} - \mathbf{b}\| = \max_i{(\mathbf{a}_i - \mathbf{b}_i)} \)`
+4. Create a function `Pletters` that gives the probability of an iterable of letters
+    * What preconditions should this function have?
+    * Remember the doctest!
  
-neither of which will be that useful.)
  ---
  
-# Normalisation of vectors
+# Breaking caesar ciphers
  
-Frequency distributions drawn from different sources will have different lengths. For a fair comparison we need to scale them. 
+## Remember the basic idea
  
-* 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 } }$$`
+```
+for each key:
+    decipher with this key
+    how close is it to English?
+    remember the best key
+```
  
-* 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 }$$`
+Try it on the text in `2013/1a.ciphertext`. Does it work?
  
  ---
  
-# Angle, not distance
-
-Rather than looking at the distance between the vectors, look at the angle between them.
-
-.float-right[![right-aligned Vector dot product](vector-dot-product.svg)]
+# Aside: Logging
  
-Vector dot product shows how much of one vector lies in the direction of another: 
-`\( \mathbf{A} \bullet \mathbf{B} = 
-\| \mathbf{A} \| \cdot \| \mathbf{B} \| \cos{\theta} \)`
-
-But, 
-`\( \mathbf{A} \bullet \mathbf{B} = \sum_i \mathbf{A}_i \cdot \mathbf{B}_i \)`
-and `\( \| \mathbf{A} \| = \sum_i \mathbf{A}_i^2 \)`
-
-A bit of rearranging give the cosine simiarity:
-`$$ \cos{\theta} = \frac{ \mathbf{A} \bullet \mathbf{B} }{ \| \mathbf{A} \| \cdot \| \mathbf{B} \| } = 
-\frac{\sum_i \mathbf{A}_i \cdot \mathbf{B}_i}{\sum_i \mathbf{A}_i^2 \times \sum_i \mathbf{B}_i^2} $$`
-
-This is independent of vector lengths!
-
-Cosine similarity is 1 if in parallel, 0 if perpendicular, -1 if antiparallel.
-
----
+Better than scattering `print()`statements through your code
  
-# An infinite number of monkeys
-
-What is the probability that this string of letters is a sample of English?
+```python
+import logging
  
-Given 'th', 'e' is about six times more likely than 'a' or 'i'.
+logger = logging.getLogger(__name__)
+logger.addHandler(logging.FileHandler('cipher.log'))
+logger.setLevel(logging.WARNING)
  
-## Naive Bayes, or the bag of letters
+        logger.debug('Caesar break attempt using key {0} gives fit of {1} '
+                      'and decrypt starting: {2}'.format(shift, fit, plaintext[:50]))
  
-Ignore letter order, just treat each letter individually.
+```
+* Yes, it's ugly.
  
-Probability of a text is `\( \prod_i p_i \)`
+Use `logger.setLevel()` to change the level: CRITICAL, ERROR, WARNING, INFO, DEBUG
  
-(Implmentation issue: this can often underflow, so get in the habit of rephrasing it as `\( \sum_i \log p_i \)`)
+Use `logger.debug()`, `logger.info()`, etc. to log a message.
  
  ---
  
-# Which is best?
-
-   | Euclidean | Normalised
----|-----------|------------  
-L1 |     x     |      x
-L2 |     x     |      x
-L3 |     x     |      x
-Cosine |     x     |      x
-
-And the probability measure!
-
-* Nine different ways of measuring fitness.
+# How much ciphertext do we need?
  
-## Computing is an empircal science
+## Let's do an experiment to find out
  
+1. Load the whole corpus into a string (sanitised)
+2. Select a random chunk of plaintext and a random key
+3. Encipher the text
+4. Score 1 point if `caesar_cipher_break()` recovers the correct key
+5. Repeat many times and with many plaintext lengths
  
  
      </textarea>
diff --git a/slides/fast-good-cheap.gif b/slides/fast-good-cheap.gif

new file mode 100644 (file)

index 0000000..63411f0

Binary files /dev/null and b/slides/fast-good-cheap.gif differ
diff --git a/slides/further-work.html b/slides/further-work.html

new file mode 100644 (file)

index 0000000..64a9729
--- /dev/null
+++ b/slides/further-work.html
@@ -0,0 +1,92 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title>Breaking keyword ciphers</title>
+    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
+    <style type="text/css">
+      /* Slideshow styles */
+      body {
+        font-size: 20px;
+      }
+      h1, h2, h3 {
+        font-weight: 400;
+        margin-bottom: 0;
+      }
+      h1 { font-size: 3em; }
+      h2 { font-size: 2em; }
+      h3 { font-size: 1.6em; }
+      a, a > code {
+        text-decoration: none;
+      }
+      code {
+        -moz-border-radius: 5px;
+        -web-border-radius: 5px;
+        background: #e7e8e2;
+        border-radius: 5px;
+        font-size: 16px;
+      }
+      .plaintext {
+        background: #272822;
+        color: #80ff80;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+      .ciphertext {
+        background: #272822;
+        color: #ff6666;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+       .float-right {
+        float: right;
+      }
+    </style>
+  </head>
+  <body>
+    <textarea id="source">
+
+# Taking this further
+ 
+### Countdown 
+* Conundrum
+* Letters
+   * Picking letters to maximise score
+* Numbers
+   * Read the "Functional Pearl"
+
+### Hangman
+* Letter probabilities based on each word occurring once in the dictionary
+* Set of candidate words filtered by length, letters guessed
+
+### Text generation
+* Read some text, find the n-grams, generate more text from that.
+
+### Spelling correction
+* Suggest the most likely correct word, given the probability of these errors.
+
+    </textarea>
+    <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
+    </script>
+
+    <script type="text/javascript"
+      src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
+
+    <script type="text/javascript">
+      var slideshow = remark.create({ ratio: "16:9" });
+
+      // Setup MathJax
+      MathJax.Hub.Config({
+        tex2jax: {
+        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
+        }
+      });
+      MathJax.Hub.Queue(function() {
+        $(MathJax.Hub.getAllJax()).map(function(index, elem) {
+            return(elem.SourceElement());
+        }).parent().addClass('has-jax');
+      });
+      MathJax.Hub.Configured();
+    </script>
+  </body>
+</html>
+
diff --git a/slides/gcd.svg b/slides/gcd.svg

new file mode 100644 (file)

index 0000000..80f8256
--- /dev/null
+++ b/slides/gcd.svg
@@ -0,0 +1,344 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<svg version="1.2" width="50mm" height="70mm" viewBox="0 0 5000 7000" preserveAspectRatio="xMidYMid" fill-rule="evenodd" clip-path="url(#presentation_clip_path)" stroke-width="28.222" stroke-linejoin="round" xmlns="http://www.w3.org/2000/svg" xmlns:ooo="http://xml.openoffice.org/svg/export" xmlns:xlink="http://www.w3.org/1999/xlink" xml:space="preserve">
+ <defs class="ClipPathGroup">
+  <clipPath id="presentation_clip_path" clipPathUnits="userSpaceOnUse">
+   <rect x="0" y="0" width="5000" height="7000"/>
+  </clipPath>
+ </defs>
+ <defs class="TextShapeIndex">
+  <g ooo:slide="id1" ooo:id-list="id3 id4 id5 id6 id7 id8 id9 id10 id11 id12 id13 id14 id15 id16 id17 id18 id19 id20 id21 id22 id23 id24 id25 id26 id27 id28 id29 id30 id31 id32 id33 id34 id35 id36 id37 id38"/>
+ </defs>
+ <defs class="EmbeddedBulletChars">
+  <g id="bullet-char-template(57356)" transform="scale(0.00048828125,-0.00048828125)">
+   <path d="M 580,1141 L 1163,571 580,0 -4,571 580,1141 Z"/>
+  </g>
+  <g id="bullet-char-template(57354)" transform="scale(0.00048828125,-0.00048828125)">
+   <path d="M 8,1128 L 1137,1128 1137,0 8,0 8,1128 Z"/>
+  </g>
+  <g id="bullet-char-template(10146)" transform="scale(0.00048828125,-0.00048828125)">
+   <path d="M 174,0 L 602,739 174,1481 1456,739 174,0 Z M 1358,739 L 309,1346 659,739 1358,739 Z"/>
+  </g>
+  <g id="bullet-char-template(10132)" transform="scale(0.00048828125,-0.00048828125)">
+   <path d="M 2015,739 L 1276,0 717,0 1260,543 174,543 174,936 1260,936 717,1481 1274,1481 2015,739 Z"/>
+  </g>
+  <g id="bullet-char-template(10007)" transform="scale(0.00048828125,-0.00048828125)">
+   <path d="M 0,-2 C -7,14 -16,27 -25,37 L 356,567 C 262,823 215,952 215,954 215,979 228,992 255,992 264,992 276,990 289,987 310,991 331,999 354,1012 L 381,999 492,748 772,1049 836,1024 860,1049 C 881,1039 901,1025 922,1006 886,937 835,863 770,784 769,783 710,716 594,584 L 774,223 C 774,196 753,168 711,139 L 727,119 C 717,90 699,76 672,76 641,76 570,178 457,381 L 164,-76 C 142,-110 111,-127 72,-127 30,-127 9,-110 8,-76 1,-67 -2,-52 -2,-32 -2,-23 -1,-13 0,-2 Z"/>
+  </g>
+  <g id="bullet-char-template(10004)" transform="scale(0.00048828125,-0.00048828125)">
+   <path d="M 285,-33 C 182,-33 111,30 74,156 52,228 41,333 41,471 41,549 55,616 82,672 116,743 169,778 240,778 293,778 328,747 346,684 L 369,508 C 377,444 397,411 428,410 L 1163,1116 C 1174,1127 1196,1133 1229,1133 1271,1133 1292,1118 1292,1087 L 1292,965 C 1292,929 1282,901 1262,881 L 442,47 C 390,-6 338,-33 285,-33 Z"/>
+  </g>
+  <g id="bullet-char-template(9679)" transform="scale(0.00048828125,-0.00048828125)">
+   <path d="M 813,0 C 632,0 489,54 383,161 276,268 223,411 223,592 223,773 276,916 383,1023 489,1130 632,1184 813,1184 992,1184 1136,1130 1245,1023 1353,916 1407,772 1407,592 1407,412 1353,268 1245,161 1136,54 992,0 813,0 Z"/>
+  </g>
+  <g id="bullet-char-template(8226)" transform="scale(0.00048828125,-0.00048828125)">
+   <path d="M 346,457 C 273,457 209,483 155,535 101,586 74,649 74,723 74,796 101,859 155,911 209,963 273,989 346,989 419,989 480,963 531,910 582,859 608,796 608,723 608,648 583,586 532,535 482,483 420,457 346,457 Z"/>
+  </g>
+  <g id="bullet-char-template(8211)" transform="scale(0.00048828125,-0.00048828125)">
+   <path d="M -4,459 L 1135,459 1135,606 -4,606 -4,459 Z"/>
+  </g>
+ </defs>
+ <defs class="TextEmbeddedBitmaps"/>
+ <g>
+  <g id="id2" class="Master_Slide">
+   <g id="bg-id2" class="Background"/>
+   <g id="bo-id2" class="BackgroundObjects"/>
+  </g>
+ </g>
+ <g class="SlideGroup">
+  <g>
+   <g id="id1" class="Slide" clip-path="url(#presentation_clip_path)">
+    <g class="Page">
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id3">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 1083,3500 C 1041,3500 1000,3541 1000,3583 L 1000,3917 C 1000,3959 1041,4001 1083,4001 L 1417,4001 C 1459,4001 1501,3959 1501,3917 L 1501,3583 C 1501,3541 1459,3500 1417,3500 L 1083,3500 Z M 1000,3500 L 1000,3500 Z M 1501,4001 L 1501,4001 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1083,3500 C 1041,3500 1000,3541 1000,3583 L 1000,3917 C 1000,3959 1041,4001 1083,4001 L 1417,4001 C 1459,4001 1501,3959 1501,3917 L 1501,3583 C 1501,3541 1459,3500 1417,3500 L 1083,3500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1000,3500 L 1000,3500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1501,4001 L 1501,4001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id4">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 1083,4000 C 1041,4000 1000,4041 1000,4083 L 1000,4417 C 1000,4459 1041,4501 1083,4501 L 1417,4501 C 1459,4501 1501,4459 1501,4417 L 1501,4083 C 1501,4041 1459,4000 1417,4000 L 1083,4000 Z M 1000,4000 L 1000,4000 Z M 1501,4501 L 1501,4501 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1083,4000 C 1041,4000 1000,4041 1000,4083 L 1000,4417 C 1000,4459 1041,4501 1083,4501 L 1417,4501 C 1459,4501 1501,4459 1501,4417 L 1501,4083 C 1501,4041 1459,4000 1417,4000 L 1083,4000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1000,4000 L 1000,4000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1501,4501 L 1501,4501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id5">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 1083,4500 C 1041,4500 1000,4541 1000,4583 L 1000,4917 C 1000,4959 1041,5001 1083,5001 L 1417,5001 C 1459,5001 1501,4959 1501,4917 L 1501,4583 C 1501,4541 1459,4500 1417,4500 L 1083,4500 Z M 1000,4500 L 1000,4500 Z M 1501,5001 L 1501,5001 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1083,4500 C 1041,4500 1000,4541 1000,4583 L 1000,4917 C 1000,4959 1041,5001 1083,5001 L 1417,5001 C 1459,5001 1501,4959 1501,4917 L 1501,4583 C 1501,4541 1459,4500 1417,4500 L 1083,4500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1000,4500 L 1000,4500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1501,5001 L 1501,5001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id6">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 1083,5000 C 1041,5000 1000,5041 1000,5083 L 1000,5417 C 1000,5459 1041,5501 1083,5501 L 1417,5501 C 1459,5501 1501,5459 1501,5417 L 1501,5083 C 1501,5041 1459,5000 1417,5000 L 1083,5000 Z M 1000,5000 L 1000,5000 Z M 1501,5501 L 1501,5501 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1083,5000 C 1041,5000 1000,5041 1000,5083 L 1000,5417 C 1000,5459 1041,5501 1083,5501 L 1417,5501 C 1459,5501 1501,5459 1501,5417 L 1501,5083 C 1501,5041 1459,5000 1417,5000 L 1083,5000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1000,5000 L 1000,5000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1501,5501 L 1501,5501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id7">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 1083,3000 C 1041,3000 1000,3041 1000,3083 L 1000,3417 C 1000,3459 1041,3501 1083,3501 L 1417,3501 C 1459,3501 1501,3459 1501,3417 L 1501,3083 C 1501,3041 1459,3000 1417,3000 L 1083,3000 Z M 1000,3000 L 1000,3000 Z M 1501,3501 L 1501,3501 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1083,3000 C 1041,3000 1000,3041 1000,3083 L 1000,3417 C 1000,3459 1041,3501 1083,3501 L 1417,3501 C 1459,3501 1501,3459 1501,3417 L 1501,3083 C 1501,3041 1459,3000 1417,3000 L 1083,3000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1000,3000 L 1000,3000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1501,3501 L 1501,3501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id8">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 1083,6000 C 1041,6000 1000,6041 1000,6083 L 1000,6417 C 1000,6459 1041,6501 1083,6501 L 1417,6501 C 1459,6501 1501,6459 1501,6417 L 1501,6083 C 1501,6041 1459,6000 1417,6000 L 1083,6000 Z M 1000,6000 L 1000,6000 Z M 1501,6501 L 1501,6501 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1083,6000 C 1041,6000 1000,6041 1000,6083 L 1000,6417 C 1000,6459 1041,6501 1083,6501 L 1417,6501 C 1459,6501 1501,6459 1501,6417 L 1501,6083 C 1501,6041 1459,6000 1417,6000 L 1083,6000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1000,6000 L 1000,6000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1501,6501 L 1501,6501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id9">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 1083,5500 C 1041,5500 1000,5541 1000,5583 L 1000,5917 C 1000,5959 1041,6001 1083,6001 L 1417,6001 C 1459,6001 1501,5959 1501,5917 L 1501,5583 C 1501,5541 1459,5500 1417,5500 L 1083,5500 Z M 1000,5500 L 1000,5500 Z M 1501,6001 L 1501,6001 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1083,5500 C 1041,5500 1000,5541 1000,5583 L 1000,5917 C 1000,5959 1041,6001 1083,6001 L 1417,6001 C 1459,6001 1501,5959 1501,5917 L 1501,5583 C 1501,5541 1459,5500 1417,5500 L 1083,5500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1000,5500 L 1000,5500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1501,6001 L 1501,6001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id10">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 1083,6500 C 1041,6500 1000,6541 1000,6583 L 1000,6917 C 1000,6959 1041,7001 1083,7001 L 1417,7001 C 1459,7001 1501,6959 1501,6917 L 1501,6583 C 1501,6541 1459,6500 1417,6500 L 1083,6500 Z M 1000,6500 L 1000,6500 Z M 1501,7001 L 1501,7001 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1083,6500 C 1041,6500 1000,6541 1000,6583 L 1000,6917 C 1000,6959 1041,7001 1083,7001 L 1417,7001 C 1459,7001 1501,6959 1501,6917 L 1501,6583 C 1501,6541 1459,6500 1417,6500 L 1083,6500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1000,6500 L 1000,6500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 1501,7001 L 1501,7001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id11">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 83,3500 C 41,3500 0,3541 0,3583 L 0,3917 C 0,3959 41,4001 83,4001 L 417,4001 C 459,4001 501,3959 501,3917 L 501,3583 C 501,3541 459,3500 417,3500 L 83,3500 Z M 0,3500 L 0,3500 Z M 501,4001 L 501,4001 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,3500 C 41,3500 0,3541 0,3583 L 0,3917 C 0,3959 41,4001 83,4001 L 417,4001 C 459,4001 501,3959 501,3917 L 501,3583 C 501,3541 459,3500 417,3500 L 83,3500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,3500 L 0,3500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,4001 L 501,4001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id12">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 83,4000 C 41,4000 0,4041 0,4083 L 0,4417 C 0,4459 41,4501 83,4501 L 417,4501 C 459,4501 501,4459 501,4417 L 501,4083 C 501,4041 459,4000 417,4000 L 83,4000 Z M 0,4000 L 0,4000 Z M 501,4501 L 501,4501 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,4000 C 41,4000 0,4041 0,4083 L 0,4417 C 0,4459 41,4501 83,4501 L 417,4501 C 459,4501 501,4459 501,4417 L 501,4083 C 501,4041 459,4000 417,4000 L 83,4000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,4000 L 0,4000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,4501 L 501,4501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id13">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 83,4500 C 41,4500 0,4541 0,4583 L 0,4917 C 0,4959 41,5001 83,5001 L 417,5001 C 459,5001 501,4959 501,4917 L 501,4583 C 501,4541 459,4500 417,4500 L 83,4500 Z M 0,4500 L 0,4500 Z M 501,5001 L 501,5001 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,4500 C 41,4500 0,4541 0,4583 L 0,4917 C 0,4959 41,5001 83,5001 L 417,5001 C 459,5001 501,4959 501,4917 L 501,4583 C 501,4541 459,4500 417,4500 L 83,4500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,4500 L 0,4500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,5001 L 501,5001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id14">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 83,5000 C 41,5000 0,5041 0,5083 L 0,5417 C 0,5459 41,5501 83,5501 L 417,5501 C 459,5501 501,5459 501,5417 L 501,5083 C 501,5041 459,5000 417,5000 L 83,5000 Z M 0,5000 L 0,5000 Z M 501,5501 L 501,5501 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,5000 C 41,5000 0,5041 0,5083 L 0,5417 C 0,5459 41,5501 83,5501 L 417,5501 C 459,5501 501,5459 501,5417 L 501,5083 C 501,5041 459,5000 417,5000 L 83,5000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,5000 L 0,5000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,5501 L 501,5501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id15">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 83,3000 C 41,3000 0,3041 0,3083 L 0,3417 C 0,3459 41,3501 83,3501 L 417,3501 C 459,3501 501,3459 501,3417 L 501,3083 C 501,3041 459,3000 417,3000 L 83,3000 Z M 0,3000 L 0,3000 Z M 501,3501 L 501,3501 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,3000 C 41,3000 0,3041 0,3083 L 0,3417 C 0,3459 41,3501 83,3501 L 417,3501 C 459,3501 501,3459 501,3417 L 501,3083 C 501,3041 459,3000 417,3000 L 83,3000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,3000 L 0,3000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,3501 L 501,3501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id16">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 83,6000 C 41,6000 0,6041 0,6083 L 0,6417 C 0,6459 41,6501 83,6501 L 417,6501 C 459,6501 501,6459 501,6417 L 501,6083 C 501,6041 459,6000 417,6000 L 83,6000 Z M 0,6000 L 0,6000 Z M 501,6501 L 501,6501 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,6000 C 41,6000 0,6041 0,6083 L 0,6417 C 0,6459 41,6501 83,6501 L 417,6501 C 459,6501 501,6459 501,6417 L 501,6083 C 501,6041 459,6000 417,6000 L 83,6000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,6000 L 0,6000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,6501 L 501,6501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id17">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 83,5500 C 41,5500 0,5541 0,5583 L 0,5917 C 0,5959 41,6001 83,6001 L 417,6001 C 459,6001 501,5959 501,5917 L 501,5583 C 501,5541 459,5500 417,5500 L 83,5500 Z M 0,5500 L 0,5500 Z M 501,6001 L 501,6001 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,5500 C 41,5500 0,5541 0,5583 L 0,5917 C 0,5959 41,6001 83,6001 L 417,6001 C 459,6001 501,5959 501,5917 L 501,5583 C 501,5541 459,5500 417,5500 L 83,5500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,5500 L 0,5500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,6001 L 501,6001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id18">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 83,6500 C 41,6500 0,6541 0,6583 L 0,6917 C 0,6959 41,7001 83,7001 L 417,7001 C 459,7001 501,6959 501,6917 L 501,6583 C 501,6541 459,6500 417,6500 L 83,6500 Z M 0,6500 L 0,6500 Z M 501,7001 L 501,7001 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,6500 C 41,6500 0,6541 0,6583 L 0,6917 C 0,6959 41,7001 83,7001 L 417,7001 C 459,7001 501,6959 501,6917 L 501,6583 C 501,6541 459,6500 417,6500 L 83,6500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,6500 L 0,6500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,7001 L 501,7001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id19">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 83,1500 C 41,1500 0,1541 0,1583 L 0,1917 C 0,1959 41,2001 83,2001 L 417,2001 C 459,2001 501,1959 501,1917 L 501,1583 C 501,1541 459,1500 417,1500 L 83,1500 Z M 0,1500 L 0,1500 Z M 501,2001 L 501,2001 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,1500 C 41,1500 0,1541 0,1583 L 0,1917 C 0,1959 41,2001 83,2001 L 417,2001 C 459,2001 501,1959 501,1917 L 501,1583 C 501,1541 459,1500 417,1500 L 83,1500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,1500 L 0,1500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,2001 L 501,2001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id20">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 83,2000 C 41,2000 0,2041 0,2083 L 0,2417 C 0,2459 41,2501 83,2501 L 417,2501 C 459,2501 501,2459 501,2417 L 501,2083 C 501,2041 459,2000 417,2000 L 83,2000 Z M 0,2000 L 0,2000 Z M 501,2501 L 501,2501 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,2000 C 41,2000 0,2041 0,2083 L 0,2417 C 0,2459 41,2501 83,2501 L 417,2501 C 459,2501 501,2459 501,2417 L 501,2083 C 501,2041 459,2000 417,2000 L 83,2000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,2000 L 0,2000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,2501 L 501,2501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id21">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 83,2500 C 41,2500 0,2541 0,2583 L 0,2917 C 0,2959 41,3001 83,3001 L 417,3001 C 459,3001 501,2959 501,2917 L 501,2583 C 501,2541 459,2500 417,2500 L 83,2500 Z M 0,2500 L 0,2500 Z M 501,3001 L 501,3001 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,2500 C 41,2500 0,2541 0,2583 L 0,2917 C 0,2959 41,3001 83,3001 L 417,3001 C 459,3001 501,2959 501,2917 L 501,2583 C 501,2541 459,2500 417,2500 L 83,2500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,2500 L 0,2500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,3001 L 501,3001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id22">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 83,1000 C 41,1000 0,1041 0,1083 L 0,1417 C 0,1459 41,1501 83,1501 L 417,1501 C 459,1501 501,1459 501,1417 L 501,1083 C 501,1041 459,1000 417,1000 L 83,1000 Z M 0,1000 L 0,1000 Z M 501,1501 L 501,1501 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,1000 C 41,1000 0,1041 0,1083 L 0,1417 C 0,1459 41,1501 83,1501 L 417,1501 C 459,1501 501,1459 501,1417 L 501,1083 C 501,1041 459,1000 417,1000 L 83,1000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,1000 L 0,1000 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,1501 L 501,1501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id23">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 83,500 C 41,500 0,541 0,583 L 0,917 C 0,959 41,1001 83,1001 L 417,1001 C 459,1001 501,959 501,917 L 501,583 C 501,541 459,500 417,500 L 83,500 Z M 0,500 L 0,500 Z M 501,1001 L 501,1001 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,500 C 41,500 0,541 0,583 L 0,917 C 0,959 41,1001 83,1001 L 417,1001 C 459,1001 501,959 501,917 L 501,583 C 501,541 459,500 417,500 L 83,500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,500 L 0,500 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,1001 L 501,1001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id24">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 83,0 C 41,0 0,41 0,83 L 0,417 C 0,459 41,501 83,501 L 417,501 C 459,501 501,459 501,417 L 501,83 C 501,41 459,0 417,0 L 83,0 Z M 0,0 L 0,0 Z M 501,501 L 501,501 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 83,0 C 41,0 0,41 0,83 L 0,417 C 0,459 41,501 83,501 L 417,501 C 459,501 501,459 501,417 L 501,83 C 501,41 459,0 417,0 L 83,0 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 0,0 L 0,0 Z"/>
+       <path fill="none" stroke="rgb(197,0,11)" d="M 501,501 L 501,501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id25">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 4583,3500 C 4541,3500 4500,3541 4500,3583 L 4500,3917 C 4500,3959 4541,4001 4583,4001 L 4917,4001 C 4959,4001 5001,3959 5001,3917 L 5001,3583 C 5001,3541 4959,3500 4917,3500 L 4583,3500 Z M 4500,3500 L 4500,3500 Z M 5001,4001 L 5001,4001 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4583,3500 C 4541,3500 4500,3541 4500,3583 L 4500,3917 C 4500,3959 4541,4001 4583,4001 L 4917,4001 C 4959,4001 5001,3959 5001,3917 L 5001,3583 C 5001,3541 4959,3500 4917,3500 L 4583,3500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4500,3500 L 4500,3500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 5001,4001 L 5001,4001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id26">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 4583,4000 C 4541,4000 4500,4041 4500,4083 L 4500,4417 C 4500,4459 4541,4501 4583,4501 L 4917,4501 C 4959,4501 5001,4459 5001,4417 L 5001,4083 C 5001,4041 4959,4000 4917,4000 L 4583,4000 Z M 4500,4000 L 4500,4000 Z M 5001,4501 L 5001,4501 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4583,4000 C 4541,4000 4500,4041 4500,4083 L 4500,4417 C 4500,4459 4541,4501 4583,4501 L 4917,4501 C 4959,4501 5001,4459 5001,4417 L 5001,4083 C 5001,4041 4959,4000 4917,4000 L 4583,4000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4500,4000 L 4500,4000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 5001,4501 L 5001,4501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id27">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 4583,4500 C 4541,4500 4500,4541 4500,4583 L 4500,4917 C 4500,4959 4541,5001 4583,5001 L 4917,5001 C 4959,5001 5001,4959 5001,4917 L 5001,4583 C 5001,4541 4959,4500 4917,4500 L 4583,4500 Z M 4500,4500 L 4500,4500 Z M 5001,5001 L 5001,5001 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4583,4500 C 4541,4500 4500,4541 4500,4583 L 4500,4917 C 4500,4959 4541,5001 4583,5001 L 4917,5001 C 4959,5001 5001,4959 5001,4917 L 5001,4583 C 5001,4541 4959,4500 4917,4500 L 4583,4500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4500,4500 L 4500,4500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 5001,5001 L 5001,5001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id28">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 4583,5000 C 4541,5000 4500,5041 4500,5083 L 4500,5417 C 4500,5459 4541,5501 4583,5501 L 4917,5501 C 4959,5501 5001,5459 5001,5417 L 5001,5083 C 5001,5041 4959,5000 4917,5000 L 4583,5000 Z M 4500,5000 L 4500,5000 Z M 5001,5501 L 5001,5501 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4583,5000 C 4541,5000 4500,5041 4500,5083 L 4500,5417 C 4500,5459 4541,5501 4583,5501 L 4917,5501 C 4959,5501 5001,5459 5001,5417 L 5001,5083 C 5001,5041 4959,5000 4917,5000 L 4583,5000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4500,5000 L 4500,5000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 5001,5501 L 5001,5501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id29">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 4583,3000 C 4541,3000 4500,3041 4500,3083 L 4500,3417 C 4500,3459 4541,3501 4583,3501 L 4917,3501 C 4959,3501 5001,3459 5001,3417 L 5001,3083 C 5001,3041 4959,3000 4917,3000 L 4583,3000 Z M 4500,3000 L 4500,3000 Z M 5001,3501 L 5001,3501 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4583,3000 C 4541,3000 4500,3041 4500,3083 L 4500,3417 C 4500,3459 4541,3501 4583,3501 L 4917,3501 C 4959,3501 5001,3459 5001,3417 L 5001,3083 C 5001,3041 4959,3000 4917,3000 L 4583,3000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4500,3000 L 4500,3000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 5001,3501 L 5001,3501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id30">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 4583,6000 C 4541,6000 4500,6041 4500,6083 L 4500,6417 C 4500,6459 4541,6501 4583,6501 L 4917,6501 C 4959,6501 5001,6459 5001,6417 L 5001,6083 C 5001,6041 4959,6000 4917,6000 L 4583,6000 Z M 4500,6000 L 4500,6000 Z M 5001,6501 L 5001,6501 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4583,6000 C 4541,6000 4500,6041 4500,6083 L 4500,6417 C 4500,6459 4541,6501 4583,6501 L 4917,6501 C 4959,6501 5001,6459 5001,6417 L 5001,6083 C 5001,6041 4959,6000 4917,6000 L 4583,6000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4500,6000 L 4500,6000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 5001,6501 L 5001,6501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id31">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 4583,5500 C 4541,5500 4500,5541 4500,5583 L 4500,5917 C 4500,5959 4541,6001 4583,6001 L 4917,6001 C 4959,6001 5001,5959 5001,5917 L 5001,5583 C 5001,5541 4959,5500 4917,5500 L 4583,5500 Z M 4500,5500 L 4500,5500 Z M 5001,6001 L 5001,6001 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4583,5500 C 4541,5500 4500,5541 4500,5583 L 4500,5917 C 4500,5959 4541,6001 4583,6001 L 4917,6001 C 4959,6001 5001,5959 5001,5917 L 5001,5583 C 5001,5541 4959,5500 4917,5500 L 4583,5500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4500,5500 L 4500,5500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 5001,6001 L 5001,6001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id32">
+       <path fill="rgb(255,66,14)" stroke="none" d="M 4583,6500 C 4541,6500 4500,6541 4500,6583 L 4500,6917 C 4500,6959 4541,7001 4583,7001 L 4917,7001 C 4959,7001 5001,6959 5001,6917 L 5001,6583 C 5001,6541 4959,6500 4917,6500 L 4583,6500 Z M 4500,6500 L 4500,6500 Z M 5001,7001 L 5001,7001 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4583,6500 C 4541,6500 4500,6541 4500,6583 L 4500,6917 C 4500,6959 4541,7001 4583,7001 L 4917,7001 C 4959,7001 5001,6959 5001,6917 L 5001,6583 C 5001,6541 4959,6500 4917,6500 L 4583,6500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4500,6500 L 4500,6500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 5001,7001 L 5001,7001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id33">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 3583,4000 C 3541,4000 3500,4041 3500,4083 L 3500,4417 C 3500,4459 3541,4501 3583,4501 L 3917,4501 C 3959,4501 4001,4459 4001,4417 L 4001,4083 C 4001,4041 3959,4000 3917,4000 L 3583,4000 Z M 3500,4000 L 3500,4000 Z M 4001,4501 L 4001,4501 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3583,4000 C 3541,4000 3500,4041 3500,4083 L 3500,4417 C 3500,4459 3541,4501 3583,4501 L 3917,4501 C 3959,4501 4001,4459 4001,4417 L 4001,4083 C 4001,4041 3959,4000 3917,4000 L 3583,4000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3500,4000 L 3500,4000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4001,4501 L 4001,4501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id34">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 3583,4500 C 3541,4500 3500,4541 3500,4583 L 3500,4917 C 3500,4959 3541,5001 3583,5001 L 3917,5001 C 3959,5001 4001,4959 4001,4917 L 4001,4583 C 4001,4541 3959,4500 3917,4500 L 3583,4500 Z M 3500,4500 L 3500,4500 Z M 4001,5001 L 4001,5001 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3583,4500 C 3541,4500 3500,4541 3500,4583 L 3500,4917 C 3500,4959 3541,5001 3583,5001 L 3917,5001 C 3959,5001 4001,4959 4001,4917 L 4001,4583 C 4001,4541 3959,4500 3917,4500 L 3583,4500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3500,4500 L 3500,4500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4001,5001 L 4001,5001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id35">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 3583,5000 C 3541,5000 3500,5041 3500,5083 L 3500,5417 C 3500,5459 3541,5501 3583,5501 L 3917,5501 C 3959,5501 4001,5459 4001,5417 L 4001,5083 C 4001,5041 3959,5000 3917,5000 L 3583,5000 Z M 3500,5000 L 3500,5000 Z M 4001,5501 L 4001,5501 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3583,5000 C 3541,5000 3500,5041 3500,5083 L 3500,5417 C 3500,5459 3541,5501 3583,5501 L 3917,5501 C 3959,5501 4001,5459 4001,5417 L 4001,5083 C 4001,5041 3959,5000 3917,5000 L 3583,5000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3500,5000 L 3500,5000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4001,5501 L 4001,5501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id36">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 3583,6000 C 3541,6000 3500,6041 3500,6083 L 3500,6417 C 3500,6459 3541,6501 3583,6501 L 3917,6501 C 3959,6501 4001,6459 4001,6417 L 4001,6083 C 4001,6041 3959,6000 3917,6000 L 3583,6000 Z M 3500,6000 L 3500,6000 Z M 4001,6501 L 4001,6501 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3583,6000 C 3541,6000 3500,6041 3500,6083 L 3500,6417 C 3500,6459 3541,6501 3583,6501 L 3917,6501 C 3959,6501 4001,6459 4001,6417 L 4001,6083 C 4001,6041 3959,6000 3917,6000 L 3583,6000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3500,6000 L 3500,6000 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4001,6501 L 4001,6501 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id37">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 3583,5500 C 3541,5500 3500,5541 3500,5583 L 3500,5917 C 3500,5959 3541,6001 3583,6001 L 3917,6001 C 3959,6001 4001,5959 4001,5917 L 4001,5583 C 4001,5541 3959,5500 3917,5500 L 3583,5500 Z M 3500,5500 L 3500,5500 Z M 4001,6001 L 4001,6001 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3583,5500 C 3541,5500 3500,5541 3500,5583 L 3500,5917 C 3500,5959 3541,6001 3583,6001 L 3917,6001 C 3959,6001 4001,5959 4001,5917 L 4001,5583 C 4001,5541 3959,5500 3917,5500 L 3583,5500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3500,5500 L 3500,5500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4001,6001 L 4001,6001 Z"/>
+      </g>
+     </g>
+     <g class="com.sun.star.drawing.CustomShape">
+      <g id="id38">
+       <path fill="rgb(255,204,153)" stroke="none" d="M 3583,6500 C 3541,6500 3500,6541 3500,6583 L 3500,6917 C 3500,6959 3541,7001 3583,7001 L 3917,7001 C 3959,7001 4001,6959 4001,6917 L 4001,6583 C 4001,6541 3959,6500 3917,6500 L 3583,6500 Z M 3500,6500 L 3500,6500 Z M 4001,7001 L 4001,7001 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3583,6500 C 3541,6500 3500,6541 3500,6583 L 3500,6917 C 3500,6959 3541,7001 3583,7001 L 3917,7001 C 3959,7001 4001,6959 4001,6917 L 4001,6583 C 4001,6541 3959,6500 3917,6500 L 3583,6500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 3500,6500 L 3500,6500 Z"/>
+       <path fill="none" stroke="rgb(255,66,14)" d="M 4001,7001 L 4001,7001 Z"/>
+      </g>
+     </g>
+    </g>
+   </g>
+  </g>
+ </g>
+</svg>
+\ No newline at end of file
diff --git a/slides/keyword-break.html b/slides/keyword-break.html

new file mode 100644 (file)

index 0000000..49160bb
--- /dev/null
+++ b/slides/keyword-break.html
@@ -0,0 +1,224 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title>Breaking keyword ciphers</title>
+    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
+    <style type="text/css">
+      /* Slideshow styles */
+      body {
+        font-size: 20px;
+      }
+      h1, h2, h3 {
+        font-weight: 400;
+        margin-bottom: 0;
+      }
+      h1 { font-size: 3em; }
+      h2 { font-size: 2em; }
+      h3 { font-size: 1.6em; }
+      a, a > code {
+        text-decoration: none;
+      }
+      code {
+        -moz-border-radius: 5px;
+        -web-border-radius: 5px;
+        background: #e7e8e2;
+        border-radius: 5px;
+        font-size: 16px;
+      }
+      .plaintext {
+        background: #272822;
+        color: #80ff80;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+      .ciphertext {
+        background: #272822;
+        color: #ff6666;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+       .float-right {
+        float: right;
+      }
+    </style>
+  </head>
+  <body>
+    <textarea id="source">
+
+# Breaking keyword ciphers
+
+a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
+--|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--
+k | e | y | w | o | r | d | a | b | c | f | g | h | i | j | l | m | n | p | q | s | t | u | v | x | z
+
+---
+
+# Duplicate and extend your `affine_break()` function
+
+* How to cycle through all the keys? What _are_ all the keys?
+
+* Look at `words.txt`
+
+---
+
+# Test it. 
+
+* `2013/4a.ciphertext`
+* `2013/4b.ciphertext`
+
+This will take a while. Fire up a system monitor. What's wrong?
+
+---
+
+# Python, threads, and the GIL
+
+Thread-safe shared-memory code is hard.
+
+Python's Global Interpreter Lock prevents shooting yourself in the foot.
+
+Where you want true parallelism, need different threads (Python processes).
+
+* Thread-safe shared-memory code is hard.
+
+The `multiprocessing` library makes this easier.
+
+But before we get there, a couple of diversions...
+
+---
+
+# DRYing code
+
+Three cipher breaking tasks so far.
+
+All working on the same principle:
+
+```
+find a way to enumerate all the possible keys
+initialise 'best so far'
+for each key:
+    decipher message with this key
+    score it
+    if it's better than the best so far:
+        update best so far
+```
+
+Repetition of code is a bad smell.
+
+Separate the 'try all keys, keep the best' logic from the 'score this one key' logic.
+
+---
+
+# map()
+
+A common task is to apply a function to each item in a sequence, returning a sequence of the results.
+
+```python
+def double(x):
+    return x * 2
+
+>>> map(double, [1,2,3])
+[2,4,6]
+```
+
+* `map()` is a higher-order function: its first argument is the function that's applied.
+
+How can we use this for keyword cipher breaking?
+
+---
+
+# Mapping keyword decipherings
+
+Define a function that takes a possible key (keyword and cipher type) and returns the key and its fitness.
+
+* (Also pass in the message and the fitness function)
+
+Use `map()` and `max()` to find the best key
+
+---
+
+# Arity of print()
+
+How many arguments does this take?
+
+How do you write a function that takes this many arguments?
+
+---
+
+# Function arguments
+
+## Positional, keyword
+
+* Common or garden parameters, as you're used to.
+* `def keyword_encipher(message, keyword, Keyword_wrap_alphabet.from_a):`
+
+## Excess positional
+* `def mean(x, *xs):`
+
+First number goes in `x`, remaining go in the tuple `xs`
+
+## Excess keyword
+
+* `def myfunc(arg1=0, **kwargs):`
+
+`kwargs` will be a Dict of the remaining keywords (not `arg1`)
+
+---
+
+# Back to `multiprocessing`
+
+What does `Pool.starmap()` do?
+
+---
+
+```python
+from multiprocessing import Pool
+
+def keyword_break_mp(message, wordlist=keywords, fitness=Pletters, chunksize=500):
+    helper_args = [??? for word in wordlist] # One tuple for each possible key
+    with Pool() as pool:
+        breaks = pool.starmap(keyword_break_worker, helper_args, chunksize) 
+        return max(breaks, key=lambda k: k[1])
+
+def keyword_break_worker(???):
+    ???
+    return (key, fitness)
+```
+
+* Gotcha: the function in `Pool.starmap()` must be defined at the top level
+    * This is definitely a "feature"
+
+---
+
+# Performance and chunksize
+
+Try the multiprocessing keyword break. Is it using all the resources?
+
+Setting `chunksize` is an art.
+
+## Map-reduce as a general pattern for multiprocessing
+
+    </textarea>
+    <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
+    </script>
+
+    <script type="text/javascript"
+      src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
+
+    <script type="text/javascript">
+      var slideshow = remark.create({ ratio: "16:9" });
+
+      // Setup MathJax
+      MathJax.Hub.Config({
+        tex2jax: {
+        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
+        }
+      });
+      MathJax.Hub.Queue(function() {
+        $(MathJax.Hub.getAllJax()).map(function(index, elem) {
+            return(elem.SourceElement());
+        }).parent().addClass('has-jax');
+      });
+      MathJax.Hub.Configured();
+    </script>
+  </body>
+</html>
diff --git a/slides/keyword-encipher.html b/slides/keyword-encipher.html

new file mode 100644 (file)

index 0000000..168bb5f
--- /dev/null
+++ b/slides/keyword-encipher.html
@@ -0,0 +1,209 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title>Keyword ciphers</title>
+    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
+    <style type="text/css">
+      /* Slideshow styles */
+      body {
+        font-size: 20px;
+      }
+      h1, h2, h3 {
+        font-weight: 400;
+        margin-bottom: 0;
+      }
+      h1 { font-size: 3em; }
+      h2 { font-size: 2em; }
+      h3 { font-size: 1.6em; }
+      a, a > code {
+        text-decoration: none;
+      }
+      code {
+        -moz-border-radius: 5px;
+        -web-border-radius: 5px;
+        background: #e7e8e2;
+        border-radius: 5px;
+        font-size: 16px;
+      }
+      .plaintext {
+        background: #272822;
+        color: #80ff80;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+      .ciphertext {
+        background: #272822;
+        color: #ff6666;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+       .float-right {
+        float: right;
+      }
+    </style>
+  </head>
+  <body>
+    <textarea id="source">
+
+# Keyword ciphers
+
+a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
+--|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--
+k | e | y | w | o | r | d | a | b | c | f | g | h | i | j | l | m | n | p | q | s | t | u | v | x | z
+
+* Taking a more Pythonic approach
+
+---
+
+# The cipher
+
+* Still character-by-character substitution, still monosubstitution.
+
+Ciphertext alphabet: start with a keyword, write out the rest of the alphabet, removing duplicates.
+
+## Three variants
+
+Write out the rest of the alphabet...
+
+1. ...starting from 'a' (keywordabcf...)
+2. ...starting from the last letter of the keyword (keywordfgh...)
+3. ...starting from the largest letter of the keyword (keywordzabc...)
+
+---
+
+# A more Pythonic way
+
+_string_`.translate()` and _string_`.maketrans()`
+
+* Make the 'ciphertext' alphabet, relate to the 'plaintext' alphabet (`string.ascii_lowercase`)
+* Use those to make the translation table
+* Enciphering is simply applying `plaintext.translate(enciphering_table)`
+* Deciphering just uses a different table
+
+---
+
+# Making the cipher alphabet from a keyword
+
+Three challenges:
+
+1. How to say which type of cipher alphabet to use
+2. Where to start the rest of the alphabet
+3. Removing duplicate letters
+
+Solutions:
+
+1. Keyword arguments for procedures
+2. sort and slices
+3. Use something like an ordered set
+
+Both enciphering and deciphering need the same keyword-based alphabet, so pull this out into another procedure.
+
+---
+
+# Keyword arguments
+
+Used to:
+
+1. give a default value for a parameter
+2. allow parameters to be named (not just positional)
+
+Give our `keyword_encipher` and `keyword_decipher` procedures a keyword parameter of `wrap_alphabet`.
+
+Pass this parameter to the `keyword_alphabet` procedure.
+
+## wrap_alphabet has no inherent meaning
+Use Python 3.4's `Enum`
+```python
+from enum import Enum
+
+class Keyword_wrap_alphabet(Enum):
+    from_a = 1
+    from_last = 2
+    from_largest = 3
+```
+
+(Use integers in earlier Pythons)
+---
+
+# Deduplicating a sequence
+
+We need
+
+* Something set-like
+* Something ordered
+
+No ordered set in Python, but do have an ordered dict.
+
+* Keys of a dict are a set. 
+* Keys in an ordered dict retain their order (subsequent instances are ignored)
+
+`deduplicated_list = list(collections.OrderedDict.fromkeys(list))`
+
+---
+
+# Sorts and slices
+
+## Recap 
+Write out the rest of the alphabet...
+
+1. ...starting from 'a' (keywordabcf...)
+2. ...starting from the last letter of the keyword (keywordfgh...)
+3. ...starting from the largest letter of the keyword (keywordzabc...)
+
+* Santitise the keyword before we use it
+
+---
+# Making the keyword alphabet
+
+## Cases
+1. As we're deduplicating anyway, just add the entire alphabet to the end of the keyword, then deduplicate. 
+`deduplicate(keyword + string.ascii_lowercase)`
+
+2. and 3. How to find the appropriate letter of the keyword.
+
+`deduplicate(keyword + string_ascii_lowercase[from:] + string.ascii_lowercase)`
+
+Question: why not take a slice of the second alphabet copy?
+
+Question: what do we use as the last letter of 'character'? 'r' or 'e'?
+
+`sorted()` will put a string in lexicographical order.
+`.find()` will find an item in a sequence
+
+---
+
+# Keyword enciphering
+
+Now we've got the keyword-based cipher alphabet, simply use `.translate()` to do the enciphering/deciphering.
+
+Use `''.maketrans()` to make the translation table.
+
+Sorted!
+
+Does it pass the tests?
+
+    </textarea>
+    <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
+    </script>
+
+    <script type="text/javascript"
+      src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
+
+    <script type="text/javascript">
+      var slideshow = remark.create({ ratio: "16:9" });
+
+      // Setup MathJax
+      MathJax.Hub.Config({
+        tex2jax: {
+        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
+        }
+      });
+      MathJax.Hub.Queue(function() {
+        $(MathJax.Hub.getAllJax()).map(function(index, elem) {
+            return(elem.SourceElement());
+        }).parent().addClass('has-jax');
+      });
+      MathJax.Hub.Configured();
+    </script>
+  </body>
+</html>
diff --git a/slides/transposition-encipher.html b/slides/transposition-encipher.html

new file mode 100644 (file)

index 0000000..0c09a4b
--- /dev/null
+++ b/slides/transposition-encipher.html
@@ -0,0 +1,258 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title>Keyword ciphers</title>
+    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
+    <style type="text/css">
+      /* Slideshow styles */
+      body {
+        font-size: 20px;
+      }
+      h1, h2, h3 {
+        font-weight: 400;
+        margin-bottom: 0;
+      }
+      h1 { font-size: 3em; }
+      h2 { font-size: 2em; }
+      h3 { font-size: 1.6em; }
+      a, a > code {
+        text-decoration: none;
+      }
+      code {
+        -moz-border-radius: 5px;
+        -web-border-radius: 5px;
+        background: #e7e8e2;
+        border-radius: 5px;
+        font-size: 16px;
+      }
+      .plaintext {
+        background: #272822;
+        color: #80ff80;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+      .ciphertext {
+        background: #272822;
+        color: #ff6666;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+       .float-right {
+        float: right;
+      }
+    </style>
+  </head>
+  <body>
+    <textarea id="source">
+
+# Transposition ciphers
+
+    attack the fort at dawn
+
+    a t t a c
+    k t h e f
+    o r t a t
+    d a w n
+
+    akod ttra aean cft
+
+---
+
+# Transposition ciphers
+
+Rather than changing symbols (substitution ciphers),
+
+Rearrange them.
+
+Still disguises the message.
+
+(Good ciphers do both, and more.)
+
+---
+
+# Scytale
+
+Even older than Caesar cipher.
+
+* Wrap a strip round a pole
+* Write the message along it
+* Unwind the strip
+* "Unreadable" unless reader has pole of same diameter
+
+    attack the fort at dawn
+
+    a t t a c
+    k t h e f
+    o r t a t
+    d a w n
+
+    akod ttra aean cft
+
+---
+
+# Generalising: column transposition ciphers
+
+Scytale essentially fills a grid by rows, then reads it by columns
+
+* (Deciphering is the reverse)
+
+Column transposition ciphers:
+
+* Fill a grid
+* Reorder columns based on keyword
+* Read the grid (perhaps different direction)
+
+Scytale is just a special case of column transposition.
+
+---
+
+# Grids and data structures
+
+How to represent a grid?
+
+What operations do we need to do on it?
+
+---
+
+# Grids and data structures
+
+How to represent a grid?
+
+* List of strings
+* Each row is a string
+* Rows in order in the list
+
+What operations do we need to do on it?
+
+* Fill, by rows or columns
+* Empty, by rows or columns
+* Rearrange columns
+* Calculate the size of the grid
+* Pad message to fit a rectangle of the required size
+
+---
+
+# Finding sizes
+
+Know number of columns
+
+Number of rows = ceiling(message length / columns)
+
+Paddding is (rows * columns) - message length
+
+* What to use as default padding? 
+* Keyword parameter!
+
+## Fit 'thequickbrownfox' (16 letters) into grid of 
+
+* 4 columns
+* 5 columns
+
+---
+
+# Fill and empty grid by rows
+
+Split message into row-sized chunks
+
+* slices and ranges
+
+Append all the rows together
+
+* `&lt;string&gt;.join()`
+
+Keep thinking about test cases!
+
+---
+
+# Fill and empty grid by columns
+
+Idea: fill and empty by rows, with a transposition.
+
+`zip(*rows)` and `itertools.zip_longest(*rows)`
+
+---
+
+# Swapping columns
+
+How to represent a transposition (_permutation_, to mathematicians)?
+
+How to create it from a keyword?
+
+---
+
+# Idea of a transposition
+
+Says, for each element, where it should go
+
+```
+0 1 2 3 4 5 6
+t r e a s o n
+
+a e n o r s t 
+3 2 6 5 1 4 0
+```
+
+The transposition `(3, 2, 6, 5, 1, 4, 0)` says that what was in position 3 moves to position 0, what was in position 2 moves to position 1, what was in position 6 moves to position 2, ...
+
+`enumerate(_iterable_)` yields an iterator that walks over the iterator, including the element indexes.
+
+```python
+>>> [i for i in enumerate('treason')]
+[(0, 't'), (1, 'r'), (2, 'e'), (3, 'a'), (4, 's'), (5, 'o'), (6, 'n')]
+>>> [i for i in enumerate((3, 2, 6, 5, 1, 4, 0))]
+[(0, 3), (1, 2), (2, 6), (3, 5), (4, 1), (5, 4), (6, 0)]
+```
+
+Write the `transpose` and `untranspose` functions.
+
+---
+
+# Transposition from a keyword
+
+Deduplicate the keyword
+
+Sort it
+
+Use `&lt;iterable&gt;.index()` to find the positions of the letters in the sorted keyword
+
+---
+
+# Transposition ciphers
+
+Put it all together 
+
+---
+
+# Masking the fill characters
+
+Padding characters can be distinctive.
+
+Make a function that generates a random letter, based on the `normalised_english_counts`
+
+Use `callable()` to check if the `fillvalue` should be called or just inserted
+
+    </textarea>
+    <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
+    </script>
+
+    <script type="text/javascript"
+      src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
+
+    <script type="text/javascript">
+      var slideshow = remark.create({ ratio: "16:9" });
+
+      // Setup MathJax
+      MathJax.Hub.Config({
+        tex2jax: {
+        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
+        }
+      });
+      MathJax.Hub.Queue(function() {
+        $(MathJax.Hub.getAllJax()).map(function(index, elem) {
+            return(elem.SourceElement());
+        }).parent().addClass('has-jax');
+      });
+      MathJax.Hub.Configured();
+    </script>
+  </body>
+</html>
diff --git a/slides/word-segmentation.html b/slides/word-segmentation.html

new file mode 100644 (file)

index 0000000..16fcb0a
--- /dev/null
+++ b/slides/word-segmentation.html
@@ -0,0 +1,370 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title>Word segmentation</title>
+    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
+    <style type="text/css">
+      /* Slideshow styles */
+      body {
+        font-size: 20px;
+      }
+      h1, h2, h3 {
+        font-weight: 400;
+        margin-bottom: 0;
+      }
+      h1 { font-size: 3em; }
+      h2 { font-size: 2em; }
+      h3 { font-size: 1.6em; }
+      a, a > code {
+        text-decoration: none;
+      }
+      code {
+        -moz-border-radius: 5px;
+        -web-border-radius: 5px;
+        background: #e7e8e2;
+        border-radius: 5px;
+        font-size: 16px;
+      }
+      .plaintext {
+        background: #272822;
+        color: #80ff80;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+      .ciphertext {
+        background: #272822;
+        color: #ff6666;
+        text-shadow: 0 0 20px #333;
+        padding: 2px 5px;
+      }
+       .float-right {
+        float: right;
+      }
+    </style>
+  </head>
+
+  <body>
+    <textarea id="source">
+
+# Word segmentation
+
+`makingsenseofthis`
+
+`making sense of this`
+
+---
+
+# The problem
+
+Ciphertext is re-split into groups to hide word bounaries.
+
+* HELMU TSCOU SINSA REISU PPOSE KINDI NTHEI ROWNW AYBUT THERE ISLIT TLEWA RMTHI NTHEK INDNE SSIRE CEIVE 
+
+How can we rediscover the word boundaries?
+
+* helmut s cousins are i suppose kind in their own way but there is little warmth in the kindness i receive
+
+---
+
+# Simple approach
+
+1. Try all possible word boundaries
+2. Return the one that looks most like English
+
+What's the complexity of this process?
+
+* (We'll fix that in a bit...)
+
+---
+
+# What do we mean by "looks like English"?
+
+Naïve Bayes bag-of-words worked well for cipher breaking. Can we apply the same intuition here?
+
+Probability of a bag-of-words (ignoring inter-word dependencies).
+
+Finding the counts of words in text is harder than letters.
+
+* More tokens, so need more data to cover sufficient words.
+
+---
+# Data sparsity and smoothing
+
+`counts_1w.txt` is the 333,333 most common words types, with number of tokens for each, collected by Google.
+
+Doesn't cover a lot of words we want, such as proper nouns.
+
+We'll have to guess the probability of unknown word.
+
+Lots of ways to do this properly (Laplace smoothing, Good-Turing smoothing)...
+
+...but we'll ignore them all.
+
+Assume unknown words have a count of 1.
+
+---
+
+# Storing word probabilities
+
+We want something like a `defaultdict` but with our own default value
+
+Subclass a dict!
+
+Constructor (`__init__`) takes a data file, does all the adding up and taking logs
+
+`__missing__` handles the case when the key is missing
+
+
+```python
+class Pdist(dict):
+    def __init__(self, data=[]):
+        for key, count in data2:
+            ...
+        self.total = ...
+    def __missing__(self, key):
+        return ...
+
+Pw = Pdist(data...)
+
+def Pwords(words):
+    return ...
+```
+
+---
+
+# Testing the bag of words model
+
+
+```python
+>>> 'hello' in Pw.keys()       >>> Pwords(['hello'])
+True                           -4.25147684171819
+>>> 'inigo' in Pw.keys()       >>> Pwords(['hello', 'my'])
+True                           -6.995724679281423
+>>> 'blj' in Pw.keys()         >>> Pwords(['hello', 'my', 'name'])
+False                          -10.098177451501074
+>>> Pw['hello']                >>> Pwords(['hello', 'my', 'name', 'is'])
+-4.25147684171819              -12.195018236240843
+>>> Pw['my']                   >>> Pwords(['hello', 'my', 'name', 'is', 'inigo'])
+-2.7442478375632335            -18.927603013570945
+>>> Pw['name']                 >>> Pwords(['hello', 'my', 'name', 'is', 'blj'])
+-3.102452772219651             -23.964487301167402
+>>> Pw['is']                   
+-2.096840784739768             
+>>> Pw['blj']                  
+-11.76946906492656
+```
+
+---
+
+# Splitting the input
+
+```
+To segment a string:
+    find all possible splits into a first portion and remainder
+    for each split:
+        segment the remainder
+    return the split with highest score
+```
+
+Indexing pulls out letters. `'sometext'[0]` = 's' ; `'keyword'[3]` = 'e' ; `'keyword'[-1]` = 't'
+
+Slices pulls out substrings. `'keyword'[1:4]` = 'ome' ; `'keyword'[:3]` = 'som' ; `'keyword'[5:]` = 'ext'
+
+`range()` will sweep across the string
+
+## Test case
+
+```python
+>>> splits('sometext')
+[('s', 'ometext'), ('so', 'metext'), ('som', 'etext'), ('some', 'text'), 
+ ('somet', 'ext'), ('somete', 'xt'), ('sometex', 't'), ('sometext', '')]
+```
+
+The last one is important
+
+* What if this is the last word of the text?
+
+---
+
+# Effeciency and memoisation
+
+* helmut s cousins are i suppose kind in their own way but there is little warmth in the kindness i receive
+
+At any stage, can consider the sentence as prefix, word, suffix
+
+* `littlewarmthin | the | kindness i receive`
+* `littlewarmthi | nthe | kindness i receive`
+* `littlewarmth | inthe | kindness i receive`
+* `littlewarmt | hinthe | kindness i receive`
+
+P(sentence) = P(prefix) × P(word) × P(suffix)
+
+* We're assuming independence of sections.
+* For a given word/suffix split, there is only one best segmentation of the suffix.
+* Best segmentation of sentence (with split here) must have the best segmentation of the suffix.
+* Once we've found it, no need to recalculate it.
+
+## What's the complexity now?
+
+---
+
+# Memoisation
+
+* Maintain a table of previously-found results
+* Every time we're asked to calculate a segmentation, look in the table.
+* If it's in the table, just return that.
+* If not, calculate it and store the result in the table.
+
+Wrap the segment function in something that maintains that table.
+
+In the standard library: `lru_cache` as a function decorator.
+
+```python
+from functools import lru_cache
+
+@lru_cache()
+def segment(text):
+    ...
+```
+* (Plenty of tutorials online on function decorators.)
+
+---
+
+# Implmentation detail
+
+You'll hit Python's recursion level limit.
+
+Easy to reset:
+
+```python
+import sys
+sys.setrecursionlimit(1000000)
+```
+
+---
+
+# Testing segmentation
+
+```python
+>>> segment('hello')
+['hello']
+>>> segment('hellomy')
+['hello', 'my']
+>>> segment('hellomyname')
+['hello', 'my', 'name']
+>>> segment('hellomynameis')
+['hellomynameis']
+```
+
+Oh.
+
+Why?
+
+---
+
+# A broken language model
+
+```python
+>>> Pwords(['hello'])
+-4.25147684171819
+>>> Pwords(['hello', 'my'])
+-6.995724679281423
+>>> Pwords(['hello', 'my', 'name'])
+-10.098177451501074
+>>> Pwords(['hello', 'my', 'name', 'is'])
+-12.195018236240843
+
+>>> Pw['is']                   
+-2.096840784739768             
+>>> Pw['blj']                  
+-11.76946906492656
+```
+
+Need a better estimate for probability of unknown words.
+
+Needs to take account of length of word.
+
+* Longer words are less probable.
+
+## To IPython for investigation!
+
+---
+
+# Making Pdist more flexible
+
+Want to give a sensible default for unknown elements
+
+* But this will vary by referent
+* Different languages, *n*-grams, etc. 
+
+Make it a parameter!
+
+---
+
+# Hint
+
+```python
+class Pdist(dict):
+    def __init__(self, data=[], estimate_of_missing=None):
+        for key, count in data2:
+            ...
+        self.total = ...
+    def __missing__(self, key):
+        if estimate_of_missing:
+            return estimate_of_missing(key, self.total)
+        else:
+            return ...
+
+def log_probability_of_unknown_word(key, N):
+    return -log10(N * 10**((len(key) - 2) * 1.4))
+
+Pw = Pdist(datafile('count_1w.txt'), log_probability_of_unknown_word)            
+```
+
+---
+
+# Testing segmentation again
+
+```python
+>>> segment('hello')
+['hello']
+>>> segment('hellomy')
+['hello', 'my']
+>>> segment('hellomyname')
+['hello', 'my', 'name']
+>>> segment('hellomynameis')
+['hello', 'my', 'name', 'is']
+>>> ' '.join(segment(sanitise('HELMU TSCOU SINSA REISU PPOSE KINDI NTHEI ROWNW '
+                              'AYBUT THERE ISLIT TLEWA RMTHI NTHEK INDNE SSIRE CEIVE ')))
+'helmut s cousins are i suppose kind in their own way but there is 
+ little warmth in the kindness i receive'
+```
+
+Try it out on the full decrypt of `2013/2b.ciphertext` (it's a Caesar cipher)
+
+
+    </textarea>
+    <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
+    </script>
+
+    <script type="text/javascript"
+      src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
+
+    <script type="text/javascript">
+      var slideshow = remark.create({ ratio: "16:9" });
+
+      // Setup MathJax
+      MathJax.Hub.Config({
+        tex2jax: {
+        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
+        }
+      });
+      MathJax.Hub.Queue(function() {
+        $(MathJax.Hub.getAllJax()).map(function(index, elem) {
+            return(elem.SourceElement());
+        }).parent().addClass('has-jax');
+      });
+      MathJax.Hub.Configured();
+    </script>
+  </body>
+</html>
author	Neil Smith <neil.git@njae.me.uk>
	Thu, 3 Jul 2014 19:44:02 +0000 (20:44 +0100)
committer	Neil Smith <neil.git@njae.me.uk>
	Thu, 3 Jul 2014 19:44:02 +0000 (20:44 +0100)
slides/affine-break.html	[new file with mode: 0644]	patch \| blob
slides/affine-encipher.html	[new file with mode: 0644]	patch \| blob
slides/alternative-plaintext-scoring.html	[new file with mode: 0644]	patch \| blob
slides/caesar-break.html		patch \| blob \| history
slides/fast-good-cheap.gif	[new file with mode: 0644]	patch \| blob
slides/further-work.html	[new file with mode: 0644]	patch \| blob
slides/gcd.svg	[new file with mode: 0644]	patch \| blob
slides/keyword-break.html	[new file with mode: 0644]	patch \| blob
slides/keyword-encipher.html	[new file with mode: 0644]	patch \| blob
slides/transposition-encipher.html	[new file with mode: 0644]	patch \| blob
slides/word-segmentation.html	[new file with mode: 0644]	patch \| blob