Hey, everyone, and welcome back to this class natural language processing in Python.
In this lecture, we are going to outline all of the pieces of the code that we need to complete in
order to have a fully functioning message decryption script.
As usual, you're strongly encouraged to code by yourself first, or at least try to write as much of
it as possible by yourself.
So in this lecture, we're going to list out all of the pieces and also give you a general overview
of the structure of the code.
Then you can pick and choose which parts of the code you think you'll be able to write on your own and
in which ones you might need help with.
If you notice that this is just way over your head and you have no idea how you will write any of this
code.
Let me remind you that this section of the course is considered optional.
It should be very interesting to those who are interested.
But if the concepts are too overwhelming for you, please feel free to move on.
Let's start with the data that we're going to use, thanks to Project Gutenberg, we have access to
many classic books, which you can download in plain text, which require very little pre-processing.
I provided you with a starter file called Cipher a placeholder dot pi.
This gives you two things.
First, it gives you a link to download Moby Dick in plain text, which is the book I use to build a
character level language model.
If you recall, that's just the unit graham and bigram possibilities.
Second, I provide you with another snippet of text, this time from a different book The Adventures
of Sherlock Holmes.
This snippet of text will serve as the message that we want to encrypt and then decrypt using our algorithm.
Of course, if you would like to choose a different message to send.
That's OK, too.
You can even choose your own text corpus to train your language model on if you want.
If you plan on trying to write the code by yourself, then you should only look at this file and not
at any other Python files.
Let's now look at a high level outline of what we want our script to do.
The first major task will be to create a random substitution cipher.
Recall that this is just a dictionary that maps the unencrypted letter to the encrypted letter.
So this serves as our ground truth, and this is what our algorithm is trying to find.
The second major task will be to read in the Moby Dick text and create a character level language model.
These are the unique graham and bigram probabilities.
Remember that if we have letters in our alphabet, then we'll have you anagram probabilities and a v
squared bigram probabilities.
It would also be useful to have a function that will take in a message represented by a string or a
list of strings and return its log likelihood.
This is the function that will need to evaluate the fitness of a decrypted message.
The next major task will be to create encoding and decoding functions.
We'll use the encoding function to encrypt our message using the true substitution cipher, which we
will assume is unknown to the decryption algorithm.
We'll use the decoding function to decrypt an encrypted message using a guess for the substitution cipher.
So that's the main difference between these two functions.
The encoding function uses the true substitution cipher and the decoding function uses our gas.
Finally, we'll need to run our genetic algorithm.
This will involve initializing the first generation of the population and then going into a loop where
we continually make new offspring, evaluate each member of the population and keep only the fittest
individuals.
We repeat that process until we've reached a maximum number of iterations, at which point we've hopefully
decrypted the hidden message.
Afterwards, we would, of course, like to print out the results and compare it to the true message.
To summarize all the steps we need to do, let's reiterate them one more time.
First, we need to create the substitution cipher.
Next, we need to create our language model using the book Moby Dick.
This should include a function that can evaluate the log likelihood of a given message.
Next, we're going to encode our message using the true substitution cipher.
We'll also need a decoding function that we make use of later.
Next, we run through the genetic algorithm described previously in order to find the substitution cipher
that yields a message with the maximum log likelihood.
If you decide to code this yourself, which I hope you do.
Then good luck and I will see you in the next lecture.