DIVIDE AND CONQUER (LINEAR SPACE).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#mat1 = [[0 for x in range(len(str2)+1)] for x in range(2)]\n",
    "#mat2 = [[0 for x in range(len(str2)+1)] for x in range(2)]\n",
    "def compute_midpoint(str1,str2):\n",
    "    \n",
    "    \n",
    "    if (len(str1)/2==0):\n",
    "        \n",
    "        a = (divide(str1, str2, (len(str1))/2, len(str2)))\n",
    "        \n",
    "        b = (divide(str1[::-1], str2[::-1], (len(str1))/2, len(str2)))\n",
    "    \n",
    "    else:\n",
    "        \n",
    "        a = (divide(str1, str2, (len(str1))/2, len(str2)))\n",
    "        \n",
    "        b = (divide(str1[::-1], str2[::-1], (len(str1)+1)/2, len(str2)))\n",
    "    \n",
    "    b = b[::-1]\n",
    "    \n",
    "    from operator import add\n",
    "    c = map(add, a, b)\n",
    "    \n",
    "    midpoint = min(xrange(len(c)), key=c.__getitem__)\n",
    "    \n",
    "    return  midpoint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def divide(str1, str2, m, n):\n",
    "    dp = [[0 for x in range(len(str2)+1)] for x in range(2)]\n",
    "    # FORWARD COMPUTATION and BACKWARD COMPUTATION; TO FIND BEST q FOR (X/2,q)\n",
    "    \n",
    "    for i in range(m+1):\n",
    "        \n",
    "        for j in range(n+1):\n",
    "            \n",
    "            if ((i >= 1 and j > 1)):\n",
    "                dp[0][j-2]=dp[1][j-2]\n",
    "                \n",
    "            if i == 0:\n",
    "                dp[0][j] = j    \n",
    " \n",
    "            elif j == 0:\n",
    "                dp[1][j] = i    \n",
    " \n",
    "           \n",
    "            elif str1[i-1]==str2[j-1]:\n",
    "                dp[1][j]=min(dp[1][j-1]+1,dp[0][j]+1,dp[0][j-1])\n",
    "                 \n",
    "            else:\n",
    "                dp[1][j] =  min(dp[1][j-1]+1,dp[0][j]+1,dp[0][j-1]+1)\n",
    "                \n",
    "            if (i>=1 and j==n):\n",
    "                #dp[0][j-2]=dp[1][j-2]\n",
    "                dp[0][j-1]=dp[1][j-1]\n",
    "                dp[0][j] = dp[1][j]\n",
    "                \n",
    "            #print \"this is 0th row\",dp[0]\n",
    "            #print \"this is 1st row\",dp[1]\n",
    "            #print  \"i = \",i,\"\\n\"           \n",
    "            \n",
    "                \n",
    "    return dp[1]       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def alignment(str1,str2,m,n,al):   \n",
    "    aln_X = \"\" \n",
    "    aln_Y = \"\"\n",
    "    while (m>0 or n>0):\n",
    "    \n",
    "        if(m>0 and n>0 and al[m][n]=='S'):\n",
    "            aln_X = aln_X + str1[m-1]\n",
    "            aln_Y = aln_Y + str2[n-1]\n",
    "            m = m-1\n",
    "            n = n-1\n",
    "        \n",
    "        \n",
    "        elif (m>0 and al[m][n] == 'D'):\n",
    "            aln_X = aln_X + str1[m-1]\n",
    "            aln_Y = aln_Y + '-'\n",
    "            m = m-1\n",
    "        \n",
    "        else:\n",
    "            aln_X = aln_X + '+'\n",
    "            aln_Y = aln_Y + str2[n-1]\n",
    "            n = n-1\n",
    "\n",
    "    l1 = aln_X[::-1]\n",
    "    l2 = aln_Y[::-1]            \n",
    "        \n",
    "    return l1,l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def align_this(str1, str2, m, n):\n",
    "    \n",
    "    dyn = [[0 for x in range(len(str2)+1)] for x in range(len(str1)+1)]\n",
    "    al  = [[0 for x in range(len(str2)+1)] for x in range(len(str1)+1)]\n",
    "    \n",
    "    for i in range(m+1):\n",
    "        for j in range(n+1):\n",
    "            if (i==0 and j==0):\n",
    "                al[i][j]=\"N\"\n",
    "   \n",
    "            elif (i == 0):\n",
    "                dyn[i][j] = j\n",
    "                al[i][j] = \"I\"\n",
    "           \n",
    "            elif (j == 0):\n",
    "                dyn[i][j] = i    \n",
    "                al[i][j] = \"D\"\n",
    "                \n",
    "            elif (str1[i-1]==str2[j-1]):\n",
    "                \n",
    "                inse=dyn[i][j-1]+1\n",
    "                dele=dyn[i-1][j]+1\n",
    "                subs=dyn[i-1][j-1]\n",
    "                \n",
    "                key_values={'insert':inse,'delete':dele,'subs':subs}\n",
    "                \n",
    "                dyn[i][j]=min(inse,dele,subs)\n",
    "                \n",
    "                ops=next(key for key, value in key_values.iteritems() if value == dyn[i][j])\n",
    "                \n",
    "                if(ops=='insert'):\n",
    "                    al[i][j]='I'\n",
    "                elif(ops=='delete'):\n",
    "                    al[i][j]='D'\n",
    "                else:\n",
    "                    al[i][j]='S'\n",
    "                 \n",
    "            else:\n",
    "                inse=dyn[i][j-1]+1\n",
    "                dele=dyn[i-1][j]+1\n",
    "                subs=dyn[i-1][j-1]+1\n",
    "                \n",
    "                key_values={'insert':inse,'delete':dele,'subs':subs}\n",
    "                \n",
    "                dyn[i][j]=min(inse,dele,subs)    \n",
    "                \n",
    "                ops=next(key for key, value in key_values.iteritems() if value == dyn[i][j])\n",
    "                \n",
    "                if(ops=='insert'):\n",
    "                    al[i][j]='I'\n",
    "                elif(ops=='delete'):\n",
    "                    al[i][j]='D'\n",
    "                else:\n",
    "                    al[i][j]='S'\n",
    "                    \n",
    "    return dyn[m][n],al"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ED=0\n",
    "\n",
    "def Conquer(str1,str2):\n",
    "    \n",
    "    algn_X=\"\"\n",
    "    algn_Y=\"\"\n",
    "    \n",
    "    if len(str1) == 0:\n",
    "        \n",
    "        ED=len(str2)\n",
    "        for i in range(len(str2)):\n",
    "            algn_X=\"-\" + algn_X\n",
    "            algn_Y=algn_Y + algn_Y[i]\n",
    "        \n",
    "    elif len(str2) == 0:\n",
    "        \n",
    "        ED=len(str1)\n",
    "        for i in range(len(str2)):\n",
    "            algn_X = algn_X + algn_X[i]\n",
    "            algn_Y = \"-\" + algn[Y]\n",
    "        \n",
    "     \n",
    "    elif len(str1) <=2 or len(str2) <=2 :\n",
    "        \n",
    "        m=len(str1)\n",
    "        n=len(str2)\n",
    "        ED,mat=align_this(str1, str2, m, n)\n",
    "        x,y= alignment(str1,str2,m,n,mat)\n",
    "        algn_X = algn_X + x\n",
    "        algn_Y = algn_Y + y\n",
    "        \n",
    "    else:\n",
    "        m=len(str1)\n",
    "        n=len(str2)\n",
    "        mid_y = compute_midpoint(str1,str2)\n",
    "        \n",
    "        Z1,algn_X1,algn_Y1 = Conquer(str1[0:m/2],str2[0:mid_y]) \n",
    "        Z2,algn_X2,algn_Y2 = Conquer(str1[m/2:m],str2[mid_y:n])\n",
    "        \n",
    "        ED = Z1+Z2\n",
    "        algn_X = algn_X1 + algn_X2\n",
    "        algn_Y = algn_Y1 + algn_Y2\n",
    "\n",
    "        \n",
    "    return ED,algn_X,algn_Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Edit Distance is:  11 \n",
      "\n",
      "Corresponding Alignment : \n",
      "\n",
      "+ev+apotranspiration\n",
      "mechano-recep---tion\n",
      "\n",
      "Time taken for execution 0:00:00.002000 seconds\n"
     ]
    }
   ],
   "source": [
    "str1=\"evapotranspiration\"\n",
    "str2=\"mechanoreception\"\n",
    "\n",
    "Ed,X,Y=Conquer(str1,str2)\n",
    "\n",
    "from datetime import datetime\n",
    "start_time = datetime.now()\n",
    "print\"The Edit Distance is: \", Ed ,\"\\n\"\n",
    "print \"Corresponding Alignment : \\n\"\n",
    "print X\n",
    "print Y\n",
    "end_time = datetime.now()\n",
    "print \"\\nTime taken for execution\",end_time - start_time, \"seconds\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "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.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}