3.JellyFishStringMatching.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# JellyFish"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**CONTENTS**:\n",
    "\n",
    "+ **Introduction** - Outlining the Problem\n",
    "+ **JellyFish and It's Algorithms** - Brief introduction to JellyFish\n",
    "+ **Levenshtein Distance** - Description, Calculation, and Examples\n",
    "+ **Damerau Levenshtein Distance** - Description, Calculation, and Examples\n",
    "+ **Jaro Distance** - Description, Calculation, and Examples\n",
    "+ **Jaro-Winkler Distance** - Description, Calculation, and Examples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "ImportError",
     "evalue": "No module named pandas",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mImportError\u001b[0m                               Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-1-ac2b71ec9a17>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;32mimport\u001b[0m \u001b[0mpandas\u001b[0m \u001b[1;32mas\u001b[0m \u001b[0mpd\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      2\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mnumpy\u001b[0m \u001b[1;32mas\u001b[0m \u001b[0mnp\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mdatetime\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mos\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m \u001b[1;32mfrom\u001b[0m \u001b[0mpandas\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mDataFrame\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mImportError\u001b[0m: No module named pandas"
     ]
    }
   ],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import datetime\n",
    "import os\n",
    "from pandas import DataFrame\n",
    "from numpy import nan as NA\n",
    "from IPython.core.display import HTML\n",
    "from IPython.core.display import Image\n",
    "from IPython.display import Math\n",
    "from IPython.display import Latex\n",
    "import collections\n",
    "import jellyfish as jf\n",
    "import re"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With regard to style names in production data we face two distinct problems:\n",
    "\n",
    "1. Style names not being clean within factory. <br />\n",
    "</p> </p> The fact of the matter is that often the string values of the style names are not clean meaning that styles that in reality are the same are not recognised as such. This is clearly problematic as we want to be able to ;identify those styles that are produced on multiple lines in order to sensibly create the running days values, &nbsp;&nbsp;&nbsp;to do across line analysis of the same styles etc. etc. \n",
    "\n",
    "2. Matching styles across factory. <br />\n",
    "</p> </p> Eventually we will want to be able to match styles across factories in order to identify those styles that are produced in multiple factories. The reasons for this are pretty obvious. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## JellyFish and Its Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jellyfish is a python library for doing approximate and phonetic matching of strings. It allows for string comparison using the following algorithms:\n",
    "\n",
    "+ Levenshtein Distance\n",
    "+ Damerau-Levenshtein Distance\n",
    "+ Jaro Distance\n",
    "+ Jaro-Winkler Distance\n",
    "+ Match Rating Approach Comparison\n",
    "+ Hamming Distance\n",
    "\n",
    "All of the above are metrics for measuring the difference between two sequences. Each of these will not be briefly introduced and an example given:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###**Levenshtein Distance**<br />\n",
    "The Levenshtein distance between two words is the minimum number of single-character edits (insertion, deletion, substitution) required to transform one string into another. The lower the score, the lower the number of edits. If the score is 0, then no edits are needed so the strings are exactly the same. \n",
    "\n",
    "For example, the Levenshtein distance between \"kitten\" and \"sitting\" is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:\n",
    "\n",
    "+ Edit 1: kitten → sitten (substitution of \"s\" for \"k\")\n",
    "+ Edit 2: sitten → sittin (substitution of \"i\" for \"e\")\n",
    "+ Edit 3: sittin → sitting (insertion of \"g\" at the end)\n",
    "\n",
    "The measure is most useful when looking to match short strings with longer strings. It takes a lot of computational power to do this with long strings and may not therefore be totally appropriate.  \n",
    "\n",
    "For more information about the measure see\n",
    "\n",
    "http://en.wikipedia.org/wiki/Levenshtein_distance\n",
    "\n",
    "Now some examples follow:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = 'Rory'\n",
    "B = 'Ronnie'\n",
    "\n",
    "jf.levenshtein_distance(unicode(A), unicode(B))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As the following demonstrates, the algorithm also considers case, which is a strong argument for converting all strings to the same case. This is a pretty standard way of working with strings so will come as no surprise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = 'Rory'\n",
    "B = 'rory'\n",
    "jf.levenshtein_distance(unicode(A), unicode(B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Now the levenshtein score of 0 means the strings are an exact match. \n",
    "jf.levenshtein_distance(unicode(A.lower()), unicode(B.lower()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###**Damerau Levenshtein Distance**<br />\n",
    "This measure is very similar to the Levenshtein distance, in that it is a measure of the minimum number of edits needed to transform one string into another. The permissible 'edits' in the Levenshtein distance are insertions, deletion and substitution whereas in the Damerau Levenshtein distance the transposition of two adjacent characters is also allowed. Damerau claimed that these four edits correspond to 80% of human spelling errors. \n",
    "\n",
    "As with the Levenshtein distance a score of zero indicates and exact match etc.\n",
    "\n",
    "This measure may be an improvement on the Levenshtein distance as using the Damerau Levenshtein Distance strings where two letters are simply the wrong way around will have a lower score (indicating a better match) than they would under the Levenshtein measure. \n",
    "\n",
    "A simple example will suffice:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jf.levenshtein_distance(unicode('jellyfihs'), unicode('jellyfish'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jf.damerau_levenshtein_distance(unicode('jellyfihs'), unicode('jellyfish'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, the **Levenshtein** distance works like this:\n",
    "\n",
    "+ Edit 1: jellyfihs → jellyfiss (substitution of \"s\" for \"h\")\n",
    "+ Edit 2: jellyfiss → jellyfish (substitution of \"h\" for \"s\")\n",
    "\n",
    "This is only one way it could happen. For instance 'h' could have been deleted, and then inserted (and so on), but the minimum number of edits is always 2\n",
    "\n",
    "The **Damerau Levenshtein** distance works like this:\n",
    "\n",
    "+ Edit 1: jellyfihs → jellyfish (transposition of 's' and 'h' adjacent characters)\n",
    "\n",
    "The measure may therefore be a better one in that it recognises strings as being closer than the Levenshtein measure in cases where there has been a simple mix up of characters. \n",
    "\n",
    "\n",
    "**NB** I have observed some odd behaviour of the jf.damerau_levenshtein_distance algorithm. The odd behaviour may be related to me misunderstanding the nature of the measure, or it may be a problem with coding of the library. I have written to the developer for clarification. If you are interested, then see the following, if not then skip to the next measure below.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jf.damerau_levenshtein_distance(unicode('jellyfihs'), unicode('jellyfish'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jf.damerau_levenshtein_distance(unicode('ifhs'), unicode('fish'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I find the above output very odd for the reason that the scores should be the same as the edits required in both instances are exactly the same:\n",
    "\n",
    "In the first example:\n",
    "\n",
    "+ Edit 1: jellyifhs → jellyfihs (transpose adjacent characters 'i' and 'f')\n",
    "+ Edit 2: jellyfihs → jellyfish (transpose adjacent characters 'h' and 's')\n",
    "\n",
    "In the second example:\n",
    "\n",
    "+ Edit 1: ifhs → fihs (transpose adjacent characters 'i' and 'f')\n",
    "+ Edit 2: fihs → fish (transpose adjacent characters 'h' and 's')\n",
    "\n",
    "Why the outputs are different remains to be determined.\n",
    "\n",
    "**Update** It appears from looking at the source code that in some cases the function is returning the OSA  measure not the Damerau Levenshtein measure. The developer is now aware, and has been contacted. use this measure with caution. \n",
    "\n",
    "More information on the measure can be found at http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###**Jaro Distance**<br />\n",
    "The Jaro distance is a measure that considers the number of matching characters in both strings being compared, and also the number of transpositions which is defined as the number of matching characters (in a different sequence order) divided by two. The measure returns a score between 0 and 1, 0 being no match whatsoever (as defined in the calculation) and 1 being a perfect match. \n",
    "\n",
    "Beware that this measure will ignore matching characters that are more than a certain distance from each other. This could either be a good thing (to ignore spurious matches) or a bad thing (ignoring correct matches). In any event, it is important to be aware of this, so it is explained in detail below.\n",
    "\n",
    "It is calculated as follows:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\begin{eqnarray}\n",
       "d_j = \\left\\{\n",
       "    \\begin{array}{1 1}\n",
       "        0 & \\quad \\text{if $m$ = 0 <}\\\\\n",
       "        \\\\\n",
       "        \\frac{1}{3} \\bigg(\\frac{m}{|s_1|} + \\frac{m}{|s_2|} + \\frac{m - t}{m} & \\quad \\text{otherwise}\n",
       "    \\end{array} \\right.\n",
       "\\end{eqnarray}"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Latex(r\"\"\"\\begin{eqnarray}\n",
    "d_j = \\left\\{\n",
    "    \\begin{array}{1 1}\n",
    "        0 & \\quad \\text{if $m$ = 0 <}\\\\\n",
    "        \\\\\n",
    "        \\frac{1}{3} \\bigg(\\frac{m}{|s_1|} + \\frac{m}{|s_2|} + \\frac{m - t}{m} & \\quad \\text{otherwise}\n",
    "    \\end{array} \\right.\n",
    "\\end{eqnarray}\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ **$m$** is the number of matching characters\n",
    "+ **$t$** is half the number of transpositions.\n",
    "+ **$|s_1|$** is the length of the first string to be matched\n",
    "+ **$|s_2|$** is the length of the second string to be matched\n",
    "\n",
    "If the number of matching characters is 0, then the measure equals 0\n",
    "\n",
    "A character in each string is only considered to be matching if it is the same and obeys the following rule as to distance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\begin{eqnarray}\n",
       "\\frac{max(|s_1|,|s_2|)}{2} -1\n",
       "\\end{eqnarray}"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Latex(r\"\"\"\\begin{eqnarray}\n",
    "\\frac{max(|s_1|,|s_2|)}{2} -1\n",
    "\\end{eqnarray}\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Observe the following:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S1 = 'AzzzzB'\n",
    "S2 = 'BxxA'\n",
    "jf.jaro_winkler(unicode(S1), unicode(S2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Although the characters A and B appear in both strings, m = 0 because they are farther in distance from each other than:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\begin{eqnarray}\n",
       "\\frac{max(|6|,|4|)}{2} -1 = 2\n",
       "\\end{eqnarray}"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Latex(r\"\"\"\\begin{eqnarray}\n",
    "\\frac{max(|6|,|4|)}{2} -1 = 2\n",
    "\\end{eqnarray}\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Transpositions are also important as already mentioned. The number of transpositions is calculated as \"The number of matching (but different sequence order) characters divided by 2\". Observe the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9523809523809524"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S3 = 'Poverty'\n",
    "S4 = 'Poervty'\n",
    "jf.jaro_distance(unicode(S3), unicode(S4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sadly it looks like this is also being calculated incorrectly. To my mind the calculation should be as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\begin{eqnarray}\n",
       "\\Bigg(\\frac{7}{7} + \\frac{7}{7} + \\frac{7- \\frac{3}{2}}{7}\\Bigg) = 0.9285714\n",
       "\\end{eqnarray}"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Latex(r\"\"\"\\begin{eqnarray}\n",
    "\\Bigg(\\frac{7}{7} + \\frac{7}{7} + \\frac{7- \\frac{3}{2}}{7}\\Bigg) = 0.9285714\n",
    "\\end{eqnarray}\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Whereas is appears that it is being calcualted as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\begin{eqnarray}\n",
       "\\Bigg(\\frac{7}{7} + \\frac{7}{7} + \\frac{7- \\frac{2}{2}}{7}\\Bigg) = 0.9523809\n",
       "\\end{eqnarray}"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Latex(r\"\"\"\\begin{eqnarray}\n",
    "\\Bigg(\\frac{7}{7} + \\frac{7}{7} + \\frac{7- \\frac{2}{2}}{7}\\Bigg) = 0.9523809\n",
    "\\end{eqnarray}\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The critical difference is that I calculate the number of matching (but different sequence order) characters as 3, those being:\n",
    "\n",
    "+ e\n",
    "+ r\n",
    "+ v\n",
    "\n",
    "Whereas it appears that JellyFish thinks there are only two.\n",
    "\n",
    "Again, I have raised this issue with the developer. It may resolved in future, but for now use this measure with caution. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###**Jaro-Winkler Distance**\n",
    "The Jaro-Winkler Distance measure builds upon the Jaro measure, but uses a prefix scale which gives more favorable ratings to strings that match from the beginning for a set prefix length. This will become clear when the calculation is viewed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\begin{eqnarray}\n",
       "d_w = d_j + (\\ell p(1 - d_j))\n",
       "\\end{eqnarray}"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Latex(r\"\"\"\\begin{eqnarray}\n",
    "d_w = d_j + (\\ell p(1 - d_j))\n",
    "\\end{eqnarray}\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The expression is made up of the following:\n",
    "\n",
    "+ **$d_w$** is the Jarrow-Winkler distance\n",
    "+ **$d_j$** is the Jaro distance for strings s1 and s2\n",
    "+ **$\\ell$** is the length of the common prefix up to a maximum of 4 characters\n",
    "+ **$p$** is a constant scaling factor for how much the score is adjusted upwards for having common prefixes. It should not exceed  0.25, otherwise the distance can become larger than 1. The standard value for this constant in Winkler's work is 0.1\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The key takeaway is that strings that begin with the same prefixes score more highly...\n",
    "\n",
    "Observe the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9363636363636364"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S5 = 'Innovaiosn'\n",
    "S6 = 'Innovations'\n",
    "jf.jaro_distance(unicode(S5), unicode(S6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9618181818181818"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jf.jaro_winkler(unicode(S5), unicode(S6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Although it is not stated anywhere in the jellyfish documentation, it is clear that the value of $p$ is 0.1, this is because rearranging the following to solve for $\\ell$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\begin{eqnarray}\n",
       "d_w = d_j + (\\ell p(1 - d_j))\\\\\n",
       "\\\\\n",
       "\\\\\n",
       "\\ell = \\frac{d_w - d_j}{1 - d_j} * \\frac{1}{4}\\\\\n",
       "\\\\\n",
       "\\\\\n",
       "0.1 = \\frac{0.96182-0.936364}{1-0.936364} * \\frac{1}{4}\n",
       "\n",
       "\\end{eqnarray}"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Latex(r\"\"\"\\begin{eqnarray}\n",
    "d_w = d_j + (\\ell p(1 - d_j))\\\\\n",
    "\\\\\n",
    "\\\\\n",
    "\\ell = \\frac{d_w - d_j}{1 - d_j} * \\frac{1}{4}\\\\\n",
    "\\\\\n",
    "\\\\\n",
    "0.1 = \\frac{0.96182-0.936364}{1-0.936364} * \\frac{1}{4}\n",
    "\n",
    "\\end{eqnarray}\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In some implementations of Jaro-Winkler, the prefix bonus is only added when the compared strings have a Jaro distance above a set \"boost threshold\". In the work of the developer himself, this threshold was set at 0.7. In other words, if the Jaro measure is less than 0.7, then even if the prefixes of the string are the same up to four characters, the prefix bonus will not be applied. Then the calculation looks like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\begin{eqnarray}\n",
       "d_w = \\left\\{\n",
       "    \\begin{array}{1 1}\n",
       "        d_j & \\quad \\text{if $d_j$ < $b_t$}\\\\\n",
       "        d_j + (\\ell p(1 - d_j)) & \\quad \\text{otherwise}\n",
       "    \\end{array} \\right.\n",
       "\\end{eqnarray}"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Latex(r\"\"\"\\begin{eqnarray}\n",
    "d_w = \\left\\{\n",
    "    \\begin{array}{1 1}\n",
    "        d_j & \\quad \\text{if $d_j$ < $b_t$}\\\\\n",
    "        d_j + (\\ell p(1 - d_j)) & \\quad \\text{otherwise}\n",
    "    \\end{array} \\right.\n",
    "\\end{eqnarray}\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, as there is no documentation to JellyFish it is hard to know if this is being applied, and if so, at what level the $b_t$ value is set to trigger the prefix bonus. However, a bit of easy experimentation can demonstrate, firstly I compare strings that have a Jaro score just below 0.7, and then strings that have a score just above 0.7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6777777777777777"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S7 = 'ABCDqwerty'\n",
    "S8 = 'ABCDpoiuyt'\n",
    "jf.jaro_distance(unicode(S7), unicode(S8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6777777777777777"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jf.jaro_winkler(unicode(S7), unicode(S8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7333333333333334"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S9 = 'ABCDqwerty'\n",
    "S10 = 'ABCDpoiuty'\n",
    "jf.jaro_distance(unicode(S9), unicode(S10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8400000000000001"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jf.jaro_winkler(unicode(S9), unicode(S10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above output indicates that indeed, there implementation of the Jaro-Winkler measure in JellyFish uses a threshold of 0.7 for $b_t$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Developer - Pranav Shukla <br>\n",
    "Email - pranavdynamic@gmail.com"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}