assignment-07 First Step of using machine learning and models..ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Assignment-07 First Step of using machine learning and models."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://github.com/Computing-Intelligence/jupyters_and_slides/raw/master/entrance-test/images/kkb-ai.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "fname = './data/sqlResult_1558435.csv'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = pd.read_csv(fname, encoding='gb18030')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "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>id</th>\n",
       "      <th>author</th>\n",
       "      <th>source</th>\n",
       "      <th>content</th>\n",
       "      <th>feature</th>\n",
       "      <th>title</th>\n",
       "      <th>url</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>89617</td>\n",
       "      <td>NaN</td>\n",
       "      <td>快科技@http://www.kkj.cn/</td>\n",
       "      <td>此外，自本周（6月12日）起，除小米手机6等15款机型外，其余机型已暂停更新发布（含开发版/...</td>\n",
       "      <td>{\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"37\"...</td>\n",
       "      <td>小米MIUI 9首批机型曝光：共计15款</td>\n",
       "      <td>http://www.cnbeta.com/articles/tech/623597.htm</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>89616</td>\n",
       "      <td>NaN</td>\n",
       "      <td>快科技@http://www.kkj.cn/</td>\n",
       "      <td>骁龙835作为唯一通过Windows 10桌面平台认证的ARM处理器，高通强调，不会因为只考...</td>\n",
       "      <td>{\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"15\"...</td>\n",
       "      <td>骁龙835在Windows 10上的性能表现有望改善</td>\n",
       "      <td>http://www.cnbeta.com/articles/tech/623599.htm</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>89615</td>\n",
       "      <td>NaN</td>\n",
       "      <td>快科技@http://www.kkj.cn/</td>\n",
       "      <td>此前的一加3T搭载的是3400mAh电池，DashCharge快充规格为5V/4A。\\r\\n...</td>\n",
       "      <td>{\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"18\"...</td>\n",
       "      <td>一加手机5细节曝光：3300mAh、充半小时用1天</td>\n",
       "      <td>http://www.cnbeta.com/articles/tech/623601.htm</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>89614</td>\n",
       "      <td>NaN</td>\n",
       "      <td>新华社</td>\n",
       "      <td>这是6月18日在葡萄牙中部大佩德罗冈地区拍摄的被森林大火烧毁的汽车。新华社记者张立云摄\\r\\n</td>\n",
       "      <td>{\"type\":\"国际新闻\",\"site\":\"环球\",\"commentNum\":\"0\",\"j...</td>\n",
       "      <td>葡森林火灾造成至少62人死亡 政府宣布进入紧急状态（组图）</td>\n",
       "      <td>http://world.huanqiu.com/hot/2017-06/10866126....</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>89613</td>\n",
       "      <td>胡淑丽_MN7479</td>\n",
       "      <td>深圳大件事</td>\n",
       "      <td>（原标题：44岁女子跑深圳约会网友被拒，暴雨中裸身奔走……）\\r\\n@深圳交警微博称：昨日清...</td>\n",
       "      <td>{\"type\":\"新闻\",\"site\":\"网易热门\",\"commentNum\":\"978\",...</td>\n",
       "      <td>44岁女子约网友被拒暴雨中裸奔 交警为其披衣相随</td>\n",
       "      <td>http://news.163.com/17/0618/00/CN617P3Q0001875...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      id      author                  source  \\\n",
       "0  89617         NaN  快科技@http://www.kkj.cn/   \n",
       "1  89616         NaN  快科技@http://www.kkj.cn/   \n",
       "2  89615         NaN  快科技@http://www.kkj.cn/   \n",
       "3  89614         NaN                     新华社   \n",
       "4  89613  胡淑丽_MN7479                   深圳大件事   \n",
       "\n",
       "                                             content  \\\n",
       "0  此外，自本周（6月12日）起，除小米手机6等15款机型外，其余机型已暂停更新发布（含开发版/...   \n",
       "1  骁龙835作为唯一通过Windows 10桌面平台认证的ARM处理器，高通强调，不会因为只考...   \n",
       "2  此前的一加3T搭载的是3400mAh电池，DashCharge快充规格为5V/4A。\\r\\n...   \n",
       "3    这是6月18日在葡萄牙中部大佩德罗冈地区拍摄的被森林大火烧毁的汽车。新华社记者张立云摄\\r\\n   \n",
       "4  （原标题：44岁女子跑深圳约会网友被拒，暴雨中裸身奔走……）\\r\\n@深圳交警微博称：昨日清...   \n",
       "\n",
       "                                             feature  \\\n",
       "0  {\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"37\"...   \n",
       "1  {\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"15\"...   \n",
       "2  {\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"18\"...   \n",
       "3  {\"type\":\"国际新闻\",\"site\":\"环球\",\"commentNum\":\"0\",\"j...   \n",
       "4  {\"type\":\"新闻\",\"site\":\"网易热门\",\"commentNum\":\"978\",...   \n",
       "\n",
       "                           title  \\\n",
       "0           小米MIUI 9首批机型曝光：共计15款   \n",
       "1     骁龙835在Windows 10上的性能表现有望改善   \n",
       "2      一加手机5细节曝光：3300mAh、充半小时用1天   \n",
       "3  葡森林火灾造成至少62人死亡 政府宣布进入紧急状态（组图）   \n",
       "4       44岁女子约网友被拒暴雨中裸奔 交警为其披衣相随   \n",
       "\n",
       "                                                 url  \n",
       "0     http://www.cnbeta.com/articles/tech/623597.htm  \n",
       "1     http://www.cnbeta.com/articles/tech/623599.htm  \n",
       "2     http://www.cnbeta.com/articles/tech/623601.htm  \n",
       "3  http://world.huanqiu.com/hot/2017-06/10866126....  \n",
       "4  http://news.163.com/17/0618/00/CN617P3Q0001875...  "
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "content.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "xinhua_news = content[content['source'] == '新华社']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8778051801676133"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(xinhua_news) / len(content)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 任务描述"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "报社等相关的机构，往往会遇到一个问题，就是别人家的机构使用自己的文章但是并没有标明来源。 在本次任务中，我们将解决新华社的文章被抄袭引用的问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定的数据集合中，存在一些新闻预料，该预料是来自新华社，但是其来源并不是新华社，请设计技巧学习模型解决该问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1566105348906&di=ee9a2de91207767364853d4decc6cca3&imgtype=0&src=http%3A%2F%2Fmmbiz.qpic.cn%2Fmmbiz_png%2FTicO2kbP6Ao5sCsSQDpehZiczLdC6hDCNvoicjcOCEKX2bLxBc9gVOw28zHyFibfIWq9ceRibP6HDTKReGkr6YyTfQQ%2F640%3Fwx_fmt%3Dpng)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step1: 数据分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "请在课程的GitHub中下载数据集，然后使用pandas进行读取。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "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>id</th>\n",
       "      <th>author</th>\n",
       "      <th>source</th>\n",
       "      <th>content</th>\n",
       "      <th>feature</th>\n",
       "      <th>title</th>\n",
       "      <th>url</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>89617</td>\n",
       "      <td>NaN</td>\n",
       "      <td>快科技@http://www.kkj.cn/</td>\n",
       "      <td>此外，自本周（6月12日）起，除小米手机6等15款机型外，其余机型已暂停更新发布（含开发版/...</td>\n",
       "      <td>{\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"37\"...</td>\n",
       "      <td>小米MIUI 9首批机型曝光：共计15款</td>\n",
       "      <td>http://www.cnbeta.com/articles/tech/623597.htm</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>89616</td>\n",
       "      <td>NaN</td>\n",
       "      <td>快科技@http://www.kkj.cn/</td>\n",
       "      <td>骁龙835作为唯一通过Windows 10桌面平台认证的ARM处理器，高通强调，不会因为只考...</td>\n",
       "      <td>{\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"15\"...</td>\n",
       "      <td>骁龙835在Windows 10上的性能表现有望改善</td>\n",
       "      <td>http://www.cnbeta.com/articles/tech/623599.htm</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>89615</td>\n",
       "      <td>NaN</td>\n",
       "      <td>快科技@http://www.kkj.cn/</td>\n",
       "      <td>此前的一加3T搭载的是3400mAh电池，DashCharge快充规格为5V/4A。\\r\\n...</td>\n",
       "      <td>{\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"18\"...</td>\n",
       "      <td>一加手机5细节曝光：3300mAh、充半小时用1天</td>\n",
       "      <td>http://www.cnbeta.com/articles/tech/623601.htm</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>89614</td>\n",
       "      <td>NaN</td>\n",
       "      <td>新华社</td>\n",
       "      <td>这是6月18日在葡萄牙中部大佩德罗冈地区拍摄的被森林大火烧毁的汽车。新华社记者张立云摄\\r\\n</td>\n",
       "      <td>{\"type\":\"国际新闻\",\"site\":\"环球\",\"commentNum\":\"0\",\"j...</td>\n",
       "      <td>葡森林火灾造成至少62人死亡 政府宣布进入紧急状态（组图）</td>\n",
       "      <td>http://world.huanqiu.com/hot/2017-06/10866126....</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>89613</td>\n",
       "      <td>胡淑丽_MN7479</td>\n",
       "      <td>深圳大件事</td>\n",
       "      <td>（原标题：44岁女子跑深圳约会网友被拒，暴雨中裸身奔走……）\\r\\n@深圳交警微博称：昨日清...</td>\n",
       "      <td>{\"type\":\"新闻\",\"site\":\"网易热门\",\"commentNum\":\"978\",...</td>\n",
       "      <td>44岁女子约网友被拒暴雨中裸奔 交警为其披衣相随</td>\n",
       "      <td>http://news.163.com/17/0618/00/CN617P3Q0001875...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>89612</td>\n",
       "      <td>张怡</td>\n",
       "      <td>中国证券报?中证网</td>\n",
       "      <td>受到A股被纳入MSCI指数的利好消息刺激，A股市场从周三开始再度上演龙马行情，周四上午金...</td>\n",
       "      <td>{\"type\":\"市场\",\"site\":\"中证网\",\"commentNum\":\"0\",\"jo...</td>\n",
       "      <td>金融股一枝独秀 配置价值犹存</td>\n",
       "      <td>http://www.cs.com.cn/gppd/201706/t20170623_533...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>89611</td>\n",
       "      <td>NaN</td>\n",
       "      <td>威锋网@http://www.feng.com/</td>\n",
       "      <td>虽然至今夏普智能手机在市场上无法排得上号，已经完全没落，并于 2013 年退出中国市场，但是...</td>\n",
       "      <td>{\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"21\"...</td>\n",
       "      <td>配骁龙660 全面屏鼻祖夏普新机酝酿中</td>\n",
       "      <td>http://www.cnbeta.com/articles/tech/623603.htm</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>89610</td>\n",
       "      <td>申玉彬 整理</td>\n",
       "      <td>中国证券报?中证网</td>\n",
       "      <td>沙漠雄鹰：震荡有利消化套牢筹码\\r\\n　　周四开盘上证50在银行券商大蓝筹带动下一度涨近...</td>\n",
       "      <td>{\"type\":\"市场\",\"site\":\"中证网\",\"commentNum\":\"0\",\"jo...</td>\n",
       "      <td>博友早评：震荡有利消化套牢筹码</td>\n",
       "      <td>http://www.cs.com.cn/gppd/201706/t20170623_533...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>89609</td>\n",
       "      <td>李杭_BJS4645</td>\n",
       "      <td>荆楚网-楚天都市报</td>\n",
       "      <td>（原标题：武汉警方一下子抓了808人，还都是俊男靓女！原来他们每天偷偷摸摸干这事！）\\r\\n...</td>\n",
       "      <td>{\"type\":\"新闻\",\"site\":\"网易热门\",\"commentNum\":\"1600\"...</td>\n",
       "      <td>武汉千余警察出动 抓获808名俊男靓女全是诈骗犯</td>\n",
       "      <td>http://news.163.com/17/0614/14/CMT9N8G80001899...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>89608</td>\n",
       "      <td>吴瞬</td>\n",
       "      <td>中国证券报?中证网</td>\n",
       "      <td>6月21日，A股纳入MSCI指数尘埃落定，但当天被寄予厚望的券商股并未扛起反弹大旗。22...</td>\n",
       "      <td>{\"type\":\"市场\",\"site\":\"中证网\",\"commentNum\":\"0\",\"jo...</td>\n",
       "      <td>纳入MSCI指数 A股长期配置价值提升</td>\n",
       "      <td>http://www.cs.com.cn/gppd/201706/t20170623_533...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      id      author                    source  \\\n",
       "0  89617         NaN    快科技@http://www.kkj.cn/   \n",
       "1  89616         NaN    快科技@http://www.kkj.cn/   \n",
       "2  89615         NaN    快科技@http://www.kkj.cn/   \n",
       "3  89614         NaN                       新华社   \n",
       "4  89613  胡淑丽_MN7479                     深圳大件事   \n",
       "5  89612          张怡                 中国证券报?中证网   \n",
       "6  89611         NaN  威锋网@http://www.feng.com/   \n",
       "7  89610      申玉彬 整理                 中国证券报?中证网   \n",
       "8  89609  李杭_BJS4645                 荆楚网-楚天都市报   \n",
       "9  89608          吴瞬                 中国证券报?中证网   \n",
       "\n",
       "                                             content  \\\n",
       "0  此外，自本周（6月12日）起，除小米手机6等15款机型外，其余机型已暂停更新发布（含开发版/...   \n",
       "1  骁龙835作为唯一通过Windows 10桌面平台认证的ARM处理器，高通强调，不会因为只考...   \n",
       "2  此前的一加3T搭载的是3400mAh电池，DashCharge快充规格为5V/4A。\\r\\n...   \n",
       "3    这是6月18日在葡萄牙中部大佩德罗冈地区拍摄的被森林大火烧毁的汽车。新华社记者张立云摄\\r\\n   \n",
       "4  （原标题：44岁女子跑深圳约会网友被拒，暴雨中裸身奔走……）\\r\\n@深圳交警微博称：昨日清...   \n",
       "5  　　受到A股被纳入MSCI指数的利好消息刺激，A股市场从周三开始再度上演龙马行情，周四上午金...   \n",
       "6  虽然至今夏普智能手机在市场上无法排得上号，已经完全没落，并于 2013 年退出中国市场，但是...   \n",
       "7  　　沙漠雄鹰：震荡有利消化套牢筹码\\r\\n　　周四开盘上证50在银行券商大蓝筹带动下一度涨近...   \n",
       "8  （原标题：武汉警方一下子抓了808人，还都是俊男靓女！原来他们每天偷偷摸摸干这事！）\\r\\n...   \n",
       "9  　　6月21日，A股纳入MSCI指数尘埃落定，但当天被寄予厚望的券商股并未扛起反弹大旗。22...   \n",
       "\n",
       "                                             feature  \\\n",
       "0  {\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"37\"...   \n",
       "1  {\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"15\"...   \n",
       "2  {\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"18\"...   \n",
       "3  {\"type\":\"国际新闻\",\"site\":\"环球\",\"commentNum\":\"0\",\"j...   \n",
       "4  {\"type\":\"新闻\",\"site\":\"网易热门\",\"commentNum\":\"978\",...   \n",
       "5  {\"type\":\"市场\",\"site\":\"中证网\",\"commentNum\":\"0\",\"jo...   \n",
       "6  {\"type\":\"科技\",\"site\":\"cnbeta\",\"commentNum\":\"21\"...   \n",
       "7  {\"type\":\"市场\",\"site\":\"中证网\",\"commentNum\":\"0\",\"jo...   \n",
       "8  {\"type\":\"新闻\",\"site\":\"网易热门\",\"commentNum\":\"1600\"...   \n",
       "9  {\"type\":\"市场\",\"site\":\"中证网\",\"commentNum\":\"0\",\"jo...   \n",
       "\n",
       "                           title  \\\n",
       "0           小米MIUI 9首批机型曝光：共计15款   \n",
       "1     骁龙835在Windows 10上的性能表现有望改善   \n",
       "2      一加手机5细节曝光：3300mAh、充半小时用1天   \n",
       "3  葡森林火灾造成至少62人死亡 政府宣布进入紧急状态（组图）   \n",
       "4       44岁女子约网友被拒暴雨中裸奔 交警为其披衣相随   \n",
       "5                 金融股一枝独秀 配置价值犹存   \n",
       "6            配骁龙660 全面屏鼻祖夏普新机酝酿中   \n",
       "7                博友早评：震荡有利消化套牢筹码   \n",
       "8       武汉千余警察出动 抓获808名俊男靓女全是诈骗犯   \n",
       "9            纳入MSCI指数 A股长期配置价值提升   \n",
       "\n",
       "                                                 url  \n",
       "0     http://www.cnbeta.com/articles/tech/623597.htm  \n",
       "1     http://www.cnbeta.com/articles/tech/623599.htm  \n",
       "2     http://www.cnbeta.com/articles/tech/623601.htm  \n",
       "3  http://world.huanqiu.com/hot/2017-06/10866126....  \n",
       "4  http://news.163.com/17/0618/00/CN617P3Q0001875...  \n",
       "5  http://www.cs.com.cn/gppd/201706/t20170623_533...  \n",
       "6     http://www.cnbeta.com/articles/tech/623603.htm  \n",
       "7  http://www.cs.com.cn/gppd/201706/t20170623_533...  \n",
       "8  http://news.163.com/17/0614/14/CMT9N8G80001899...  \n",
       "9  http://www.cs.com.cn/gppd/201706/t20170623_533...  "
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "content.head(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step2: 数据预处理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将pandas中的数据，依据是否是新华社的文章，请改变成新的数据dataframe: <content, y>, 其中，content是文章内容，y是0或者1. 你可能要使用到pandas的dataframe操作。https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.apply.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "source = content['source']\n",
    "source = source.apply(lambda x: 1 if x == '新华社' else 0)\n",
    "\n",
    "frame = {\"content\": content['content'], \"y\": source}\n",
    "df = pd.DataFrame(frame)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "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>content</th>\n",
       "      <th>y</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>此外，自本周（6月12日）起，除小米手机6等15款机型外，其余机型已暂停更新发布（含开发版/...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>骁龙835作为唯一通过Windows 10桌面平台认证的ARM处理器，高通强调，不会因为只考...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>此前的一加3T搭载的是3400mAh电池，DashCharge快充规格为5V/4A。\\r\\n...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>这是6月18日在葡萄牙中部大佩德罗冈地区拍摄的被森林大火烧毁的汽车。新华社记者张立云摄\\r\\n</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>（原标题：44岁女子跑深圳约会网友被拒，暴雨中裸身奔走……）\\r\\n@深圳交警微博称：昨日清...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                             content  y\n",
       "0  此外，自本周（6月12日）起，除小米手机6等15款机型外，其余机型已暂停更新发布（含开发版/...  0\n",
       "1  骁龙835作为唯一通过Windows 10桌面平台认证的ARM处理器，高通强调，不会因为只考...  0\n",
       "2  此前的一加3T搭载的是3400mAh电池，DashCharge快充规格为5V/4A。\\r\\n...  0\n",
       "3    这是6月18日在葡萄牙中部大佩德罗冈地区拍摄的被森林大火烧毁的汽车。新华社记者张立云摄\\r\\n  1\n",
       "4  （原标题：44岁女子跑深圳约会网友被拒，暴雨中裸身奔走……）\\r\\n@深圳交警微博称：昨日清...  0"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step3: 使用tfidf进行文本向量化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "参考 https://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.TfidfVectorizer.html 对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对文本进行向量化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "89611"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "87054"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df = df.dropna()\n",
    "len(df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "100\n",
      "200\n",
      "300\n",
      "400\n",
      "500\n",
      "600\n",
      "700\n",
      "800\n",
      "900\n",
      "1000\n",
      "1100\n",
      "1200\n",
      "1300\n",
      "1400\n",
      "1500\n",
      "1600\n",
      "1700\n",
      "1800\n",
      "1900\n",
      "2000\n",
      "2100\n",
      "2200\n",
      "2300\n",
      "2400\n",
      "2500\n",
      "2600\n",
      "2700\n",
      "2800\n",
      "2900\n",
      "3000\n",
      "3100\n",
      "3200\n",
      "3300\n",
      "3400\n",
      "3500\n",
      "3600\n",
      "3700\n",
      "3800\n",
      "3900\n",
      "4000\n",
      "4100\n",
      "4200\n",
      "4300\n",
      "4400\n",
      "4500\n",
      "4600\n",
      "4700\n",
      "4800\n",
      "4900\n",
      "5000\n",
      "5100\n",
      "5200\n",
      "5300\n",
      "5400\n",
      "5500\n",
      "5600\n",
      "5700\n",
      "5800\n",
      "5900\n",
      "6000\n",
      "6100\n",
      "6200\n",
      "6300\n",
      "6400\n",
      "6500\n",
      "6600\n",
      "6700\n",
      "6800\n",
      "6900\n",
      "7000\n",
      "7100\n",
      "7200\n",
      "7300\n",
      "7400\n",
      "7500\n",
      "7600\n",
      "7700\n",
      "7800\n",
      "7900\n",
      "8000\n",
      "8100\n",
      "8200\n",
      "8300\n",
      "8400\n",
      "8500\n",
      "8600\n",
      "8700\n",
      "8800\n",
      "8900\n",
      "9000\n",
      "9100\n",
      "9200\n",
      "9300\n",
      "9400\n",
      "9500\n",
      "9600\n",
      "9700\n",
      "9800\n",
      "9900\n",
      "10000\n",
      "10100\n",
      "10200\n",
      "10300\n",
      "10400\n",
      "10500\n",
      "10600\n",
      "10700\n",
      "10800\n",
      "10900\n",
      "11000\n",
      "11100\n",
      "11200\n",
      "11300\n",
      "11400\n",
      "11500\n",
      "11600\n",
      "11700\n",
      "11800\n",
      "11900\n",
      "12000\n",
      "12100\n",
      "12200\n",
      "12300\n",
      "12400\n",
      "12500\n",
      "12600\n",
      "12700\n",
      "12800\n",
      "12900\n",
      "13000\n",
      "13100\n",
      "13200\n",
      "13300\n",
      "13400\n",
      "13500\n",
      "13600\n",
      "13700\n",
      "13800\n",
      "13900\n",
      "14000\n",
      "14100\n",
      "14200\n",
      "14300\n",
      "14400\n",
      "14500\n",
      "14600\n",
      "14700\n",
      "14800\n",
      "14900\n",
      "15000\n",
      "15100\n",
      "15200\n",
      "15300\n",
      "15400\n",
      "15500\n",
      "15600\n",
      "15700\n",
      "15800\n",
      "15900\n",
      "16000\n",
      "16100\n",
      "16200\n",
      "16300\n",
      "16400\n",
      "16500\n",
      "16600\n",
      "16700\n",
      "16800\n",
      "16900\n",
      "17000\n",
      "17100\n",
      "17200\n",
      "17300\n",
      "17400\n",
      "17500\n",
      "17600\n",
      "17700\n",
      "17800\n",
      "17900\n",
      "18000\n",
      "18100\n",
      "18200\n",
      "18300\n",
      "18400\n",
      "18500\n",
      "18600\n",
      "18700\n",
      "18800\n",
      "18900\n",
      "19000\n",
      "19100\n",
      "19200\n",
      "19300\n",
      "19400\n",
      "19500\n",
      "19600\n",
      "19700\n",
      "19800\n",
      "19900\n",
      "20000\n",
      "20100\n",
      "20200\n",
      "20300\n",
      "20400\n",
      "20500\n",
      "20600\n",
      "20700\n",
      "20800\n",
      "20900\n",
      "21000\n",
      "21100\n",
      "21200\n",
      "21300\n",
      "21400\n",
      "21500\n",
      "21600\n",
      "21700\n",
      "21800\n",
      "21900\n",
      "22000\n",
      "22100\n",
      "22200\n",
      "22300\n",
      "22400\n",
      "22500\n",
      "22600\n",
      "22700\n",
      "22800\n",
      "22900\n",
      "23000\n",
      "23100\n",
      "23200\n",
      "23300\n",
      "23400\n",
      "23500\n",
      "23600\n",
      "23700\n",
      "23800\n",
      "23900\n",
      "24000\n",
      "24100\n",
      "24200\n",
      "24300\n",
      "24400\n",
      "24500\n",
      "24600\n",
      "24700\n",
      "24800\n",
      "24900\n",
      "25000\n",
      "25100\n",
      "25200\n",
      "25300\n",
      "25400\n",
      "25500\n",
      "25600\n",
      "25700\n",
      "25800\n",
      "25900\n",
      "26000\n",
      "26100\n",
      "26200\n",
      "26300\n",
      "26400\n",
      "26500\n",
      "26600\n",
      "26700\n",
      "26800\n",
      "26900\n",
      "27000\n",
      "27100\n",
      "27200\n",
      "27300\n",
      "27400\n",
      "27500\n",
      "27600\n",
      "27700\n",
      "27800\n",
      "27900\n",
      "28000\n",
      "28100\n",
      "28200\n",
      "28300\n",
      "28400\n",
      "28500\n",
      "28600\n",
      "28700\n",
      "28800\n",
      "28900\n",
      "29000\n",
      "29100\n",
      "29200\n",
      "29300\n",
      "29400\n",
      "29500\n",
      "29600\n",
      "29700\n",
      "29800\n",
      "29900\n",
      "30000\n",
      "30100\n",
      "30200\n",
      "30300\n",
      "30400\n",
      "30500\n",
      "30600\n",
      "30700\n",
      "30800\n",
      "30900\n",
      "31000\n",
      "31100\n",
      "31200\n",
      "31300\n",
      "31400\n",
      "31500\n",
      "31600\n",
      "31700\n",
      "31800\n",
      "31900\n",
      "32000\n",
      "32100\n",
      "32200\n",
      "32300\n",
      "32400\n",
      "32500\n",
      "32600\n",
      "32700\n",
      "32800\n",
      "32900\n",
      "33000\n",
      "33100\n",
      "33200\n",
      "33300\n",
      "33400\n",
      "33500\n",
      "33600\n",
      "33700\n",
      "33800\n",
      "33900\n",
      "34000\n",
      "34100\n",
      "34200\n",
      "34300\n",
      "34400\n",
      "34500\n",
      "34600\n",
      "34700\n",
      "34800\n",
      "34900\n",
      "35000\n",
      "35100\n",
      "35200\n",
      "35300\n",
      "35400\n",
      "35500\n",
      "35600\n",
      "35700\n",
      "35800\n",
      "35900\n",
      "36000\n",
      "36100\n",
      "36200\n",
      "36300\n",
      "36400\n",
      "36500\n",
      "36600\n",
      "36700\n",
      "36800\n",
      "36900\n",
      "37000\n",
      "37100\n",
      "37200\n",
      "37300\n",
      "37400\n",
      "37500\n",
      "37600\n",
      "37700\n",
      "37800\n",
      "37900\n",
      "38000\n",
      "38100\n",
      "38200\n",
      "38300\n",
      "38400\n",
      "38500\n",
      "38600\n",
      "38700\n",
      "38800\n",
      "38900\n",
      "39000\n",
      "39100\n",
      "39200\n",
      "39300\n",
      "39400\n",
      "39500\n",
      "39600\n",
      "39700\n",
      "39800\n",
      "39900\n",
      "40000\n",
      "40100\n",
      "40200\n",
      "40300\n",
      "40400\n",
      "40500\n",
      "40600\n",
      "40700\n",
      "40800\n",
      "40900\n",
      "41000\n",
      "41100\n",
      "41200\n",
      "41300\n",
      "41400\n",
      "41500\n",
      "41600\n",
      "41700\n",
      "41800\n",
      "41900\n",
      "42000\n",
      "42100\n",
      "42200\n",
      "42300\n",
      "42400\n",
      "42500\n",
      "42600\n",
      "42700\n",
      "42800\n",
      "42900\n",
      "43000\n",
      "43100\n",
      "43200\n",
      "43300\n",
      "43400\n",
      "43500\n",
      "43600\n",
      "43700\n",
      "43800\n",
      "43900\n",
      "44000\n",
      "44100\n",
      "44200\n",
      "44300\n",
      "44400\n",
      "44500\n",
      "44600\n",
      "44700\n",
      "44800\n",
      "44900\n",
      "45000\n",
      "45100\n",
      "45200\n",
      "45300\n",
      "45400\n",
      "45500\n",
      "45600\n",
      "45700\n",
      "45800\n",
      "45900\n",
      "46000\n",
      "46100\n",
      "46200\n",
      "46300\n",
      "46400\n",
      "46500\n",
      "46600\n",
      "46700\n",
      "46800\n",
      "46900\n",
      "47000\n",
      "47100\n",
      "47200\n",
      "47300\n",
      "47400\n",
      "47500\n",
      "47600\n",
      "47700\n",
      "47800\n",
      "47900\n",
      "48000\n",
      "48100\n",
      "48200\n",
      "48300\n",
      "48400\n",
      "48500\n",
      "48600\n",
      "48700\n",
      "48800\n",
      "48900\n",
      "49000\n",
      "49100\n",
      "49200\n",
      "49300\n",
      "49400\n",
      "49500\n",
      "49600\n",
      "49700\n",
      "49800\n",
      "49900\n",
      "50000\n",
      "50100\n",
      "50200\n",
      "50300\n",
      "50400\n",
      "50500\n",
      "50600\n",
      "50700\n",
      "50800\n",
      "50900\n",
      "51000\n",
      "51100\n",
      "51200\n",
      "51300\n",
      "51400\n",
      "51500\n",
      "51600\n",
      "51700\n",
      "51800\n",
      "51900\n",
      "52000\n",
      "52100\n",
      "52200\n",
      "52300\n",
      "52400\n",
      "52500\n",
      "52600\n",
      "52700\n",
      "52800\n",
      "52900\n",
      "53000\n",
      "53100\n",
      "53200\n",
      "53300\n",
      "53400\n",
      "53500\n",
      "53600\n",
      "53700\n",
      "53800\n",
      "53900\n",
      "54000\n",
      "54100\n",
      "54200\n",
      "54300\n",
      "54400\n",
      "54500\n",
      "54600\n",
      "54700\n",
      "54800\n",
      "54900\n",
      "55000\n",
      "55100\n",
      "55200\n",
      "55300\n",
      "55400\n",
      "55500\n",
      "55600\n",
      "55700\n",
      "55800\n",
      "55900\n",
      "56000\n",
      "56100\n",
      "56200\n",
      "56300\n",
      "56400\n",
      "56500\n",
      "56600\n",
      "56700\n",
      "56800\n",
      "56900\n",
      "57000\n",
      "57100\n",
      "57200\n",
      "57300\n",
      "57400\n",
      "57500\n",
      "57600\n",
      "57700\n",
      "57800\n",
      "57900\n",
      "58000\n",
      "58100\n",
      "58200\n",
      "58300\n",
      "58400\n",
      "58500\n",
      "58600\n",
      "58700\n",
      "58800\n",
      "58900\n",
      "59000\n",
      "59100\n",
      "59200\n",
      "59300\n",
      "59400\n",
      "59500\n",
      "59600\n",
      "59700\n",
      "59800\n",
      "59900\n",
      "60000\n",
      "60100\n",
      "60200\n",
      "60300\n",
      "60400\n",
      "60500\n",
      "60600\n",
      "60700\n",
      "60800\n",
      "60900\n",
      "61000\n",
      "61100\n",
      "61200\n",
      "61300\n",
      "61400\n",
      "61500\n",
      "61600\n",
      "61700\n",
      "61800\n",
      "61900\n",
      "62000\n",
      "62100\n",
      "62200\n",
      "62300\n",
      "62400\n",
      "62500\n",
      "62600\n",
      "62700\n",
      "62800\n",
      "62900\n",
      "63000\n",
      "63100\n",
      "63200\n",
      "63300\n",
      "63400\n",
      "63500\n",
      "63600\n",
      "63700\n",
      "63800\n",
      "63900\n",
      "64000\n",
      "64100\n",
      "64200\n",
      "64300\n",
      "64400\n",
      "64500\n",
      "64600\n",
      "64700\n",
      "64800\n",
      "64900\n",
      "65000\n",
      "65100\n",
      "65200\n",
      "65300\n",
      "65400\n",
      "65500\n",
      "65600\n",
      "65700\n",
      "65800\n",
      "65900\n",
      "66000\n",
      "66100\n",
      "66200\n",
      "66300\n",
      "66400\n",
      "66500\n",
      "66600\n",
      "66700\n",
      "66800\n",
      "66900\n",
      "67000\n",
      "67100\n",
      "67200\n",
      "67300\n",
      "67400\n",
      "67500\n",
      "67600\n",
      "67700\n",
      "67800\n",
      "67900\n",
      "68000\n",
      "68100\n",
      "68200\n",
      "68300\n",
      "68400\n",
      "68500\n",
      "68600\n",
      "68700\n",
      "68800\n",
      "68900\n",
      "69000\n",
      "69100\n",
      "69200\n",
      "69300\n",
      "69400\n",
      "69500\n",
      "69600\n",
      "69700\n",
      "69800\n",
      "69900\n",
      "70000\n",
      "70100\n",
      "70200\n",
      "70300\n",
      "70400\n",
      "70500\n",
      "70600\n",
      "70700\n",
      "70800\n",
      "70900\n",
      "71000\n",
      "71100\n",
      "71200\n",
      "71300\n",
      "71400\n",
      "71500\n",
      "71600\n",
      "71700\n",
      "71800\n",
      "71900\n",
      "72000\n",
      "72100\n",
      "72200\n",
      "72300\n",
      "72400\n",
      "72500\n",
      "72600\n",
      "72700\n",
      "72800\n",
      "72900\n",
      "73000\n",
      "73100\n",
      "73200\n",
      "73300\n",
      "73400\n",
      "73500\n",
      "73600\n",
      "73700\n",
      "73800\n",
      "73900\n",
      "74000\n",
      "74100\n",
      "74200\n",
      "74300\n",
      "74400\n",
      "74500\n",
      "74600\n",
      "74700\n",
      "74800\n",
      "74900\n",
      "75000\n",
      "75100\n",
      "75200\n",
      "75300\n",
      "75400\n",
      "75500\n",
      "75600\n",
      "75700\n",
      "75800\n",
      "75900\n",
      "76000\n",
      "76100\n",
      "76200\n",
      "76300\n",
      "76400\n",
      "76500\n",
      "76600\n",
      "76700\n",
      "76800\n",
      "76900\n",
      "77000\n",
      "77100\n",
      "77200\n",
      "77300\n",
      "77400\n",
      "77500\n",
      "77600\n",
      "77700\n",
      "77800\n",
      "77900\n",
      "78000\n",
      "78100\n",
      "78200\n",
      "78300\n",
      "78400\n",
      "78500\n",
      "78600\n",
      "78700\n",
      "78800\n",
      "78900\n",
      "79000\n",
      "79100\n",
      "79200\n",
      "79300\n",
      "79400\n",
      "79500\n",
      "79600\n",
      "79700\n",
      "79800\n",
      "79900\n",
      "80000\n",
      "80100\n",
      "80200\n",
      "80300\n",
      "80400\n",
      "80500\n",
      "80600\n",
      "80700\n",
      "80800\n",
      "80900\n",
      "81000\n",
      "81100\n",
      "81200\n",
      "81300\n",
      "81400\n",
      "81500\n",
      "81600\n",
      "81700\n",
      "81800\n",
      "81900\n",
      "82000\n",
      "82100\n",
      "82200\n",
      "82300\n",
      "82400\n",
      "82500\n",
      "82600\n",
      "82700\n",
      "82800\n",
      "82900\n",
      "83000\n",
      "83100\n",
      "83200\n",
      "83300\n",
      "83400\n",
      "83500\n",
      "83600\n",
      "83700\n",
      "83800\n",
      "83900\n",
      "84000\n",
      "84100\n",
      "84200\n",
      "84300\n",
      "84400\n",
      "84500\n",
      "84600\n",
      "84700\n",
      "84800\n",
      "84900\n",
      "85000\n",
      "85100\n",
      "85200\n",
      "85300\n",
      "85400\n",
      "85500\n",
      "85600\n",
      "85700\n",
      "85800\n",
      "85900\n",
      "86000\n",
      "86100\n",
      "86200\n",
      "86300\n",
      "86400\n",
      "86500\n",
      "86600\n",
      "86700\n",
      "86800\n",
      "86900\n",
      "87000\n"
     ]
    }
   ],
   "source": [
    "# Before fitting tf-idf, we need to cut sentence to words since tf-idf is based on words\n",
    "\n",
    "input = df['content']\n",
    "\n",
    "import re\n",
    "import jieba\n",
    "\n",
    "cut_2_words_list = []\n",
    "for idx, news in enumerate(input):\n",
    "    clean_news = ''.join(re.findall(r'[\\d|\\w]+', news))\n",
    "    news_words = jieba.cut(clean_news)\n",
    "    cut_2_words_list.append(\" \".join(list(news_words)))\n",
    "    \n",
    "    if idx % 100 == 0:\n",
    "        print(idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "word_list_file = \"./news_list.txt\"\n",
    "import pickle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "# dump the list to file for later use\n",
    "word_list_file = \"./news_list.txt\"\n",
    "\n",
    "import pickle\n",
    "\n",
    "with open(word_list_file, \"wb\") as fp:\n",
    "    pickle.dump(cut_2_words_list, fp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "# load the list from file\n",
    "with open(word_list_file, \"rb\") as fp:\n",
    "    cut_2_words_list = pickle.load(fp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "87054"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(cut_2_words_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.feature_extraction.text import TfidfVectorizer\n",
    "\n",
    "# considering the later computation when fed to model, limit feature size to 1000\n",
    "# it turns out modelling with 1000 dimensional data is not good, so reduce to 400 dimension\n",
    "vectorizer = TfidfVectorizer(max_features=400)\n",
    "X = vectorizer.fit_transform(cut_2_words_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<87054x400 sparse matrix of type '<class 'numpy.float64'>'\n",
       "\twith 2173709 stored elements in Compressed Sparse Row format>"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(87054,)"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = df['y']\n",
    "y.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step4: 参考scikit-learning的方法，构建你的第一个机器学习模型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ 按照课程讲解的内容，把数据集分割为 traning_data, validation_data, test_data. https://scikit-learn.org/stable/modules/generated/sklearn.model_selection.train_test_split.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\wanga26\\AppData\\Local\\Continuum\\anaconda3\\envs\\cs231n\\lib\\site-packages\\sklearn\\model_selection\\_split.py:2026: FutureWarning: From version 0.21, test_size will always complement train_size unless both are specified.\n",
      "  FutureWarning)\n"
     ]
    }
   ],
   "source": [
    "# split data to train_data and test_data first\n",
    "from sklearn.model_selection import train_test_split\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, train_size=0.85)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((62895, 400), (62895,), (13059, 400), (13059,))"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_train.shape, y_train.shape, X_test.shape, y_test.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\wanga26\\AppData\\Local\\Continuum\\anaconda3\\envs\\cs231n\\lib\\site-packages\\sklearn\\model_selection\\_split.py:2026: FutureWarning: From version 0.21, test_size will always complement train_size unless both are specified.\n",
      "  FutureWarning)\n"
     ]
    }
   ],
   "source": [
    "# split train data to train_data and validation data further\n",
    "X_train, X_val, y_train, y_val = train_test_split(X_train, y_train, train_size=0.85)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((62895, 400), (62895,), (11100, 400), (11100,))"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_train.shape, y_train.shape, X_val.shape, y_val.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ 参照scikit learning的示例，从构建你的第一个KNN机器学习模型。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.025932788848876953\n",
      "model score on validation set is 0.9315315315315316\n",
      "147.16286969184875\n"
     ]
    }
   ],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "\n",
    "neigh = KNeighborsClassifier(n_neighbors=3)\n",
    "start_time = time.time()\n",
    "neigh.fit(X_train, y_train)\n",
    "mid_time = time.time()\n",
    "print(\"{}\".format(mid_time-start_time))\n",
    "print(\"model score on validation set is {}\".format(neigh.score(X_val, y_val)))\n",
    "end_time = time.time()\n",
    "print(\"{}\".format(end_time-start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step5: 在traning_data, validation_data, test_data 上观察其相关metric: recall, precision, f1等， 并解释其含义. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.metrics import precision_score, recall_score, f1_score, roc_auc_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "# metrics on validation_data\n",
    "predicted_y_val = neigh.predict(X_val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### precision score ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9469587777457481"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# precision score\n",
    "precision_score(y_val, predicted_y_val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### recall score ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9793302196164165"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recall_score(y_val, predicted_y_val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### f1 score ####"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9628724963361016"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f1_score(y_val, predicted_y_val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test data ##"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# metrics on test_data\n",
    "predicted_y_test = neigh.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "precision score is 0.9440927402778919\n",
      "recall_score score is 0.9757817811012917\n",
      "f1_score score is 0.9596757344030756\n"
     ]
    }
   ],
   "source": [
    "# metrics on test_data\n",
    "print(\"precision score is {}\".format(precision_score(y_test, predicted_y_test)))\n",
    "print(\"recall_score score is {}\".format(recall_score(y_test, predicted_y_test)))\n",
    "print(\"f1_score score is {}\".format(f1_score(y_test, predicted_y_test)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step6: 使用 test_data 对其进行新数据的判断, 你有没"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### See the last section in Test data ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step7: 调整不同的参数，观察变化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "# grid search to optimize hyperparameter\n",
    "from sklearn.model_selection import GridSearchCV\n",
    "parameters = {'n_neighbors': [3, 5, 7]}\n",
    "knn = KNeighborsClassifier()\n",
    "clf = GridSearchCV(knn, parameters, scoring='f1', verbose=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clf.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## It's too slow. Give up finally"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step8: 不断改变参数，直到性能达到“某个”点。问：“某个”怎么定义？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Final parameters for KNN: k=3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step9: 找出所以预测为 1， 但是实际为 0 的文章。 作为抄袭的候选者。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "predicted_y_test = neigh.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((87054, 400), (87054,))"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape, y.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "ename": "MemoryError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mMemoryError\u001b[0m                               Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-76-f8f09b9f94a5>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mpredicted_y\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mneigh\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpredict\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mX\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      2\u001b[0m \u001b[1;31m# split to small pieces since hitting memory error\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m \u001b[0mpredicted_y\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m[\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m \u001b[0mstarting\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m \u001b[1;32mwhile\u001b[0m \u001b[0mi\u001b[0m \u001b[1;33m<\u001b[0m \u001b[0mX\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mshape\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Continuum\\anaconda3\\envs\\cs231n\\lib\\site-packages\\sklearn\\neighbors\\classification.py\u001b[0m in \u001b[0;36mpredict\u001b[1;34m(self, X)\u001b[0m\n\u001b[0;32m    143\u001b[0m         \u001b[0mX\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mcheck_array\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mX\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0maccept_sparse\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;34m'csr'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    144\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 145\u001b[1;33m         \u001b[0mneigh_dist\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mneigh_ind\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mkneighbors\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mX\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    146\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    147\u001b[0m         \u001b[0mclasses_\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mclasses_\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Continuum\\anaconda3\\envs\\cs231n\\lib\\site-packages\\sklearn\\neighbors\\base.py\u001b[0m in \u001b[0;36mkneighbors\u001b[1;34m(self, X, n_neighbors, return_distance)\u001b[0m\n\u001b[0;32m    355\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0meffective_metric_\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;34m'euclidean'\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    356\u001b[0m                 dist = pairwise_distances(X, self._fit_X, 'euclidean',\n\u001b[1;32m--> 357\u001b[1;33m                                           n_jobs=n_jobs, squared=True)\n\u001b[0m\u001b[0;32m    358\u001b[0m             \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    359\u001b[0m                 dist = pairwise_distances(\n",
      "\u001b[1;32m~\\AppData\\Local\\Continuum\\anaconda3\\envs\\cs231n\\lib\\site-packages\\sklearn\\metrics\\pairwise.py\u001b[0m in \u001b[0;36mpairwise_distances\u001b[1;34m(X, Y, metric, n_jobs, **kwds)\u001b[0m\n\u001b[0;32m   1245\u001b[0m         \u001b[0mfunc\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mpartial\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mdistance\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mcdist\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmetric\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mmetric\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0mkwds\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m   1246\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m-> 1247\u001b[1;33m     \u001b[1;32mreturn\u001b[0m \u001b[0m_parallel_pairwise\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mX\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mY\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfunc\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mn_jobs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0mkwds\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m   1248\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m   1249\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Continuum\\anaconda3\\envs\\cs231n\\lib\\site-packages\\sklearn\\metrics\\pairwise.py\u001b[0m in \u001b[0;36m_parallel_pairwise\u001b[1;34m(X, Y, func, n_jobs, **kwds)\u001b[0m\n\u001b[0;32m   1088\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0mn_jobs\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m   1089\u001b[0m         \u001b[1;31m# Special case to avoid picklability checks in delayed\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m-> 1090\u001b[1;33m         \u001b[1;32mreturn\u001b[0m \u001b[0mfunc\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mX\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mY\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0mkwds\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m   1091\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m   1092\u001b[0m     \u001b[1;31m# TODO: in some cases, backend='threading' may be appropriate\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Continuum\\anaconda3\\envs\\cs231n\\lib\\site-packages\\sklearn\\metrics\\pairwise.py\u001b[0m in \u001b[0;36meuclidean_distances\u001b[1;34m(X, Y, Y_norm_squared, squared, X_norm_squared)\u001b[0m\n\u001b[0;32m    244\u001b[0m         \u001b[0mYY\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mrow_norms\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mY\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0msquared\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mTrue\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mnp\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnewaxis\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m:\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    245\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 246\u001b[1;33m     \u001b[0mdistances\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msafe_sparse_dot\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mX\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mY\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mT\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdense_output\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mTrue\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    247\u001b[0m     \u001b[0mdistances\u001b[0m \u001b[1;33m*=\u001b[0m \u001b[1;33m-\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    248\u001b[0m     \u001b[0mdistances\u001b[0m \u001b[1;33m+=\u001b[0m \u001b[0mXX\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Continuum\\anaconda3\\envs\\cs231n\\lib\\site-packages\\sklearn\\utils\\extmath.py\u001b[0m in \u001b[0;36msafe_sparse_dot\u001b[1;34m(a, b, dense_output)\u001b[0m\n\u001b[0;32m    133\u001b[0m     \"\"\"\n\u001b[0;32m    134\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0missparse\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mor\u001b[0m \u001b[0missparse\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 135\u001b[1;33m         \u001b[0mret\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0ma\u001b[0m \u001b[1;33m*\u001b[0m \u001b[0mb\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    136\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mdense_output\u001b[0m \u001b[1;32mand\u001b[0m \u001b[0mhasattr\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mret\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"toarray\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    137\u001b[0m             \u001b[0mret\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mret\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mtoarray\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Continuum\\anaconda3\\envs\\cs231n\\lib\\site-packages\\scipy\\sparse\\base.py\u001b[0m in \u001b[0;36m__mul__\u001b[1;34m(self, other)\u001b[0m\n\u001b[0;32m    477\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mshape\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m!=\u001b[0m \u001b[0mother\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mshape\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    478\u001b[0m                 \u001b[1;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'dimension mismatch'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 479\u001b[1;33m             \u001b[1;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_mul_sparse_matrix\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mother\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    480\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    481\u001b[0m         \u001b[1;31m# If it's a list or whatever, treat it like a matrix\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Continuum\\anaconda3\\envs\\cs231n\\lib\\site-packages\\scipy\\sparse\\compressed.py\u001b[0m in \u001b[0;36m_mul_sparse_matrix\u001b[1;34m(self, other)\u001b[0m\n\u001b[0;32m    501\u001b[0m         \u001b[0mindptr\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mnp\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0masarray\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mindptr\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdtype\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0midx_dtype\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    502\u001b[0m         \u001b[0mindices\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mnp\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mempty\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnnz\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdtype\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0midx_dtype\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 503\u001b[1;33m         \u001b[0mdata\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mnp\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mempty\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnnz\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdtype\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mupcast\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdtype\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mother\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdtype\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    504\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    505\u001b[0m         \u001b[0mfn\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mgetattr\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0m_sparsetools\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;34m'_matmat_pass2'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mMemoryError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "predicted_y = neigh.predict(X)\n",
    "# split to small pieces since hitting memory error\n",
    "predicted_y = []\n",
    "starting = 0\n",
    "while i < X.shape[0]:\n",
    "    X_sample = X[i:i+10000, :]\n",
    "    predicted_y += neigh.predict()\n",
    "    \n",
    "    i += 10000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(13059,)"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_test.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(12094,)"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predicted_y_test[predicted_y_test == y_test].shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(965,)"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predicted_y_test[predicted_y_test != y_test].shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(965,)"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predicted_y_test[predicted_y_test != y_test].shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(13059, 400)"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_test.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Logistic Regression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.linear_model import LogisticRegression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "LogisticRegression(C=1.0, class_weight=None, dual=False, fit_intercept=True,\n",
       "          intercept_scaling=1, max_iter=100, multi_class='ovr', n_jobs=1,\n",
       "          penalty='l2', random_state=None, solver='liblinear', tol=0.0001,\n",
       "          verbose=0, warm_start=False)"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lr = LogisticRegression(penalty='l2', multi_class=\"ovr\")\n",
    "lr.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9783783783783784"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lr.score(X_val, y_val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Metrics of linear regression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "precision score is 0.9830358893900765\n",
      "recall_score score is 0.9933610780816489\n",
      "f1_score score is 0.9881715130606211\n"
     ]
    }
   ],
   "source": [
    "# metrics on validation set\n",
    "predicted_y_val = lr.predict(X_val)\n",
    "print(\"precision score is {}\".format(precision_score(y_val, predicted_y_val)))\n",
    "print(\"recall_score score is {}\".format(recall_score(y_val, predicted_y_val)))\n",
    "print(\"f1_score score is {}\".format(f1_score(y_val, predicted_y_val)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The results are pretty good: fast and metrics are also quite good :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "precision score is 0.9813513965546078\n",
      "recall_score score is 0.9923050904786065\n",
      "f1_score score is 0.9867978472922974\n"
     ]
    }
   ],
   "source": [
    "# metrics on test set\n",
    "predicted_y_test = lr.predict(X_test)\n",
    "print(\"precision score is {}\".format(precision_score(y_test, predicted_y_test)))\n",
    "print(\"recall_score score is {}\".format(recall_score(y_test, predicted_y_test)))\n",
    "print(\"f1_score score is {}\".format(f1_score(y_test, predicted_y_test)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(87054, 400)"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(87054, 2)"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "predicted_y = lr.predict(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add a new column to the df\n",
    "df['predicted_y'] = predicted_y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "scrolled": false
   },
   "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>content</th>\n",
       "      <th>y</th>\n",
       "      <th>predicted_y</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>此外，自本周（6月12日）起，除小米手机6等15款机型外，其余机型已暂停更新发布（含开发版/...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>骁龙835作为唯一通过Windows 10桌面平台认证的ARM处理器，高通强调，不会因为只考...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>此前的一加3T搭载的是3400mAh电池，DashCharge快充规格为5V/4A。\\r\\n...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>这是6月18日在葡萄牙中部大佩德罗冈地区拍摄的被森林大火烧毁的汽车。新华社记者张立云摄\\r\\n</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>（原标题：44岁女子跑深圳约会网友被拒，暴雨中裸身奔走……）\\r\\n@深圳交警微博称：昨日清...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>受到A股被纳入MSCI指数的利好消息刺激，A股市场从周三开始再度上演龙马行情，周四上午金...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>虽然至今夏普智能手机在市场上无法排得上号，已经完全没落，并于 2013 年退出中国市场，但是...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>沙漠雄鹰：震荡有利消化套牢筹码\\r\\n　　周四开盘上证50在银行券商大蓝筹带动下一度涨近...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>（原标题：武汉警方一下子抓了808人，还都是俊男靓女！原来他们每天偷偷摸摸干这事！）\\r\\n...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>6月21日，A股纳入MSCI指数尘埃落定，但当天被寄予厚望的券商股并未扛起反弹大旗。22...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                             content  y  predicted_y\n",
       "0  此外，自本周（6月12日）起，除小米手机6等15款机型外，其余机型已暂停更新发布（含开发版/...  0            0\n",
       "1  骁龙835作为唯一通过Windows 10桌面平台认证的ARM处理器，高通强调，不会因为只考...  0            0\n",
       "2  此前的一加3T搭载的是3400mAh电池，DashCharge快充规格为5V/4A。\\r\\n...  0            0\n",
       "3    这是6月18日在葡萄牙中部大佩德罗冈地区拍摄的被森林大火烧毁的汽车。新华社记者张立云摄\\r\\n  1            1\n",
       "4  （原标题：44岁女子跑深圳约会网友被拒，暴雨中裸身奔走……）\\r\\n@深圳交警微博称：昨日清...  0            0\n",
       "5  　　受到A股被纳入MSCI指数的利好消息刺激，A股市场从周三开始再度上演龙马行情，周四上午金...  0            0\n",
       "6  虽然至今夏普智能手机在市场上无法排得上号，已经完全没落，并于 2013 年退出中国市场，但是...  0            0\n",
       "7  　　沙漠雄鹰：震荡有利消化套牢筹码\\r\\n　　周四开盘上证50在银行券商大蓝筹带动下一度涨近...  0            0\n",
       "8  （原标题：武汉警方一下子抓了808人，还都是俊男靓女！原来他们每天偷偷摸摸干这事！）\\r\\n...  0            0\n",
       "9  　　6月21日，A股纳入MSCI指数尘埃落定，但当天被寄予厚望的券商股并未扛起反弹大旗。22...  0            0"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.head(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "suspicious_news = df[ (df['y'] == 0) & (df['predicted_y'] == 1) ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "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>content</th>\n",
       "      <th>y</th>\n",
       "      <th>predicted_y</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>九成以上的源包用逐位对应的方式构建，未来版本的 Debian 还将提供验证包的工具和元数据；...</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>20</th>\n",
       "      <td>原标题：叙利亚被“袭机”事件惹怒俄罗斯 警告将瞄准美战机\\r\\n　　海外网6月19日电 ...</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>36</th>\n",
       "      <td>这名黑客今年25岁，两年前因为一次联合调查被英国警方抓捕。\\r\\nSean Caffrey在...</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>37</th>\n",
       "      <td>切尔西球星法布雷加斯正与女友达涅拉-塞曼享受假期，在个人的INSTAGRAM上，小法发布...</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>51</th>\n",
       "      <td>戈壁的大漠黄沙曾掩埋了无数西域古道，而如今一条大漠天路正顽强地与黄沙“搏斗”，在乌兰布和、腾...</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                              content  y  predicted_y\n",
       "16  九成以上的源包用逐位对应的方式构建，未来版本的 Debian 还将提供验证包的工具和元数据；...  0            1\n",
       "20  　　原标题：叙利亚被“袭机”事件惹怒俄罗斯 警告将瞄准美战机\\r\\n　　海外网6月19日电 ...  0            1\n",
       "36  这名黑客今年25岁，两年前因为一次联合调查被英国警方抓捕。\\r\\nSean Caffrey在...  0            1\n",
       "37  　　切尔西球星法布雷加斯正与女友达涅拉-塞曼享受假期，在个人的INSTAGRAM上，小法发布...  0            1\n",
       "51  戈壁的大漠黄沙曾掩埋了无数西域古道，而如今一条大漠天路正顽强地与黄沙“搏斗”，在乌兰布和、腾...  0            1"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "suspicious_news.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step10： 总结该过程，什么是数据思维？什么是机器学习思维？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### (Optional)使用第4课讲解的 edit distance，在涉嫌抄袭的文章中，找到其重复的文字与被修改过的文字。 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16    九成以上的源包用逐位对应的方式构建，未来版本的 Debian 还将提供验证包的工具和元数据；...\n",
       "20    　　原标题：叙利亚被“袭机”事件惹怒俄罗斯 警告将瞄准美战机\\r\\n　　海外网6月19日电 ...\n",
       "36    这名黑客今年25岁，两年前因为一次联合调查被英国警方抓捕。\\r\\nSean Caffrey在...\n",
       "37    　　切尔西球星法布雷加斯正与女友达涅拉-塞曼享受假期，在个人的INSTAGRAM上，小法发布...\n",
       "51    戈壁的大漠黄沙曾掩埋了无数西域古道，而如今一条大漠天路正顽强地与黄沙“搏斗”，在乌兰布和、腾...\n",
       "Name: content, dtype: object"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "candidate = suspicious_news['content']\n",
    "candidate.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Int64Index([   16,    20,    36,    37,    51,    56,    61,    63,    70,\n",
       "               94,\n",
       "            ...\n",
       "            10843, 10935, 10948, 10952, 10954, 10958, 10965, 10970, 10974,\n",
       "            10978],\n",
       "           dtype='int64', length=1371)"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "candidate.index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "这名黑客今年25岁，两年前因为一次联合调查被英国警方抓捕。\r\n",
      "Sean Caffrey在2014年6月发动了这场攻击，当时他还匿名发布了控制数据库的页面截图，并配文称“我们在你们数据库里哦，我们控制了你们的卫星”。\r\n",
      "但是，在英国国家犯罪局介入针对攻击的调查，并追溯到相关网络连接的9个月后，Sean Caffrey 被逮捕。\r\n",
      "英国国家犯罪局在他的硬盘上发现了被盗窃的数据，还发现了一个已打开的与攻击有关的在线消息帐户，并以化名在 Caffrey 的电脑运行。\r\n",
      "与此同时，政府却坚称，没有分类数据被盗，但是五角大楼却预估，它们因为此次攻击，需要花费50万英镑进行修复。Caffrey于本周四在伯明翰法院承认了一项指控：“计算机滥用法”规定的罪行。\r\n",
      "\n"
     ]
    }
   ],
   "source": [
    "## take the first candidate as one example\n",
    "candidate = suspicious_news['content'].iloc[2]\n",
    "print(candidate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "candidate = \"\".join(re.findall(\"\\w+\", candidate))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Original version of edit distance: recursive function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = {}\n",
    "def edit_distance(str1, str2):\n",
    "    if len(str1) == 0:\n",
    "        if str2:\n",
    "            operation = 'ADD {}'.format(str2[-1])\n",
    "            solution[(str1, str2)] = operation\n",
    "        else:\n",
    "            solution[(str1, str2)] = ''\n",
    "        return len(str2)\n",
    "    \n",
    "    if len(str2) == 0:\n",
    "        if str1:\n",
    "            operation = \"DEL {}\".format(str1[-1])\n",
    "            solution[(str1, str2)] = operation\n",
    "        else:\n",
    "            solution[(str1, str2)] = ''\n",
    "        return len(str1)\n",
    "    \n",
    "    if str1[-1] == str2[-1]:\n",
    "        operation = ''  # operation is empty\n",
    "        solution[(str1, str2)] = operation\n",
    "        return edit_distance(str1[:-1], str2[:-1])\n",
    "    else:\n",
    "        distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n",
    "                                  (edit_distance(str1[:-1], str2) + 1, \"DEL {}\".format(str1[-1])), \n",
    "                                  (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n",
    "                                  key=lambda x: x[0]\n",
    "                                 )\n",
    "        solution[(str1, str2)] = operation\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m-----------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m               Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-23-21cb7dc8b824>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"acdacdacdacdacdacd\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"abcdabcdabcdabcdabcdabcd\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     20\u001b[0m         \u001b[0moperation\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m''\u001b[0m  \u001b[1;31m# operation is empty\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     21\u001b[0m         \u001b[0msolution\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0moperation\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 22\u001b[1;33m         \u001b[1;32mreturn\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     20\u001b[0m         \u001b[0moperation\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m''\u001b[0m  \u001b[1;31m# operation is empty\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     21\u001b[0m         \u001b[0msolution\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0moperation\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 22\u001b[1;33m         \u001b[1;32mreturn\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     22\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 24\u001b[1;33m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0m\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     22\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 24\u001b[1;33m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0m\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     22\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 24\u001b[1;33m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0m\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     22\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 24\u001b[1;33m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0m\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     22\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 24\u001b[1;33m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0m\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 26\u001b[1;33m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0m\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     28\u001b[0m                                  )\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 26\u001b[1;33m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0m\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     28\u001b[0m                                  )\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     20\u001b[0m         \u001b[0moperation\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m''\u001b[0m  \u001b[1;31m# operation is empty\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     21\u001b[0m         \u001b[0msolution\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0moperation\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 22\u001b[1;33m         \u001b[1;32mreturn\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[1;32m---> 25\u001b[1;33m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     22\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 24\u001b[1;33m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0m\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 26\u001b[1;33m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0m\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     28\u001b[0m                                  )\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[1;32m---> 25\u001b[1;33m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     22\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 24\u001b[1;33m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0m\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 26\u001b[1;33m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0m\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     28\u001b[0m                                  )\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 26\u001b[1;33m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0m\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     28\u001b[0m                                  )\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[1;32m---> 25\u001b[1;33m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     22\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 24\u001b[1;33m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0m\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 26\u001b[1;33m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0m\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     28\u001b[0m                                  )\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 26\u001b[1;33m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0m\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     28\u001b[0m                                  )\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[1;32m---> 25\u001b[1;33m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 26\u001b[1;33m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0m\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     28\u001b[0m                                  )\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[1;32m---> 25\u001b[1;33m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[0;32m     25\u001b[0m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 26\u001b[1;33m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0m\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     28\u001b[0m                                  )\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[1;32m---> 25\u001b[1;33m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m     23\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         distance, operation = min([(edit_distance(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n\u001b[1;32m---> 25\u001b[1;33m                                   \u001b[1;33m(\u001b[0m\u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"DEL {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     26\u001b[0m                                   (edit_distance(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))], \n\u001b[0;32m     27\u001b[0m                                   \u001b[0mkey\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-7-5602ea14531d>\u001b[0m in \u001b[0;36medit_distance\u001b[1;34m(str1, str2)\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[0msolution\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m{\u001b[0m\u001b[1;33m}\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[1;32mdef\u001b[0m \u001b[0medit_distance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr1\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mstr2\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m             \u001b[0moperation\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m'ADD {}'\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mstr2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "edit_distance(\"acdacdacdacdacdacd\", \"abcdabcdabcdabcdabcdabcd\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [],
   "source": [
    "def timer(func):\n",
    "    \n",
    "    def wrapper(str1, str2):\n",
    "        start_time = time.time()\n",
    "        result = func(str1, str2)\n",
    "        end_time = time.time()\n",
    "        print(\"Elapse time: {}\".format(end_time-start_time))\n",
    "        return result\n",
    "    \n",
    "    return wrapper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "def your_sleep():\n",
    "    time.sleep(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [],
   "source": [
    "your_sleep = timer(your_sleep)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elapse time: 5.001163959503174\n"
     ]
    }
   ],
   "source": [
    "your_sleep()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### solution_1: use one dict to store the temporary distances (still recursive)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = {}\n",
    "\n",
    "distance_cache = {}\n",
    "\n",
    "\n",
    "def edit_distance_1(str1, str2):\n",
    "    if (str1, str2) in distance_cache:\n",
    "        return distance_cache[(str1, str2)]\n",
    "\n",
    "    if (str2, str1) in distance_cache:\n",
    "        return distance_cache[(str2, str1)]\n",
    "\n",
    "    if len(str1) == 0:\n",
    "        if str2:\n",
    "            operation = 'ADD {}'.format(str2[-1])\n",
    "            solution[(str1, str2)] = operation\n",
    "        else:\n",
    "            solution[(str1, str2)] = ''\n",
    "\n",
    "        distance = len(str2)\n",
    "        distance_cache[(str1, str2)] = distance\n",
    "        return distance\n",
    "\n",
    "    if len(str2) == 0:\n",
    "        if str1:\n",
    "            operation = \"DEL {}\".format(str1[-1])\n",
    "            solution[(str1, str2)] = operation\n",
    "        else:\n",
    "            solution[(str1, str2)] = ''\n",
    "\n",
    "        distance = len(str1)\n",
    "        distance_cache[(str1, str2)] = distance\n",
    "        return distance\n",
    "\n",
    "    if str1[-1] == str2[-1]:\n",
    "        operation = ''  # operation is empty\n",
    "        solution[(str1, str2)] = operation\n",
    "        distance = edit_distance_1(str1[:-1], str2[:-1])\n",
    "        distance_cache[(str1, str2)] = distance\n",
    "        return distance\n",
    "    else:\n",
    "        distance, operation = min([(edit_distance_1(str1[:-1], str2[:-1]) + 1, 'SUB {}=>{}'.format(str1[-1], str2[-1])),\n",
    "                                   (edit_distance_1(str1[:-1], str2) + 1, \"DEL {}\".format(str1[-1])),\n",
    "                                   (edit_distance_1(str1, str2[:-1]) + 1, \"ADD {}\".format(str2[-1]))],\n",
    "                                  key=lambda x: x[0]\n",
    "                                  )\n",
    "        solution[(str1, str2)] = operation\n",
    "        distance_cache[(str1, str2)] = distance\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elapse time: 0.0029921531677246094\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6.0"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edit_distance_2(\"acdacdacdacdacdacd\", \"abcdabcdabcdabcdabcdabcd\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### solution_2: use one array to store the temporary distances"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "def edit_distance_2(str1, str2):\n",
    "    # str1 -> str2\n",
    "    m = len(str1)\n",
    "    n = len(str2)\n",
    "\n",
    "    # create a matrix to save all the temporary solutions\n",
    "    import numpy as np\n",
    "    dp = np.zeros((n + 1, m + 1))\n",
    "\n",
    "    # build the array/matrix from bottom up\n",
    "    for i in range(n + 1):\n",
    "        for j in range(m + 1):\n",
    "            if i == 0:\n",
    "                dp[i][j] = j\n",
    "\n",
    "            elif j == 0:\n",
    "                dp[i][j] = i\n",
    "\n",
    "            elif str1[j-1] == str2[i-1]:\n",
    "                dp[i][j] = dp[i - 1][j - 1]\n",
    "\n",
    "            elif str1[j-1] != str2[i-1]:\n",
    "                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1], dp[i - 1][j]) + 1\n",
    "\n",
    "    return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'这名黑客今年25岁两年前因为一次联合调查被英国警方抓捕SeanCaffrey在2014年6月发动了这场攻击当时他还匿名发布了控制数据库的页面截图并配文称我们在你们数据库里哦我们控制了你们的卫星但是在英国国家犯罪局介入针对攻击的调查并追溯到相关网络连接的9个月后SeanCaffrey被逮捕英国国家犯罪局在他的硬盘上发现了被盗窃的数据还发现了一个已打开的与攻击有关的在线消息帐户并以化名在Caffrey的电脑运行与此同时政府却坚称没有分类数据被盗但是五角大楼却预估它们因为此次攻击需要花费50万英镑进行修复Caffrey于本周四在伯明翰法院承认了一项指控计算机滥用法规定的罪行'"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "277"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edit_distance_1(candidate, df['content'][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'此外，自本周（6月12日）起，除小米手机6等15款机型外，其余机型已暂停更新发布（含开发版/体验版内测，稳定版暂不受影响），以确保工程师可以集中全部精力进行系统优化工作。有人猜测这也是将精力主要用到MIUI 9的研发之中。\\r\\nMIUI 8去年5月发布，距今已有一年有余，也是时候更新换代了。\\r\\n当然，关于MIUI 9的确切信息，我们还是等待官方消息。\\r\\n'"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df['content'][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {
    "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>content</th>\n",
       "      <th>y</th>\n",
       "      <th>predicted_y</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>此外，自本周（6月12日）起，除小米手机6等15款机型外，其余机型已暂停更新发布（含开发版/...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>骁龙835作为唯一通过Windows 10桌面平台认证的ARM处理器，高通强调，不会因为只考...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>此前的一加3T搭载的是3400mAh电池，DashCharge快充规格为5V/4A。\\r\\n...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>这是6月18日在葡萄牙中部大佩德罗冈地区拍摄的被森林大火烧毁的汽车。新华社记者张立云摄\\r\\n</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>（原标题：44岁女子跑深圳约会网友被拒，暴雨中裸身奔走……）\\r\\n@深圳交警微博称：昨日清...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                             content  y  predicted_y\n",
       "0  此外，自本周（6月12日）起，除小米手机6等15款机型外，其余机型已暂停更新发布（含开发版/...  0            0\n",
       "1  骁龙835作为唯一通过Windows 10桌面平台认证的ARM处理器，高通强调，不会因为只考...  0            0\n",
       "2  此前的一加3T搭载的是3400mAh电池，DashCharge快充规格为5V/4A。\\r\\n...  0            0\n",
       "3    这是6月18日在葡萄牙中部大佩德罗冈地区拍摄的被森林大火烧毁的汽车。新华社记者张立云摄\\r\\n  1            1\n",
       "4  （原标题：44岁女子跑深圳约会网友被拒，暴雨中裸身奔走……）\\r\\n@深圳交警微博称：昨日清...  0            0"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'这名黑客今年25岁两年前因为一次联合调查被英国警方抓捕SeanCaffrey在2014年6月发动了这场攻击当时他还匿名发布了控制数据库的页面截图并配文称我们在你们数据库里哦我们控制了你们的卫星但是在英国国家犯罪局介入针对攻击的调查并追溯到相关网络连接的9个月后SeanCaffrey被逮捕英国国家犯罪局在他的硬盘上发现了被盗窃的数据还发现了一个已打开的与攻击有关的在线消息帐户并以化名在Caffrey的电脑运行与此同时政府却坚称没有分类数据被盗但是五角大楼却预估它们因为此次攻击需要花费50万英镑进行修复Caffrey于本周四在伯明翰法院承认了一项指控计算机滥用法规定的罪行'"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "content        这名黑客今年25岁，两年前因为一次联合调查被英国警方抓捕。\\r\\nSean Caffrey在...\n",
       "y                                                              0\n",
       "predicted_y                                                    1\n",
       "Name: 36, dtype: object"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.loc[36]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "287"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(candidate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_news = df['content'].tolist()\n",
    "all_clear_news = []\n",
    "\n",
    "for news in all_news:\n",
    "    news = ''.join(re.findall('\\w+', news))\n",
    "    all_clear_news.append(news)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(all_clear_news)\n",
    "\n",
    "all_clear_news = sorted(all_clear_news, key=lambda x: len(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {},
   "outputs": [],
   "source": [
    "suspicious_news = suspicious_news['content'].tolist()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {},
   "outputs": [],
   "source": [
    "suspicious_news = sorted(suspicious_news, key=lambda x: len(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 216,
   "metadata": {},
   "outputs": [],
   "source": [
    "candidate = \"\".join(re.findall(\"\\w+\",suspicious_news[45]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 217,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'几辆花车在巡游中俄罗斯少年参加花车巡游活动6月22日第八届中俄文化大集在黑龙江省黑河市开幕2000余名中俄两国民众参加花车巡游活动新华社发'"
      ]
     },
     "execution_count": 217,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "86"
      ]
     },
     "execution_count": 197,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(all_clear_news[10000])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "287"
      ]
     },
     "execution_count": 187,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(candidate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_copy_news():\n",
    "    min_distance = float('inf')\n",
    "    copy_news = ''\n",
    "    candidate_len = len(candidate)\n",
    "    \n",
    "    for idx, news in enumerate(all_clear_news[:20000]):\n",
    "        if news == candidate: continue # origianl news\n",
    "        if len(news) > 3 * candidate_len:\n",
    "            break # too long news, could not be copy news\n",
    "        \n",
    "        distance = edit_distance_2(candidate, news)\n",
    "        \n",
    "        if distance < min_distance:\n",
    "            min_distance = distance\n",
    "            copy_news = news\n",
    "        \n",
    "        if idx %100 == 0:\n",
    "            print(idx)\n",
    "            \n",
    "    return min_distance, copy_news"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "100\n",
      "200\n",
      "300\n",
      "400\n",
      "500\n",
      "600\n",
      "700\n",
      "800\n",
      "900\n",
      "1000\n",
      "1100\n",
      "1200\n",
      "1300\n",
      "1400\n",
      "1500\n",
      "1600\n",
      "1700\n",
      "1800\n",
      "1900\n",
      "2000\n",
      "2100\n",
      "2200\n",
      "2300\n",
      "2400\n",
      "2500\n",
      "2600\n",
      "2700\n",
      "2800\n",
      "2900\n",
      "3000\n",
      "3100\n",
      "3200\n",
      "3300\n",
      "3400\n",
      "3500\n",
      "3600\n",
      "3700\n",
      "3800\n",
      "3900\n",
      "4000\n",
      "4100\n",
      "4200\n",
      "4300\n",
      "4400\n",
      "4500\n",
      "4600\n",
      "4700\n",
      "4800\n",
      "4900\n",
      "5000\n",
      "5100\n",
      "5200\n",
      "5300\n",
      "5400\n",
      "5500\n",
      "5600\n",
      "5700\n",
      "5800\n",
      "5900\n",
      "6000\n",
      "6100\n",
      "6200\n",
      "6300\n",
      "6400\n",
      "6500\n",
      "6600\n",
      "6700\n",
      "6800\n",
      "6900\n",
      "7000\n",
      "7100\n",
      "7200\n",
      "7300\n",
      "7400\n",
      "7500\n",
      "7600\n",
      "7700\n",
      "7800\n",
      "7900\n",
      "8000\n",
      "8100\n",
      "8200\n",
      "8300\n",
      "8400\n",
      "8500\n",
      "8600\n",
      "8700\n",
      "8800\n",
      "8900\n",
      "9000\n",
      "9100\n",
      "9200\n",
      "9300\n",
      "9400\n",
      "9500\n",
      "9600\n",
      "9700\n",
      "9800\n",
      "9900\n",
      "10000\n",
      "10100\n",
      "10200\n",
      "10300\n",
      "10400\n",
      "10500\n",
      "10600\n",
      "10700\n",
      "10800\n",
      "10900\n",
      "11000\n",
      "11100\n",
      "11200\n",
      "11300\n",
      "11400\n",
      "11500\n",
      "11600\n",
      "11700\n",
      "11800\n",
      "11900\n",
      "12000\n",
      "12100\n",
      "12200\n",
      "12300\n",
      "12400\n",
      "12500\n",
      "12600\n",
      "12700\n",
      "12800\n",
      "12900\n",
      "13000\n",
      "13100\n",
      "13200\n",
      "13300\n",
      "13400\n",
      "13500\n",
      "13600\n",
      "13700\n",
      "13800\n",
      "13900\n",
      "14000\n",
      "14100\n",
      "14200\n",
      "14300\n",
      "14400\n",
      "14500\n",
      "14600\n",
      "14700\n",
      "14800\n",
      "14900\n",
      "15000\n",
      "15100\n",
      "15200\n",
      "15300\n",
      "15400\n",
      "15500\n",
      "15600\n",
      "15700\n",
      "15800\n",
      "15900\n",
      "16000\n",
      "16100\n",
      "16200\n",
      "16300\n",
      "16400\n",
      "16500\n",
      "16600\n",
      "16700\n",
      "16800\n",
      "16900\n",
      "17000\n",
      "17100\n",
      "17200\n",
      "17300\n",
      "17400\n",
      "17500\n",
      "17600\n",
      "17700\n",
      "17800\n",
      "17900\n",
      "18000\n",
      "18100\n",
      "18200\n",
      "18300\n",
      "18400\n",
      "18500\n",
      "18600\n",
      "18700\n",
      "18800\n",
      "18900\n",
      "19000\n",
      "19100\n",
      "19200\n",
      "19300\n",
      "19400\n",
      "19500\n",
      "19600\n",
      "19700\n",
      "19800\n",
      "19900\n"
     ]
    }
   ],
   "source": [
    "distance, copy_news = find_copy_news()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'几辆花车在巡游中俄罗斯少年参加花车巡游活动6月22日第八届中俄文化大集在黑龙江省黑河市开幕2000余名中俄两国民众参加花车巡游活动新华社发'"
      ]
     },
     "execution_count": 223,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'新华社照片北京2017年5月11日n布赫同志生平照片n2007年布赫同志与蒙古族少年在一起n新华社发'"
      ]
     },
     "execution_count": 224,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "copy_news"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:cs231n]",
   "language": "python",
   "name": "conda-env-cs231n-py"
  },
  "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}