FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Added ShiftDecoder to notebook by Chipe1 · Pull Request #463 · aimacode/aima-python · GitHub

  1. aimacode
  2. aima-python

Repository navigation

Added ShiftDecoder to notebook #463

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
norvig merged 3 commits into from
Apr 6, 2017
Conversation 3 Commits 3 Checks 0 Files changed
Merged

Added ShiftDecoder to notebook #463

Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
a52b431
Added ShiftDecoder to notebook
Chipe1 Apr 1, 2017
1e4a929
replaced code with psource
Chipe1 Apr 1, 2017
bcf0d0b
fix spelling mistakes
Chipe1 Apr 2, 2017
File filter

Filter by extension

Filter by extension .ipynb  (1) All 1 file type selected
Viewed files
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Unified
Split
Hide whitespace
Diff view
Unified
Split
Hide whitespace
220 changes: 184 additions & 36 deletions text.ipynb
Show comments
View file
Open in desktop
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Original file line number Diff line number Diff line change
Expand Up @@ -13,6 +13,20 @@
"This notebook serves as supporting material for topics covered in **Chapter 22 - Natural Language Processing** from the book *Artificial Intelligence: A Modern Approach*. This notebook uses implementations from [text.py](https://github.com/aimacode/aima-python/blob/master/text.py)."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true,
"deletable": true,
"editable": true
},
"outputs": [],
"source": [
"from text import *\n",
"from utils import DataFile"
]
},
{
"cell_type": "markdown",
"metadata": {
Expand All @@ -26,7 +40,11 @@
"* Viterbi Text Segmentation\n",
" * Overview\n",
" * Implementation\n",
" * Example"
" * Example\n",
"* Decoders\n",
" * Introduction\n",
" * Shift Decoder\n",
" * Permutation Decoder"
]
},
{
Expand All @@ -49,7 +67,7 @@
},
{
"cell_type": "code",
"execution_count": 4,
"execution_count": 2,
"metadata": {
"collapsed": false,
"deletable": true,
Expand All @@ -66,9 +84,6 @@
}
],
"source": [
"from text import UnigramTextModel, NgramTextModel, words\n",
"from utils import DataFile\n",
"\n",
"flatland = DataFile(\"EN-text/flatland.txt\").read()\n",
"wordseq = words(flatland)\n",
"\n",
Expand Down Expand Up @@ -117,38 +132,15 @@
},
{
"cell_type": "code",
"execution_count": 1,
"execution_count": 3,
"metadata": {
"collapsed": true,
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [],
"source": [
"def viterbi_segment(text, P):\n",
" \"\"\"Find the best segmentation of the string of characters, given the\n",
" UnigramTextModel P.\"\"\"\n",
" # best[i] = best probability for text[0:i]\n",
" # words[i] = best word ending at position i\n",
" n = len(text)\n",
" words = [''] + list(text)\n",
" best = [1.0] + [0.0] * n\n",
" # Fill in the vectors best words via dynamic programming\n",
" for i in range(n+1):\n",
" for j in range(0, i):\n",
" w = text[j:i]\n",
" newbest = P[w] * best[i - len(w)]\n",
" if newbest >= best[i]:\n",
" best[i] = newbest\n",
" words[i] = w\n",
" # Now recover the sequence of best words\n",
" sequence = []\n",
" i = len(words) - 1\n",
" while i > 0:\n",
" sequence[0:0] = [words[i]]\n",
" i = i - len(words[i])\n",
" # Return sequence of best words and overall probability\n",
" return sequence, best[-1]"
"%psource viterbi_segment"
]
},
{
Expand Down Expand Up @@ -177,7 +169,7 @@
},
{
"cell_type": "code",
"execution_count": 6,
"execution_count": 4,
"metadata": {
"collapsed": false,
"deletable": true,
Expand All @@ -194,9 +186,6 @@
}
],
"source": [
"from text import UnigramTextModel, words, viterbi_segment\n",
"from utils import DataFile\n",
"\n",
"flatland = DataFile(\"EN-text/flatland.txt\").read()\n",
"wordseq = words(flatland)\n",
"P = UnigramTextModel(wordseq)\n",
Expand All @@ -216,6 +205,165 @@
"source": [
"The algorithm correctly retrieved the words from the string. It also gave us the probability of this sequence, which is small, but still the most probable segmentation of the string."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"## Decoders\n",
"\n",
"### Introduction\n",
"\n",
"In this section we will try to decode ciphertext using probabilistic text models. A ciphertext is obtained by performing encryption on a text message. This encryption lets us communicate safely, as anyone who has access to the ciphertext but doesn't know how to decode it cannot read the message. We will restrict our study to <b>Monoalphabetic Substitution Ciphers</b>. These are primitive forms of cipher where each letter in the message text (also known as plaintext) is replaced by another another letter of the alphabet.\n",
"\n",
"### Shift Decoder\n",
"\n",
"#### The Caesar cipher\n",
"\n",
"The Caesar cipher, also known as shift cipher is a form of monoalphabetic substitution ciphers where each letter is <i>shifted</i> by a fixed value. A shift by <b>`n`</b> in this context means that each letter in the plaintext is replaced with a letter corresponding to `n` letters down in the alphabet. For example the plaintext `\"ABCDWXYZ\"` shifted by `3` yields `\"DEFGZABC\"`. Note how `X` became `A`. This is because the alphabet is cyclic, i.e. the letter after the last letter in the alphabet, `Z`, is the first letter of the alphabet - `A`."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"DEFGZABC\n"
]
}
],
"source": [
"plaintext = \"ABCDWXYZ\"\n",
"ciphertext = shift_encode(plaintext, 3)\n",
"print(ciphertext)"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"#### Decoding a Caesar cipher\n",
"\n",
"To decode a Caesar cipher we exploit the fact that not all letters in the alphabet are used equally. Some letters are used more than others and some pairs of letters are more probable to occur together. We call a pair of consecutive letters a <b>bigram</b>."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['th', 'hi', 'is', 's ', ' i', 'is', 's ', ' a', 'a ', ' s', 'se', 'en', 'nt', 'te', 'en', 'nc', 'ce']\n"
]
}
],
"source": [
"print(bigrams('this is a sentence'))"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"We use `CountingProbDist` to get the probability distribution of bigrams. In the latin alphabet consists of only only `26` letters. This limits the total number of possible substitutions to `26`. We reverse the shift encoding for a given `n` and check how probable it is using the bigram distribution. We try all `26` values of `n`, i.e. from `n = 0` to `n = 26` and use the value of `n` which gives the most probable plaintext."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [],
"source": [
"%psource ShiftDecoder"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"#### Example\n",
"\n",
"Let us encode a secret message using Caeasar cipher and then try decoding it using `ShiftDecoder`. We will again use `flatland.txt` to build the text model"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The code is \"Guvf vf n frperg zrffntr\"\n"
]
}
],
"source": [
"plaintext = \"This is a secret message\"\n",
"ciphertext = shift_encode(plaintext, 13)\n",
"print('The code is', '\"' + ciphertext + '\"')"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The decoded message is \"This is a secret message\"\n"
]
}
],
"source": [
"flatland = DataFile(\"EN-text/flatland.txt\").read()\n",
"decoder = ShiftDecoder(flatland)\n",
"\n",
"decoded_message = decoder.decode(ciphertext)\n",
"print('The decoded message is', '\"' + decoded_message + '\"')"
]
}
],
"metadata": {
Expand All @@ -234,7 +382,7 @@
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.2"
"version": "3.6.0"
}
},
"nbformat": 4,
Expand Down
Back | FazBrowse Home | New Git URL