如何知道计算弦之间的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

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

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

ins del sub 
  2   0   1 

来自?adist：

如果counts为TRUE，则将转换计数作为此矩阵的“ counts”属性返回，作为3维数组，其维数与x的元素，y的元素以及转换的类型（插入，删除和替换）。

Answer 2

这称为Needleman-Wunsch算法。它既可以计算两个字符串之间的距离，又可以计算所谓的traceback，从而可以重新构造对齐方式。

由于在比较生物序列时，这个问题大多出现在生物学中，因此该算法（及相关算法）在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)

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