如何知道计算字符串之间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")。

Answer 1

这就是所谓的Needleman-Wunsch算法。它计算两个字符串之间的距离以及所谓的回溯，这允许您重建对齐。

由于在比较生物序列时，这一问题主要出现在生物学中，该算法(及其相关算法)是在R包{生物串}中实现的，它是生物导体的一部分。

由于这个包实现比简单的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)

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

Answer 2

使用adist()，您可以检索操作：

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

ins del sub 
  2   0   1 

来自?adist

如果计数为真，则转换计数作为此矩阵的“计数”属性返回，作为一个三维数组，其维数分别对应于x元素、y元素和转换类型(插入、删除和替换)。

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

老实说，我对代码感到惭愧--一次只去一个角色似乎太浪费了。但在插入和删除的情况下，我想不出如何提取正确的字符.所以更优雅的答案是欢迎的！