<p>我认为在这种情况下,更深入地理解算法是很重要的。我不会给你一些伪代码,我会带你浏览算法的基本步骤,并向你展示你想要的数据是如何“编码”在最终的结果矩阵中的。当然,如果不需要滚动自己的算法,那么显然应该使用其他人的,如<a href="https://stackoverflow.com/a/10639697/577088">MattH suggests</a>!</p>
<h3>大局</h3>
<p>在我看来,这是<a href="http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm" rel="noreferrer">Wagner-Fischer algorithm</a>的一个实现。基本思想是计算“邻近”前缀之间的距离,取最小值,然后计算当前字符串对与之之间的距离。例如,假设有两个字符串<code>'i'</code>和<code>'h'</code>。让我们沿着矩阵的垂直和水平轴排列它们,如下所示:</p>
<pre><code> _ h
_ 0 1
i 1 1
</code></pre>
<p>这里,<code>'_'</code>表示一个空字符串,矩阵中的每个单元格对应一个编辑序列,该编辑序列接受一个输入(<code>''</code>或<code>'i'</code>)到一个输出(<code>''</code>或<code>'h'</code>)。</p>
<p>空字符串到任何长度为L的字符串的距离是L(需要L插入)。任何长度为L的字符串到空字符串的距离也是L(需要删除L)。它包含第一行和第一列中的值,这些值只是递增的。</p>
<p>从那里,您可以计算任意位置的值,方法是从左上、左上和左上的值中取最小值,然后添加一个,或者,如果字符串中该点的字母相同,则不改变左上角的值。对于上表中<code>(1, 1)</code>处的值,最小值是<code>0</code>处的<code>(0, 0)</code>,因此<code>(1, 1)</code>处的值是<code>1</code>,这是从<code>'i'</code>到<code>'h'</code>(一个替换)的最小编辑距离。所以一般来说,最小编辑距离总是在矩阵的右下角。</p>
<p>现在我们再做一个,比较<code>is</code>和<code>hi</code>。这里,矩阵中的每个细胞都对应一个编辑序列,该编辑序列将输入(<code>''</code>,<code>'i'</code>,或<code>'is'</code>)转换为输出(<code>''</code>,<code>'h'</code>,或<code>'hi'</code>)。</p>
<pre><code> _ h i
_ 0 1 2
i 1 1 #
s 2 # #
</code></pre>
<p>我们首先放大矩阵,使用<code>#</code>作为我们还不知道的值的占位符,然后通过递增来扩展第一行和第一列。这样,我们就可以开始计算上面标记为<code>#</code>的位置的结果。让我们从<code>(2, 1)</code>(in(row,column)开始,即row major表示法。在上、左上和左上值中,最小值是<code>1</code>。表中对应的字母是不同的——<code>s</code>和<code>h</code>——所以我们在最小值上加一个字母,得到<code>2</code>,然后继续。</p>
<pre><code> _ h i
_ 0 1 2
i 1 1 #
s 2 2 #
</code></pre>
<p>让我们转到<code>(1, 2)</code>处的值。现在情况有点不同了,因为表中对应的字母是相同的——它们都是<code>i</code>。这意味着我们可以选择在左上角单元格<em>中取值,而无需添加一个</em>。这里的指导直觉是,我们不必增加计数,因为同一个字母被添加到这个位置的两个字符串中。因为两条弦的长度都增加了一个,所以我们是对角移动的。</p>
<pre><code> _ h i
_ 0 1 2
i 1 1 1
s 2 2 #
</code></pre>
<p>最后一个空牢房,一切恢复正常。对应的字母是<code>s</code>和<code>i</code>,因此我们再次取最小值并加上一个,得到<code>2</code>:</p>
<pre><code> _ h i
_ 0 1 2
i 1 1 1
s 2 2 2
</code></pre>
<p>如果我们继续这个过程,用<code>is</code>和<code>hi</code>--<code>isnt</code>(忽略标点符号)和<code>hint</code>开头的两个更长的单词,就会得到这个表:</p>
<pre><code> _ h i n t
_ 0 1 2 3 4
i 1 1 1 2 3
s 2 2 2 2 3
n 3 3 3 2 3
t 4 4 4 3 2
</code></pre>
<p>这个矩阵稍微复杂一些,但是这里的最后最小编辑距离仍然是<code>2</code>,因为这两个字符串的最后两个字母是相同的。方便!</p>
<h3>重新创建编辑序列</h3>
<p>那么我们如何从这个表中提取编辑类型呢?关键是要认识到表上的移动对应于特定类型的编辑。例如,从<code>(0, 0)</code>向右移动到<code>(0, 1)</code>将我们从<code>_ -> _</code>带到无需编辑,<code>_ -> h</code>,需要一次编辑,一次插入。同样,从<code>(0, 0)</code>到<code>(1, 0)</code>的向下移动将我们从不需要编辑的<code>_ -> _</code>带到<code>i -> _</code>,需要一次编辑,一次删除。最后,从<code>(0, 0)</code>到<code>(1, 1)</code>的对角线移动将我们从不需要编辑的<code>_ -> _</code>移动到<code>i -> h</code>,需要一次编辑,一次替换。</p>
<p>所以现在我们所要做的就是反转我们的步骤,从左上、左上和左上三个单元格中跟踪局部最小值,回到原点<code>(0, 0)</code>,记住如果当前值与最小值相同,那么我们必须转到左上角的单元格,因为这是唯一一种不增加编辑距离的移动。</p>
<p>下面详细描述了您可以采取的步骤。从完成矩阵的右下角开始,重复以下步骤,直到到达左上角:</p>
<ol>
<li>看看左上角邻近的牢房。如果不存在,则转到步骤3。如果单元格确实存在,请注意存储在其中的值。</li>
<li>左上角单元格中的值是否等于当前单元格中的值?如果是,请执行以下操作:
<ul>
<li>记录空操作(即<code>Equal</code>)。在这种情况下不需要编辑,因为此位置的字符相同。</li>
<li>更新当前单元格,向上和向左移动。</li>
<li>返回步骤1。</li>
</ul></li>
<li>这里有很多分支:
<ul>
<li>如果左边没有单元格,上面也没有单元格,那么你就在左上角,算法已经完成了。</li>
<li>如果左侧没有单元格,请转到步骤4。(这将继续循环,直到到达左上角。)</li>
<li>如果上面没有单元格,请转到步骤5。(这将继续循环,直到到达左上角。)</li>
<li>否则,请在左侧单元格、左上方单元格和上方单元格之间进行三种方式的比较。选择值最小的那个。如果有多个候选者,您可以随机选择一个;它们在这个阶段都是有效的。(它们对应于具有相同总编辑距离的不同编辑路径。)
<ul>
<li>如果您选择了上面的单元格,请转到步骤4。</li>
<li>如果你选择左边的单元格,请转到步骤5。</li>
<li>如果选择左上角的单元格,请转到步骤6。</li>
</ul></li>
</ul></li>
<li>你在向上移动。执行以下操作:
<ul>
<li>在当前单元格中记录输入字符的删除。</li>
<li>更新当前单元格,向上移动。</li>
<li>返回步骤1。</li>
</ul></li>
<li>你在向左移动。执行以下操作:
<ul>
<li>在当前单元格中记录输出字符的插入。</li>
<li>更新当前单元格,向左移动。</li>
<li>返回步骤1。</li>
</ul></li>
<li>你在斜向移动。执行以下操作:
<ul>
<li>记录当前单元格中输入字符替换为当前单元格中输出字符的情况。</li>
<li>更新当前单元格,向上和向左移动。</li>
<li>返回步骤1。</li>
</ul></li>
</ol>
<h3>组合起来</h3>
<p>在上面的示例中,有两种可能的路径:</p>
<pre><code>(4, 4) -> (3, 3) -> (2, 2) -> (1, 2) -> (0, 1) -> (0, 0)
</code></pre>
<p>以及</p>
<pre><code>(4, 4) -> (3, 3) -> (2, 2) -> (1, 1) -> (0, 0)
</code></pre>
<p>逆转他们,我们得到</p>
<pre><code>(0, 0) -> (0, 1) -> (1, 2) -> (2, 2) -> (3, 3) -> (4, 4)
</code></pre>
<p>以及</p>
<pre><code>(0, 0) -> (1, 1) -> (2, 2) -> (3, 3) -> (4, 4)
</code></pre>
<p>所以对于第一个版本,我们的第一个操作是向右移动,即插入。插入的字母是<code>h</code>,因为我们正在从<code>isnt</code>移动到<code>hint</code>。(这对应于详细输出中的<code>Insert, h</code>。)我们的下一个操作是对角线移动,即替换或禁止操作。在这种情况下,这是禁止操作,因为两个位置的编辑距离相同(即字母相同)。所以<code>Equal, i, i</code>。然后向下移动,对应于删除。删除的字母是<code>s</code>,因为我们再次从<code>isnt</code>移动到<code>hint</code>。(通常,要插入的字母来自输出字符串,而要删除的字母来自In把字符串放进去。)这就是<code>Delete, s</code>。然后两个对角线移动值不变:<code>Equal, n, n</code>和<code>Equal, t, t</code>。</p>
<p>结果是:</p>
<pre><code>Insert, h
Equal, i, i
Delete, s
Equal, n, n
Equal, t, t
</code></pre>
<p>在<code>isnt</code>上执行以下指令:</p>
<pre><code>isnt (No change)
hisnt (Insertion)
hisnt (No change)
hint (Deletion)
hint (No change)
hint (No change)
</code></pre>
<p>总编辑距离为2。</p>
<p>我将留下第二条最小路径作为练习。请记住,这两条路径是完全等价的;它们可能不同,但它们将导致相同的最小编辑距离2,因此是完全可互换的。在任何一点,当你通过矩阵反向工作时,如果你看到两个不同的可能的局部极小值,你可以选择其中一个,并且最终的结果保证是正确的</p>
<p>一旦你摸索了这一切,就不难编码了。在这种情况下,关键是首先要深入理解算法。一旦你做到了,把它编码起来就轻而易举了。</p>
<h3>累积与重建</h3>
<p>最后,您可以选择在填充矩阵时累积编辑。在这种情况下,矩阵中的每个单元格都可以是一个元组:<code>(2, ('ins', 'eq', 'del', 'eq', 'eq'))</code>。您可以增加长度,<em>和</em>附加对应于从最小先前状态移动的操作。这就消除了回溯,从而降低了代码的复杂性;但它占用了额外的内存。如果执行此操作,最终编辑序列将与最终编辑距离一起显示在矩阵的右下角。</p>