{"cells":[{"metadata":{"trusted":true},"cell_type":"code","source":"import numpy as np\nimport pandas as pd","execution_count":null,"outputs":[]},{"metadata":{"id":"3ARF78qsH4zr"},"cell_type":"markdown","source":"# Introduction"},{"metadata":{"id":"XFqftQTWH7Ly"},"cell_type":"markdown","source":"Goal:\n\n* evaluate spelling similarity of two string \n\n\n\nStep:\n\n* initial state : the word we're transforming\n\n* operators : delete,switch,replace,insert (Note that replace is equal to delete + insert)\n\n* goal state : the word we're trying to get to\n\n* path cost : what we want to minimize --- the number of edits\n\n\nMore application :\n\n* DNA, spell correction and more\n\n\nDetail introduction :\n\n* https://web.stanford.edu/class/cs124/lec/med.pdf"},{"metadata":{"id":"mGrAk8IkJU45"},"cell_type":"markdown","source":"# Algorithms"},{"metadata":{"id":"G8fP_9M-Gcgs"},"cell_type":"markdown","source":"### Dynamic Programming(Levenshstein)"},{"metadata":{"id":"zu_m9oXIJIYZ"},"cell_type":"markdown","source":"$$\\text{Initialization}$$\n\n\\begin{align}\nD[0,0] &= 0 \\\\\nD[i,0] &= D[i-1,0] + del\\_cost(source[i]) \\tag{1}\\\\\nD[0,j] &= D[0,j-1] + ins\\_cost(target[j]) \\\\\n\\end{align}"},{"metadata":{"id":"b5uH45uaJLUJ"},"cell_type":"markdown","source":"\n$$\\text{Per Cell Operations}$$\n\\begin{align}\n \\\\\nD[i,j] =min\n\\begin{cases}\nD[i-1,j] + del\\_cost\\\\\nD[i,j-1] + ins\\_cost\\\\\nD[i-1,j-1] + \\left\\{\\begin{matrix}\nrep\\_cost; & if src[i]\\neq tar[j]\\\\\n0 ; & if src[i]=tar[j]\n\\end{matrix}\\right.\n\\end{cases}\n\\tag{2}\n\\end{align}"},{"metadata":{"id":"0uwDWlHVGc4E","trusted":false},"cell_type":"code","source":"# if we set the parameters to 1,1,2, the method is calledd levenshstein distance\n\ndef dp_solver(word,target,del_cost=1,ins_cost=1,rep_cost=2):\n\n  # initialize\n  m=len(word)\n  n=len(target)\n  D=np.zeros((m+1,n+1))\n  for i in range(m+1):\n    D[i,0]=i\n  for j in range(n+1):\n    D[0,j]=j\n\n  for i in range(1,m+1):\n    for j in range(1,n+1):\n      if word[i-1]!=target[j-1]:\n        rp=rep_cost\n      else:\n        rp=0\n      \n      D[i,j]=min([D[i-1,j]+del_cost,D[i,j-1]+ins_cost,D[i-1,j-1]+rp])\n\n  min_dis=D[m,n]\n\n  return D,min_dis","execution_count":null,"outputs":[]},{"metadata":{"id":"H-rATsf-Gc1L","outputId":"7460a417-845e-48c7-b7c8-c79697ab5bdf","trusted":false},"cell_type":"code","source":"word='intention'\ntarget='execution'\n\nmatrix,min_dis=dp_solver(word,target)\n\nprint('minimum distance edit number :' ,min_dis)\n\npd.DataFrame(matrix,columns=['#']+[c for c in target],\n             index=['#']+[c for c in word])","execution_count":null,"outputs":[]},{"metadata":{"id":"EGnhGZCOOXbs"},"cell_type":"markdown","source":" \n What can't we know from the DP table? :\n \n * I N T E & N T I O N\n\n * & E X E C U T I O N\n\n * I -> & : delete  (cost : 1)\n\n * N -> E : replace  (cost : 2)\n\n * T -> X : replace  (cost : 2)\n\n * & -> C : insert  (cost : 2)\n\n * N -> U : replace  (cost: 1 )\n\n\n Use BackTrace solve this problem"},{"metadata":{"id":"XgWinJeDGfLT"},"cell_type":"markdown","source":"### BackTrace"},{"metadata":{"id":"kk0_mGr1QZRZ"},"cell_type":"markdown","source":"* We often need to align each charactor of the two strings to each other \n\n* Every time we enter a cell, remember where we came from \n\n* When we reach the end, trace back the path from the upper right corner to read off the alignment"},{"metadata":{"id":"ASYFuddURWrA"},"cell_type":"markdown","source":"$$\\text{Base Conditions}$$\n\n\\begin{align}\nD[i,0] &= i \\ \\ \\ D[0,j] = j \n\\end{align}"},{"metadata":{"id":"HgpKwpZKR4g_"},"cell_type":"markdown","source":"$$\\text{Recurrence Relation}$$\n\n\\begin{align}\n \\\\\nD[i,j] =min\n\\begin{cases}\nD[i-1,j] + del\\_cost\\\\\nD[i,j-1] + ins\\_cost\\\\\nD[i-1,j-1] + \\left\\{\\begin{matrix}\nrep\\_cost; & if src[i]\\neq tar[j]\\\\\n0 ; & if src[i]=tar[j]\n\\end{matrix}\\right.\n\\end{cases}\n\\tag{2}\n\\end{align}"},{"metadata":{"id":"ethfIMVMSKpm"},"cell_type":"markdown","source":"\\begin{align}\n \\\\\nptr[i,j] =\n\\begin{cases}\nLEFT(insert)\\\\\nDOWN(delete)\\\\\nDIAG(replace)\n\\end{cases}\n\\end{align}"},{"metadata":{"id":"QeEa1q_VGf-d","trusted":false},"cell_type":"code","source":"def BackTraceSolver(src,tar,del_cost=1,ins_cost=1,rep_cost=2):\n  m=len(src)\n  n=len(tar)\n\n  D=np.zeros((m+1,n+1))\n  \n  for i in range(m+1):\n    D[i,0]=i\n  for j in range(n+1):\n    D[0,j]=j\n\n  prt={}\n  for i in range(1,m+1):\n    for j in range(1,n+1):\n      if src[i-1]!=tar[j-1]:\n        rp=rep_cost\n      else:\n        rp=0\n\n      search={}\n      search[(i-1,j)]=D[i-1,j]+del_cost\n      search[(i,j-1)]=D[i,j-1]+ins_cost\n      search[(i-1,j-1)]=D[i-1,j-1]+rp\n\n\n      D[i,j]=min(search.values())\n\n      re_search={val:key for key,val in search.items()}\n\n      if (search[(i-1,j)]!=search[(i,j-1)]!=search[(i-1,j-1)]):\n        d_i,d_j=re_search[D[i,j]]\n        #record path\n        prt[(i,j)]=(d_i,d_j)\n\n      else:\n        #record path\n        prt[(i,j)]=(i-1,j-1)\n\n  # trace back from last point\n  trace_back=[]\n  last_pt=(m,n)\n  while True:\n    try :\n      prt[last_pt]\n    except:\n      trace_back.append(last_pt)\n      break\n    trace_back.append(last_pt)\n    last_pt=prt[last_pt]\n\n\n  min_dis=D[m,n]\n\n  return D,min_dis,trace_back","execution_count":null,"outputs":[]},{"metadata":{"id":"DiP09JBPGgtb","trusted":false},"cell_type":"code","source":"src='intention'\ntar='execution'\n\nmatrix,min_ids,trace_back=BackTraceSolver(src,tar)","execution_count":null,"outputs":[]},{"metadata":{"id":"-p4xG45Nbfo0","outputId":"c5452ef1-f792-4afa-a257-c17b825187ab","trusted":false},"cell_type":"code","source":"trace_back","execution_count":null,"outputs":[]},{"metadata":{"id":"B4fIc3TGc0xJ","trusted":false},"cell_type":"code","source":"trace_matrix=matrix.copy()\nfor item in trace_back:\n  i,j=item\n  trace_matrix[i][j]=1e-7","execution_count":null,"outputs":[]},{"metadata":{"id":"IxFXT8Ngdh5E","outputId":"d3bee96e-aa90-434c-a4d3-7df7bb00db41","trusted":false},"cell_type":"code","source":"df=pd.DataFrame(trace_matrix,columns=['#']+[c for c in target],\n             index=['#']+[c for c in word])\ndf","execution_count":null,"outputs":[]},{"metadata":{"id":"AhfkHpmnil79"},"cell_type":"markdown","source":"* Show the result by checking the table and print"},{"metadata":{"id":"msngHyaeiLn1","outputId":"91e2f294-fc8f-48b8-d291-35d5e7c7421e","trusted":false},"cell_type":"code","source":"print('i->#') #delete\nprint('n->e') #replace\nprint('t->x') #replace\nprint('e->e,c') #insert\nprint('n->u') #replace\nprint('tion->tion') #same","execution_count":null,"outputs":[]},{"metadata":{"id":"-ebyXb9KjruE"},"cell_type":"markdown","source":"heatmap"},{"metadata":{"id":"a-bWb_Xxk3O7"},"cell_type":"markdown","source":"* left : insert\n\n* up : delete\n\n* diag : replace"},{"metadata":{"id":"tljGkvwKjqrv","outputId":"2d887c4b-7c6d-42fc-a005-b93631ea3b8c","trusted":false},"cell_type":"code","source":"import seaborn as sns\n\nsns.heatmap(data=df)","execution_count":null,"outputs":[]},{"metadata":{"id":"Tb1pY6Kpju-p","trusted":false},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat":4,"nbformat_minor":4}