R 中的实现：查找两个字符列表之间的距离

Question

我是 R 的新手，想了解如何在 R 中实现下面的算法。我有两个字符列表，想看看这两个字符之间的最小距离是多少。

List 1: "a", "b", "c"
List 2: "a", "b", "c", "d"

第一步：我创建了一个像这样的 table :

  a   b   c
a 0   1   2
b 1
c 2
d 3

在第二步：我用'0'填充了矩阵的其余部分

  a   b   c
a 0   1   2
b 1   0   0
c 2   0   0
d 3   0   0

现在，我想开始通过这个算法计算这两个列表之间的距离并更新矩阵：

if (characters_in_header_of_matrix[i]==characters_in_column_of_matrix [j] & value[i,j] == value[i+1][j-1] )
then {get the 'diagonal value' #diagonal value= value[i, j-1]}

else{
value[i,j] = min(value[i-1, j], value[i-1, j-1],  value[i, j-1]) + 1
}
endif

为了找到您可以在 header 和矩阵列中看到的两个列表之间的差异，我使用了 strcmp() 函数。但是，我未能实现这一点。最终结果应如下所示：

  a   b   c
a 0   1   2
b 1   0   1
c 2   1   0
d 3   2   1

我会很感激你的help.Thanks

Answer 1

在 R 中，有些事情您可以可以使用for循环和条件进行暴力破解，但它们可能很容易用矢量化方法完成.好处可能是速度（尽管可能不是），但通常可以在更简单的代码和（一旦您可以理解这些功能）可读性和可维护性中得到赞赏。

以这个问题为例：

l1 <- c("a", "b", "c")
l2 <- c("a", "b", "c", "d")

您想从 l2 中的每个字母中找到 l1 中的每个字母之间的 "distance"（绝对距离，具体而言）。 outer 函数对两个向量执行 "outer product"。例如，如果我们要建设性地（不是实际上）做 outer(a:c, 1:3)，它会配对 a1、a2、a3、b1、...， c3。（这不是合法的 R 代码，仅用于演示，尽管通过一些小的添加可以很容易地完成。）

在我们的例子中，如果我们做 outer(l1, l2)，它使用的函数默认为乘法 (*)，因为它最初的用途通常是线性代数，但这个函数很容易被覆盖FUN=。在内部，它正在做的是创建两个（更长的）向量来完成所有配对。如果我们引入调试功能来检查状态，我们可以看到幕后发生的事情。

debugfunc <- function(a, b) { browser(); 1; }

（1 仅用作占位符。）

outer(l1, l2, FUN=debugfunc)
# Called from: FUN(X, Y, ...)
# Browse[2]> 
a # <--- the object 'a' here is the first argument to this function
#  [1] "a" "b" "c" "a" "b" "c" "a" "b" "c" "a" "b" "c"
# Browse[2]> 
b # <--- the second argument
#  [1] "a" "a" "a" "b" "b" "b" "c" "c" "c" "d" "d" "d"

按顺序，"a" 与 "a" 配对，然后 "b" 与 "a" 配对，然后 "c" 与 "a" 配对，依此类推。它用完第一个 (l1) 向量，然后递增第二个向量，重复直到两个向量都用完。在这一点上，debugfunc 只用这两个向量调用一次（不是像某些人怀疑的那样每对调用一次），因此您的 FUN= 函数必须能够在一次调用中完成所有操作。

有人可能想看看这里的距离。您可以使用 match("a", letters)（伴随的 LETTERS 全部大写）来确定单个字母在字母表中的位置。通常，match 查找第一个参数在第二个参数中的位置。所以继续 debugfunc:

# Browse[2]> 
match(a, letters)
#  [1] 1 2 3 1 2 3 1 2 3 1 2 3
# Browse[2]> 
match(b, letters)
#  [1] 1 1 1 2 2 2 3 3 3 4 4 4

所以你真正想要的是这两个数值向量之间的差异。可以轻松做到：

# Browse[2]> 
match(a, letters) - match(b, letters)
#  [1]  0  1  2 -1  0  1 -2 -1  0 -3 -2 -1

但是因为我们需要绝对距离，所以我们真的需要

# Browse[2]> 
abs( match(a, letters) - match(b, letters) )
#  [1] 0 1 2 1 0 1 2 1 0 3 2 1

好的，我想我们的功能在这里。让我们跳出调试器 (Q) 并更正式地尝试一下：

distfunc <- function(a, b) abs( match(a, letters) - match(b, letters) )
outer(l1, l2, FUN=distfunc)
#      [,1] [,2] [,3] [,4]
# [1,]    0    1    2    3
# [2,]    1    0    1    2
# [3,]    2    1    0    1

注意第一个参数变成了行，所以 l1 长度为 3 给了我们 3 行。如果您需要应用 row/column 名称，则：

o <- outer(l1, l2, FUN=distfunc)
dimnames(o) <- list(l1, l2)
o
#   a b c d
# a 0 1 2 3
# b 1 0 1 2
# c 2 1 0 1

（改变参数的顺序将为您提供您正在寻找的矩阵。）

R 中的实现：查找两个字符列表之间的距离

implementation in R: Finding the distance between two lists of characters

datatable

r

edit-distance

matrix

dataframe