text: {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Rabin-Karp method\n",
      "\n",
      "If you think hard enough, there's nothing that diferrentiates piecs of text from numbers. You can think of letters as digits and base of the numbers as sufficently big to accomodate for all the digits. For example take the following text\n",
      "\n",
      "$$\n",
      "babacb\n",
      "$$\n",
      "\n",
      "it can be though of as a number base 26 (for all the english letters):\n",
      "\n",
      "$$\n",
      "(1,0,1,0,2,1)_{26}\n",
      "$$\n",
      "\n",
      "We can transform this number to base 10 using the following equation.\n",
      "\n",
      "$$\n",
      "1*26^5 + 0 * 26^4 + 1*26^3 + 0*26^2 + 2*26^1 + 1*26^0 = 11899005\n",
      "$$\n",
      "\n",
      "From the formulation above the following property should be clear.\n",
      "\n",
      "$$\n",
      "abba = abb * 26 + b\n",
      "$$\n",
      "\n",
      "in general we can write $concat(word, letter) = base * word + letter$ (1).\n",
      "\n",
      "There's also a small technicality. When we compare numbers then $0001$ and $001$ and $1$ are equivalent. This means that we cannot map any letter to 0 if we want to be able to successfuly compare the numbers. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Observation (1) allows us to quickly compute hashes for all the prefixes of a given word. Just like in class we are going to use modular arithmetic for our computations."
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 8,
     "metadata": {
      "collapsed": false
     },
     "outputs": [
      {
       "name": "stdout",
       "output_type": "stream",
       "text": [
        "'A' 65\n",
        "'a' 97\n",
        "'b' 98\n",
        "'c' 99\n",
        "' ' 32\n",
        "'c' - 'a' + 1 = 3\n"
       ]
      }
     ],
     "source": [
      "# we need to map letters to numbers. Python function ord does the job\n",
      "print(repr('A'), ord('A'))\n",
      "print(repr('a'), ord('a'))\n",
      "print(repr('b'), ord('b'))\n",
      "print(repr('c'), ord('c'))\n",
      "print(repr(' '), ord(' '))\n",
      "\n",
      "print('%s - %s + 1 = %d' % (repr('c'), repr('a'), ord('c') - ord('a') + 1))\n"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 17,
     "metadata": {
      "collapsed": false
     },
     "outputs": [],
     "source": [
      "BIG_FAT_PRIME = 2**32 - 1\n",
      "ENGLISH_BASE = 30 # in theory 27 is sufficient but better safe than sorry!\n",
      "\n",
      "def compute_hashes(text, base=ENGLISH_BASE, modulo = BIG_FAT_PRIME):\n",
      "    # \n",
      "    h = [None for _ in range(len(text) + 1)]\n",
      "    h[0] = 0 # hash of empty word is 0\n",
      "    for i in range(len(text)):\n",
      "        # we only deal with english letters so we subtract 'a'\n",
      "        # to normalize range. We add 0 to avoid creating zero digit.\n",
      "        letter_as_number = (ord(text[i]) - ord('a') + 1)\n",
      "        h[i + 1] = h[i] * base + letter_as_number\n",
      "        h[i + 1] %= modulo\n",
      "        # at the end of the iteration h[i+1] is the hash\n",
      "        # of prefix of text of lenght (i+1) which in\n",
      "        # Python is text[:(i+1)]\n",
      "    return h"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "PROTIP: If you happen to ever implemented this is lower level programming language like C or C++, be ware of integer overflows."
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 18,
     "metadata": {
      "collapsed": false
     },
     "outputs": [
      {
       "data": {
        "text/plain": [
         "[0, 2, 61, 1832, 54961, 1648833, 49464992]"
        ]
       },
       "execution_count": 18,
       "metadata": {},
       "output_type": "execute_result"
      }
     ],
     "source": [
      "compute_hashes(\"babacb\")"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 19,
     "metadata": {
      "collapsed": false
     },
     "outputs": [
      {
       "data": {
        "text/plain": [
         "[0, 2, 61, 1832, 54964, 1648924, 49467724]"
        ]
       },
       "execution_count": 19,
       "metadata": {},
       "output_type": "execute_result"
      }
     ],
     "source": [
      "compute_hashes(\"babddd\")"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 20,
     "metadata": {
      "collapsed": false
     },
     "outputs": [
      {
       "data": {
        "text/plain": [
         "[0,\n",
         " 2,\n",
         " 61,\n",
         " 1832,\n",
         " 54964,\n",
         " 1648924,\n",
         " 49467721,\n",
         " 1484031649,\n",
         " 1571276524,\n",
         " 4188622771,\n",
         " 1104631594,\n",
         " 3074176759,\n",
         " 2030989594,\n",
         " 800145691,\n",
         " 2529534259]"
        ]
       },
       "execution_count": 20,
       "metadata": {},
       "output_type": "execute_result"
      }
     ],
     "source": [
      "# for longer strings modulo matters\n",
      "compute_hashes(\"babddasdasdsad\")"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## hashes of substrings\n",
      "\n",
      "Now here's a crutial observation. Let's take polynomial representation of string  $babacb$ (where $X$ is the base)\n",
      "\n",
      "$$\n",
      "b*X^5 + a * X^4 + b*X^3 + a*X^2 + c*X^1 + b*X^0 \n",
      "$$\n",
      "\n",
      "Say we want to compute hash of $ac$ which is conveniently appears on 4-th index the string we originally hashed. Moreover we have hashes of all the prefixes - it seems like we are in good shape:\n",
      "\n",
      "\\begin{align}\n",
      "\\text{we have }\\ \\ \\ & hash(babac) &=\\ & b*X^4 + a * X^3 + b*X^2 &+& a*X^1 + c*X^0 \\\\\n",
      "\\text{we have }\\ \\ \\  & hash(bab)   &=\\ & b*X^2 + a * X^1 + b*X^0&&\\\\\n",
      "\\text{we WANT }\\ \\ \\  & hash(ac)    &=\\ &                         && a*X^1 + c*X^0\\\\\n",
      "\\end{align}\n",
      "\n",
      "\n",
      "From above we can clearly see that:\n",
      "\n",
      "$$\n",
      "hash(ac) = hash(babac) - X^2 * hash(bab)\n",
      "$$\n",
      "\n",
      "We can generalize this to arbitrary substring of our hashed string. Assume we hashed string $s_0, s_1, ..., s_{n-1}$ such that $h_0 = hash(\\emptyset)$, $h_1 = hash(s_0)$, $h_2 = hash(s_0, s_1)$ etc. \n",
      "Then we can compute $hash(s_i, ..., s_j)$ using the following formula:\n",
      "\n",
      "$$\n",
      "hash(s_i, ..., s_{j-1}) = h_j - h_i * X ^{j - i}\n",
      "$$\n",
      "\n",
      "This looks very close to $O(1)$ complexity hash computation if not for $X ^{j - i}$. But since there are at most $n$ different powers of $X$ that we are interested in, we can precompute them in $O(n)$ time."
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 37,
     "metadata": {
      "collapsed": true
     },
     "outputs": [],
     "source": [
      "def compute_powers(n, base=ENGLISH_BASE, modulo=BIG_FAT_PRIME):\n",
      "    powers = [None for _ in range(n + 1)]\n",
      "    powers[0] = 1\n",
      "    for i in range(n):\n",
      "        powers[i+1] = (powers[i] * base) % modulo\n",
      "    return powers"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 38,
     "metadata": {
      "collapsed": false
     },
     "outputs": [
      {
       "data": {
        "text/plain": [
         "[1,\n",
         " 30,\n",
         " 900,\n",
         " 27000,\n",
         " 810000,\n",
         " 24300000,\n",
         " 729000000,\n",
         " 395163525,\n",
         " 3264971160,\n",
         " 3459854310,\n",
         " 716414220]"
        ]
       },
       "execution_count": 38,
       "metadata": {},
       "output_type": "execute_result"
      }
     ],
     "source": [
      "compute_powers(10)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now we can put all those observations together into efficient detastructure that allows us to compute hashes of substrings in $O(1)$"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 77,
     "metadata": {
      "collapsed": true
     },
     "outputs": [],
     "source": [
      "class Hasher(object):\n",
      "    def __init__(self, word):\n",
      "        self.h = compute_hashes(word)\n",
      "        self.powers = compute_powers(len(word))\n",
      "        \n",
      "    def substring_hash(self, i, j):\n",
      "        result = self.h[j] - self.h[i] * self.powers[j-i]\n",
      "        return result % BIG_FAT_PRIME"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 78,
     "metadata": {
      "collapsed": false
     },
     "outputs": [],
     "source": [
      "TEXT = \"abcxabcx\"\n",
      "h = Hasher(TEXT)"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 79,
     "metadata": {
      "collapsed": false
     },
     "outputs": [
      {
       "name": "stdout",
       "output_type": "stream",
       "text": [
        "[ab]cxabcx 32\n",
        "abcx[ab]cx 32\n",
        "abc[xa]bcx 721\n"
       ]
      }
     ],
     "source": [
      "def highlight(word, i, j):\n",
      "    return word[:i] + \"[\" + word[i:j] + \"]\" + word[j:]\n",
      "\n",
      "print(highlight(TEXT, 0, 2), h.substring_hash(0, 2))\n",
      "print(highlight(TEXT, 4, 6), h.substring_hash(4, 6))\n",
      "print(highlight(TEXT, 3, 5), h.substring_hash(3, 5))"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Hasher complexity analysis.\n",
      "\n",
      "Preprocessing (`__init__`):\n",
      "- `compute_hashes` is $O(n)$\n",
      "- 'compute_powers` is $O(n)$\n",
      "Therefore precomputing is $O(n)$.\n",
      "\n",
      "Queries (`substring_hash`) is of complexity $O(1)$ - it is just a simple formula."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Notice that this technique is very powerful. More powerful than we need for pattern matching. It should not be a surprise that we can easily use it to solve pattern matching"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 100,
     "metadata": {
      "collapsed": false
     },
     "outputs": [],
     "source": [
      "# hasher for text\n",
      "text_h = Hasher(\"to be or not to be\")"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 101,
     "metadata": {
      "collapsed": false
     },
     "outputs": [
      {
       "data": {
        "text/plain": [
         "65"
        ]
       },
       "execution_count": 101,
       "metadata": {},
       "output_type": "execute_result"
      }
     ],
     "source": [
      "# hash of the pattern\n",
      "compute_hashes(\"be\")[-1]"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 102,
     "metadata": {
      "collapsed": false
     },
     "outputs": [
      {
       "data": {
        "text/plain": [
         "65"
        ]
       },
       "execution_count": 102,
       "metadata": {},
       "output_type": "execute_result"
      }
     ],
     "source": [
      "# hash of the occurence of \"be\" in original text. \n",
      "text_h.substring_hash(3, 5)"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 105,
     "metadata": {
      "collapsed": false
     },
     "outputs": [],
     "source": [
      "def compute_matches(text, pattern):\n",
      "    # hash of patter\n",
      "    pattern_hash = compute_hashes(pattern)[-1]\n",
      "    # hasher for text\n",
      "    text_h = Hasher(text)\n",
      "    res = []\n",
      "    for i in range(len(text) - len(pattern) + 1):\n",
      "        # i is potential match start index\n",
      "        # compare hash in text with hash of pattern\n",
      "        if text_h.substring_hash(i, i + len(pattern)) == pattern_hash:\n",
      "            # if matching append to result list.\n",
      "            res.append(i)\n",
      "    return res"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 106,
     "metadata": {
      "collapsed": false
     },
     "outputs": [
      {
       "data": {
        "text/plain": [
         "[3, 16]"
        ]
       },
       "execution_count": 106,
       "metadata": {},
       "output_type": "execute_result"
      }
     ],
     "source": [
      "compute_matches(\"to be or not to be\", \"be\")"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Rabin-Karp complexity analysis\n",
      "\n",
      "Assume that pattern is of length $n$ and text of length $m$\n",
      "\n",
      "- pattern hash: $O(n)$\n",
      "- text preprocessing $O(m)$.\n",
      "- $n - m$ iterations of main loop with $O(1)$ hash computation in each loop\n",
      "\n",
      "total: $O(n+m)$\n",
      "\n",
      "Catch? Relies on luck."
     ]
    }
   ],
   "metadata": {
    "kernelspec": {
     "display_name": "Python 3",
     "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.4.1"
    }
   },
   "nbformat": 4,
   "nbformat_minor": 0
  }
  