如何知道计算字符串Levenshtein距离的操作？

Question

使用函数stringdist，我可以计算两个字符串之间的Levenshtein距离:它计算将一个字符串转换为另一个字符串所需的删除、插入和替换次数。例如, stringdist("abc abc","abcd abc") = 1，因为在第二个字符串中插入了字符“d”。

是否有可能知道用于获得两个字符串之间的Levenshtein距离的操作？或者知道不同的字符（在这个例子中只有“d”）是什么吗？ 谢谢。

library(stringdist)
stringdist("abc abc","abcde acc") = 3

我想知道：

• "d"已插入

• "e"已插入

• "b"被替换为"c"

更简单地说，我想要列表（“d”，“e”，“c”）。

- yaki

---

莱文斯坦编辑路径不一定是唯一的：通常有多个等长且最小的编辑序列，可以将一个字符串转换为另一个字符串。 - user4117783

Answer 1

使用adist()函数，可以检索出执行的操作：

drop(attr(adist("abc abc","abcde acc", count = TRUE), "counts"))

ins del sub 
  2   0   1 

来自 ?adist:

如果counts为TRUE，则转换计数将作为此矩阵的“counts”属性返回，以三维数组形式返回，其中的维度对应于x元素、y元素和转换类型（插入、删除和替换）。

- tmfmnk

---

谢谢，这对我很有帮助！你知道是否有一个函数可以直接知道与这些操作相应的字符吗？否则，我可以尝试使用attr(adist("abda cc","abc abc", count = TRUE),"trafos") #= "MMSDMSIM"创建一个函数，其中M=match，S=substitute，D=delete，I=insert。 - yaki

不知道有没有什么便捷的函数可以做到这一点。但是，我认为玩弄'转换'会让您达到预期的结果。 - tmfmnk

Answer 2

这被称为Needleman-Wunsch算法，它同时计算两个字符串之间的距离以及所谓的回溯，从而可以重构对齐结果。

由于这个问题主要出现在比较生物序列时，因此这个算法（以及相关算法）被实现在R包{Biostrings}中，该包是Bioconductor的一部分。

由于该包实现了比简单的Levenshtein距离更通用的解决方案，使用方法不幸更加复杂，使用指南也相应地很长。但是，对于您的目的，基本用法如下：

library(Biostrings)

dist_mat = diag(27L)
colnames(dist_mat) = rownames(dist_mat) = c(letters, ' ')

result = pairwiseAlignment(
    "abc abc", "abcde acc",
    substitutionMatrix = dist_mat,
    gapOpening = 1, gapExtension = 1
)

这不仅仅会给你一个列表 c('b', 'c', 'c')，因为该列表并不能完全代表实际发生的情况。相反，它会返回两个字符串之间的一个对齐。这可以表示为具有替换和空格的序列：

score(result)
# [1] 3
aligned(result)
as.matrix(aligned(result))
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
# [1,] "a"  "b"  "c"  "-"  "-"  " "  "a"  "b"  "c"
aligned(result)

—— 对于第二个字符串中的每个字符，它提供了原始字符串中相应的字符，用 - 替换插入的字符。基本上，这是将第一个字符串转换为第二个字符串的“配方”。请注意，它只包含插入和替换，不包括删除。要获得这些，您需要以相反的方式执行对齐（即交换字符串参数）。

- Konrad Rudolph

---

不幸的是，上面的代码要求您手动指定 dist_mat，以便它包含字符串可能包含的每个字符的一行和一列。因此，此答案中显示的代码仅允许小写字母和空格，没有其他内容。 - Konrad Rudolph

Answer 3

这里是提取每种类型更改数量以及每种操作对应字符的代码：

source_string="12234"
target_string="02345"
lev=adist(source_string,target_string,count=T)

#number of operations of each kind
attributes(lev)$counts[,,"ins"] 
attributes(lev)$counts[,,"del"]
attributes(lev)$counts[,,"sub"]

substitution_bank=deletion_bank=insertion_bank=match_bank=NULL

changes<-strsplit(attributes(lev)$trafos, "")[[1]]

counter_source=counter_target=1
for(j in changes){
 if(j=="S") {
   substitution_bank=rbind(substitution_bank,
           cbind(strsplit(source_string,"")[[1]][counter_source], strsplit(target_string,"")[[1]][counter_target]))
   counter_source=counter_source+1
   counter_target=counter_target+1
 }
 if(j=="I") {
   insertion_bank=rbind(insertion_bank,
                           strsplit(target_string,"")[[1]][counter_target])
   counter_target=counter_target+1
 }
 if(j=="D") {
   deletion_bank=rbind(deletion_bank,
                        strsplit(source_string,"")[[1]][counter_source])
   counter_source=counter_source+1
 }
 if(j=="M") {
   match_bank=rbind(match_bank,
                           strsplit(source_string,"")[[1]][counter_source])
   counter_source=counter_source+1
   counter_target=counter_target+1
 }
 

}

substitution_bank
deletion_bank
insertion_bank
match_bank

说实话，我为这段代码感到羞愧--一次只处理一个字符似乎太浪费了。但是在插入和删除同时存在的情况下，我无法想出如何提取正确的字符...所以更优雅的答案会受到欢迎！

- A Cristia

Answer 4

调查@tmfmnk的评论，看看trafos引导我采取以下方法。

返回字符串的部分，其中edit_string等于match的函数：

character_match = function(string, edit_string, match, drop = NA){
  # convert to array
  string = strsplit(string, "")[[1]]
  edit_string = strsplit(edit_string, "")[[1]]
  
  if(!is.na(drop)){
    edit_string = edit_string[edit_string != drop]
  }
  
  if(length(string) != length(edit_string)){
    stop("string and edit_string are different lengths")
  }
  
  output = rep("_", length(edit_string))
  is_match = edit_string == match
  output[is_match] = string[is_match]
  
  output = paste0(output, collapse = "")
  return(output)
}

应用于这个问题：

s1 = "123456789"
s2 = "0123zz67"

out = adist(s1, s2, counts = TRUE)
edit_string = drop(attr(out, "trafos"))

现在编辑字符串将包括以下字母代码：

• I = 插入
• M = 匹配
• S = 替换
• D = 删除

我们可以使用以下函数提取它们：

# characters in s1 that match s2
character_match(s1, edit_string, "M", "I")
# "123__67__"

# characters in s1 that were substituted out
character_match(s1, edit_string, "S", "I")
# "___45____"

# characters in s1 that were deleted
character_match(s1, edit_string, "D", "I")
# "_______89"

# characters in s2 that match s1
character_match(s2, edit_string, "M", "D")
# "_123__67"

# characters in s2 that were substituted in
character_match(s2, edit_string, "S", "D")
# "____zz__"

# characters in s2 that were inserted
character_match(s2, edit_string, "I", "D")
# "0_______"

从这里很容易看出哪些字符和位置被插入、删除或替换。

- Simon.S.A.