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

Question

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

是否可以知道为获得两个字符串之间的编辑距离所做的操作？或者知道两个字符串之间不同的字符（在这个例子中，只有 "d"）？谢谢

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

我想知道:

"d" 已插入
"e" 已插入
"b"被代入了"c"

或者更简单地说，我想要列表 ("d"、"e"、"c")。

Answer 1

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

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

ins del sub 
  2   0   1

来自?adist：

If counts is TRUE, the transformation counts are returned as the "counts" attribute of this matrix, as a 3-dimensional array with dimensions corresponding to the elements of x, the elements of y, and the type of transformation (insertions, deletions and substitutions), respectively.

Answer 2

这被称为Needleman–Wunsch algorithm。它计算两个字符串之间的距离以及 so-called traceback，这允许您重建对齐方式。

由于在比较生物序列时这个问题主要出现在生物学中，因此该算法（和相关算法）在 R 包中实现 {Biostrings}, which is part of Bioconductor。

由于这个包实现的是比简单的 Levenshtein 距离更通用的解决方案，不幸的是用法更复杂，并且 usage vignette 相应地很长。但您的基本用法如下：

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')，因为该列表并不完全代表此处实际发生的情况。相反，它将在两个字符串之间 return 一个 alignment。这可以表示为具有替换和间隙的序列：

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 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

老实说，我为代码感到羞耻——一次只写一个字符似乎很浪费。但是在同时存在插入和删除的情况下，我无法弄清楚如何提取正确的字符...所以欢迎更优雅的答案！

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

How to know the operations made to calculate the Levenshtein distance between strings?

string

r

levenshtein-distance

stringdist