📄 editdistance.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd"><html><head> <title>Description of editDistance</title> <meta name="keywords" content="editDistance"> <meta name="description" content="editDistance: Edit distance (ED) via dynamic programming"> <meta http-equiv="Content-Type" content="text/html; charset=big5"> <meta name="generator" content="m2html © 2003 Guillaume Flandin"> <meta name="robots" content="index, follow"> <link type="text/css" rel="stylesheet" href="../m2html.css"></head><body><a name="_top"></a><div><a href="../index.html">Home</a> > <a href="index.html">dcpr</a> > editDistance.m</div><!--<table width="100%"><tr><td align="left"><a href="../index.html"><img alt="<" border="0" src="../left.png"> Master index</a></td><td align="right"><a href="index.html">Index for dcpr <img alt=">" border="0" src="../right.png"></a></td></tr></table>--><h1>editDistance</h1><h2><a name="_name"></a>PURPOSE <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="box"><strong>editDistance: Edit distance (ED) via dynamic programming</strong></div><h2><a name="_synopsis"></a>SYNOPSIS <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="box"><strong>function [minDist, edPath, edTable] = editDistance(a, b, substituteCost, plotOpt) </strong></div><h2><a name="_description"></a>DESCRIPTION <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="fragment"><pre class="comment">editDistance: Edit distance (ED) via dynamic programming
Usage: [minDist, edPath, edTable] = editDistance(a, b, substituteCost, plotOpt)
a: input string 1
b: input string 2
plotOpt: plot option
minDist: minimum edit distance
edPath: optimal path of dynamical programming through the ED table
edTable: ED table for applying dynamic programming
Type "editDistance" for a self-demo.</pre></div><!-- crossreference --><h2><a name="_cross"></a>CROSS-REFERENCE INFORMATION <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2>This function calls:<ul style="list-style-image:url(../matlabicon.gif)"><li><a href="dpPathPlot4strMatch.html" class="code" title="function dpPathPlot4strMatch(str1, str2, lcsPath, lcsTable, prevx, prevy)">dpPathPlot4strMatch</a> dpPathPlot4strMatch: Plot the path of dynamic programming for string match.</li></ul>This function is called by:<ul style="list-style-image:url(../matlabicon.gif)"></ul><!-- crossreference --><h2><a name="_subfunctions"></a>SUBFUNCTIONS <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><ul style="list-style-image:url(../matlabicon.gif)"><li><a href="#_sub1" class="code">function selfdemo</a></li></ul><h2><a name="_source"></a>SOURCE CODE <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="fragment"><pre>0001 <a name="_sub0" href="#_subfunctions" class="code">function [minDist, edPath, edTable] = editDistance(a, b, substituteCost, plotOpt)</a>0002 <span class="comment">%editDistance: Edit distance (ED) via dynamic programming</span>0003 <span class="comment">% Usage: [minDist, edPath, edTable] = editDistance(a, b, substituteCost, plotOpt)</span>0004 <span class="comment">% a: input string 1</span>0005 <span class="comment">% b: input string 2</span>0006 <span class="comment">% plotOpt: plot option</span>0007 <span class="comment">% minDist: minimum edit distance</span>0008 <span class="comment">% edPath: optimal path of dynamical programming through the ED table</span>0009 <span class="comment">% edTable: ED table for applying dynamic programming</span>0010 <span class="comment">%</span>0011 <span class="comment">% Type "editDistance" for a self-demo.</span>0012 0013 <span class="comment">% Roger Jang, 20081008</span>0014 0015 <span class="keyword">if</span> nargin<1, <a href="#_sub1" class="code" title="subfunction selfdemo">selfdemo</a>; <span class="keyword">return</span>; <span class="keyword">end</span>0016 <span class="keyword">if</span> nargin<3, substituteCost=2; <span class="keyword">end</span>0017 <span class="keyword">if</span> nargin<4, plotOpt=0; <span class="keyword">end</span>0018 0019 a=a(:)'; m=length(a);0020 b=b(:)'; n=length(b);0021 edTable=zeros(m, n);0022 prevx=zeros(m, n);0023 prevy=zeros(m, n);0024 cost=zeros(3,1);0025 <span class="comment">% Compute the first element</span>0026 edTable(1,1)=(a(1)~=b(1))*substituteCost;0027 prevx(1,1)=0; <span class="comment">% not plotted</span>0028 prevy(1,1)=0; <span class="comment">% not plotted</span>0029 <span class="comment">% Compute the first row & column</span>0030 <span class="keyword">for</span> i=2:m0031 cost=(a(i)~=b(1))*substituteCost;0032 [edTable(i,1), index]=min([edTable(i-1,1)+1, cost+i-1]);0033 <span class="keyword">if</span> index==10034 prevx(i,1)=i-1;0035 prevy(i,1)=1;0036 <span class="keyword">else</span>0037 prevx(i,1)=i-1;0038 prevy(i,1)=0;0039 <span class="keyword">end</span>0040 <span class="keyword">end</span>0041 <span class="keyword">for</span> j=2:n0042 cost=(a(1)~=b(j))*substituteCost;0043 [edTable(1,j), index]=min([edTable(1,j-1)+1, cost+j-1]);0044 <span class="keyword">if</span> index==10045 prevx(1,j) = 1;0046 prevy(1,j) = j-1;0047 <span class="keyword">else</span>0048 prevx(1,j) = 0;0049 prevy(1,j) = j-1;0050 <span class="keyword">end</span>0051 <span class="keyword">end</span>0052 <span class="comment">% Compute all the other elements</span>0053 <span class="keyword">for</span> i=2:m,0054 <span class="keyword">for</span> j=2:n,0055 cost=(a(i)~=b(j))*substituteCost;0056 cost(1)=edTable(i-1, j-1)+cost;0057 cost(2)=edTable(i-1, j)+1;0058 cost(3)=edTable(i, j-1)+1;0059 [edTable(i,j), index]=min(cost);0060 <span class="keyword">switch</span> index0061 <span class="keyword">case</span> 10062 prevx(i,j)=i-1;0063 prevy(i,j)=j-1;0064 <span class="keyword">case</span> 20065 prevx(i,j)=i-1;0066 prevy(i,j)=j;0067 <span class="keyword">case</span> 30068 prevx(i,j)=i;0069 prevy(i,j)=j-1;0070 <span class="keyword">end</span>0071 <span class="keyword">end</span>0072 <span class="keyword">end</span>0073 0074 <span class="comment">% ====== Return length of ED string</span>0075 minDist = edTable(m, n);0076 0077 <span class="comment">% ====== Return the optimal path of the dynamical programming</span>0078 <span class="keyword">if</span> nargout>1 | plotOpt0079 now = [m, n];0080 prev = [prevx(now(1), now(2)), prevy(now(1), now(2))];0081 edPath = now;0082 <span class="keyword">while</span> all(prev>0)0083 now = prev;0084 prev = [prevx(now(1), now(2)), prevy(now(1), now(2))];0085 edPath = [edPath; now];0086 <span class="keyword">end</span> 0087 edPath = flipud(edPath);0088 <span class="keyword">end</span>0089 0090 <span class="comment">% ====== Plot</span>0091 <span class="keyword">if</span> plotOpt0092 <a href="dpPathPlot4strMatch.html" class="code" title="function dpPathPlot4strMatch(str1, str2, lcsPath, lcsTable, prevx, prevy)">dpPathPlot4strMatch</a>(a, b, edPath, edTable, prevx, prevy);0093 title(sprintf(<span class="string">'Min. edit distance = %d'</span>, edTable(<span class="keyword">end</span>, end)));0094 <span class="keyword">end</span>0095 0096 <span class="comment">% ====== Self demo</span>0097 <a name="_sub1" href="#_subfunctions" class="code">function selfdemo</a>0098 str1=<span class="string">'execution'</span>;0099 str2=<span class="string">'intention'</span>;0100 substituteCost=2;0101 plotOpt=1;0102 [minDist, edPath, edTable] = feval(mfilename, str1, str2, substituteCost, plotOpt);</pre></div><hr><address>Generated on Thu 30-Oct-2008 12:53:56 by <strong><a href="http://www.artefact.tk/software/matlab/m2html/">m2html</a></strong> © 2003</address></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -