2

我正在使用 Julia 中的 Wagner–Fischer 算法研究 Levenshtein 距离。

得到最优值很容易，但在从矩阵的右下角回溯时，得到最优的操作顺序就有点困难了，比如插入或删除。

我可以记录每个 d[i][j] 的指针信息，但它可能会给我 3 个方向让我回到 d[i-1][j-1] 进行替换，d[i-1][j]用于删除和 d[i][j-1] 用于插入。所以我试图得到所有给我最佳 Levenshtein 距离的操作集的组合。

看来我可以将一个操作集存储在一个数组中，但是我不知道所有组合的总数以及长度，所以我很难定义一个数组来存储枚举期间的操作集过程。如何在存储前一个数组的同时生成数组？或者我应该使用数据框？

4

2 回答 2

2

如果您实施 Wagner-Fischer 算法，在某个时候，您会选择三个替代方案中的最小值（请参阅 Wikipedia 伪代码）。此时，您将选择的备选方案保存在另一个矩阵中。使用如下语句：

c[i,j] = indmin([d[i-1,j]+1,d[i,j-1]+1,d[i-1,j-1]+1])
# indmin returns the index of the minimum element in a collection.

现在c[i,j]根据删除、插入或替换包含 1,2 或 3。在计算结束时，您使最终的d矩阵元素达到最小距离，然后您c向后跟随矩阵并读取每一步的动作。通过查看当前步骤中 string1和 string2中的哪个元素来跟踪i并j允许读取确切的替换。无法避免保持矩阵 like ，因为在算法结束时，有关中间选择（由 完成）的信息将丢失。ijcmin

于 2015-11-17T19:31:12.383 回答
0

我不确定我是否得到了您的问题，但无论如何，vectors在 Julia 中是动态数据结构，因此您始终可以使用适当的函数来扩展它，例如pull!(), append!()，preapend!()也可以reshape()将结果向量变为所需大小的数组。
但可以使用sparse()矩阵获得上述情况的一种特殊方法：

import Base.zero
Base.zero(ASCIIString)=""
module GSparse
  export insertion,deletion,substitude,result
  s=sparse(ASCIIString[])
  deletion(newval::ASCIIString)=begin
    global s
    s.n+=1
    push!(s.colptr,last(s.colptr))
    s[s.m,s.n]=newval
  end
  insertion(newval::ASCIIString)=begin
    global s
    s.m+=1
    s[s.m,s.n]=newval
  end
  substitude(newval::ASCIIString)=begin
    global s
    s.n+=1
    s.m+=1
    push!(s.colptr,last(s.colptr))
    s[s.m,s.n]=newval
  end
  result()=begin
    global s
    ret=zeros(ASCIIString,size(s))
    le=length(s)
    for (i = 1:le)
      ret[le-i+1]=s[i]
    end
    ret
  end
end
using GSparse
insertion("test");
insertion("testo");
insertion("testok");
substitude("1estok");
deletion("1stok");
result()

我喜欢这种方法，因为对于大文本，您可以有许多零元素。我也以正向填充数据结构并通过反转创建结果。

于 2015-11-17T08:40:16.967 回答