在 Julia 中计算 Levenshtein 距离时记录所有最佳序列比对

Question

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

从矩阵的右下角回溯时，求最优值容易，但求最优操作顺序，如插入或删除，有点难。

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

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

Answer 1

我不确定我是否得到了你的问题，但无论如何，Julia 中的 vectors 是动态数据结构，因此你始终可以使用适当的函数来扩展它，例如 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()

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

Answer 2

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

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 矩阵向后并读取每一步的动作。跟踪 i 和 j 允许通过查看当前步骤中位于 i 的 string1 和位于 j 的 string2 中的哪个元素来读取确切的替换。无法避免保留像 c 这样的矩阵，因为在算法结束时，有关中间选择的信息（由 min 完成）将丢失。

在 Julia 中计算 Levenshtein 距离时记录所有最佳序列比对

Record all optimal sequence alignments when calculating Levenshtein distance in Julia

combinations

levenshtein-distance

julia

sequence-alignment