{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Edit distance, every cell\n",
    "\n",
    "The three tables and the backtrace for cat to cart, with the recurrence spelled out rather than optimised.\n",
    "\n",
    "From chapter 2, [Corpora and Preprocessing](https://nlp.jcrlabz.com/book/corpora/), of the course notes.\n",
    "\n",
    "Source: `book/code/worked_examples/edit_distance.py`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What you need\n",
    "\n",
    "Nothing. This example uses only the Python standard library."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Nothing to install: this example uses only the Python standard library.\n",
    "import sys; print(sys.version.split()[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The script\n",
    "\n",
    "Everything the example defines, in one cell. Run it and the definitions\n",
    "are live in the notebook."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "\"\"\"Minimum edit distance, worked out the way Chapter 2 works it out.\n",
    "\n",
    "Run this and you get the same three tables and the same trace the book prints\n",
    "for `cat` to `cart`. Change the two words at the bottom and it works them out\n",
    "for yours.\n",
    "\n",
    "    python3 edit_distance.py                  # cat -> cart, as in the book\n",
    "    python3 edit_distance.py sunday saturday  # the chapter's exercise\n",
    "    python3 edit_distance.py cat cut --sub 2  # see the penalties bite\n",
    "\n",
    "The code is written to be read, not to be fast. Every step of the recurrence\n",
    "is spelled out.\n",
    "\n",
    "Install:  nothing, the Python standard library is enough\n",
    "\"\"\"\n",
    "\n",
    "import argparse\n",
    "\n",
    "\n",
    "def costs(sub_cost=1, ins_cost=1, del_cost=1):\n",
    "    \"\"\"The penalties. Levenshtein uses 1, 1, and 0-or-1 for a substitution.\n",
    "\n",
    "    Jurafsky and Martin often use sub_cost=2, reasoning that a substitution is\n",
    "    really a deletion plus an insertion. Try both and watch the answer move.\n",
    "    \"\"\"\n",
    "    def sub(a, b):\n",
    "        return 0 if a == b else sub_cost      # a match is free\n",
    "    return sub, (lambda b: ins_cost), (lambda a: del_cost)\n",
    "\n",
    "\n",
    "def build_table(s, t, sub_cost=1, ins_cost=1, del_cost=1):\n",
    "    \"\"\"Return the full (len(s)+1) x (len(t)+1) table of distances.\"\"\"\n",
    "    sub, ins, dele = costs(sub_cost, ins_cost, del_cost)\n",
    "    D = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]\n",
    "\n",
    "    # Base cases: turning a prefix into the empty string costs one edit per\n",
    "    # character, and the other way round costs one insertion per character.\n",
    "    for i in range(len(s) + 1):\n",
    "        D[i][0] = i * del_cost\n",
    "    for j in range(len(t) + 1):\n",
    "        D[0][j] = j * ins_cost\n",
    "\n",
    "    for i in range(1, len(s) + 1):\n",
    "        for j in range(1, len(t) + 1):\n",
    "            delete = D[i - 1][j] + dele(s[i - 1])\n",
    "            insert = D[i][j - 1] + ins(t[j - 1])\n",
    "            match = D[i - 1][j - 1] + sub(s[i - 1], t[j - 1])\n",
    "            D[i][j] = min(delete, insert, match)\n",
    "    return D\n",
    "\n",
    "\n",
    "def trace_back(D, s, t, sub_cost=1, ins_cost=1, del_cost=1):\n",
    "    \"\"\"Walk from the answer cell to the origin, recovering the edits.\n",
    "\n",
    "    At each cell we ask which of the three neighbours actually produced this\n",
    "    value. Diagonal is preferred, so a match is reported as a match rather\n",
    "    than as a delete plus an insert that happens to cost the same.\n",
    "    \"\"\"\n",
    "    sub, ins, dele = costs(sub_cost, ins_cost, del_cost)\n",
    "    i, j = len(s), len(t)\n",
    "    path, steps = [(i, j)], []\n",
    "    while i > 0 or j > 0:\n",
    "        if i > 0 and j > 0 and D[i][j] == D[i-1][j-1] + sub(s[i-1], t[j-1]):\n",
    "            op = \"match\" if s[i-1] == t[j-1] else f\"substitute {s[i-1]}->{t[j-1]}\"\n",
    "            frm, i, j = (i-1, j-1), i-1, j-1\n",
    "        elif j > 0 and D[i][j] == D[i][j-1] + ins(t[j-1]):\n",
    "            op, frm, j = f\"insert {t[j-1]}\", (i, j-1), j - 1\n",
    "        else:\n",
    "            op, frm, i = f\"delete {s[i-1]}\", (i-1, j), i - 1\n",
    "        steps.append((path[-1], frm, op))\n",
    "        path.append(frm)\n",
    "    return list(reversed(path)), list(reversed(steps))\n",
    "\n",
    "\n",
    "def show(D, s, t, rows=None, cols=None, path=None, box=False):\n",
    "    \"\"\"Print the table, optionally only the top-left corner, path cells starred.\"\"\"\n",
    "    rows = len(s) + 1 if rows is None else rows\n",
    "    cols = len(t) + 1 if cols is None else cols\n",
    "    path = set(path or [])\n",
    "    head = \"    \" + \"\".join(f\"{c:>5}\" for c in [\"#\"] + list(t)[:cols - 1])\n",
    "    print(head)\n",
    "    print(\"    \" + \"-\" * (5 * cols))\n",
    "    for i in range(rows):\n",
    "        label = \"#\" if i == 0 else s[i - 1]\n",
    "        line = f\"{label:>3} |\"\n",
    "        for j in range(cols):\n",
    "            cell = str(D[i][j])\n",
    "            if box and (i, j) == (len(s), len(t)):\n",
    "                cell = f\"[{cell}]\"                 # the answer\n",
    "            elif (i, j) in path:\n",
    "                cell = f\"*{cell}\"                  # on the cheapest path\n",
    "            line += f\"{cell:>5}\"\n",
    "        print(line)\n",
    "\n",
    "\n",
    "def main():\n",
    "    ap = argparse.ArgumentParser(description=__doc__)\n",
    "    ap.add_argument(\"source\", nargs=\"?\", default=\"cat\")\n",
    "    ap.add_argument(\"target\", nargs=\"?\", default=\"cart\")\n",
    "    ap.add_argument(\"--sub\", type=int, default=1, help=\"substitution penalty\")\n",
    "    ap.add_argument(\"--ins\", type=int, default=1, help=\"insertion penalty\")\n",
    "    ap.add_argument(\"--del\", dest=\"dele\", type=int, default=1,\n",
    "                    help=\"deletion penalty\")\n",
    "    a = ap.parse_args()\n",
    "    s, t = a.source, a.target\n",
    "\n",
    "    print(f\"\\n{s!r} -> {t!r}   penalties: sub={a.sub} ins={a.ins} del={a.dele}\")\n",
    "    D = build_table(s, t, a.sub, a.ins, a.dele)\n",
    "\n",
    "    print(\"\\nSTEP 1: the first four cells\")\n",
    "    print(\"  base cases fill the top row and the left column;\")\n",
    "    print(f\"  D[1,1] compares {s[0]!r} with {t[0]!r}:\")\n",
    "    print(f\"    delete -> D[0,1] + {a.dele} = {D[0][1] + a.dele}\")\n",
    "    print(f\"    insert -> D[1,0] + {a.ins} = {D[1][0] + a.ins}\")\n",
    "    same = s[0] == t[0]\n",
    "    print(f\"    {'match' if same else 'substitute'}  -> D[0,0] + \"\n",
    "          f\"{0 if same else a.sub} = {0 if same else a.sub}\")\n",
    "    print()\n",
    "    show(D, s, t, rows=2, cols=2)\n",
    "\n",
    "    print(\"\\nSTEP 2: the first pass\")\n",
    "    show(D, s, t, rows=2)\n",
    "\n",
    "    print(\"\\nSTEP 3: the finished table (* = on the cheapest path, [] = answer)\")\n",
    "    path, steps = trace_back(D, s, t, a.sub, a.ins, a.dele)\n",
    "    show(D, s, t, path=path, box=True)\n",
    "\n",
    "    print(f\"\\nEDIT DISTANCE = {D[len(s)][len(t)]}\\n\")\n",
    "    print(\"THE TRACE (read downwards to replay the edits):\")\n",
    "    print(f\"  {'cell':<10}{'from':<10}{'operation'}\")\n",
    "    for (ci, cj), (fi, fj), op in steps:\n",
    "        print(f\"  D[{ci},{cj}]{'':<4}D[{fi},{fj}]{'':<4}{op}\")\n",
    "    kept = [op for _, _, op in steps if op != \"match\"]\n",
    "    print(f\"\\n  {len(kept)} non-free edit(s): {', '.join(kept) or 'none'}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Running it\n",
    "\n",
    "The script is a command line tool, so each run below sets the arguments\n",
    "and calls `main()`. The heading shows the equivalent shell command."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "def run(*args):\n",
    "    sys.argv = [\"edit_distance.py\", *args]\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `python3 edit_distance.py`\n",
    "\n",
    "The chapter's tables, then the path that produced the answer."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `python3 edit_distance.py kitten sitting`\n",
    "\n",
    "Any pair of words works. This one costs 3."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "run(\"kitten\", \"sitting\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `python3 edit_distance.py kitten sitting --sub 2`\n",
    "\n",
    "Charge 2 for a substitution and the same pair costs 5, because the cheapest path is now a different path."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "run(\"kitten\", \"sitting\", \"--sub\", \"2\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "Read the chapter this comes from: [Corpora and Preprocessing](https://nlp.jcrlabz.com/book/corpora/)."
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "edit_distance.ipynb",
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}