edit-distance.ipynb

{
 "metadata": {
  "name": "edit-distance"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# \u7f16\u8f91\u8ddd\u79bb\n",
      "\n",
      "\u6765\u81ea[\u7ef4\u57fa\u767e\u79d1](https://zh.wikipedia.org/wiki/%E7%B7%A8%E8%BC%AF%E8%B7%9D%E9%9B%A2):\n",
      "\n",
      "> \u7f16\u8f91\u8ddd\u79bb\uff0c\u53c8\u79f0Levenshtein\u8ddd\u79bb\uff0c\u662f\u6307\u4e24\u4e2a\u5b57\u4e32\u4e4b\u95f4\uff0c\u7531\u4e00\u4e2a\u8f6c\u6210\u53e6\u4e00\u4e2a\u6240\u9700\u7684\u6700\u5c11\u7f16\u8f91\u64cd\u4f5c\u6b21\u6570\u3002\u8bb8\u53ef\u7684\u7f16\u8f91\u64cd\u4f5c\u5305\u62ec\u5c06\u4e00\u4e2a\u5b57\u7b26\u66ff\u6362\u6210\u53e6\u4e00\u4e2a\u5b57\u7b26\uff0c\u63d2\u5165\u4e00\u4e2a\u5b57\u7b26\uff0c\u5220\u9664\u4e00\u4e2a\u5b57\u7b26\u3002\n",
      "\n",
      "\u4e00\u4e2a\u5177\u4f53\u5e94\u7528: [lit](https://github.com/Answeror/lit).\n",
      "\n",
      "## \u7b80\u5355\u5b9e\u73b0"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def dis(s, t):\n",
      "    if not s:\n",
      "        return len(t)\n",
      "    if not t:\n",
      "        return len(s)\n",
      "    if s[0] == t[0]:\n",
      "        return dis(s[1:], t[1:])\n",
      "    return 1 + min(\n",
      "        dis(s, t[1:]),\n",
      "        dis(s[1:], t),\n",
      "        dis(s[1:], t[1:])\n",
      "    )\n",
      "\n",
      "dis('foo', 'fobar')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "3"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "\u4e0b\u9762\u6211\u4eec\u751f\u6210\u4e00\u4e9b\u968f\u673a\u5b57\u7b26\u4e32, \u7528\u6765\u6d4b\u8bd5\u7b97\u6cd5\u6548\u7387:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import random\n",
      "import string\n",
      "\n",
      "''.join(random.choice(string.digits) for x in range(5))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "'41996'"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def randstr(n):\n",
      "    return ''.join(random.choice(string.digits) for x in range(n))\n",
      "\n",
      "lhs = randstr(11)\n",
      "rhs = randstr(11)\n",
      "\n",
      "import time\n",
      "\n",
      "start = time.clock()\n",
      "dis(lhs, rhs)\n",
      "print time.clock() - start"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "6.30167549872\n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# memo\n",
      "\n",
      "\u770b\u770b`dis`\u88ab\u540c\u6837\u7684\u53c2\u6570\u8c03\u7528\u4e86\u591a\u5c11\u6b21:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "count = {}\n",
      "\n",
      "def dis(s, t):\n",
      "    count[(s, t)] = count.get((s, t), 0) + 1\n",
      "    if not s:\n",
      "        return len(t)\n",
      "    if not t:\n",
      "        return len(s)\n",
      "    if s[0] == t[0]:\n",
      "        return dis(s[1:], t[1:])\n",
      "    return 1 + min(\n",
      "        dis(s, t[1:]),\n",
      "        dis(s[1:], t),\n",
      "        dis(s[1:], t[1:])\n",
      "    )\n",
      "    \n",
      "dis(lhs, rhs)\n",
      "print max(count.values())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2751263\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "\u62d2\u7edd\u91cd\u590d\u8ba1\u7b97!"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "memo = {}\n",
      "\n",
      "def dis(s, t):\n",
      "    if (s, t) not in memo:\n",
      "        def inner():\n",
      "            if not s:\n",
      "                return len(t)\n",
      "            if not t:\n",
      "                return len(s)\n",
      "            if s[0] == t[0]:\n",
      "                return dis(s[1:], t[1:])\n",
      "            return 1 + min(\n",
      "                dis(s, t[1:]),\n",
      "                dis(s[1:], t),\n",
      "                dis(s[1:], t[1:])\n",
      "            )\n",
      "        memo[(s, t)] = inner()\n",
      "    return memo[(s, t)]\n",
      "\n",
      "start = time.clock()\n",
      "dis(lhs, rhs)\n",
      "print time.clock() - start"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0.000412662940107\n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "\u505a\u4e2a\u66f4\u52a0\u901a\u7528\u7684memo:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def memoed(f):\n",
      "    memo = {}\n",
      "    def inner(*args):\n",
      "        if args not in memo:\n",
      "            memo[args] = f(*args)\n",
      "        return memo[args]\n",
      "    return inner\n",
      "\n",
      "# \u8fd9\u91ccdis\u548c\u6700\u521d\u7684dis\u5b9a\u4e49\u5b8c\u5168\u4e00\u81f4\n",
      "def dis(s, t):\n",
      "    if not s:\n",
      "        return len(t)\n",
      "    if not t:\n",
      "        return len(s)\n",
      "    if s[0] == t[0]:\n",
      "        return dis(s[1:], t[1:])\n",
      "    return 1 + min(\n",
      "        dis(s, t[1:]),\n",
      "        dis(s[1:], t),\n",
      "        dis(s[1:], t[1:])\n",
      "    )\n",
      "\n",
      "# \u505amemo, \u540c\u65f6\u53c8\u4e0d\u7528\u6539\u53d8\u539f\u6765dis\u7684\u5b9e\u73b0.\n",
      "dis = memoed(dis)\n",
      "\n",
      "start = time.clock()\n",
      "dis(lhs, rhs)\n",
      "print time.clock() - start"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0.00031414692835\n"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Python\u91cc, \u51fd\u6570\u4e5f\u662f\u4e00\u79cd\u5bf9\u8c61, \u53ef\u4ee5\u88ab\u4f20\u9012.\n",
      "\n",
      "\u4e0d\u7528\u7ea0\u7ed3\"\u5bf9\u8c61(object)\"\u662f\u4ec0\u4e48\u4e1c\u897f, \u53ef\u4ee5\u6682\u65f6\u7406\u89e3\u6210\u5185\u5b58\u91cc\u7684\u4e00\u5757\u6570\u636e. \u4e00\u4e2a\u6574\u6570\u662f\u5bf9\u8c61, \u4e00\u4e2a\u5b57\u7b26\u4e32\u4e5f\u662f\u5bf9\u8c61."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### *args\n",
      "\n",
      "\u8bf7\u8ba4\u771f\u9605\u8bfb\u4e0b\u9762\u7684\u94fe\u63a5:\n",
      "\n",
      "<http://stackoverflow.com/a/2921893/238472>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## \u88c5\u9970\u5668(decorator)\n",
      "\n",
      "\u7b80\u5355\u6765\u8bf4, \u4e00\u4e2a\u88c5\u9970\u5668\u5c31\u662f\u4e00\u4e2a\u4ee5\u51fd\u6570\u4e3a\u53c2\u6570, \u5e76\u8fd4\u56de\u51fd\u6570\u7684\u51fd\u6570.\n",
      "\n",
      "\u66f4\u52a0\u8be6\u7ec6\u7684\u5173\u4e8e\u88c5\u9970\u5668\u7684\u6559\u7a0b\u53c2\u89c1[\u8fd9\u91cc](http://stackoverflow.com/a/1594484/238472)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def memoed(f):\n",
      "    memo = {}\n",
      "    def inner(*args):\n",
      "        if args not in memo:\n",
      "            memo[args] = f(*args)\n",
      "        return memo[args]\n",
      "    return inner\n",
      "\n",
      "@memoed\n",
      "def dis(s, t):\n",
      "    if not s:\n",
      "        return len(t)\n",
      "    if not t:\n",
      "        return len(s)\n",
      "    if s[0] == t[0]:\n",
      "        return dis(s[1:], t[1:])\n",
      "    return 1 + min(\n",
      "        dis(s, t[1:]),\n",
      "        dis(s[1:], t),\n",
      "        dis(s[1:], t[1:])\n",
      "    )\n",
      "\n",
      "start = time.clock()\n",
      "dis(lhs, rhs)\n",
      "print time.clock() - start"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0.000331583390608\n"
       ]
      }
     ],
     "prompt_number": 7
    }
   ],
   "metadata": {}
  }
 ]
}