{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "abf762d1-9baa-4692-8711-063646be886b",
   "metadata": {
    "tags": [
     "remove-cell"
    ]
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05b9fdef-2838-4c2c-acc0-56402b646f82",
   "metadata": {
    "tags": [
     "hide-cell"
    ]
   },
   "outputs": [],
   "source": [
    "%pip install levenshtein"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca24fa87-1cab-4259-be91-dfe1cea53806",
   "metadata": {},
   "source": [
    "# Sequence-based similarity"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99bd69c4-150f-423d-90fb-83b2791278a8",
   "metadata": {},
   "source": [
    "Consider search engines that have indexes of text content. Entering a misspelled search term will match misspellings in the database, but modern search engines often suggest similar queries with larger number of hits in the database. How do they do it? Search engines (like elasticsearch) generate a wide range of possible misspellings of the query and present search results (or spelling suggestions) informed by queries for a comprehensive set of deletion- substitution-, insertion-, and transposition- modified words."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1dcd0313-0a9f-4b39-a54f-54a3d38a729c",
   "metadata": {},
   "source": [
    "Edit distance (also known as Levenshtein distance) is another approach at fuzzy matching, inspired by the process of changing one input into another. It is more sensitive than Jaccard similarity scoring but requires more computations (that is to say, it takes more time to run when other factors are held constant)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b23a463-bc12-480e-9209-314b5a485ab0",
   "metadata": {},
   "source": [
    "## Hamming distance"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f63a381-169f-4e1b-85a8-6c8ff8f4cd94",
   "metadata": {},
   "source": [
    "If all of the symbols of interest are the same length, say, five-letter telegraph abbreviations, it is simple to count the number of differences letter-by-letter: ENBET differs in one position from ERBET and differs in two positions from TRBET. \n",
    "\n",
    "This counting-of-differences distance metric goes by the name ''Hamming distance'', but this is suited for vocabularies of aligned codewords all the same length.  \n",
    "\n",
    "Hamming distance would make sense, for instance, comparing dates in ISO-8601 format represented as strings, like \"2020-03-15\" and \"2023-09-21\".  Differences of a single character have Hamming distance one; transpositions of digits have Hamming distance 2. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c488feb1-7123-4010-bae8-009e8dd1f609",
   "metadata": {},
   "source": [
    "## Levenshtein (edit) distance"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51433011-4cd8-48fe-94af-ab440092b425",
   "metadata": {},
   "source": [
    "If you think about the process of editing text, you can modify text by adding text, deleting text, or, if you are inclined, by both deleting and adding in about the same place. By counting the number of steps needed to transform `string1` into `string2` using these three operations, **deletion**, **insertion**, and **substitution**, we can define a number that describes how similar the two strings are.  There are algorithms that will find the minimum number of edits that will transform one string into another (similar) string and this minimum number of edits score has many uses in data munging."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "589599e5-efa2-4343-b074-dfb55e360806",
   "metadata": {},
   "source": [
    "The Levenshtein distance counts the differences between two strings by describing the minimum number of steps needed to transform one string into the other, where the permitted steps are\n",
    "1. substitution (replace a character with a different one)\n",
    "2. insertion (add a character), and\n",
    "3. deletion.\n",
    "\n",
    "This is the number of single-character edits needed to transform one string into another.\n",
    "\n",
    "\n",
    "Levenshtein distance is fairly easy to illustrate by providing an example alignment: "
   ]
  },
  {
   "cell_type": "raw",
   "id": "9b687b76-fe4d-4372-a835-f212bbf94a7c",
   "metadata": {},
   "source": [
    "\"Didn't you see her?\" \n",
    "\"Did she see where to go?\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b787f58c-6621-4a40-83d5-d2ac90bea5e2",
   "metadata": {},
   "source": [
    "The first string can be changed into the second with a three-character deletion (`n't`), a three-character substitution (`she` for `you`), and eight characters of insertions  `w` and `e to go`. "
   ]
  },
  {
   "cell_type": "raw",
   "id": "f47f2339-da10-4ec4-aacb-c6811eb131f5",
   "metadata": {},
   "source": [
    "Didn't you see *her*******?\n",
    "   DDD SSS     I   IIIIIII \n",
    "Did*** she see where to go?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84bd6d9e-6984-4a8b-963b-6663aae5cbcc",
   "metadata": {},
   "source": [
    "The edit distance between the strings is the sum of the number of changes.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5176af69-1e6d-4613-9f42-476da2966e21",
   "metadata": {},
   "source": [
    "Search engines which index text can sometimes give reasonable results when given inexact search queries, but it is not without some engineering.  Entering a misspelled search term will match misspellings in the database and will fail to find exact matches on the correct spelling.  Modern search engines often suggest similar queries with larger number of hits in the database. How do they do it? Search engines (like elasticsearch) generate a wide range of possible misspellings of the query and present search results (or spelling suggestions) informed by queries for a comprehensive set of deletion- substitution-, insertion-, and transposition- modified words.  Yes, you have to check the search index hundreds of times, but if you see a one- or two-letter different search term with hundreds of times the hits, you would do well to suggest it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fc622b97-455e-4b99-9b51-e734c7335bb4",
   "metadata": {},
   "outputs": [],
   "source": [
    "import Levenshtein"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9591eeeb-9ab6-46d9-99c9-f5622a4415d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "from Levenshtein import distance"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed84baf5-09ab-433e-9e1f-ec0d02f765b9",
   "metadata": {},
   "source": [
    "The `Levenshtein.distance` function finds the minimum number of steps.  For two completely different words, all the letters must be replaced:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c703402-b3e5-4d62-b02a-5e29d14dda1b",
   "metadata": {},
   "outputs": [],
   "source": [
    "distance(\"one\", \"six\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7caf1288-1f67-4b86-99cf-59b4f4959d09",
   "metadata": {},
   "source": [
    "While for a word that is a subset of another, the missing letters must all be added:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9f27e27-f94d-49b5-ae76-72b590670b06",
   "metadata": {},
   "outputs": [],
   "source": [
    "distance(\"seven\", \"seventeen\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef4580dc-bec3-406d-9ea4-591e71e844b5",
   "metadata": {},
   "source": [
    "## Distances between number words"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee84667d-f55e-4a13-9fad-f0e0f7eb07d2",
   "metadata": {},
   "source": [
    "Here we calculate the Levenshtein distance between the words for the first twenty counting numbers in English:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c8780520-c79a-432f-9670-29f0baf3cecf",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers2 = [\"one\", \"two\", \"three\", \"four\", \"five\", \"six\", \"seven\", \"eight\", \"nine\", \"ten\",\n",
    "           \"eleven\", \"twelve\", \"thirteen\", \"fourteen\", \"fifteen\", \"sixteen\", \"seventeen\",\n",
    "           \"eighteen\", \"nineteen\", \"twenty\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "70ffc1ec-41be-4303-8730-7067c71901b9",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = np.zeros((20,20))\n",
    "# Calculate distance between all pairs of strings in numbers2\n",
    "for i in range(len(numbers2)):\n",
    "    for j in range(len(numbers2)):\n",
    "        d[i][j] = distance( numbers2[i], numbers2[j])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "601d7830-63b6-4436-94cf-9aebf8792882",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "plt.imshow(d)\n",
    "plt.colorbar()\n",
    "plt.title(\"Levenshtein distance between number words\")\n",
    "plt.yticks(np.arange(len(numbers2)), numbers2, fontsize=6);\n",
    "plt.xticks(np.arange(len(numbers2)), numbers2, fontsize=6, rotation=90);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47c5ace0-e180-4cbc-b4f4-9bb518329d2d",
   "metadata": {},
   "source": [
    "This looks different from the set-based number-word similarity graph we constructed earlier.  First, we are measuring distance, not similarity, so the diagonal has distance 0 instead of similarity 1.  Second, the range of the distances is integers between 0 and the sum of the lengths of the two strings being compared.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1b7680f-9fc2-4161-b7bd-14f93c1ccc2f",
   "metadata": {},
   "source": [
    "Since this depends on a property of the strings that is not interesting, we can divide by the maximum possible "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f27cb71a-1028-439e-ab2d-43f496bdf0b6",
   "metadata": {},
   "source": [
    "The calculation of edit distance is, in general, more expensive to calculate than Jaccard similarity or Hamming distance; there are three possible operations at each position, and the operations may need to be repeated.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a69abdb0-b0b3-4908-8df6-b11583c2a130",
   "metadata": {},
   "outputs": [],
   "source": [
    "d2 = np.zeros((20,20))\n",
    "# Calculate distance between all pairs of strings in numbers2\n",
    "for i in range(len(numbers2)):\n",
    "    for j in range(len(numbers2)):\n",
    "        d2[i][j] = distance( numbers2[i], numbers2[j]) / (len(numbers2[i]) + len(numbers2[j])) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b46396bd-796b-4a6f-b523-73eacebe881b",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "plt.imshow(1-d2)\n",
    "plt.colorbar()\n",
    "plt.title(\"Levenshtein similarity between number words\")\n",
    "plt.yticks(np.arange(len(numbers2)), numbers2, fontsize=6);\n",
    "plt.xticks(np.arange(len(numbers2)), numbers2, fontsize=6, rotation=90);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6a4955a-2c91-43db-8117-c96c6280b93c",
   "metadata": {},
   "source": [
    "## Spelling correction"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1bdf8bb2-d803-46f2-a071-95e4d89ed0ae",
   "metadata": {},
   "source": [
    "One straightforward application of fuzzy matching is spelling correction; after checking each token in a document to see if it is in the dictionary, the words which are not in the dictionary are presented to the user along with suggestions of dictionary words that are similar to the unmatched word.\n",
    "\n",
    "The fuzzy matching can either start from the misspelled word and generate all possible misspellings out to a certain edit distance, or can start from the words in the dictionary, and find those with the fewest needed edits.  Think for a minute which of these might be cheaper (in terms of number of comparisons required.) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9b3a0438-a9a2-4baa-873d-cf08f9634277",
   "metadata": {},
   "outputs": [],
   "source": [
    "words = pd.read_csv(\"../../data/SINGLE.txt\", header=None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c50f4fd-e2fc-4d53-8e40-59687c0ec205",
   "metadata": {},
   "outputs": [],
   "source": [
    "words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e040f5e-88dd-41b5-ab05-9c411d0c9a86",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Start with a special-purpose function that only finds the distance\n",
    "# to one word of interest: \n",
    "word = \"wprd\"   # This is a misspelling\n",
    "def dist_to_word(w):\n",
    "        return distance(w, word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9984d7c8-52bb-4cb2-b4d2-3a8a83f97ddf",
   "metadata": {},
   "outputs": [],
   "source": [
    "dist_to_word(\"worm\"), dist_to_word(\"wierd\"), dist_to_word(\"weird\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "68252568-680b-4378-ab8a-819cf9359efa",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check that d(word, word) == 0 \n",
    "dist_to_word(\"word\") == 0 "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "771759cf-12d3-4b44-af5f-7f10325899f9",
   "metadata": {},
   "source": [
    "Check that we can find all the distances in one step:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e669e9c7-6ba1-4b2b-9790-87d9797ae4aa",
   "metadata": {
    "tags": [
     "hide-cell"
    ]
   },
   "outputs": [],
   "source": [
    "#note xmode Minimal shortens the error message\n",
    "%xmode Minimal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6259bc1b-c139-42be-8182-4b442858c4dc",
   "metadata": {
    "tags": [
     "raises-exception"
    ]
   },
   "outputs": [],
   "source": [
    "words[0].apply(dist_to_word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "797565e2-9c70-4d94-ac3c-ccb78eebbf63",
   "metadata": {},
   "source": [
    "Well, that didn't work.  It seems some of the words in the dictionary aren't encoded as strings.  Let us find the rows that are broken:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f95c8b85-e724-4a29-b4f0-d9d4589e7d81",
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_str(s):\n",
    "    return type(s) == str\n",
    "words[0].apply(test_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "90a3ffb6-0bcc-400f-8b8e-20dfd38c227f",
   "metadata": {},
   "outputs": [],
   "source": [
    "badindexes = np.where(words[0].apply(test_str)==False)\n",
    "badindexes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3ed3b30-914c-4d16-9cb9-e13ad9f6dfbe",
   "metadata": {},
   "source": [
    "Three rows have non-string names in them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bd14619f-eb93-43e9-b41b-3c7ce8616094",
   "metadata": {},
   "outputs": [],
   "source": [
    "words.loc[badindexes]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c95a2c96-a98c-463f-b706-d756ac3f6611",
   "metadata": {},
   "source": [
    "The non-string rows are all encoded as `NaN` (Not-a-number, a special symbol that acts like a number).  Examining the dataframe does not tell us about the source of the problem.  Let's try specifying a data type to `read_csv` and hope for the best:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "282d3d9a-f60f-450a-b003-5c34ba04ddaf",
   "metadata": {},
   "outputs": [],
   "source": [
    "words = pd.read_csv(\"../../data/SINGLE.txt\", header=None, dtype=\"str\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "70376bec-3f3f-4ec7-aa1c-6f444db4389c",
   "metadata": {},
   "outputs": [],
   "source": [
    "words.loc[badindexes]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f60485b-2dc8-4a82-863b-68778631106c",
   "metadata": {},
   "source": [
    "That didn't work either, the bad values are still bad.  The documentation for `read_csv` https://pandas.pydata.org/docs/reference/api/pandas.read_csv.html\n",
    "has a parameter called `na_filter` that can be turned off."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b0236f5-4174-4c04-a430-4d2912d73cc3",
   "metadata": {},
   "outputs": [],
   "source": [
    "words = pd.read_csv(\"../../data/SINGLE.txt\", header=None, na_filter=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7dcd18d-0e8f-49af-a9da-052758a3b692",
   "metadata": {},
   "source": [
    "And now we test for bad values: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cd9b062f-79e9-403b-9a01-3a14a2f56ed6",
   "metadata": {},
   "outputs": [],
   "source": [
    "np.where(words[0].apply(test_str)==False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c478600-ae65-409b-9aec-753c70ce3237",
   "metadata": {},
   "source": [
    "We find none.  What were those bad values, now?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "28a2985e-69af-4a6b-9b80-f95b85872943",
   "metadata": {},
   "outputs": [],
   "source": [
    "words.loc[badindexes]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1be4a38-1a36-471a-af4b-5bd15acf82cb",
   "metadata": {},
   "source": [
    "Huh.  Might want to take note of that in the future, some strings, by default, get turned into number-like NaNs."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb0bf9dd-b088-48d7-8b4a-e4e969746ea5",
   "metadata": {},
   "source": [
    "Now let us find the distances between our word and all the other words:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6657dff8-d77c-4d38-a7bb-5fd9f6fcd4d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# define this function in a function that we can use on all the rows in \n",
    "# the dictionary: \n",
    "def distance_to_all(word):\n",
    "    def dist_to_word(w):\n",
    "        return distance(w, word)\n",
    "    distances = words[0].apply(dist_to_word)\n",
    "    return distances"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7cf9731b-c165-4ad7-89ee-2ee47a5e330d",
   "metadata": {},
   "outputs": [],
   "source": [
    "distance_to_all(\"wprd\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3023773e-c9f1-453a-98b8-6b126603dbee",
   "metadata": {},
   "source": [
    "Let's make a new dataframe with the words and the distances to \"wprd\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52651e87-fec1-4086-9f18-cc7afff34997",
   "metadata": {},
   "outputs": [],
   "source": [
    "wprd_dist = words.copy()\n",
    "wprd_dist[\"distance\"] = distance_to_all(\"wprd\")\n",
    "wprd_dist"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca947ca4-b3c1-4f44-92d1-8619e0013038",
   "metadata": {},
   "source": [
    "Let us examine the histogram of distances.  All the words in the dictionary are in there."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5fc6461-cb96-4584-9d07-688b9f25460e",
   "metadata": {},
   "outputs": [],
   "source": [
    "wprd_dist.distance.value_counts()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a8e1473-86a4-4b01-9abd-3de9a9f219f7",
   "metadata": {},
   "source": [
    "This ordering of the histogram is not ideal for understanding, let us sort by distance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2257402f-5405-4e38-91bf-4468c46919b8",
   "metadata": {},
   "outputs": [],
   "source": [
    "wprd_dist.distance.value_counts().sort_index()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50ce8972-0956-40a6-b34b-eed9cfb425ba",
   "metadata": {},
   "source": [
    "From the table, which gives the values of edit distance as the index and the number of dictionary words at each distance from our target word as values, we see there are three dictionary words at distance 1, and 147 words at edit distance 2. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d7c7108-cf96-4b33-ad90-e13261666a9f",
   "metadata": {},
   "outputs": [],
   "source": [
    "wprd_dist.query(\"distance < 2\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05a2f9e0-ec99-4846-b4ca-f7ec607a895e",
   "metadata": {},
   "outputs": [],
   "source": [
    "wprd_dist.query(\"distance == 2\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "921adcb7-b40b-4c53-b298-014b544be59c",
   "metadata": {},
   "source": [
    "This certainly gives us a starting point (or at least a partly ordered list) of plausible words.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "283bb42a-474a-49a4-86a6-be8993c1421c",
   "metadata": {},
   "source": [
    "## Diffs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2d50795-cc83-4678-ad35-c2f76e35a49d",
   "metadata": {},
   "source": [
    "An alignment-based representation of the changes to a document is sometimes an effective way of learning what has changed; algorithms that will compare documents, find the minimum number of edits and show what the edits are with highlighting can be helpful when examining changes to documents or code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67ad8398-8ab1-4575-946c-b5f7822e991a",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}