NLP/03_string_distances_with_exercise.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# String distances\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:51.642172Z",
     "start_time": "2022-03-02T13:43:48.910197Z"
    }
   },
   "outputs": [],
   "source": [
    "import nltk\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "#import editdistance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: nltk in /Users/qijunjin/miniforge3/lib/python3.9/site-packages (3.7)\n",
      "Requirement already satisfied: tqdm in /Users/qijunjin/miniforge3/lib/python3.9/site-packages (from nltk) (4.62.3)\n",
      "Requirement already satisfied: regex>=2021.8.3 in /Users/qijunjin/miniforge3/lib/python3.9/site-packages (from nltk) (2022.1.18)\n",
      "Requirement already satisfied: click in /Users/qijunjin/miniforge3/lib/python3.9/site-packages (from nltk) (8.0.4)\n",
      "Requirement already satisfied: joblib in /Users/qijunjin/miniforge3/lib/python3.9/site-packages (from nltk) (1.1.0)\n"
     ]
    }
   ],
   "source": [
    "!pip install nltk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package words to /Users/qijunjin/nltk_data...\n",
      "[nltk_data]   Package words is already up-to-date!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import nltk\n",
    "\n",
    "nltk.download('words')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:51.714260Z",
     "start_time": "2022-03-02T13:43:51.643892Z"
    }
   },
   "outputs": [],
   "source": [
    "words = nltk.corpus.words.words()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:52.702841Z",
     "start_time": "2022-03-02T13:43:52.391683Z"
    }
   },
   "outputs": [],
   "source": [
    "pd.DataFrame(words).to_csv(\"words_nltk.csv\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Jaccard similarity\n",
    "\n",
    "\n",
    "Jaccard Distance is a measure of dissimilarity for sets. The lower the dissimilarity, the more similar are two objects.\n",
    "\n",
    "$$\n",
    "\\text{jaccard_similarity}(A,B) = \\frac{| A \\cap B |} {| A \\cup B |} \n",
    "$$\n",
    "\n",
    "\n",
    "$$\n",
    "\\text{jaccard_distance}(A,B) = 1 - \\frac{| A \\cap B |} {| A \\cup B |} \n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:53.436275Z",
     "start_time": "2022-03-02T13:43:53.429108Z"
    }
   },
   "outputs": [],
   "source": [
    "def jaccard_similarity(s1,s2):\n",
    "    return len(s1.intersection(s2)) / len(s1.union(s2))\n",
    "\n",
    "def jaccard_distance(s1,s2):\n",
    "    return 1. - jaccard_similarity(s1,s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:54.276888Z",
     "start_time": "2022-03-02T13:43:54.264659Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5454545454545454"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jaccard_similarity(set(\"exponential\"),set(\"polynomial\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:55.010660Z",
     "start_time": "2022-03-02T13:43:55.004487Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8888888888888888"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jaccard_similarity(set(\"exponential\"),set(\"exponentia\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:55.787582Z",
     "start_time": "2022-03-02T13:43:55.780586Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(11, 6)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(set(\"exponential\").union(set(\"polynomial\"))), len(set(\"exponential\").intersection(set(\"polynomial\")))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:56.442480Z",
     "start_time": "2022-03-02T13:43:56.437540Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.8571428571428571, 0.1428571428571429, 0.0)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set1 = set('mapping')\n",
    "set2 = set('mappings')\n",
    "jaccard_similarity(set1,set2), jaccard_distance(set1,set2), jaccard_distance(set1,set1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:56.787495Z",
     "start_time": "2022-03-02T13:43:56.782864Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.14285714285714285"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set1 = set('mapping')\n",
    "set2 = set('mappings')\n",
    "nltk.jaccard_distance(set1, set2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is the issue with the similarity? Order of the characters not matter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:57.904589Z",
     "start_time": "2022-03-02T13:43:57.898326Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.16666666666666663"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set1 = set('panmpi')\n",
    "set2 = set('mapping')\n",
    "jaccard_distance(set1,set2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:58.591471Z",
     "start_time": "2022-03-02T13:43:58.586131Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.16666666666666663"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set1 = set('mapping')\n",
    "set2 = set('mappin')\n",
    "jaccard_distance(set1,set2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:43:59.288191Z",
     "start_time": "2022-03-02T13:43:59.283718Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set1 = set('mapping')\n",
    "set2 = set('mappin')\n",
    "nltk.jaccard_distance(set1, set2) == jaccard_distance(set1, set2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:00.427113Z",
     "start_time": "2022-03-02T13:43:59.832632Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "236736"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words     =  nltk.corpus.words.words()\n",
    "words_set = [set(w) for w in words]\n",
    "len(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:00.434286Z",
     "start_time": "2022-03-02T13:44:00.429523Z"
    }
   },
   "outputs": [],
   "source": [
    "def compute_distances(query_word, words):\n",
    "    distances = []\n",
    "\n",
    "    for word in words:\n",
    "        dist = jaccard_distance(query_word, word)\n",
    "        distances.append(dist)\n",
    "    return distances\n",
    "\n",
    "def find_k_nearest_neighbors(query_word, words, K):\n",
    "    distances = compute_distances(query_word, words)\n",
    "    idx = np.argsort(distances)[::-1] \n",
    "    return [words[i] for i in idx[0:K]]\n",
    "\n",
    "def find_k_nearest_indices(query_word, words, K, return_distances=False):\n",
    "    distances = compute_distances(query_word, words)\n",
    "    idx = np.argsort(distances) \n",
    "    \n",
    "    if return_distances:\n",
    "        return [i for i in idx[0:K]], [distances[i] for i in idx[0:K]]\n",
    "    else:\n",
    "        return [i for i in idx[0:K]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:01.270323Z",
     "start_time": "2022-03-02T13:44:00.985900Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the closest word to query={'g', 'r', 'd', 'n', 'i', 'a', 'u'} is guardian\n"
     ]
    }
   ],
   "source": [
    "query = set('guardin')\n",
    "distances = compute_distances(query,words)\n",
    "print(f\"the closest word to query={query} is {words[np.argmin(distances)]}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:03.065515Z",
     "start_time": "2022-03-02T13:44:02.984253Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['unniggard',\n",
       " 'gurniad',\n",
       " 'guarding',\n",
       " 'undaring',\n",
       " 'guardian',\n",
       " 'indiguria',\n",
       " 'ungrained',\n",
       " 'antidrug',\n",
       " 'unarraigned',\n",
       " 'underguardian']"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "closest_words = [words[d] for d in np.argsort(distances)]\n",
    "closest_words[0:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:03.947145Z",
     "start_time": "2022-03-02T13:44:03.697652Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the closest word to query={'o', 'r', 'e', 'l', 'p', 'u', 'm', 'c'} is operculum\n"
     ]
    }
   ],
   "source": [
    "query = set('compuler')\n",
    "distances = compute_distances(query,words)\n",
    "print(f\"the closest word to query={query} is {words[np.argmin(distances)]}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:05.640274Z",
     "start_time": "2022-03-02T13:44:05.549335Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['operculum',\n",
       " 'preoperculum',\n",
       " 'scruplesome',\n",
       " 'macropleural',\n",
       " 'praeoperculum',\n",
       " 'leucospermous',\n",
       " 'coelospermous',\n",
       " 'crumple',\n",
       " 'pleurocele',\n",
       " 'compeller']"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "closest_words = [words[d] for d in np.argsort(distances)]\n",
    "closest_words[0:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Improving set feature descriptor \n",
    "Let us improve the returned closest words using the jaccard distance.\n",
    "\n",
    "We can compute the jaccard distance using substrings of n characters from a string, if we do this we introduce local information about the order of substrings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:09.261177Z",
     "start_time": "2022-03-02T13:44:09.258131Z"
    }
   },
   "outputs": [],
   "source": [
    "def build_n_chars(w, n_chars=2):\n",
    "    if len(w)<n_chars:\n",
    "        return set([w])\n",
    "    else:\n",
    "        return set([w[i:i+n_chars] for i in range(len(w)-n_chars+1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:09.935122Z",
     "start_time": "2022-03-02T13:44:09.930755Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'com', 'ler', 'mpu', 'omp', 'pul', 'ule'}"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "build_n_chars('compuler',3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:11.434324Z",
     "start_time": "2022-03-02T13:44:10.232991Z"
    }
   },
   "outputs": [],
   "source": [
    "words_set_2chars = [build_n_chars(w,2) for w in words]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-03-07T18:46:14.972194Z",
     "start_time": "2021-03-07T18:46:14.970486Z"
    }
   },
   "source": [
    "##### closest word to 'compuler'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:11.439210Z",
     "start_time": "2022-03-02T13:44:11.436553Z"
    }
   },
   "outputs": [],
   "source": [
    "query = 'compuler'\n",
    "query_transformed = build_n_chars(query,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:11.736986Z",
     "start_time": "2022-03-02T13:44:11.440721Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['compulsion',\n",
       " 'compulsory',\n",
       " 'computable',\n",
       " 'puller',\n",
       " 'compulsed',\n",
       " 'compeller',\n",
       " 'completer',\n",
       " 'compiler',\n",
       " 'computer',\n",
       " 'puler']"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distances = compute_distances(query_transformed, words_set_2chars)\n",
    "idx =np.argsort(distances)[::-1]\n",
    "[words[i] for i in idx[-10:]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:12.763792Z",
     "start_time": "2022-03-02T13:44:12.464102Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>words</th>\n",
       "      <th>distances</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>puler</td>\n",
       "      <td>0.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>computer</td>\n",
       "      <td>0.444444</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>compiler</td>\n",
       "      <td>0.444444</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>completer</td>\n",
       "      <td>0.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>compeller</td>\n",
       "      <td>0.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>compulsed</td>\n",
       "      <td>0.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>puller</td>\n",
       "      <td>0.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>computable</td>\n",
       "      <td>0.545455</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>compulsory</td>\n",
       "      <td>0.545455</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>compulsion</td>\n",
       "      <td>0.545455</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "        words  distances\n",
       "0       puler   0.428571\n",
       "1    computer   0.444444\n",
       "2    compiler   0.444444\n",
       "3   completer   0.500000\n",
       "4   compeller   0.500000\n",
       "5   compulsed   0.500000\n",
       "6      puller   0.500000\n",
       "7  computable   0.545455\n",
       "8  compulsory   0.545455\n",
       "9  compulsion   0.545455"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "indices, distances = find_k_nearest_indices(query_transformed, words_set_2chars ,10, return_distances=True)\n",
    "top_k_words = [words[i] for i in indices]\n",
    "top_k_dists = distances\n",
    "df_top_k =pd.DataFrame({'words':top_k_words,\n",
    "                        'distances':top_k_dists})\n",
    "df_top_k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### feature vector with single letters and pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:19.257514Z",
     "start_time": "2022-03-02T13:44:19.253626Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'compuler'"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "query"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:21.263875Z",
     "start_time": "2022-03-02T13:44:19.856711Z"
    }
   },
   "outputs": [],
   "source": [
    "words_feature_set = [ set(w) | build_n_chars(w,2) for w in words]\n",
    "query_transformed = set(query) | build_n_chars(query,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:21.700642Z",
     "start_time": "2022-03-02T13:44:21.267470Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>words</th>\n",
       "      <th>distances</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>compiler</td>\n",
       "      <td>0.333333</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>compeller</td>\n",
       "      <td>0.333333</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>computer</td>\n",
       "      <td>0.333333</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>completer</td>\n",
       "      <td>0.368421</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>compulsed</td>\n",
       "      <td>0.400000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>puler</td>\n",
       "      <td>0.400000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>compole</td>\n",
       "      <td>0.411765</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>coruler</td>\n",
       "      <td>0.411765</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>compeer</td>\n",
       "      <td>0.411765</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>compoer</td>\n",
       "      <td>0.411765</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       words  distances\n",
       "0   compiler   0.333333\n",
       "1  compeller   0.333333\n",
       "2   computer   0.333333\n",
       "3  completer   0.368421\n",
       "4  compulsed   0.400000\n",
       "5      puler   0.400000\n",
       "6    compole   0.411765\n",
       "7    coruler   0.411765\n",
       "8    compeer   0.411765\n",
       "9    compoer   0.411765"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "indices, distances = find_k_nearest_indices(query_transformed, words_feature_set ,10, return_distances=True)\n",
    "top_k_words = [words[i] for i in indices]\n",
    "top_k_dists = distances\n",
    "df_top_k = pd.DataFrame({'words':top_k_words,\n",
    "                        'distances':top_k_dists})\n",
    "df_top_k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Edit distance\n",
    "\n",
    "Given two strings `x` and `y` the edit distance is the cheapest possible sequence of **character edits** to transform `x` to `y`.\n",
    "\n",
    "Character edits (or character transformations) are:\n",
    "\n",
    "- Insert a character `c`\n",
    "- Delete `c`\n",
    "- Replace `c` by `c'`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:26.152506Z",
     "start_time": "2022-03-02T13:44:26.143269Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "d(cat       ,drauing) = 6\n",
      "d(draw      ,drauing) = 4\n",
      "d(drawing   ,drauing) = 1\n",
      "d(drought   ,drauing) = 4\n",
      "d(linking   ,drauing) = 4\n",
      "d(living    ,drauing) = 4\n",
      "d(dragon    ,drauing) = 3\n",
      "d(handemore ,drauing) = 9\n",
      "d(eliot     ,drauing) = 6\n",
      "d(queen     ,drauing) = 6\n",
      "\n",
      "the closest word is drawing\n"
     ]
    }
   ],
   "source": [
    "mistake = \"drauing\" \n",
    "words = ['cat', 'draw', 'drawing', 'drought', 'linking',\n",
    "        'living', 'dragon', 'handemore', 'eliot', 'queen']\n",
    "\n",
    "distances = []\n",
    "for word in words:\n",
    "    ed = nltk.edit_distance(mistake, word)\n",
    "    print(\"d({:10},{}) = {}\".format(word,mistake,ed))\n",
    "    distances.append(ed)\n",
    "\n",
    "print(\"\\nthe closest word is\", words[np.argmin(distances)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:26.722662Z",
     "start_time": "2022-03-02T13:44:26.715639Z"
    }
   },
   "outputs": [],
   "source": [
    "def edit_distance_recursive(x,y):\n",
    "    if len(x) ==0:\n",
    "        return len(y)\n",
    "    if len(y) == 0:\n",
    "        return len(x)\n",
    "    \n",
    "    delta = 0 if x[-1] == y[-1] else 1\n",
    "    return min(edit_distance_recursive(x[:-1],y[:-1]) + delta,\n",
    "               edit_distance_recursive(x[:-1],y)      + 1,\n",
    "               edit_distance_recursive(x,y[:-1])      + 1)\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:27.155202Z",
     "start_time": "2022-03-02T13:44:27.149837Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edit_distance_recursive(\"ab\", \"ac\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:44:27.791821Z",
     "start_time": "2022-03-02T13:44:27.784845Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 888 µs, sys: 0 ns, total: 888 µs\n",
      "Wall time: 897 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "edit_distance_recursive(\"house\", \"hause\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:00.781654Z",
     "start_time": "2020-03-05T21:50:59.636501Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "distance by edit_distance_recursive 3\n",
      "\n",
      "CPU times: user 1.13 s, sys: 9.25 ms, total: 1.14 s\n",
      "Wall time: 1.14 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "dist_recursive = edit_distance_recursive(\"superman\", \"supermaniac\")\n",
    "print(f\"distance by edit_distance_recursive {dist_recursive}\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:00.785507Z",
     "start_time": "2020-03-05T21:51:00.783274Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time needed to compute the distance between a w and all vocab 0.0024582104228121925 hours\n"
     ]
    }
   ],
   "source": [
    "t =  len(words)/(1.13*60*60)\n",
    "print(f\"time needed to compute the distance between a w and all vocab {t} hours\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How come nltk needs less than 100 µs?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:00.789584Z",
     "start_time": "2020-03-05T21:51:00.787012Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "distance by nltk 3\n",
      "\n",
      "CPU times: user 174 µs, sys: 42 µs, total: 216 µs\n",
      "Wall time: 196 µs\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "dist_nltk = nltk.edit_distance(\"superman\", \"supermaniac\")\n",
    "print(f\"distance by nltk {dist_nltk}\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the `edit_dinstance_recursive` calls itself with the same input values many times, making it very slow.\n",
    "\n",
    "We can know the number of times it call itself using a global variable counter `n`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:01.482703Z",
     "start_time": "2020-03-05T21:51:01.479718Z"
    }
   },
   "outputs": [],
   "source": [
    "n = 0\n",
    "def edit_distance_recursive(x,y):\n",
    "    global n\n",
    "    if len(x) ==0:\n",
    "        return len(y)\n",
    "    if len(y) == 0:\n",
    "        return len(x)\n",
    "    \n",
    "    if x ==\"super\" and y==\"sup\":\n",
    "        n += 1\n",
    "    \n",
    "    delta = 0 if x[-1] == y[-1] else 1\n",
    "    return min(edit_distance_recursive(x[:-1],y[:-1]) + delta,\n",
    "               edit_distance_recursive(x[:-1],y)      + 1,\n",
    "               edit_distance_recursive(x,y[:-1])      + 1)\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:03.133314Z",
     "start_time": "2020-03-05T21:51:01.975025Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "833"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edit_distance_recursive(\"superman\", \"supermaniac\")\n",
    "n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Other types of edit distance\n",
    "\n",
    "\n",
    "You can put a diferent cost to the different operations performed when computing an edit distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-03-08T16:58:52.290378Z",
     "start_time": "2021-03-08T16:58:52.287569Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w1 = 'mapping'\n",
    "w2 = 'mappings'\n",
    "nltk.edit_distance(w1, w2,substitution_cost=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:03.145899Z",
     "start_time": "2020-03-05T21:51:03.141727Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w1 = 'mapping'\n",
    "w2 = 'mappink'\n",
    "nltk.edit_distance(w1, w2,substitution_cost=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using a big list of words\n",
    "\n",
    "\n",
    "Fast implementations are important when computing edit distances between lots of candidates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:03.458897Z",
     "start_time": "2020-03-05T21:51:03.448776Z"
    }
   },
   "outputs": [],
   "source": [
    "import editdistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we have a lot of words it's important to make sure we use a fast distance immplementation.\n",
    "\n",
    "- `editdistance` provides a much faster implementation than `nltk`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:03.870828Z",
     "start_time": "2020-03-05T21:51:03.813076Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "236736"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = nltk.corpus.words.words()\n",
    "len(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:14.724132Z",
     "start_time": "2020-03-05T21:51:03.977389Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "the closest word is drawing\n"
     ]
    }
   ],
   "source": [
    "#%%time\n",
    "mistake = \"drauing\" \n",
    "distances = []\n",
    "for word in words:\n",
    "    ed = nltk.edit_distance(mistake, word)\n",
    "    distances.append(ed)\n",
    "    \n",
    "print(\"\\nthe closest word is\", words[np.argmin(distances)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:14.727460Z",
     "start_time": "2020-03-05T21:51:14.725653Z"
    }
   },
   "outputs": [],
   "source": [
    "import editdistance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.223225Z",
     "start_time": "2020-03-05T21:51:14.728887Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "the closest word is drawing\n"
     ]
    }
   ],
   "source": [
    "#%%time\n",
    "mistake = \"drauing\" \n",
    "distances2 = []\n",
    "for word in words:\n",
    "    ed = editdistance.eval(mistake, word)\n",
    "    distances2.append(ed)\n",
    "    \n",
    "print(\"\\nthe closest word is\", words[np.argmin(distances2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.228106Z",
     "start_time": "2020-03-05T21:51:15.224695Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# both implementations provide the same results\n",
    "distances2 == distances"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing an edit distance using dynamic programming\n",
    "\n",
    "\n",
    "The basic idea to implement the edit distance in an efficient way relies on understanding that if we have the edit distances between two prefixes of two strings we can use it to compute the edit distance between the prefixes appending them with a character.\n",
    "\n",
    "\n",
    "\n",
    "###### Example\n",
    "\n",
    "Compute `d(\"hi\",\"ho\")`\n",
    "\n",
    "```\n",
    "    \"\"    h      i\n",
    "\"\"  0     1      2 \n",
    "h   1     d,i,s  d,i,s\n",
    "o   2     d,i,s  d,i,s\n",
    "```\n",
    "\n",
    "Which ends up with \n",
    "\n",
    "```\n",
    "    \"\"    h    i\n",
    "\"\"  0     1    2 \n",
    "h   1     0    1 \n",
    "o   2     1    1\n",
    "```\n",
    "\n",
    "Compute `d(\"hi\",\"hill\")`\n",
    "\n",
    "\n",
    "```\n",
    "    \"\"    h        i\n",
    "\"\"  0     1        2 \n",
    "h   1     d,i,s    d,i,s\n",
    "i   2     d,i,s    d,i,s\n",
    "l   3     d,i,s    d,i,s\n",
    "l   4     d,i,s    d,i,s\n",
    "```\n",
    "\n",
    "```\n",
    "    \"\"    h        i\n",
    "\"\"  0     1        2 \n",
    "h   1     1,1,0    d,i,s\n",
    "i   2     d,i,s    d,i,s\n",
    "l   3     d,i,s    d,i,s\n",
    "l   4     d,i,s    d,i,s\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "```\n",
    "    \"\"    h    i\n",
    "\"\"  0     1    2 \n",
    "h   1     0    1 \n",
    "i   2     1    0\n",
    "l   3     2    1\n",
    "l   4     3    2\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "##### Dynamic programming\n",
    "\n",
    "1) Define subproblems\n",
    "\n",
    "- $x[i:]$ and $y[j:]$ for all i and j\n",
    "- #subproblems = $O(|x| |y|)$\n",
    "\n",
    "2) Guess part of the overall solution\n",
    "\n",
    "we want to map the first character of x to the first character of y.\n",
    "\n",
    "\n",
    "```\n",
    "x = [x_1 x_2 ...]\n",
    "y = [y_1 y_2 ...]\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "3) Define a recurrence\n",
    "\n",
    "4) Recurrence + memoization\n",
    "\n",
    "5) Solve original problem\n",
    "\n",
    "## Edit distance full algorithm\n",
    "\n",
    "Initialization\n",
    "```\n",
    "D(i,0) = i\n",
    "D(0,j) = j\n",
    "```\n",
    "\n",
    "That is:\n",
    "\n",
    "```\n",
    "    \"\"    ------------- x --------------- \n",
    "\"\"  0      1      2               lx-1 lx\n",
    "|   1      0      0               0    0\n",
    "|   2      0      0               0    0\n",
    "    .      .      .               .    .\n",
    "y   .      .      .               .    .\n",
    "    .      .      .               .    .\n",
    "|   ly-1   0      0               0    0\n",
    "|   ly     0      0               0    0\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "Recurrence\n",
    "```\n",
    "For each i in 1...M\n",
    "    For each j in 1...N\n",
    "        del_char = D(i-1,j) + 1\n",
    "        ins_char = D(i,j-1) + 1\n",
    "     \n",
    "        if X[i] != Y[j]:\n",
    "            Z = 2\n",
    "        if X[i] = Y[j]\n",
    "            Z = 0\n",
    "         \n",
    "        sub_char = D(i-1,j-1) + Z\n",
    "        D(i,j) = min(del_char, ins_char, sub_char)\n",
    "```\n",
    "\n",
    "Termination\n",
    "\n",
    "The result will be the last position of the array `D` once it is filled.\n",
    "\n",
    "```\n",
    "return D(N,M) \n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.234206Z",
     "start_time": "2020-03-05T21:51:15.229712Z"
    }
   },
   "outputs": [],
   "source": [
    "def initialize_table(s1,s2):\n",
    "    len_x = len(s1)\n",
    "    len_y = len(s2)\n",
    "    D = np.zeros((len_x+1,len_y+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.248285Z",
     "start_time": "2020-03-05T21:51:15.235391Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0., 1., 2., 3., 4., 5.],\n",
       "       [1., 0., 0., 0., 0., 0.],\n",
       "       [2., 0., 0., 0., 0., 0.],\n",
       "       [3., 0., 0., 0., 0., 0.],\n",
       "       [4., 0., 0., 0., 0., 0.]])"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s1 = \"hill\"\n",
    "s2 = \"hello\"\n",
    "len_x = len(s1)\n",
    "len_y = len(s2)\n",
    "D = np.zeros((len_x+1,len_y+1))\n",
    "D[:,0] = range(len_x+1)\n",
    "D[0,:] = range(len_y+1)\n",
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.252138Z",
     "start_time": "2020-03-05T21:51:15.249799Z"
    }
   },
   "outputs": [],
   "source": [
    "def memoization_table(s1, s2, D):\n",
    "    colnames = [\"empty\"] + [x for x in s2]\n",
    "    rownames = [\"empty\"] + [x for x in s1]\n",
    "    print(pd.DataFrame(D, rownames, columns=colnames))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.260100Z",
     "start_time": "2020-03-05T21:51:15.253552Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "       empty    h    e    l    l    o\n",
      "empty    0.0  1.0  2.0  3.0  4.0  5.0\n",
      "h        1.0  0.0  0.0  0.0  0.0  0.0\n",
      "i        2.0  0.0  0.0  0.0  0.0  0.0\n",
      "l        3.0  0.0  0.0  0.0  0.0  0.0\n",
      "l        4.0  0.0  0.0  0.0  0.0  0.0\n"
     ]
    }
   ],
   "source": [
    "memoization_table(s1,s2,D)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.264692Z",
     "start_time": "2020-03-05T21:51:15.261510Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0., 1., 2., 3., 4., 5.],\n",
       "       [1., 0., 0., 0., 0., 0.],\n",
       "       [2., 0., 0., 0., 0., 0.],\n",
       "       [3., 0., 0., 0., 0., 0.],\n",
       "       [4., 0., 0., 0., 0., 0.]])"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.271601Z",
     "start_time": "2020-03-05T21:51:15.266249Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.,  1.,  2.,  3.,  4.,  5.,  6.,  7.,  8.,  9., 10.],\n",
       "       [ 1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 2.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 3.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 4.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 6.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 7.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 8.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 9.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [10.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [11.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.]])"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s1 = \"EXPONENTIAL\"\n",
    "s2 = \"POLYNOMIAL\"\n",
    "len_x = len(s1)\n",
    "len_y = len(s2)\n",
    "D = np.zeros((len_x + 1, len_y + 1))\n",
    "D[:,0] = range(len_x + 1)\n",
    "D[0,:] = range(len_y + 1)\n",
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.276778Z",
     "start_time": "2020-03-05T21:51:15.272807Z"
    }
   },
   "outputs": [],
   "source": [
    "s1 = \"EXPONENTIAL\"\n",
    "s2 = \"POLYNOMIAL\"\n",
    "len_x = len(s1)\n",
    "len_y = len(s2)\n",
    "D = np.zeros((len_x + 1,len_y + 1))\n",
    "D[:,0] = range(len_x + 1)\n",
    "D[0,:] = range(len_y + 1)\n",
    "D\n",
    "\n",
    "X = s1\n",
    "Y = s2\n",
    "\n",
    "w_sub = 1\n",
    "w_del = 1\n",
    "w_ins = 1\n",
    "\n",
    "for i in range(1, len(X) + 1):\n",
    "    for j in range(1, len(Y) + 1):\n",
    "        \n",
    "        del_char = D[i-1,j] + w_del\n",
    "        ins_char = D[i,j-1] + w_ins\n",
    "        \n",
    "        if X[i-1] == Y[j-1]:\n",
    "            Z = 0\n",
    "        else:\n",
    "            Z = w_sub\n",
    "        sub_char = D[i-1,j-1] + Z\n",
    "\n",
    "        D[i,j] = min(del_char, ins_char, sub_char)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.286259Z",
     "start_time": "2020-03-05T21:51:15.278252Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "       empty     P    O    L    Y    N    O    M    I    A     L\n",
      "empty    0.0   1.0  2.0  3.0  4.0  5.0  6.0  7.0  8.0  9.0  10.0\n",
      "E        1.0   1.0  2.0  3.0  4.0  5.0  6.0  7.0  8.0  9.0  10.0\n",
      "X        2.0   2.0  2.0  3.0  4.0  5.0  6.0  7.0  8.0  9.0  10.0\n",
      "P        3.0   2.0  3.0  3.0  4.0  5.0  6.0  7.0  8.0  9.0  10.0\n",
      "O        4.0   3.0  2.0  3.0  4.0  5.0  5.0  6.0  7.0  8.0   9.0\n",
      "N        5.0   4.0  3.0  3.0  4.0  4.0  5.0  6.0  7.0  8.0   9.0\n",
      "E        6.0   5.0  4.0  4.0  4.0  5.0  5.0  6.0  7.0  8.0   9.0\n",
      "N        7.0   6.0  5.0  5.0  5.0  4.0  5.0  6.0  7.0  8.0   9.0\n",
      "T        8.0   7.0  6.0  6.0  6.0  5.0  5.0  6.0  7.0  8.0   9.0\n",
      "I        9.0   8.0  7.0  7.0  7.0  6.0  6.0  6.0  6.0  7.0   8.0\n",
      "A       10.0   9.0  8.0  8.0  8.0  7.0  7.0  7.0  7.0  6.0   7.0\n",
      "L       11.0  10.0  9.0  8.0  9.0  8.0  8.0  8.0  8.0  7.0   6.0\n"
     ]
    }
   ],
   "source": [
    "memoization_table(X,Y,D)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.290355Z",
     "start_time": "2020-03-05T21:51:15.287753Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6.0"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# edit distance\n",
    "D[-1,-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Assuming same cost for all edits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.295513Z",
     "start_time": "2020-03-05T21:51:15.292067Z"
    }
   },
   "outputs": [],
   "source": [
    "def create_memoization_table(X,Y):\n",
    "\n",
    "    len_x = len(X)\n",
    "    len_y = len(Y)\n",
    "    D = np.zeros((len_x+1,len_y+1))\n",
    "    \n",
    "    for i in range(len(X)+1):\n",
    "        for j in range(len(Y)+1):\n",
    "\n",
    "            if i == 0:\n",
    "                D[i][j] = j    \n",
    "\n",
    "            elif j == 0:\n",
    "                D[i][j] = i  \n",
    "\n",
    "            elif X[i-1] == Y[j-1]: \n",
    "                D[i][j] = D[i-1][j-1]\n",
    "\n",
    "            else:\n",
    "                D[i][j] = 1+min(D[i][j-1],      # Insert \n",
    "                                D[i-1][j],      # Remove \n",
    "                                D[i-1][j-1])    # Replace \n",
    "    return D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.306055Z",
     "start_time": "2020-03-05T21:51:15.296900Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "       empty     P    O    L    Y    N    O    M    I    A     L\n",
      "empty    0.0   1.0  2.0  3.0  4.0  5.0  6.0  7.0  8.0  9.0  10.0\n",
      "E        1.0   1.0  2.0  3.0  4.0  5.0  6.0  7.0  8.0  9.0  10.0\n",
      "X        2.0   2.0  2.0  3.0  4.0  5.0  6.0  7.0  8.0  9.0  10.0\n",
      "P        3.0   2.0  3.0  3.0  4.0  5.0  6.0  7.0  8.0  9.0  10.0\n",
      "O        4.0   3.0  2.0  3.0  4.0  5.0  5.0  6.0  7.0  8.0   9.0\n",
      "N        5.0   4.0  3.0  3.0  4.0  4.0  5.0  6.0  7.0  8.0   9.0\n",
      "E        6.0   5.0  4.0  4.0  4.0  5.0  5.0  6.0  7.0  8.0   9.0\n",
      "N        7.0   6.0  5.0  5.0  5.0  4.0  5.0  6.0  7.0  8.0   9.0\n",
      "T        8.0   7.0  6.0  6.0  6.0  5.0  5.0  6.0  7.0  8.0   9.0\n",
      "I        9.0   8.0  7.0  7.0  7.0  6.0  6.0  6.0  6.0  7.0   8.0\n",
      "A       10.0   9.0  8.0  8.0  8.0  7.0  7.0  7.0  7.0  6.0   7.0\n",
      "L       11.0  10.0  9.0  8.0  9.0  8.0  8.0  8.0  8.0  7.0   6.0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6.0"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = \"EXPONENTIAL\"\n",
    "y = \"POLYNOMIAL\"\n",
    "D = create_memoization_table(x,y)\n",
    "memoization_table(x,y,D)\n",
    "D[-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.314112Z",
     "start_time": "2020-03-05T21:51:15.307689Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "       empty    E    l    i    a\n",
      "empty    0.0  1.0  2.0  3.0  4.0\n",
      "E        1.0  0.0  1.0  2.0  3.0\n",
      "l        2.0  1.0  0.0  1.0  2.0\n",
      "l        3.0  2.0  1.0  1.0  2.0\n",
      "i        4.0  3.0  2.0  1.0  2.0\n",
      "o        5.0  4.0  3.0  2.0  2.0\n",
      "t        6.0  5.0  4.0  3.0  3.0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3.0"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = \"Elliot\"\n",
    "y = \"Elia\"\n",
    "D = create_memoization_table(x,y)\n",
    "memoization_table(x,y,D)\n",
    "D[-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.321113Z",
     "start_time": "2020-03-05T21:51:15.315852Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "       empty    h    i    l    l\n",
      "empty    0.0  1.0  2.0  3.0  4.0\n",
      "h        1.0  0.0  1.0  2.0  3.0\n",
      "i        2.0  1.0  0.0  1.0  2.0\n",
      "\n",
      "The distance between hi and hill is 2.0\n"
     ]
    }
   ],
   "source": [
    "x = \"hi\"\n",
    "y = \"hill\"\n",
    "D = create_memoization_table(x,y)\n",
    "memoization_table(x,y,D)\n",
    "print(\"\\nThe distance between {} and {} is {}\".format(x,y,D[-1,-1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Timing implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.324736Z",
     "start_time": "2020-03-05T21:51:15.322924Z"
    }
   },
   "outputs": [],
   "source": [
    "x = \"EXPONENTIAL\"\n",
    "y = \"POLYNOMIAL\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:15.328826Z",
     "start_time": "2020-03-05T21:51:15.326760Z"
    }
   },
   "outputs": [],
   "source": [
    "def edit_distance_fast(x,y):\n",
    "    D = create_memoization_table(x,y)\n",
    "    return D[-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:28.598021Z",
     "start_time": "2020-03-05T21:51:15.330383Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "164 µs ± 945 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "edit_distance_fast(x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:34.514828Z",
     "start_time": "2020-03-05T21:51:28.599457Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "72.8 µs ± 762 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "nltk.edit_distance(x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:34.519906Z",
     "start_time": "2020-03-05T21:51:34.516319Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nltk.edit_distance(x,y) == edit_distance_fast(x,y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Different costs per operation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:34.525996Z",
     "start_time": "2020-03-05T21:51:34.521284Z"
    }
   },
   "outputs": [],
   "source": [
    "def memoization_table_weighted(X,Y):\n",
    "\n",
    "    len_x = len(X)\n",
    "    len_y = len(Y)\n",
    "    D = np.zeros((len_x + 1, len_y + 1))\n",
    "    D[:,0] = range(len_x + 1)\n",
    "    D[0,:] = range(len_y + 1)\n",
    "\n",
    "    w_sub = 1\n",
    "    w_del = 1\n",
    "    w_ins = 1\n",
    "\n",
    "    for i in range(1, len_x + 1):\n",
    "        for j in range(1, len_y + 1):\n",
    "            del_char = D[i-1,j] + w_del\n",
    "            ins_char = D[i,j-1] + w_ins\n",
    "\n",
    "            if X[i-1] == Y[j-1]:\n",
    "                Z = 0\n",
    "            else:\n",
    "                Z = w_sub\n",
    "            sub_char = D[i-1,j-1] + Z\n",
    "\n",
    "            D[i,j] = min(del_char, ins_char, sub_char)\n",
    "\n",
    "    return D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:34.532770Z",
     "start_time": "2020-03-05T21:51:34.527356Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "       empty    E    l    i    a\n",
      "empty    0.0  1.0  2.0  3.0  4.0\n",
      "E        1.0  0.0  1.0  2.0  3.0\n",
      "l        2.0  1.0  0.0  1.0  2.0\n",
      "l        3.0  2.0  1.0  1.0  2.0\n",
      "i        4.0  3.0  2.0  1.0  2.0\n",
      "o        5.0  4.0  3.0  2.0  2.0\n",
      "t        6.0  5.0  4.0  3.0  3.0\n",
      "\n",
      "The distance between Elliot and Elia is 3.0\n"
     ]
    }
   ],
   "source": [
    "x = \"Elliot\"\n",
    "y = \"Elia\"\n",
    "D = memoization_table_weighted(x, y)\n",
    "memoization_table(x, y, D)\n",
    "print(\"\\nThe distance between {} and {} is {}\".format(x,y,D[-1,-1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Timing "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:34.536094Z",
     "start_time": "2020-03-05T21:51:34.534199Z"
    }
   },
   "outputs": [],
   "source": [
    "x = \"EXPONENTIAL\"\n",
    "y = \"POLYNOMIAL\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:49.609577Z",
     "start_time": "2020-03-05T21:51:34.537490Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "186 µs ± 1.7 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "D = memoization_table_weighted(x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:51:55.458192Z",
     "start_time": "2020-03-05T21:51:49.610913Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "72 µs ± 272 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "nltk.edit_distance(x,y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Speeding up code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Simple example with cython"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:48:43.871037Z",
     "start_time": "2022-03-02T13:48:43.253448Z"
    }
   },
   "outputs": [],
   "source": [
    "%load_ext cython"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:48:44.385121Z",
     "start_time": "2022-03-02T13:48:44.380362Z"
    }
   },
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    a = 0.\n",
    "    b = 1.\n",
    "    for i in range(n):\n",
    "        a, b = a + b, a\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:48:58.388389Z",
     "start_time": "2022-03-02T13:48:45.372590Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html>\n",
       "<!-- Generated by Cython 0.29.25 -->\n",
       "<html>\n",
       "<head>\n",
       "    <meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\" />\n",
       "    <title>Cython: _cython_magic_5e529961db36fb5122c76f61c5a144d5.pyx</title>\n",
       "    <style type=\"text/css\">\n",
       "    \n",
       "body.cython { font-family: courier; font-size: 12; }\n",
       "\n",
       ".cython.tag  {  }\n",
       ".cython.line { margin: 0em }\n",
       ".cython.code { font-size: 9; color: #444444; display: none; margin: 0px 0px 0px 8px; border-left: 8px none; }\n",
       "\n",
       ".cython.line .run { background-color: #B0FFB0; }\n",
       ".cython.line .mis { background-color: #FFB0B0; }\n",
       ".cython.code.run  { border-left: 8px solid #B0FFB0; }\n",
       ".cython.code.mis  { border-left: 8px solid #FFB0B0; }\n",
       "\n",
       ".cython.code .py_c_api  { color: red; }\n",
       ".cython.code .py_macro_api  { color: #FF7000; }\n",
       ".cython.code .pyx_c_api  { color: #FF3000; }\n",
       ".cython.code .pyx_macro_api  { color: #FF7000; }\n",
       ".cython.code .refnanny  { color: #FFA000; }\n",
       ".cython.code .trace  { color: #FFA000; }\n",
       ".cython.code .error_goto  { color: #FFA000; }\n",
       "\n",
       ".cython.code .coerce  { color: #008000; border: 1px dotted #008000 }\n",
       ".cython.code .py_attr { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_attr  { color: #0000FF; }\n",
       ".cython.code .py_call { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_call  { color: #0000FF; }\n",
       "\n",
       ".cython.score-0 {background-color: #FFFFff;}\n",
       ".cython.score-1 {background-color: #FFFFe7;}\n",
       ".cython.score-2 {background-color: #FFFFd4;}\n",
       ".cython.score-3 {background-color: #FFFFc4;}\n",
       ".cython.score-4 {background-color: #FFFFb6;}\n",
       ".cython.score-5 {background-color: #FFFFaa;}\n",
       ".cython.score-6 {background-color: #FFFF9f;}\n",
       ".cython.score-7 {background-color: #FFFF96;}\n",
       ".cython.score-8 {background-color: #FFFF8d;}\n",
       ".cython.score-9 {background-color: #FFFF86;}\n",
       ".cython.score-10 {background-color: #FFFF7f;}\n",
       ".cython.score-11 {background-color: #FFFF79;}\n",
       ".cython.score-12 {background-color: #FFFF73;}\n",
       ".cython.score-13 {background-color: #FFFF6e;}\n",
       ".cython.score-14 {background-color: #FFFF6a;}\n",
       ".cython.score-15 {background-color: #FFFF66;}\n",
       ".cython.score-16 {background-color: #FFFF62;}\n",
       ".cython.score-17 {background-color: #FFFF5e;}\n",
       ".cython.score-18 {background-color: #FFFF5b;}\n",
       ".cython.score-19 {background-color: #FFFF57;}\n",
       ".cython.score-20 {background-color: #FFFF55;}\n",
       ".cython.score-21 {background-color: #FFFF52;}\n",
       ".cython.score-22 {background-color: #FFFF4f;}\n",
       ".cython.score-23 {background-color: #FFFF4d;}\n",
       ".cython.score-24 {background-color: #FFFF4b;}\n",
       ".cython.score-25 {background-color: #FFFF48;}\n",
       ".cython.score-26 {background-color: #FFFF46;}\n",
       ".cython.score-27 {background-color: #FFFF44;}\n",
       ".cython.score-28 {background-color: #FFFF43;}\n",
       ".cython.score-29 {background-color: #FFFF41;}\n",
       ".cython.score-30 {background-color: #FFFF3f;}\n",
       ".cython.score-31 {background-color: #FFFF3e;}\n",
       ".cython.score-32 {background-color: #FFFF3c;}\n",
       ".cython.score-33 {background-color: #FFFF3b;}\n",
       ".cython.score-34 {background-color: #FFFF39;}\n",
       ".cython.score-35 {background-color: #FFFF38;}\n",
       ".cython.score-36 {background-color: #FFFF37;}\n",
       ".cython.score-37 {background-color: #FFFF36;}\n",
       ".cython.score-38 {background-color: #FFFF35;}\n",
       ".cython.score-39 {background-color: #FFFF34;}\n",
       ".cython.score-40 {background-color: #FFFF33;}\n",
       ".cython.score-41 {background-color: #FFFF32;}\n",
       ".cython.score-42 {background-color: #FFFF31;}\n",
       ".cython.score-43 {background-color: #FFFF30;}\n",
       ".cython.score-44 {background-color: #FFFF2f;}\n",
       ".cython.score-45 {background-color: #FFFF2e;}\n",
       ".cython.score-46 {background-color: #FFFF2d;}\n",
       ".cython.score-47 {background-color: #FFFF2c;}\n",
       ".cython.score-48 {background-color: #FFFF2b;}\n",
       ".cython.score-49 {background-color: #FFFF2b;}\n",
       ".cython.score-50 {background-color: #FFFF2a;}\n",
       ".cython.score-51 {background-color: #FFFF29;}\n",
       ".cython.score-52 {background-color: #FFFF29;}\n",
       ".cython.score-53 {background-color: #FFFF28;}\n",
       ".cython.score-54 {background-color: #FFFF27;}\n",
       ".cython.score-55 {background-color: #FFFF27;}\n",
       ".cython.score-56 {background-color: #FFFF26;}\n",
       ".cython.score-57 {background-color: #FFFF26;}\n",
       ".cython.score-58 {background-color: #FFFF25;}\n",
       ".cython.score-59 {background-color: #FFFF24;}\n",
       ".cython.score-60 {background-color: #FFFF24;}\n",
       ".cython.score-61 {background-color: #FFFF23;}\n",
       ".cython.score-62 {background-color: #FFFF23;}\n",
       ".cython.score-63 {background-color: #FFFF22;}\n",
       ".cython.score-64 {background-color: #FFFF22;}\n",
       ".cython.score-65 {background-color: #FFFF22;}\n",
       ".cython.score-66 {background-color: #FFFF21;}\n",
       ".cython.score-67 {background-color: #FFFF21;}\n",
       ".cython.score-68 {background-color: #FFFF20;}\n",
       ".cython.score-69 {background-color: #FFFF20;}\n",
       ".cython.score-70 {background-color: #FFFF1f;}\n",
       ".cython.score-71 {background-color: #FFFF1f;}\n",
       ".cython.score-72 {background-color: #FFFF1f;}\n",
       ".cython.score-73 {background-color: #FFFF1e;}\n",
       ".cython.score-74 {background-color: #FFFF1e;}\n",
       ".cython.score-75 {background-color: #FFFF1e;}\n",
       ".cython.score-76 {background-color: #FFFF1d;}\n",
       ".cython.score-77 {background-color: #FFFF1d;}\n",
       ".cython.score-78 {background-color: #FFFF1c;}\n",
       ".cython.score-79 {background-color: #FFFF1c;}\n",
       ".cython.score-80 {background-color: #FFFF1c;}\n",
       ".cython.score-81 {background-color: #FFFF1c;}\n",
       ".cython.score-82 {background-color: #FFFF1b;}\n",
       ".cython.score-83 {background-color: #FFFF1b;}\n",
       ".cython.score-84 {background-color: #FFFF1b;}\n",
       ".cython.score-85 {background-color: #FFFF1a;}\n",
       ".cython.score-86 {background-color: #FFFF1a;}\n",
       ".cython.score-87 {background-color: #FFFF1a;}\n",
       ".cython.score-88 {background-color: #FFFF1a;}\n",
       ".cython.score-89 {background-color: #FFFF19;}\n",
       ".cython.score-90 {background-color: #FFFF19;}\n",
       ".cython.score-91 {background-color: #FFFF19;}\n",
       ".cython.score-92 {background-color: #FFFF19;}\n",
       ".cython.score-93 {background-color: #FFFF18;}\n",
       ".cython.score-94 {background-color: #FFFF18;}\n",
       ".cython.score-95 {background-color: #FFFF18;}\n",
       ".cython.score-96 {background-color: #FFFF18;}\n",
       ".cython.score-97 {background-color: #FFFF17;}\n",
       ".cython.score-98 {background-color: #FFFF17;}\n",
       ".cython.score-99 {background-color: #FFFF17;}\n",
       ".cython.score-100 {background-color: #FFFF17;}\n",
       ".cython.score-101 {background-color: #FFFF16;}\n",
       ".cython.score-102 {background-color: #FFFF16;}\n",
       ".cython.score-103 {background-color: #FFFF16;}\n",
       ".cython.score-104 {background-color: #FFFF16;}\n",
       ".cython.score-105 {background-color: #FFFF16;}\n",
       ".cython.score-106 {background-color: #FFFF15;}\n",
       ".cython.score-107 {background-color: #FFFF15;}\n",
       ".cython.score-108 {background-color: #FFFF15;}\n",
       ".cython.score-109 {background-color: #FFFF15;}\n",
       ".cython.score-110 {background-color: #FFFF15;}\n",
       ".cython.score-111 {background-color: #FFFF15;}\n",
       ".cython.score-112 {background-color: #FFFF14;}\n",
       ".cython.score-113 {background-color: #FFFF14;}\n",
       ".cython.score-114 {background-color: #FFFF14;}\n",
       ".cython.score-115 {background-color: #FFFF14;}\n",
       ".cython.score-116 {background-color: #FFFF14;}\n",
       ".cython.score-117 {background-color: #FFFF14;}\n",
       ".cython.score-118 {background-color: #FFFF13;}\n",
       ".cython.score-119 {background-color: #FFFF13;}\n",
       ".cython.score-120 {background-color: #FFFF13;}\n",
       ".cython.score-121 {background-color: #FFFF13;}\n",
       ".cython.score-122 {background-color: #FFFF13;}\n",
       ".cython.score-123 {background-color: #FFFF13;}\n",
       ".cython.score-124 {background-color: #FFFF13;}\n",
       ".cython.score-125 {background-color: #FFFF12;}\n",
       ".cython.score-126 {background-color: #FFFF12;}\n",
       ".cython.score-127 {background-color: #FFFF12;}\n",
       ".cython.score-128 {background-color: #FFFF12;}\n",
       ".cython.score-129 {background-color: #FFFF12;}\n",
       ".cython.score-130 {background-color: #FFFF12;}\n",
       ".cython.score-131 {background-color: #FFFF12;}\n",
       ".cython.score-132 {background-color: #FFFF11;}\n",
       ".cython.score-133 {background-color: #FFFF11;}\n",
       ".cython.score-134 {background-color: #FFFF11;}\n",
       ".cython.score-135 {background-color: #FFFF11;}\n",
       ".cython.score-136 {background-color: #FFFF11;}\n",
       ".cython.score-137 {background-color: #FFFF11;}\n",
       ".cython.score-138 {background-color: #FFFF11;}\n",
       ".cython.score-139 {background-color: #FFFF11;}\n",
       ".cython.score-140 {background-color: #FFFF11;}\n",
       ".cython.score-141 {background-color: #FFFF10;}\n",
       ".cython.score-142 {background-color: #FFFF10;}\n",
       ".cython.score-143 {background-color: #FFFF10;}\n",
       ".cython.score-144 {background-color: #FFFF10;}\n",
       ".cython.score-145 {background-color: #FFFF10;}\n",
       ".cython.score-146 {background-color: #FFFF10;}\n",
       ".cython.score-147 {background-color: #FFFF10;}\n",
       ".cython.score-148 {background-color: #FFFF10;}\n",
       ".cython.score-149 {background-color: #FFFF10;}\n",
       ".cython.score-150 {background-color: #FFFF0f;}\n",
       ".cython.score-151 {background-color: #FFFF0f;}\n",
       ".cython.score-152 {background-color: #FFFF0f;}\n",
       ".cython.score-153 {background-color: #FFFF0f;}\n",
       ".cython.score-154 {background-color: #FFFF0f;}\n",
       ".cython.score-155 {background-color: #FFFF0f;}\n",
       ".cython.score-156 {background-color: #FFFF0f;}\n",
       ".cython.score-157 {background-color: #FFFF0f;}\n",
       ".cython.score-158 {background-color: #FFFF0f;}\n",
       ".cython.score-159 {background-color: #FFFF0f;}\n",
       ".cython.score-160 {background-color: #FFFF0f;}\n",
       ".cython.score-161 {background-color: #FFFF0e;}\n",
       ".cython.score-162 {background-color: #FFFF0e;}\n",
       ".cython.score-163 {background-color: #FFFF0e;}\n",
       ".cython.score-164 {background-color: #FFFF0e;}\n",
       ".cython.score-165 {background-color: #FFFF0e;}\n",
       ".cython.score-166 {background-color: #FFFF0e;}\n",
       ".cython.score-167 {background-color: #FFFF0e;}\n",
       ".cython.score-168 {background-color: #FFFF0e;}\n",
       ".cython.score-169 {background-color: #FFFF0e;}\n",
       ".cython.score-170 {background-color: #FFFF0e;}\n",
       ".cython.score-171 {background-color: #FFFF0e;}\n",
       ".cython.score-172 {background-color: #FFFF0e;}\n",
       ".cython.score-173 {background-color: #FFFF0d;}\n",
       ".cython.score-174 {background-color: #FFFF0d;}\n",
       ".cython.score-175 {background-color: #FFFF0d;}\n",
       ".cython.score-176 {background-color: #FFFF0d;}\n",
       ".cython.score-177 {background-color: #FFFF0d;}\n",
       ".cython.score-178 {background-color: #FFFF0d;}\n",
       ".cython.score-179 {background-color: #FFFF0d;}\n",
       ".cython.score-180 {background-color: #FFFF0d;}\n",
       ".cython.score-181 {background-color: #FFFF0d;}\n",
       ".cython.score-182 {background-color: #FFFF0d;}\n",
       ".cython.score-183 {background-color: #FFFF0d;}\n",
       ".cython.score-184 {background-color: #FFFF0d;}\n",
       ".cython.score-185 {background-color: #FFFF0d;}\n",
       ".cython.score-186 {background-color: #FFFF0d;}\n",
       ".cython.score-187 {background-color: #FFFF0c;}\n",
       ".cython.score-188 {background-color: #FFFF0c;}\n",
       ".cython.score-189 {background-color: #FFFF0c;}\n",
       ".cython.score-190 {background-color: #FFFF0c;}\n",
       ".cython.score-191 {background-color: #FFFF0c;}\n",
       ".cython.score-192 {background-color: #FFFF0c;}\n",
       ".cython.score-193 {background-color: #FFFF0c;}\n",
       ".cython.score-194 {background-color: #FFFF0c;}\n",
       ".cython.score-195 {background-color: #FFFF0c;}\n",
       ".cython.score-196 {background-color: #FFFF0c;}\n",
       ".cython.score-197 {background-color: #FFFF0c;}\n",
       ".cython.score-198 {background-color: #FFFF0c;}\n",
       ".cython.score-199 {background-color: #FFFF0c;}\n",
       ".cython.score-200 {background-color: #FFFF0c;}\n",
       ".cython.score-201 {background-color: #FFFF0c;}\n",
       ".cython.score-202 {background-color: #FFFF0c;}\n",
       ".cython.score-203 {background-color: #FFFF0b;}\n",
       ".cython.score-204 {background-color: #FFFF0b;}\n",
       ".cython.score-205 {background-color: #FFFF0b;}\n",
       ".cython.score-206 {background-color: #FFFF0b;}\n",
       ".cython.score-207 {background-color: #FFFF0b;}\n",
       ".cython.score-208 {background-color: #FFFF0b;}\n",
       ".cython.score-209 {background-color: #FFFF0b;}\n",
       ".cython.score-210 {background-color: #FFFF0b;}\n",
       ".cython.score-211 {background-color: #FFFF0b;}\n",
       ".cython.score-212 {background-color: #FFFF0b;}\n",
       ".cython.score-213 {background-color: #FFFF0b;}\n",
       ".cython.score-214 {background-color: #FFFF0b;}\n",
       ".cython.score-215 {background-color: #FFFF0b;}\n",
       ".cython.score-216 {background-color: #FFFF0b;}\n",
       ".cython.score-217 {background-color: #FFFF0b;}\n",
       ".cython.score-218 {background-color: #FFFF0b;}\n",
       ".cython.score-219 {background-color: #FFFF0b;}\n",
       ".cython.score-220 {background-color: #FFFF0b;}\n",
       ".cython.score-221 {background-color: #FFFF0b;}\n",
       ".cython.score-222 {background-color: #FFFF0a;}\n",
       ".cython.score-223 {background-color: #FFFF0a;}\n",
       ".cython.score-224 {background-color: #FFFF0a;}\n",
       ".cython.score-225 {background-color: #FFFF0a;}\n",
       ".cython.score-226 {background-color: #FFFF0a;}\n",
       ".cython.score-227 {background-color: #FFFF0a;}\n",
       ".cython.score-228 {background-color: #FFFF0a;}\n",
       ".cython.score-229 {background-color: #FFFF0a;}\n",
       ".cython.score-230 {background-color: #FFFF0a;}\n",
       ".cython.score-231 {background-color: #FFFF0a;}\n",
       ".cython.score-232 {background-color: #FFFF0a;}\n",
       ".cython.score-233 {background-color: #FFFF0a;}\n",
       ".cython.score-234 {background-color: #FFFF0a;}\n",
       ".cython.score-235 {background-color: #FFFF0a;}\n",
       ".cython.score-236 {background-color: #FFFF0a;}\n",
       ".cython.score-237 {background-color: #FFFF0a;}\n",
       ".cython.score-238 {background-color: #FFFF0a;}\n",
       ".cython.score-239 {background-color: #FFFF0a;}\n",
       ".cython.score-240 {background-color: #FFFF0a;}\n",
       ".cython.score-241 {background-color: #FFFF0a;}\n",
       ".cython.score-242 {background-color: #FFFF0a;}\n",
       ".cython.score-243 {background-color: #FFFF0a;}\n",
       ".cython.score-244 {background-color: #FFFF0a;}\n",
       ".cython.score-245 {background-color: #FFFF0a;}\n",
       ".cython.score-246 {background-color: #FFFF09;}\n",
       ".cython.score-247 {background-color: #FFFF09;}\n",
       ".cython.score-248 {background-color: #FFFF09;}\n",
       ".cython.score-249 {background-color: #FFFF09;}\n",
       ".cython.score-250 {background-color: #FFFF09;}\n",
       ".cython.score-251 {background-color: #FFFF09;}\n",
       ".cython.score-252 {background-color: #FFFF09;}\n",
       ".cython.score-253 {background-color: #FFFF09;}\n",
       ".cython.score-254 {background-color: #FFFF09;}\n",
       "pre { line-height: 125%; }\n",
       "td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }\n",
       "span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }\n",
       "td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }\n",
       "span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }\n",
       ".cython .hll { background-color: #ffffcc }\n",
       ".cython { background: #f8f8f8; }\n",
       ".cython .c { color: #408080; font-style: italic } /* Comment */\n",
       ".cython .err { border: 1px solid #FF0000 } /* Error */\n",
       ".cython .k { color: #008000; font-weight: bold } /* Keyword */\n",
       ".cython .o { color: #666666 } /* Operator */\n",
       ".cython .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       ".cython .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       ".cython .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       ".cython .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       ".cython .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       ".cython .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       ".cython .gd { color: #A00000 } /* Generic.Deleted */\n",
       ".cython .ge { font-style: italic } /* Generic.Emph */\n",
       ".cython .gr { color: #FF0000 } /* Generic.Error */\n",
       ".cython .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       ".cython .gi { color: #00A000 } /* Generic.Inserted */\n",
       ".cython .go { color: #888888 } /* Generic.Output */\n",
       ".cython .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       ".cython .gs { font-weight: bold } /* Generic.Strong */\n",
       ".cython .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       ".cython .gt { color: #0044DD } /* Generic.Traceback */\n",
       ".cython .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       ".cython .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       ".cython .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       ".cython .kp { color: #008000 } /* Keyword.Pseudo */\n",
       ".cython .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       ".cython .kt { color: #B00040 } /* Keyword.Type */\n",
       ".cython .m { color: #666666 } /* Literal.Number */\n",
       ".cython .s { color: #BA2121 } /* Literal.String */\n",
       ".cython .na { color: #7D9029 } /* Name.Attribute */\n",
       ".cython .nb { color: #008000 } /* Name.Builtin */\n",
       ".cython .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       ".cython .no { color: #880000 } /* Name.Constant */\n",
       ".cython .nd { color: #AA22FF } /* Name.Decorator */\n",
       ".cython .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       ".cython .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       ".cython .nf { color: #0000FF } /* Name.Function */\n",
       ".cython .nl { color: #A0A000 } /* Name.Label */\n",
       ".cython .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       ".cython .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       ".cython .nv { color: #19177C } /* Name.Variable */\n",
       ".cython .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       ".cython .w { color: #bbbbbb } /* Text.Whitespace */\n",
       ".cython .mb { color: #666666 } /* Literal.Number.Bin */\n",
       ".cython .mf { color: #666666 } /* Literal.Number.Float */\n",
       ".cython .mh { color: #666666 } /* Literal.Number.Hex */\n",
       ".cython .mi { color: #666666 } /* Literal.Number.Integer */\n",
       ".cython .mo { color: #666666 } /* Literal.Number.Oct */\n",
       ".cython .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       ".cython .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       ".cython .sc { color: #BA2121 } /* Literal.String.Char */\n",
       ".cython .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       ".cython .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       ".cython .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       ".cython .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       ".cython .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       ".cython .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       ".cython .sx { color: #008000 } /* Literal.String.Other */\n",
       ".cython .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       ".cython .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       ".cython .ss { color: #19177C } /* Literal.String.Symbol */\n",
       ".cython .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       ".cython .fm { color: #0000FF } /* Name.Function.Magic */\n",
       ".cython .vc { color: #19177C } /* Name.Variable.Class */\n",
       ".cython .vg { color: #19177C } /* Name.Variable.Global */\n",
       ".cython .vi { color: #19177C } /* Name.Variable.Instance */\n",
       ".cython .vm { color: #19177C } /* Name.Variable.Magic */\n",
       ".cython .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "    </style>\n",
       "</head>\n",
       "<body class=\"cython\">\n",
       "<p><span style=\"border-bottom: solid 1px grey;\">Generated by Cython 0.29.25</span></p>\n",
       "<p>\n",
       "    <span style=\"background-color: #FFFF00\">Yellow lines</span> hint at Python interaction.<br />\n",
       "    Click on a line that starts with a \"<code>+</code>\" to see the C code that Cython generated for it.\n",
       "</p>\n",
       "<div class=\"cython\"><pre class=\"cython line score-16\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">1</span>: <span class=\"k\">cpdef</span> <span class=\"nf\">cy_fib</span><span class=\"p\">(</span><span class=\"nb\">int</span> <span class=\"n\">n</span><span class=\"p\">):</span></pre>\n",
       "<pre class='cython code score-16 '>static PyObject *__pyx_pw_46_cython_magic_5e529961db36fb5122c76f61c5a144d5_1cy_fib(PyObject *__pyx_self, PyObject *__pyx_arg_n); /*proto*/\n",
       "static PyObject *__pyx_f_46_cython_magic_5e529961db36fb5122c76f61c5a144d5_cy_fib(int __pyx_v_n, CYTHON_UNUSED int __pyx_skip_dispatch) {\n",
       "  CYTHON_UNUSED int __pyx_v_i;\n",
       "  float __pyx_v_a;\n",
       "  float __pyx_v_b;\n",
       "  PyObject *__pyx_r = NULL;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"cy_fib\", 0);\n",
       "/* … */\n",
       "  /* function exit code */\n",
       "  __pyx_L1_error:;\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_t_6);\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_5e529961db36fb5122c76f61c5a144d5.cy_fib\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  __pyx_r = 0;\n",
       "  __pyx_L0:;\n",
       "  <span class='refnanny'>__Pyx_XGIVEREF</span>(__pyx_r);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "/* Python wrapper */\n",
       "static PyObject *__pyx_pw_46_cython_magic_5e529961db36fb5122c76f61c5a144d5_1cy_fib(PyObject *__pyx_self, PyObject *__pyx_arg_n); /*proto*/\n",
       "static PyObject *__pyx_pw_46_cython_magic_5e529961db36fb5122c76f61c5a144d5_1cy_fib(PyObject *__pyx_self, PyObject *__pyx_arg_n) {\n",
       "  int __pyx_v_n;\n",
       "  PyObject *__pyx_r = 0;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"cy_fib (wrapper)\", 0);\n",
       "  assert(__pyx_arg_n); {\n",
       "    __pyx_v_n = <span class='pyx_c_api'>__Pyx_PyInt_As_int</span>(__pyx_arg_n); if (unlikely((__pyx_v_n == (int)-1) &amp;&amp; <span class='py_c_api'>PyErr_Occurred</span>())) <span class='error_goto'>__PYX_ERR(0, 1, __pyx_L3_error)</span>\n",
       "  }\n",
       "  goto __pyx_L4_argument_unpacking_done;\n",
       "  __pyx_L3_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_5e529961db36fb5122c76f61c5a144d5.cy_fib\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return NULL;\n",
       "  __pyx_L4_argument_unpacking_done:;\n",
       "  __pyx_r = __pyx_pf_46_cython_magic_5e529961db36fb5122c76f61c5a144d5_cy_fib(__pyx_self, ((int)__pyx_v_n));\n",
       "  int __pyx_lineno = 0;\n",
       "  const char *__pyx_filename = NULL;\n",
       "  int __pyx_clineno = 0;\n",
       "\n",
       "  /* function exit code */\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "static PyObject *__pyx_pf_46_cython_magic_5e529961db36fb5122c76f61c5a144d5_cy_fib(CYTHON_UNUSED PyObject *__pyx_self, int __pyx_v_n) {\n",
       "  PyObject *__pyx_r = NULL;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"cy_fib\", 0);\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_r);\n",
       "  __pyx_t_1 = __pyx_f_46_cython_magic_5e529961db36fb5122c76f61c5a144d5_cy_fib(__pyx_v_n, 0);<span class='error_goto'> if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 1, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  __pyx_r = __pyx_t_1;\n",
       "  __pyx_t_1 = 0;\n",
       "  goto __pyx_L0;\n",
       "\n",
       "  /* function exit code */\n",
       "  __pyx_L1_error:;\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_t_1);\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_5e529961db36fb5122c76f61c5a144d5.cy_fib\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  __pyx_r = NULL;\n",
       "  __pyx_L0:;\n",
       "  <span class='refnanny'>__Pyx_XGIVEREF</span>(__pyx_r);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">2</span>:     <span class=\"k\">cdef</span> <span class=\"kt\">int</span> <span class=\"nf\">i</span></pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">3</span>:     <span class=\"k\">cdef</span> <span class=\"kt\">float</span> <span class=\"nf\">a</span><span class=\"o\">=</span><span class=\"mf\">0.0</span><span class=\"p\">,</span> <span class=\"n\">b</span><span class=\"o\">=</span><span class=\"mf\">1.0</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_v_a = 0.0;\n",
       "  __pyx_v_b = 1.0;\n",
       "</pre><pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">4</span>:     <span class=\"k\">for</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">):</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_t_1 = __pyx_v_n;\n",
       "  __pyx_t_2 = __pyx_t_1;\n",
       "  for (__pyx_t_3 = 0; __pyx_t_3 &lt; __pyx_t_2; __pyx_t_3+=1) {\n",
       "    __pyx_v_i = __pyx_t_3;\n",
       "</pre><pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">5</span>:         <span class=\"n\">a</span><span class=\"p\">,</span> <span class=\"n\">b</span> <span class=\"o\">=</span> <span class=\"n\">a</span> <span class=\"o\">+</span> <span class=\"n\">b</span><span class=\"p\">,</span> <span class=\"n\">a</span></pre>\n",
       "<pre class='cython code score-0 '>    __pyx_t_4 = (__pyx_v_a + __pyx_v_b);\n",
       "    __pyx_t_5 = __pyx_v_a;\n",
       "    __pyx_v_a = __pyx_t_4;\n",
       "    __pyx_v_b = __pyx_t_5;\n",
       "  }\n",
       "</pre><pre class=\"cython line score-6\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">6</span>:     <span class=\"k\">return</span> <span class=\"n\">a</span></pre>\n",
       "<pre class='cython code score-6 '>  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_r);\n",
       "  __pyx_t_6 = <span class='py_c_api'>PyFloat_FromDouble</span>(__pyx_v_a);<span class='error_goto'> if (unlikely(!__pyx_t_6)) __PYX_ERR(0, 6, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_6);\n",
       "  __pyx_r = __pyx_t_6;\n",
       "  __pyx_t_6 = 0;\n",
       "  goto __pyx_L0;\n",
       "</pre></div></body></html>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%cython --a\n",
    "cpdef cy_fib(int n):\n",
    "    cdef int i\n",
    "    cdef float a=0.0, b=1.0\n",
    "    for i in range(n):\n",
    "        a, b = a + b, a\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:49:01.383457Z",
     "start_time": "2022-03-02T13:49:01.376689Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55.0"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-02T13:49:02.179499Z",
     "start_time": "2022-03-02T13:49:02.173575Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55.0"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cy_fib(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-03-08T16:47:33.773159Z",
     "start_time": "2021-03-08T16:47:33.701996Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Python version took: 0.059523759000512655 sec\n",
      " Cython version took: 0.003585041999940586 sec\n",
      " Cython is 17x faster\n",
      "\n",
      " Python version 1 run took: 5.952375900051266e-07 sec\n",
      " Cython version took: 3.585041999940586e-08 sec\n",
      " Cython is 17x faster\n"
     ]
    }
   ],
   "source": [
    "import timeit\n",
    "\n",
    "n_times = 100000\n",
    "t_fib = timeit.timeit(\"fib(10)\", setup=\"from __main__ import fib\",number=n_times)\n",
    "t_cyfib = timeit.timeit(\"cy_fib(10)\", setup=\"from __main__ import cy_fib\",number=n_times)\n",
    "t_fib_unit = t_fib/n_times\n",
    "\n",
    "t_cyfib      = timeit.timeit(\"cy_fib(10)\", setup=\"from __main__ import cy_fib\",number=n_times)\n",
    "t_cyfib_unit = t_cyfib/n_times\n",
    "\n",
    "print(\" Python version took: {} sec\\n Cython version took: {} sec\\n Cython is {:.0f}x faster\"\\\n",
    "      .format(t_fib, t_cyfib, t_fib/t_cyfib))\n",
    "\n",
    "print(\"\\n Python version 1 run took: {} sec\\n Cython version took: {} sec\\n Cython is {:.0f}x faster\"\\\n",
    "      .format(t_fib_unit, t_cyfib_unit, t_fib_unit/t_cyfib_unit))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Speeding up edit distance\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Exercise fill in cy_create_memoization_table so that it returns the matrix filled to compute the edit distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:52:48.363858Z",
     "start_time": "2020-03-05T21:52:46.379226Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html>\n",
       "<!-- Generated by Cython 0.29.6 -->\n",
       "<html>\n",
       "<head>\n",
       "    <meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\" />\n",
       "    <title>Cython: _cython_magic_8b4474fc106c14088ed8db7b91df18a5.pyx</title>\n",
       "    <style type=\"text/css\">\n",
       "    \n",
       "body.cython { font-family: courier; font-size: 12; }\n",
       "\n",
       ".cython.tag  {  }\n",
       ".cython.line { margin: 0em }\n",
       ".cython.code { font-size: 9; color: #444444; display: none; margin: 0px 0px 0px 8px; border-left: 8px none; }\n",
       "\n",
       ".cython.line .run { background-color: #B0FFB0; }\n",
       ".cython.line .mis { background-color: #FFB0B0; }\n",
       ".cython.code.run  { border-left: 8px solid #B0FFB0; }\n",
       ".cython.code.mis  { border-left: 8px solid #FFB0B0; }\n",
       "\n",
       ".cython.code .py_c_api  { color: red; }\n",
       ".cython.code .py_macro_api  { color: #FF7000; }\n",
       ".cython.code .pyx_c_api  { color: #FF3000; }\n",
       ".cython.code .pyx_macro_api  { color: #FF7000; }\n",
       ".cython.code .refnanny  { color: #FFA000; }\n",
       ".cython.code .trace  { color: #FFA000; }\n",
       ".cython.code .error_goto  { color: #FFA000; }\n",
       "\n",
       ".cython.code .coerce  { color: #008000; border: 1px dotted #008000 }\n",
       ".cython.code .py_attr { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_attr  { color: #0000FF; }\n",
       ".cython.code .py_call { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_call  { color: #0000FF; }\n",
       "\n",
       ".cython.score-0 {background-color: #FFFFff;}\n",
       ".cython.score-1 {background-color: #FFFFe7;}\n",
       ".cython.score-2 {background-color: #FFFFd4;}\n",
       ".cython.score-3 {background-color: #FFFFc4;}\n",
       ".cython.score-4 {background-color: #FFFFb6;}\n",
       ".cython.score-5 {background-color: #FFFFaa;}\n",
       ".cython.score-6 {background-color: #FFFF9f;}\n",
       ".cython.score-7 {background-color: #FFFF96;}\n",
       ".cython.score-8 {background-color: #FFFF8d;}\n",
       ".cython.score-9 {background-color: #FFFF86;}\n",
       ".cython.score-10 {background-color: #FFFF7f;}\n",
       ".cython.score-11 {background-color: #FFFF79;}\n",
       ".cython.score-12 {background-color: #FFFF73;}\n",
       ".cython.score-13 {background-color: #FFFF6e;}\n",
       ".cython.score-14 {background-color: #FFFF6a;}\n",
       ".cython.score-15 {background-color: #FFFF66;}\n",
       ".cython.score-16 {background-color: #FFFF62;}\n",
       ".cython.score-17 {background-color: #FFFF5e;}\n",
       ".cython.score-18 {background-color: #FFFF5b;}\n",
       ".cython.score-19 {background-color: #FFFF57;}\n",
       ".cython.score-20 {background-color: #FFFF55;}\n",
       ".cython.score-21 {background-color: #FFFF52;}\n",
       ".cython.score-22 {background-color: #FFFF4f;}\n",
       ".cython.score-23 {background-color: #FFFF4d;}\n",
       ".cython.score-24 {background-color: #FFFF4b;}\n",
       ".cython.score-25 {background-color: #FFFF48;}\n",
       ".cython.score-26 {background-color: #FFFF46;}\n",
       ".cython.score-27 {background-color: #FFFF44;}\n",
       ".cython.score-28 {background-color: #FFFF43;}\n",
       ".cython.score-29 {background-color: #FFFF41;}\n",
       ".cython.score-30 {background-color: #FFFF3f;}\n",
       ".cython.score-31 {background-color: #FFFF3e;}\n",
       ".cython.score-32 {background-color: #FFFF3c;}\n",
       ".cython.score-33 {background-color: #FFFF3b;}\n",
       ".cython.score-34 {background-color: #FFFF39;}\n",
       ".cython.score-35 {background-color: #FFFF38;}\n",
       ".cython.score-36 {background-color: #FFFF37;}\n",
       ".cython.score-37 {background-color: #FFFF36;}\n",
       ".cython.score-38 {background-color: #FFFF35;}\n",
       ".cython.score-39 {background-color: #FFFF34;}\n",
       ".cython.score-40 {background-color: #FFFF33;}\n",
       ".cython.score-41 {background-color: #FFFF32;}\n",
       ".cython.score-42 {background-color: #FFFF31;}\n",
       ".cython.score-43 {background-color: #FFFF30;}\n",
       ".cython.score-44 {background-color: #FFFF2f;}\n",
       ".cython.score-45 {background-color: #FFFF2e;}\n",
       ".cython.score-46 {background-color: #FFFF2d;}\n",
       ".cython.score-47 {background-color: #FFFF2c;}\n",
       ".cython.score-48 {background-color: #FFFF2b;}\n",
       ".cython.score-49 {background-color: #FFFF2b;}\n",
       ".cython.score-50 {background-color: #FFFF2a;}\n",
       ".cython.score-51 {background-color: #FFFF29;}\n",
       ".cython.score-52 {background-color: #FFFF29;}\n",
       ".cython.score-53 {background-color: #FFFF28;}\n",
       ".cython.score-54 {background-color: #FFFF27;}\n",
       ".cython.score-55 {background-color: #FFFF27;}\n",
       ".cython.score-56 {background-color: #FFFF26;}\n",
       ".cython.score-57 {background-color: #FFFF26;}\n",
       ".cython.score-58 {background-color: #FFFF25;}\n",
       ".cython.score-59 {background-color: #FFFF24;}\n",
       ".cython.score-60 {background-color: #FFFF24;}\n",
       ".cython.score-61 {background-color: #FFFF23;}\n",
       ".cython.score-62 {background-color: #FFFF23;}\n",
       ".cython.score-63 {background-color: #FFFF22;}\n",
       ".cython.score-64 {background-color: #FFFF22;}\n",
       ".cython.score-65 {background-color: #FFFF22;}\n",
       ".cython.score-66 {background-color: #FFFF21;}\n",
       ".cython.score-67 {background-color: #FFFF21;}\n",
       ".cython.score-68 {background-color: #FFFF20;}\n",
       ".cython.score-69 {background-color: #FFFF20;}\n",
       ".cython.score-70 {background-color: #FFFF1f;}\n",
       ".cython.score-71 {background-color: #FFFF1f;}\n",
       ".cython.score-72 {background-color: #FFFF1f;}\n",
       ".cython.score-73 {background-color: #FFFF1e;}\n",
       ".cython.score-74 {background-color: #FFFF1e;}\n",
       ".cython.score-75 {background-color: #FFFF1e;}\n",
       ".cython.score-76 {background-color: #FFFF1d;}\n",
       ".cython.score-77 {background-color: #FFFF1d;}\n",
       ".cython.score-78 {background-color: #FFFF1c;}\n",
       ".cython.score-79 {background-color: #FFFF1c;}\n",
       ".cython.score-80 {background-color: #FFFF1c;}\n",
       ".cython.score-81 {background-color: #FFFF1c;}\n",
       ".cython.score-82 {background-color: #FFFF1b;}\n",
       ".cython.score-83 {background-color: #FFFF1b;}\n",
       ".cython.score-84 {background-color: #FFFF1b;}\n",
       ".cython.score-85 {background-color: #FFFF1a;}\n",
       ".cython.score-86 {background-color: #FFFF1a;}\n",
       ".cython.score-87 {background-color: #FFFF1a;}\n",
       ".cython.score-88 {background-color: #FFFF1a;}\n",
       ".cython.score-89 {background-color: #FFFF19;}\n",
       ".cython.score-90 {background-color: #FFFF19;}\n",
       ".cython.score-91 {background-color: #FFFF19;}\n",
       ".cython.score-92 {background-color: #FFFF19;}\n",
       ".cython.score-93 {background-color: #FFFF18;}\n",
       ".cython.score-94 {background-color: #FFFF18;}\n",
       ".cython.score-95 {background-color: #FFFF18;}\n",
       ".cython.score-96 {background-color: #FFFF18;}\n",
       ".cython.score-97 {background-color: #FFFF17;}\n",
       ".cython.score-98 {background-color: #FFFF17;}\n",
       ".cython.score-99 {background-color: #FFFF17;}\n",
       ".cython.score-100 {background-color: #FFFF17;}\n",
       ".cython.score-101 {background-color: #FFFF16;}\n",
       ".cython.score-102 {background-color: #FFFF16;}\n",
       ".cython.score-103 {background-color: #FFFF16;}\n",
       ".cython.score-104 {background-color: #FFFF16;}\n",
       ".cython.score-105 {background-color: #FFFF16;}\n",
       ".cython.score-106 {background-color: #FFFF15;}\n",
       ".cython.score-107 {background-color: #FFFF15;}\n",
       ".cython.score-108 {background-color: #FFFF15;}\n",
       ".cython.score-109 {background-color: #FFFF15;}\n",
       ".cython.score-110 {background-color: #FFFF15;}\n",
       ".cython.score-111 {background-color: #FFFF15;}\n",
       ".cython.score-112 {background-color: #FFFF14;}\n",
       ".cython.score-113 {background-color: #FFFF14;}\n",
       ".cython.score-114 {background-color: #FFFF14;}\n",
       ".cython.score-115 {background-color: #FFFF14;}\n",
       ".cython.score-116 {background-color: #FFFF14;}\n",
       ".cython.score-117 {background-color: #FFFF14;}\n",
       ".cython.score-118 {background-color: #FFFF13;}\n",
       ".cython.score-119 {background-color: #FFFF13;}\n",
       ".cython.score-120 {background-color: #FFFF13;}\n",
       ".cython.score-121 {background-color: #FFFF13;}\n",
       ".cython.score-122 {background-color: #FFFF13;}\n",
       ".cython.score-123 {background-color: #FFFF13;}\n",
       ".cython.score-124 {background-color: #FFFF13;}\n",
       ".cython.score-125 {background-color: #FFFF12;}\n",
       ".cython.score-126 {background-color: #FFFF12;}\n",
       ".cython.score-127 {background-color: #FFFF12;}\n",
       ".cython.score-128 {background-color: #FFFF12;}\n",
       ".cython.score-129 {background-color: #FFFF12;}\n",
       ".cython.score-130 {background-color: #FFFF12;}\n",
       ".cython.score-131 {background-color: #FFFF12;}\n",
       ".cython.score-132 {background-color: #FFFF11;}\n",
       ".cython.score-133 {background-color: #FFFF11;}\n",
       ".cython.score-134 {background-color: #FFFF11;}\n",
       ".cython.score-135 {background-color: #FFFF11;}\n",
       ".cython.score-136 {background-color: #FFFF11;}\n",
       ".cython.score-137 {background-color: #FFFF11;}\n",
       ".cython.score-138 {background-color: #FFFF11;}\n",
       ".cython.score-139 {background-color: #FFFF11;}\n",
       ".cython.score-140 {background-color: #FFFF11;}\n",
       ".cython.score-141 {background-color: #FFFF10;}\n",
       ".cython.score-142 {background-color: #FFFF10;}\n",
       ".cython.score-143 {background-color: #FFFF10;}\n",
       ".cython.score-144 {background-color: #FFFF10;}\n",
       ".cython.score-145 {background-color: #FFFF10;}\n",
       ".cython.score-146 {background-color: #FFFF10;}\n",
       ".cython.score-147 {background-color: #FFFF10;}\n",
       ".cython.score-148 {background-color: #FFFF10;}\n",
       ".cython.score-149 {background-color: #FFFF10;}\n",
       ".cython.score-150 {background-color: #FFFF0f;}\n",
       ".cython.score-151 {background-color: #FFFF0f;}\n",
       ".cython.score-152 {background-color: #FFFF0f;}\n",
       ".cython.score-153 {background-color: #FFFF0f;}\n",
       ".cython.score-154 {background-color: #FFFF0f;}\n",
       ".cython.score-155 {background-color: #FFFF0f;}\n",
       ".cython.score-156 {background-color: #FFFF0f;}\n",
       ".cython.score-157 {background-color: #FFFF0f;}\n",
       ".cython.score-158 {background-color: #FFFF0f;}\n",
       ".cython.score-159 {background-color: #FFFF0f;}\n",
       ".cython.score-160 {background-color: #FFFF0f;}\n",
       ".cython.score-161 {background-color: #FFFF0e;}\n",
       ".cython.score-162 {background-color: #FFFF0e;}\n",
       ".cython.score-163 {background-color: #FFFF0e;}\n",
       ".cython.score-164 {background-color: #FFFF0e;}\n",
       ".cython.score-165 {background-color: #FFFF0e;}\n",
       ".cython.score-166 {background-color: #FFFF0e;}\n",
       ".cython.score-167 {background-color: #FFFF0e;}\n",
       ".cython.score-168 {background-color: #FFFF0e;}\n",
       ".cython.score-169 {background-color: #FFFF0e;}\n",
       ".cython.score-170 {background-color: #FFFF0e;}\n",
       ".cython.score-171 {background-color: #FFFF0e;}\n",
       ".cython.score-172 {background-color: #FFFF0e;}\n",
       ".cython.score-173 {background-color: #FFFF0d;}\n",
       ".cython.score-174 {background-color: #FFFF0d;}\n",
       ".cython.score-175 {background-color: #FFFF0d;}\n",
       ".cython.score-176 {background-color: #FFFF0d;}\n",
       ".cython.score-177 {background-color: #FFFF0d;}\n",
       ".cython.score-178 {background-color: #FFFF0d;}\n",
       ".cython.score-179 {background-color: #FFFF0d;}\n",
       ".cython.score-180 {background-color: #FFFF0d;}\n",
       ".cython.score-181 {background-color: #FFFF0d;}\n",
       ".cython.score-182 {background-color: #FFFF0d;}\n",
       ".cython.score-183 {background-color: #FFFF0d;}\n",
       ".cython.score-184 {background-color: #FFFF0d;}\n",
       ".cython.score-185 {background-color: #FFFF0d;}\n",
       ".cython.score-186 {background-color: #FFFF0d;}\n",
       ".cython.score-187 {background-color: #FFFF0c;}\n",
       ".cython.score-188 {background-color: #FFFF0c;}\n",
       ".cython.score-189 {background-color: #FFFF0c;}\n",
       ".cython.score-190 {background-color: #FFFF0c;}\n",
       ".cython.score-191 {background-color: #FFFF0c;}\n",
       ".cython.score-192 {background-color: #FFFF0c;}\n",
       ".cython.score-193 {background-color: #FFFF0c;}\n",
       ".cython.score-194 {background-color: #FFFF0c;}\n",
       ".cython.score-195 {background-color: #FFFF0c;}\n",
       ".cython.score-196 {background-color: #FFFF0c;}\n",
       ".cython.score-197 {background-color: #FFFF0c;}\n",
       ".cython.score-198 {background-color: #FFFF0c;}\n",
       ".cython.score-199 {background-color: #FFFF0c;}\n",
       ".cython.score-200 {background-color: #FFFF0c;}\n",
       ".cython.score-201 {background-color: #FFFF0c;}\n",
       ".cython.score-202 {background-color: #FFFF0c;}\n",
       ".cython.score-203 {background-color: #FFFF0b;}\n",
       ".cython.score-204 {background-color: #FFFF0b;}\n",
       ".cython.score-205 {background-color: #FFFF0b;}\n",
       ".cython.score-206 {background-color: #FFFF0b;}\n",
       ".cython.score-207 {background-color: #FFFF0b;}\n",
       ".cython.score-208 {background-color: #FFFF0b;}\n",
       ".cython.score-209 {background-color: #FFFF0b;}\n",
       ".cython.score-210 {background-color: #FFFF0b;}\n",
       ".cython.score-211 {background-color: #FFFF0b;}\n",
       ".cython.score-212 {background-color: #FFFF0b;}\n",
       ".cython.score-213 {background-color: #FFFF0b;}\n",
       ".cython.score-214 {background-color: #FFFF0b;}\n",
       ".cython.score-215 {background-color: #FFFF0b;}\n",
       ".cython.score-216 {background-color: #FFFF0b;}\n",
       ".cython.score-217 {background-color: #FFFF0b;}\n",
       ".cython.score-218 {background-color: #FFFF0b;}\n",
       ".cython.score-219 {background-color: #FFFF0b;}\n",
       ".cython.score-220 {background-color: #FFFF0b;}\n",
       ".cython.score-221 {background-color: #FFFF0b;}\n",
       ".cython.score-222 {background-color: #FFFF0a;}\n",
       ".cython.score-223 {background-color: #FFFF0a;}\n",
       ".cython.score-224 {background-color: #FFFF0a;}\n",
       ".cython.score-225 {background-color: #FFFF0a;}\n",
       ".cython.score-226 {background-color: #FFFF0a;}\n",
       ".cython.score-227 {background-color: #FFFF0a;}\n",
       ".cython.score-228 {background-color: #FFFF0a;}\n",
       ".cython.score-229 {background-color: #FFFF0a;}\n",
       ".cython.score-230 {background-color: #FFFF0a;}\n",
       ".cython.score-231 {background-color: #FFFF0a;}\n",
       ".cython.score-232 {background-color: #FFFF0a;}\n",
       ".cython.score-233 {background-color: #FFFF0a;}\n",
       ".cython.score-234 {background-color: #FFFF0a;}\n",
       ".cython.score-235 {background-color: #FFFF0a;}\n",
       ".cython.score-236 {background-color: #FFFF0a;}\n",
       ".cython.score-237 {background-color: #FFFF0a;}\n",
       ".cython.score-238 {background-color: #FFFF0a;}\n",
       ".cython.score-239 {background-color: #FFFF0a;}\n",
       ".cython.score-240 {background-color: #FFFF0a;}\n",
       ".cython.score-241 {background-color: #FFFF0a;}\n",
       ".cython.score-242 {background-color: #FFFF0a;}\n",
       ".cython.score-243 {background-color: #FFFF0a;}\n",
       ".cython.score-244 {background-color: #FFFF0a;}\n",
       ".cython.score-245 {background-color: #FFFF0a;}\n",
       ".cython.score-246 {background-color: #FFFF09;}\n",
       ".cython.score-247 {background-color: #FFFF09;}\n",
       ".cython.score-248 {background-color: #FFFF09;}\n",
       ".cython.score-249 {background-color: #FFFF09;}\n",
       ".cython.score-250 {background-color: #FFFF09;}\n",
       ".cython.score-251 {background-color: #FFFF09;}\n",
       ".cython.score-252 {background-color: #FFFF09;}\n",
       ".cython.score-253 {background-color: #FFFF09;}\n",
       ".cython.score-254 {background-color: #FFFF09;}\n",
       ".cython .hll { background-color: #ffffcc }\n",
       ".cython  { background: #f8f8f8; }\n",
       ".cython .c { color: #408080; font-style: italic } /* Comment */\n",
       ".cython .err { border: 1px solid #FF0000 } /* Error */\n",
       ".cython .k { color: #008000; font-weight: bold } /* Keyword */\n",
       ".cython .o { color: #666666 } /* Operator */\n",
       ".cython .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       ".cython .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       ".cython .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       ".cython .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       ".cython .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       ".cython .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       ".cython .gd { color: #A00000 } /* Generic.Deleted */\n",
       ".cython .ge { font-style: italic } /* Generic.Emph */\n",
       ".cython .gr { color: #FF0000 } /* Generic.Error */\n",
       ".cython .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       ".cython .gi { color: #00A000 } /* Generic.Inserted */\n",
       ".cython .go { color: #888888 } /* Generic.Output */\n",
       ".cython .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       ".cython .gs { font-weight: bold } /* Generic.Strong */\n",
       ".cython .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       ".cython .gt { color: #0044DD } /* Generic.Traceback */\n",
       ".cython .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       ".cython .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       ".cython .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       ".cython .kp { color: #008000 } /* Keyword.Pseudo */\n",
       ".cython .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       ".cython .kt { color: #B00040 } /* Keyword.Type */\n",
       ".cython .m { color: #666666 } /* Literal.Number */\n",
       ".cython .s { color: #BA2121 } /* Literal.String */\n",
       ".cython .na { color: #7D9029 } /* Name.Attribute */\n",
       ".cython .nb { color: #008000 } /* Name.Builtin */\n",
       ".cython .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       ".cython .no { color: #880000 } /* Name.Constant */\n",
       ".cython .nd { color: #AA22FF } /* Name.Decorator */\n",
       ".cython .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       ".cython .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       ".cython .nf { color: #0000FF } /* Name.Function */\n",
       ".cython .nl { color: #A0A000 } /* Name.Label */\n",
       ".cython .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       ".cython .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       ".cython .nv { color: #19177C } /* Name.Variable */\n",
       ".cython .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       ".cython .w { color: #bbbbbb } /* Text.Whitespace */\n",
       ".cython .mb { color: #666666 } /* Literal.Number.Bin */\n",
       ".cython .mf { color: #666666 } /* Literal.Number.Float */\n",
       ".cython .mh { color: #666666 } /* Literal.Number.Hex */\n",
       ".cython .mi { color: #666666 } /* Literal.Number.Integer */\n",
       ".cython .mo { color: #666666 } /* Literal.Number.Oct */\n",
       ".cython .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       ".cython .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       ".cython .sc { color: #BA2121 } /* Literal.String.Char */\n",
       ".cython .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       ".cython .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       ".cython .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       ".cython .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       ".cython .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       ".cython .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       ".cython .sx { color: #008000 } /* Literal.String.Other */\n",
       ".cython .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       ".cython .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       ".cython .ss { color: #19177C } /* Literal.String.Symbol */\n",
       ".cython .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       ".cython .fm { color: #0000FF } /* Name.Function.Magic */\n",
       ".cython .vc { color: #19177C } /* Name.Variable.Class */\n",
       ".cython .vg { color: #19177C } /* Name.Variable.Global */\n",
       ".cython .vi { color: #19177C } /* Name.Variable.Instance */\n",
       ".cython .vm { color: #19177C } /* Name.Variable.Magic */\n",
       ".cython .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "    </style>\n",
       "</head>\n",
       "<body class=\"cython\">\n",
       "<p><span style=\"border-bottom: solid 1px grey;\">Generated by Cython 0.29.6</span></p>\n",
       "<p>\n",
       "    <span style=\"background-color: #FFFF00\">Yellow lines</span> hint at Python interaction.<br />\n",
       "    Click on a line that starts with a \"<code>+</code>\" to see the C code that Cython generated for it.\n",
       "</p>\n",
       "<div class=\"cython\"><pre class=\"cython line score-0\">&#xA0;<span class=\"\">01</span>: </pre>\n",
       "<pre class=\"cython line score-8\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">02</span>: <span class=\"k\">import</span> <span class=\"nn\">numpy</span> <span class=\"k\">as</span> <span class=\"nn\">np</span></pre>\n",
       "<pre class='cython code score-8 '>  __pyx_t_1 = <span class='pyx_c_api'>__Pyx_Import</span>(__pyx_n_s_numpy, 0, 0);<span class='error_goto'> if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 2, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  if (<span class='py_c_api'>PyDict_SetItem</span>(__pyx_d, __pyx_n_s_np, __pyx_t_1) &lt; 0) <span class='error_goto'>__PYX_ERR(0, 2, __pyx_L1_error)</span>\n",
       "  <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_1); __pyx_t_1 = 0;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">03</span>: <span class=\"k\">cimport</span> <span class=\"nn\">cython</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">04</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">05</span>: <span class=\"c\">#@cython.boundscheck(False)</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">06</span>: <span class=\"c\">#@cython.wraparound(False)</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">07</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">08</span>: <span class=\"c\">#cpdef cy_create_memoization_table(str X, str Y):</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">09</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">10</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">11</span>:     <span class=\"c\"># TODO BEGIN ---------------------------</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">12</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">13</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">14</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">15</span>:     <span class=\"c\"># TODO END ---------------------------</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">16</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">17</span>:     <span class=\"c\">#return D</span></pre>\n",
       "</div></body></html>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%cython --a\n",
    "\n",
    "import numpy as np\n",
    "cimport cython\n",
    "\n",
    "cpdef cy_create_memoization_table(str X, str Y):\n",
    "\n",
    "    \n",
    "    # TODO BEGIN ---------------------------\n",
    "    \n",
    "    \n",
    "    \n",
    "    # TODO END ---------------------------\n",
    "    \n",
    "    #return D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "D1 = create_memoization_table(x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "D2 = cy_create_memoization_table(x,y)\n",
    "D2 = np.asarray(D2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "t_create_memoization_table = timeit.timeit(\"x='exponential'; y='polynomial'; create_memoization_table(x,y)\",\n",
    "                                           setup=\"import numpy as np; from __main__ import create_memoization_table\",\n",
    "                                          number=5000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "t_cy_create_memoization_table = timeit.timeit(\"x='exponential'; y='polynomial'; cy_create_memoization_table(x,y)\",\n",
    "                                              setup=\"from __main__ import cy_create_memoization_table\",\n",
    "                                              number=5000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "t_nltk = timeit.timeit(\"x='exponential'; y='polynomial'; nltk.edit_distance(x,y)\",\n",
    "                        setup=\"import nltk \",\n",
    "                        number=5000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "      Python version took: 0.8201289099997666 sec\n",
      "      Cython version took: 0.010222451001027366 sec\n",
      "      nltk   version took: 0.34801899699959904 sec\n",
      "      Cython is 80x faster than python\n",
      "      Cython is 34x faster than nltk\n",
      "      \n"
     ]
    }
   ],
   "source": [
    "print(\"\"\" \n",
    "      Python version took: {} sec\n",
    "      Cython version took: {} sec\n",
    "      nltk   version took: {} sec\n",
    "      Cython is {:.0f}x faster than python\n",
    "      Cython is {:.0f}x faster than nltk\n",
    "      \"\"\"\\\n",
    "      .format(t_create_memoization_table, \n",
    "              t_cy_create_memoization_table,\n",
    "              t_nltk, \n",
    "              t_create_memoization_table/t_cy_create_memoization_table,\n",
    "              t_nltk/t_cy_create_memoization_table))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Return to the experiment where we computed closest word\n",
    "\n",
    "\n",
    "##### Exercise: Return the last component of the DynamicProgramming matrix containing the edit distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-05T21:54:33.811051Z",
     "start_time": "2020-03-05T21:54:33.371036Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html>\n",
       "<!-- Generated by Cython 0.29.6 -->\n",
       "<html>\n",
       "<head>\n",
       "    <meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\" />\n",
       "    <title>Cython: _cython_magic_c71f487a7c38fcd1b5d77ab434cb0a89.pyx</title>\n",
       "    <style type=\"text/css\">\n",
       "    \n",
       "body.cython { font-family: courier; font-size: 12; }\n",
       "\n",
       ".cython.tag  {  }\n",
       ".cython.line { margin: 0em }\n",
       ".cython.code { font-size: 9; color: #444444; display: none; margin: 0px 0px 0px 8px; border-left: 8px none; }\n",
       "\n",
       ".cython.line .run { background-color: #B0FFB0; }\n",
       ".cython.line .mis { background-color: #FFB0B0; }\n",
       ".cython.code.run  { border-left: 8px solid #B0FFB0; }\n",
       ".cython.code.mis  { border-left: 8px solid #FFB0B0; }\n",
       "\n",
       ".cython.code .py_c_api  { color: red; }\n",
       ".cython.code .py_macro_api  { color: #FF7000; }\n",
       ".cython.code .pyx_c_api  { color: #FF3000; }\n",
       ".cython.code .pyx_macro_api  { color: #FF7000; }\n",
       ".cython.code .refnanny  { color: #FFA000; }\n",
       ".cython.code .trace  { color: #FFA000; }\n",
       ".cython.code .error_goto  { color: #FFA000; }\n",
       "\n",
       ".cython.code .coerce  { color: #008000; border: 1px dotted #008000 }\n",
       ".cython.code .py_attr { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_attr  { color: #0000FF; }\n",
       ".cython.code .py_call { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_call  { color: #0000FF; }\n",
       "\n",
       ".cython.score-0 {background-color: #FFFFff;}\n",
       ".cython.score-1 {background-color: #FFFFe7;}\n",
       ".cython.score-2 {background-color: #FFFFd4;}\n",
       ".cython.score-3 {background-color: #FFFFc4;}\n",
       ".cython.score-4 {background-color: #FFFFb6;}\n",
       ".cython.score-5 {background-color: #FFFFaa;}\n",
       ".cython.score-6 {background-color: #FFFF9f;}\n",
       ".cython.score-7 {background-color: #FFFF96;}\n",
       ".cython.score-8 {background-color: #FFFF8d;}\n",
       ".cython.score-9 {background-color: #FFFF86;}\n",
       ".cython.score-10 {background-color: #FFFF7f;}\n",
       ".cython.score-11 {background-color: #FFFF79;}\n",
       ".cython.score-12 {background-color: #FFFF73;}\n",
       ".cython.score-13 {background-color: #FFFF6e;}\n",
       ".cython.score-14 {background-color: #FFFF6a;}\n",
       ".cython.score-15 {background-color: #FFFF66;}\n",
       ".cython.score-16 {background-color: #FFFF62;}\n",
       ".cython.score-17 {background-color: #FFFF5e;}\n",
       ".cython.score-18 {background-color: #FFFF5b;}\n",
       ".cython.score-19 {background-color: #FFFF57;}\n",
       ".cython.score-20 {background-color: #FFFF55;}\n",
       ".cython.score-21 {background-color: #FFFF52;}\n",
       ".cython.score-22 {background-color: #FFFF4f;}\n",
       ".cython.score-23 {background-color: #FFFF4d;}\n",
       ".cython.score-24 {background-color: #FFFF4b;}\n",
       ".cython.score-25 {background-color: #FFFF48;}\n",
       ".cython.score-26 {background-color: #FFFF46;}\n",
       ".cython.score-27 {background-color: #FFFF44;}\n",
       ".cython.score-28 {background-color: #FFFF43;}\n",
       ".cython.score-29 {background-color: #FFFF41;}\n",
       ".cython.score-30 {background-color: #FFFF3f;}\n",
       ".cython.score-31 {background-color: #FFFF3e;}\n",
       ".cython.score-32 {background-color: #FFFF3c;}\n",
       ".cython.score-33 {background-color: #FFFF3b;}\n",
       ".cython.score-34 {background-color: #FFFF39;}\n",
       ".cython.score-35 {background-color: #FFFF38;}\n",
       ".cython.score-36 {background-color: #FFFF37;}\n",
       ".cython.score-37 {background-color: #FFFF36;}\n",
       ".cython.score-38 {background-color: #FFFF35;}\n",
       ".cython.score-39 {background-color: #FFFF34;}\n",
       ".cython.score-40 {background-color: #FFFF33;}\n",
       ".cython.score-41 {background-color: #FFFF32;}\n",
       ".cython.score-42 {background-color: #FFFF31;}\n",
       ".cython.score-43 {background-color: #FFFF30;}\n",
       ".cython.score-44 {background-color: #FFFF2f;}\n",
       ".cython.score-45 {background-color: #FFFF2e;}\n",
       ".cython.score-46 {background-color: #FFFF2d;}\n",
       ".cython.score-47 {background-color: #FFFF2c;}\n",
       ".cython.score-48 {background-color: #FFFF2b;}\n",
       ".cython.score-49 {background-color: #FFFF2b;}\n",
       ".cython.score-50 {background-color: #FFFF2a;}\n",
       ".cython.score-51 {background-color: #FFFF29;}\n",
       ".cython.score-52 {background-color: #FFFF29;}\n",
       ".cython.score-53 {background-color: #FFFF28;}\n",
       ".cython.score-54 {background-color: #FFFF27;}\n",
       ".cython.score-55 {background-color: #FFFF27;}\n",
       ".cython.score-56 {background-color: #FFFF26;}\n",
       ".cython.score-57 {background-color: #FFFF26;}\n",
       ".cython.score-58 {background-color: #FFFF25;}\n",
       ".cython.score-59 {background-color: #FFFF24;}\n",
       ".cython.score-60 {background-color: #FFFF24;}\n",
       ".cython.score-61 {background-color: #FFFF23;}\n",
       ".cython.score-62 {background-color: #FFFF23;}\n",
       ".cython.score-63 {background-color: #FFFF22;}\n",
       ".cython.score-64 {background-color: #FFFF22;}\n",
       ".cython.score-65 {background-color: #FFFF22;}\n",
       ".cython.score-66 {background-color: #FFFF21;}\n",
       ".cython.score-67 {background-color: #FFFF21;}\n",
       ".cython.score-68 {background-color: #FFFF20;}\n",
       ".cython.score-69 {background-color: #FFFF20;}\n",
       ".cython.score-70 {background-color: #FFFF1f;}\n",
       ".cython.score-71 {background-color: #FFFF1f;}\n",
       ".cython.score-72 {background-color: #FFFF1f;}\n",
       ".cython.score-73 {background-color: #FFFF1e;}\n",
       ".cython.score-74 {background-color: #FFFF1e;}\n",
       ".cython.score-75 {background-color: #FFFF1e;}\n",
       ".cython.score-76 {background-color: #FFFF1d;}\n",
       ".cython.score-77 {background-color: #FFFF1d;}\n",
       ".cython.score-78 {background-color: #FFFF1c;}\n",
       ".cython.score-79 {background-color: #FFFF1c;}\n",
       ".cython.score-80 {background-color: #FFFF1c;}\n",
       ".cython.score-81 {background-color: #FFFF1c;}\n",
       ".cython.score-82 {background-color: #FFFF1b;}\n",
       ".cython.score-83 {background-color: #FFFF1b;}\n",
       ".cython.score-84 {background-color: #FFFF1b;}\n",
       ".cython.score-85 {background-color: #FFFF1a;}\n",
       ".cython.score-86 {background-color: #FFFF1a;}\n",
       ".cython.score-87 {background-color: #FFFF1a;}\n",
       ".cython.score-88 {background-color: #FFFF1a;}\n",
       ".cython.score-89 {background-color: #FFFF19;}\n",
       ".cython.score-90 {background-color: #FFFF19;}\n",
       ".cython.score-91 {background-color: #FFFF19;}\n",
       ".cython.score-92 {background-color: #FFFF19;}\n",
       ".cython.score-93 {background-color: #FFFF18;}\n",
       ".cython.score-94 {background-color: #FFFF18;}\n",
       ".cython.score-95 {background-color: #FFFF18;}\n",
       ".cython.score-96 {background-color: #FFFF18;}\n",
       ".cython.score-97 {background-color: #FFFF17;}\n",
       ".cython.score-98 {background-color: #FFFF17;}\n",
       ".cython.score-99 {background-color: #FFFF17;}\n",
       ".cython.score-100 {background-color: #FFFF17;}\n",
       ".cython.score-101 {background-color: #FFFF16;}\n",
       ".cython.score-102 {background-color: #FFFF16;}\n",
       ".cython.score-103 {background-color: #FFFF16;}\n",
       ".cython.score-104 {background-color: #FFFF16;}\n",
       ".cython.score-105 {background-color: #FFFF16;}\n",
       ".cython.score-106 {background-color: #FFFF15;}\n",
       ".cython.score-107 {background-color: #FFFF15;}\n",
       ".cython.score-108 {background-color: #FFFF15;}\n",
       ".cython.score-109 {background-color: #FFFF15;}\n",
       ".cython.score-110 {background-color: #FFFF15;}\n",
       ".cython.score-111 {background-color: #FFFF15;}\n",
       ".cython.score-112 {background-color: #FFFF14;}\n",
       ".cython.score-113 {background-color: #FFFF14;}\n",
       ".cython.score-114 {background-color: #FFFF14;}\n",
       ".cython.score-115 {background-color: #FFFF14;}\n",
       ".cython.score-116 {background-color: #FFFF14;}\n",
       ".cython.score-117 {background-color: #FFFF14;}\n",
       ".cython.score-118 {background-color: #FFFF13;}\n",
       ".cython.score-119 {background-color: #FFFF13;}\n",
       ".cython.score-120 {background-color: #FFFF13;}\n",
       ".cython.score-121 {background-color: #FFFF13;}\n",
       ".cython.score-122 {background-color: #FFFF13;}\n",
       ".cython.score-123 {background-color: #FFFF13;}\n",
       ".cython.score-124 {background-color: #FFFF13;}\n",
       ".cython.score-125 {background-color: #FFFF12;}\n",
       ".cython.score-126 {background-color: #FFFF12;}\n",
       ".cython.score-127 {background-color: #FFFF12;}\n",
       ".cython.score-128 {background-color: #FFFF12;}\n",
       ".cython.score-129 {background-color: #FFFF12;}\n",
       ".cython.score-130 {background-color: #FFFF12;}\n",
       ".cython.score-131 {background-color: #FFFF12;}\n",
       ".cython.score-132 {background-color: #FFFF11;}\n",
       ".cython.score-133 {background-color: #FFFF11;}\n",
       ".cython.score-134 {background-color: #FFFF11;}\n",
       ".cython.score-135 {background-color: #FFFF11;}\n",
       ".cython.score-136 {background-color: #FFFF11;}\n",
       ".cython.score-137 {background-color: #FFFF11;}\n",
       ".cython.score-138 {background-color: #FFFF11;}\n",
       ".cython.score-139 {background-color: #FFFF11;}\n",
       ".cython.score-140 {background-color: #FFFF11;}\n",
       ".cython.score-141 {background-color: #FFFF10;}\n",
       ".cython.score-142 {background-color: #FFFF10;}\n",
       ".cython.score-143 {background-color: #FFFF10;}\n",
       ".cython.score-144 {background-color: #FFFF10;}\n",
       ".cython.score-145 {background-color: #FFFF10;}\n",
       ".cython.score-146 {background-color: #FFFF10;}\n",
       ".cython.score-147 {background-color: #FFFF10;}\n",
       ".cython.score-148 {background-color: #FFFF10;}\n",
       ".cython.score-149 {background-color: #FFFF10;}\n",
       ".cython.score-150 {background-color: #FFFF0f;}\n",
       ".cython.score-151 {background-color: #FFFF0f;}\n",
       ".cython.score-152 {background-color: #FFFF0f;}\n",
       ".cython.score-153 {background-color: #FFFF0f;}\n",
       ".cython.score-154 {background-color: #FFFF0f;}\n",
       ".cython.score-155 {background-color: #FFFF0f;}\n",
       ".cython.score-156 {background-color: #FFFF0f;}\n",
       ".cython.score-157 {background-color: #FFFF0f;}\n",
       ".cython.score-158 {background-color: #FFFF0f;}\n",
       ".cython.score-159 {background-color: #FFFF0f;}\n",
       ".cython.score-160 {background-color: #FFFF0f;}\n",
       ".cython.score-161 {background-color: #FFFF0e;}\n",
       ".cython.score-162 {background-color: #FFFF0e;}\n",
       ".cython.score-163 {background-color: #FFFF0e;}\n",
       ".cython.score-164 {background-color: #FFFF0e;}\n",
       ".cython.score-165 {background-color: #FFFF0e;}\n",
       ".cython.score-166 {background-color: #FFFF0e;}\n",
       ".cython.score-167 {background-color: #FFFF0e;}\n",
       ".cython.score-168 {background-color: #FFFF0e;}\n",
       ".cython.score-169 {background-color: #FFFF0e;}\n",
       ".cython.score-170 {background-color: #FFFF0e;}\n",
       ".cython.score-171 {background-color: #FFFF0e;}\n",
       ".cython.score-172 {background-color: #FFFF0e;}\n",
       ".cython.score-173 {background-color: #FFFF0d;}\n",
       ".cython.score-174 {background-color: #FFFF0d;}\n",
       ".cython.score-175 {background-color: #FFFF0d;}\n",
       ".cython.score-176 {background-color: #FFFF0d;}\n",
       ".cython.score-177 {background-color: #FFFF0d;}\n",
       ".cython.score-178 {background-color: #FFFF0d;}\n",
       ".cython.score-179 {background-color: #FFFF0d;}\n",
       ".cython.score-180 {background-color: #FFFF0d;}\n",
       ".cython.score-181 {background-color: #FFFF0d;}\n",
       ".cython.score-182 {background-color: #FFFF0d;}\n",
       ".cython.score-183 {background-color: #FFFF0d;}\n",
       ".cython.score-184 {background-color: #FFFF0d;}\n",
       ".cython.score-185 {background-color: #FFFF0d;}\n",
       ".cython.score-186 {background-color: #FFFF0d;}\n",
       ".cython.score-187 {background-color: #FFFF0c;}\n",
       ".cython.score-188 {background-color: #FFFF0c;}\n",
       ".cython.score-189 {background-color: #FFFF0c;}\n",
       ".cython.score-190 {background-color: #FFFF0c;}\n",
       ".cython.score-191 {background-color: #FFFF0c;}\n",
       ".cython.score-192 {background-color: #FFFF0c;}\n",
       ".cython.score-193 {background-color: #FFFF0c;}\n",
       ".cython.score-194 {background-color: #FFFF0c;}\n",
       ".cython.score-195 {background-color: #FFFF0c;}\n",
       ".cython.score-196 {background-color: #FFFF0c;}\n",
       ".cython.score-197 {background-color: #FFFF0c;}\n",
       ".cython.score-198 {background-color: #FFFF0c;}\n",
       ".cython.score-199 {background-color: #FFFF0c;}\n",
       ".cython.score-200 {background-color: #FFFF0c;}\n",
       ".cython.score-201 {background-color: #FFFF0c;}\n",
       ".cython.score-202 {background-color: #FFFF0c;}\n",
       ".cython.score-203 {background-color: #FFFF0b;}\n",
       ".cython.score-204 {background-color: #FFFF0b;}\n",
       ".cython.score-205 {background-color: #FFFF0b;}\n",
       ".cython.score-206 {background-color: #FFFF0b;}\n",
       ".cython.score-207 {background-color: #FFFF0b;}\n",
       ".cython.score-208 {background-color: #FFFF0b;}\n",
       ".cython.score-209 {background-color: #FFFF0b;}\n",
       ".cython.score-210 {background-color: #FFFF0b;}\n",
       ".cython.score-211 {background-color: #FFFF0b;}\n",
       ".cython.score-212 {background-color: #FFFF0b;}\n",
       ".cython.score-213 {background-color: #FFFF0b;}\n",
       ".cython.score-214 {background-color: #FFFF0b;}\n",
       ".cython.score-215 {background-color: #FFFF0b;}\n",
       ".cython.score-216 {background-color: #FFFF0b;}\n",
       ".cython.score-217 {background-color: #FFFF0b;}\n",
       ".cython.score-218 {background-color: #FFFF0b;}\n",
       ".cython.score-219 {background-color: #FFFF0b;}\n",
       ".cython.score-220 {background-color: #FFFF0b;}\n",
       ".cython.score-221 {background-color: #FFFF0b;}\n",
       ".cython.score-222 {background-color: #FFFF0a;}\n",
       ".cython.score-223 {background-color: #FFFF0a;}\n",
       ".cython.score-224 {background-color: #FFFF0a;}\n",
       ".cython.score-225 {background-color: #FFFF0a;}\n",
       ".cython.score-226 {background-color: #FFFF0a;}\n",
       ".cython.score-227 {background-color: #FFFF0a;}\n",
       ".cython.score-228 {background-color: #FFFF0a;}\n",
       ".cython.score-229 {background-color: #FFFF0a;}\n",
       ".cython.score-230 {background-color: #FFFF0a;}\n",
       ".cython.score-231 {background-color: #FFFF0a;}\n",
       ".cython.score-232 {background-color: #FFFF0a;}\n",
       ".cython.score-233 {background-color: #FFFF0a;}\n",
       ".cython.score-234 {background-color: #FFFF0a;}\n",
       ".cython.score-235 {background-color: #FFFF0a;}\n",
       ".cython.score-236 {background-color: #FFFF0a;}\n",
       ".cython.score-237 {background-color: #FFFF0a;}\n",
       ".cython.score-238 {background-color: #FFFF0a;}\n",
       ".cython.score-239 {background-color: #FFFF0a;}\n",
       ".cython.score-240 {background-color: #FFFF0a;}\n",
       ".cython.score-241 {background-color: #FFFF0a;}\n",
       ".cython.score-242 {background-color: #FFFF0a;}\n",
       ".cython.score-243 {background-color: #FFFF0a;}\n",
       ".cython.score-244 {background-color: #FFFF0a;}\n",
       ".cython.score-245 {background-color: #FFFF0a;}\n",
       ".cython.score-246 {background-color: #FFFF09;}\n",
       ".cython.score-247 {background-color: #FFFF09;}\n",
       ".cython.score-248 {background-color: #FFFF09;}\n",
       ".cython.score-249 {background-color: #FFFF09;}\n",
       ".cython.score-250 {background-color: #FFFF09;}\n",
       ".cython.score-251 {background-color: #FFFF09;}\n",
       ".cython.score-252 {background-color: #FFFF09;}\n",
       ".cython.score-253 {background-color: #FFFF09;}\n",
       ".cython.score-254 {background-color: #FFFF09;}\n",
       ".cython .hll { background-color: #ffffcc }\n",
       ".cython  { background: #f8f8f8; }\n",
       ".cython .c { color: #408080; font-style: italic } /* Comment */\n",
       ".cython .err { border: 1px solid #FF0000 } /* Error */\n",
       ".cython .k { color: #008000; font-weight: bold } /* Keyword */\n",
       ".cython .o { color: #666666 } /* Operator */\n",
       ".cython .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       ".cython .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       ".cython .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       ".cython .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       ".cython .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       ".cython .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       ".cython .gd { color: #A00000 } /* Generic.Deleted */\n",
       ".cython .ge { font-style: italic } /* Generic.Emph */\n",
       ".cython .gr { color: #FF0000 } /* Generic.Error */\n",
       ".cython .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       ".cython .gi { color: #00A000 } /* Generic.Inserted */\n",
       ".cython .go { color: #888888 } /* Generic.Output */\n",
       ".cython .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       ".cython .gs { font-weight: bold } /* Generic.Strong */\n",
       ".cython .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       ".cython .gt { color: #0044DD } /* Generic.Traceback */\n",
       ".cython .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       ".cython .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       ".cython .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       ".cython .kp { color: #008000 } /* Keyword.Pseudo */\n",
       ".cython .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       ".cython .kt { color: #B00040 } /* Keyword.Type */\n",
       ".cython .m { color: #666666 } /* Literal.Number */\n",
       ".cython .s { color: #BA2121 } /* Literal.String */\n",
       ".cython .na { color: #7D9029 } /* Name.Attribute */\n",
       ".cython .nb { color: #008000 } /* Name.Builtin */\n",
       ".cython .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       ".cython .no { color: #880000 } /* Name.Constant */\n",
       ".cython .nd { color: #AA22FF } /* Name.Decorator */\n",
       ".cython .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       ".cython .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       ".cython .nf { color: #0000FF } /* Name.Function */\n",
       ".cython .nl { color: #A0A000 } /* Name.Label */\n",
       ".cython .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       ".cython .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       ".cython .nv { color: #19177C } /* Name.Variable */\n",
       ".cython .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       ".cython .w { color: #bbbbbb } /* Text.Whitespace */\n",
       ".cython .mb { color: #666666 } /* Literal.Number.Bin */\n",
       ".cython .mf { color: #666666 } /* Literal.Number.Float */\n",
       ".cython .mh { color: #666666 } /* Literal.Number.Hex */\n",
       ".cython .mi { color: #666666 } /* Literal.Number.Integer */\n",
       ".cython .mo { color: #666666 } /* Literal.Number.Oct */\n",
       ".cython .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       ".cython .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       ".cython .sc { color: #BA2121 } /* Literal.String.Char */\n",
       ".cython .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       ".cython .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       ".cython .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       ".cython .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       ".cython .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       ".cython .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       ".cython .sx { color: #008000 } /* Literal.String.Other */\n",
       ".cython .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       ".cython .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       ".cython .ss { color: #19177C } /* Literal.String.Symbol */\n",
       ".cython .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       ".cython .fm { color: #0000FF } /* Name.Function.Magic */\n",
       ".cython .vc { color: #19177C } /* Name.Variable.Class */\n",
       ".cython .vg { color: #19177C } /* Name.Variable.Global */\n",
       ".cython .vi { color: #19177C } /* Name.Variable.Instance */\n",
       ".cython .vm { color: #19177C } /* Name.Variable.Magic */\n",
       ".cython .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "    </style>\n",
       "</head>\n",
       "<body class=\"cython\">\n",
       "<p><span style=\"border-bottom: solid 1px grey;\">Generated by Cython 0.29.6</span></p>\n",
       "<p>\n",
       "    <span style=\"background-color: #FFFF00\">Yellow lines</span> hint at Python interaction.<br />\n",
       "    Click on a line that starts with a \"<code>+</code>\" to see the C code that Cython generated for it.\n",
       "</p>\n",
       "<div class=\"cython\"><pre class=\"cython line score-0\">&#xA0;<span class=\"\">01</span>: </pre>\n",
       "<pre class=\"cython line score-8\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">02</span>: <span class=\"k\">import</span> <span class=\"nn\">numpy</span> <span class=\"k\">as</span> <span class=\"nn\">np</span></pre>\n",
       "<pre class='cython code score-8 '>  __pyx_t_1 = <span class='pyx_c_api'>__Pyx_Import</span>(__pyx_n_s_numpy, 0, 0);<span class='error_goto'> if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 2, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  if (<span class='py_c_api'>PyDict_SetItem</span>(__pyx_d, __pyx_n_s_np, __pyx_t_1) &lt; 0) <span class='error_goto'>__PYX_ERR(0, 2, __pyx_L1_error)</span>\n",
       "  <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_1); __pyx_t_1 = 0;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">03</span>: <span class=\"k\">cimport</span> <span class=\"nn\">cython</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">04</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">05</span>: <span class=\"c\">#@cython.boundscheck(False)</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">06</span>: <span class=\"c\">#@cython.wraparound(False)</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">07</span>: <span class=\"c\">#cpdef edit_distance(str X, str Y):</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">08</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">09</span>:     <span class=\"c\">### TODO BEGIN ----------------------------------</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">10</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">11</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">12</span>:     <span class=\"c\">### TODO END ------------------------------------</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">13</span>: <span class=\"c\">#    return dist</span></pre>\n",
       "</div></body></html>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%cython --a\n",
    "\n",
    "import numpy as np\n",
    "cimport cython\n",
    "\n",
    "cpdef edit_distance(str X, str Y):\n",
    "\n",
    "    ### TODO BEGIN ----------------------------------\n",
    "    \n",
    "    \n",
    "    ### TODO END ------------------------------------\n",
    "    return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edit_distance(\"lik\", \"cat\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "236736"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = nltk.corpus.words.words()\n",
    "len(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "the closest word is drawing\n",
      "CPU times: user 10.3 s, sys: 28.2 ms, total: 10.3 s\n",
      "Wall time: 10.3 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "mistake = \"drauing\" \n",
    "distances = []\n",
    "for word in words:\n",
    "    ed = nltk.edit_distance(mistake, word)\n",
    "    distances.append(ed)\n",
    "    \n",
    "print(\"\\nthe closest word is\", words[np.argmin(distances)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "the closest word is drawing\n",
      "CPU times: user 451 ms, sys: 1.81 ms, total: 453 ms\n",
      "Wall time: 452 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "mistake = \"drauing\" \n",
    "cy_distances = []\n",
    "for word in words:\n",
    "    ed = editdistance.eval(mistake, word)\n",
    "    cy_distances.append(ed)\n",
    "    \n",
    "print(\"\\nthe closest word is\", words[np.argmin(cy_distances)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'edit_distance' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "File \u001b[0;32m<timed exec>:4\u001b[0m, in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'edit_distance' is not defined"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "mistake = \"drauing\" \n",
    "cy_distances = []\n",
    "for word in words:\n",
    "    ed = edit_distance(mistake, word)\n",
    "    cy_distances.append(ed)\n",
    "    \n",
    "print(\"\\nthe closest word is\", words[np.argmin(cy_distances)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distances == cy_distances"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 0)"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "editdistance.eval(\"hi\", \"hi\"), edit_distance(\"hi\",\"hi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 1)"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "editdistance.eval(\"hi\", \"ho\"), edit_distance(\"hi\",\"ho\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "##### Interesting material on string similarities\n",
    "\n",
    "Approximate string matching:\n",
    "\n",
    "https://medium.com/@wolfgarbe/fast-approximate-string-matching-with-large-edit-distances-in-big-data-2015-9174a0968c0b\n",
    "\n",
    "Levenshtein distance using a trie:\n",
    "\n",
    "http://stevehanov.ca/blog/?id=114\n",
    "\n",
    "About jaccard distance:\n",
    "\n",
    "https://python.gotrained.com/nltk-edit-distance-jaccard-distance/\n",
    "\n",
    "\n",
    "Nice work on string similarities:\n",
    "\n",
    "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19.7158&rep=rep1&type=pdf\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.10"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}