📄 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="lcs: Longest (maximum) common subsequence"> <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>lcs: Longest (maximum) common subsequence</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, edStr, 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">lcs: Longest (maximum) common subsequence
Usage: [count, edPath, edStr, edTable] = lcsm(a, b, plotOpt)
a: input string 1
b: input string 2
plotOpt: plot option
count: count of LCS
edPath: optimal path of dynamical programming through the lcs table
edStr: LCS string
edTable: LCS table for applying dynamic programming
Type "lcs" 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)"></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 edPathPlot(str1, str2, lcsPath, lcsStr, lcsTable, prevx, prevy)</a></li><li><a href="#_sub2" 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, edStr, edTable] = editDistance(a, b, substituteCost, plotOpt)</a>0002 <span class="comment">%lcs: Longest (maximum) common subsequence</span>0003 <span class="comment">% Usage: [count, edPath, edStr, edTable] = lcsm(a, b, 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">% count: count of LCS</span>0008 <span class="comment">% edPath: optimal path of dynamical programming through the lcs table</span>0009 <span class="comment">% edStr: LCS string</span>0010 <span class="comment">% edTable: LCS table for applying dynamic programming</span>0011 <span class="comment">%</span>0012 <span class="comment">% Type "lcs" for a self-demo.</span>0013 0014 <span class="comment">% Roger Jang, 981226, 990409, 20060528</span>0015 0016 <span class="keyword">if</span> nargin<1, <a href="#_sub2" class="code" title="subfunction selfdemo">selfdemo</a>; <span class="keyword">return</span>; <span class="keyword">end</span>0017 <span class="keyword">if</span> nargin<3, substituteCost=2; <span class="keyword">end</span>0018 <span class="keyword">if</span> nargin<4, plotOpt=0; <span class="keyword">end</span>0019 0020 a = a(:).'; m = length(a);0021 b = b(:).'; n = length(b);0022 edTable = zeros(m+1, n+1);0023 edTable(:,1)=0:m;0024 edTable(1,:)=(0:n)';0025 prevx = zeros(m+1, n+1);0026 prevy = zeros(m+1, n+1);0027 cost=zeros(3,1);0028 <span class="comment">% Find LCS using dynamic programming</span>0029 <span class="keyword">for</span> i=1:m,0030 <span class="keyword">for</span> j = 1:n,0031 <span class="keyword">if</span> a(i)==b(j)0032 cost=0;0033 <span class="keyword">else</span>0034 cost=substituteCost;0035 <span class="keyword">end</span>0036 cost(1)=edTable(i, j)+cost;0037 cost(2)=edTable(i, j+1)+1;0038 cost(3)=edTable(i+1, j)+1;0039 [edTable(i+1,j+1), index]=min(cost);0040 <span class="keyword">switch</span> index0041 <span class="keyword">case</span> 10042 prevx(i+1,j+1) = i;0043 prevy(i+1,j+1) = j;0044 <span class="keyword">case</span> 20045 prevx(i+1,j+1) = i;0046 prevy(i+1,j+1) = j+1;0047 <span class="keyword">case</span> 30048 prevx(i+1,j+1) = i+1;0049 prevy(i+1,j+1) = j;0050 <span class="keyword">end</span>0051 <span class="keyword">end</span>0052 <span class="keyword">end</span>0053 0054 <span class="comment">% Get rid of initial conditions</span>0055 edTable = edTable(2:<span class="keyword">end</span>, 2:end);0056 prevx = prevx(2:<span class="keyword">end</span>, 2:end)-1;0057 prevy = prevy(2:<span class="keyword">end</span>, 2:end)-1;0058 0059 <span class="comment">% ====== Return length of LCS string</span>0060 minDist = edTable(m, n);0061 0062 <span class="comment">% ====== Return the optimal path of the dynamical programming</span>0063 <span class="keyword">if</span> nargout>1 | plotOpt0064 now = [m, n];0065 prev = [prevx(now(1), now(2)), prevy(now(1), now(2))];0066 edPath = now;0067 <span class="keyword">while</span> all(prev>0),0068 now = prev;0069 prev = [prevx(now(1), now(2)), prevy(now(1), now(2))];0070 edPath = [edPath; now];0071 <span class="keyword">end</span> 0072 edPath = flipud(edPath);0073 <span class="keyword">end</span>0074 0075 <span class="comment">% ====== Return the LCS string</span>0076 <span class="keyword">if</span> nargout>2 | plotOpt <span class="comment">% return LCS string</span>0077 temp = edTable((edPath(:,2)-1)*m+edPath(:,1)); <span class="comment">% LCS count along the path</span>0078 temp = [0; temp];0079 index = find(diff(temp));0080 edStr = a(edPath(index,1));0081 <span class="keyword">end</span>0082 0083 <span class="comment">% ====== Plot</span>0084 <span class="keyword">if</span> plotOpt0085 <a href="#_sub1" class="code" title="subfunction edPathPlot(str1, str2, lcsPath, lcsStr, lcsTable, prevx, prevy)">edPathPlot</a>(a, b, edPath, edStr, edTable, prevx, prevy);0086 <span class="keyword">end</span>0087 0088 0089 <span class="comment">% ====== edPathPlot: Plot the path of ED</span>0090 <a name="_sub1" href="#_subfunctions" class="code">function edPathPlot(str1, str2, lcsPath, lcsStr, lcsTable, prevx, prevy)</a>0091 m = length(str1);0092 n = length(str2);0093 <span class="comment">%[xx, yy] = meshgrid(1:m, 1:n);</span>0094 <span class="comment">%plot(xx(:), yy(:), '.');</span>0095 plot(nan, nan); axis([0 m+1 0 n+1]); box on;0096 set(gca, <span class="string">'xtick'</span>, 1:m);0097 set(gca, <span class="string">'ytick'</span>, 1:n);0098 set(gca, <span class="string">'xticklabel'</span>, str1(:));0099 set(gca, <span class="string">'yticklabel'</span>, str2(:));0100 xlabel([<span class="string">'String1 = '</span>, str1]);0101 ylabel([<span class="string">'String2 = '</span>, str2]);0102 title([<span class="string">'LCS table and LCS path; with LCS = '</span>, lcsStr]);0103 <span class="comment">% === Plot LCS table</span>0104 <span class="keyword">for</span> i = 1:m0105 <span class="keyword">for</span> j = 1:n0106 text(i, j, int2str(lcsTable(i,j)), <span class="string">'hori'</span>, <span class="string">'center'</span>);0107 <span class="keyword">end</span>0108 <span class="keyword">end</span>0109 <span class="comment">% === Plot prevPos</span>0110 <span class="keyword">for</span> i=2:m+10111 <span class="keyword">for</span> j=2:n+10112 now=i+j*sqrt(-1);0113 next=prevx(i-1,j-1)+1+(prevy(i-1,j-1)+1)*sqrt(-1);0114 arrowPlot(now, next, [1 0 0]);0115 <span class="keyword">end</span>0116 <span class="keyword">end</span>0117 <span class="comment">% === Plot LCS path</span>0118 <span class="keyword">for</span> i = 1:size(lcsPath,1)-1,0119 line(lcsPath(i:i+1, 1), lcsPath(i:i+1, 2));0120 <span class="keyword">end</span>0121 <span class="comment">% === Circle matched elements</span>0122 temp = lcsTable((lcsPath(:,2)-1)*m+lcsPath(:,1)); <span class="comment">% LCS count along the path</span>0123 temp = [0; temp];0124 index = find(diff(temp));0125 match_point = lcsPath(index, :);0126 line(match_point(:,1), match_point(:, 2), <span class="string">'marker'</span>, <span class="string">'o'</span>, <span class="string">'markersize'</span>, 15, <span class="string">'color'</span>, <span class="string">'r'</span>, <span class="string">'linestyle'</span>, <span class="string">'none'</span>);0127 0128 0129 <span class="comment">% ====== Self demo</span>0130 <a name="_sub2" href="#_subfunctions" class="code">function selfdemo</a>0131 str1=<span class="string">'execution'</span>;0132 str2=<span class="string">'intention'</span>;0133 substituteCost=2;0134 plotOpt=1;0135 [minDist, edPath, edStr, 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 + -