计算两个整数矩阵/数据帧的所有行之间的成对汉明距离

我有两个数据框，df1与参考数据和df2与新数据。对于中的每一行df2，我需要找到最佳（和第二最佳）匹配行df1就汉明距离而言。

I used e1071计算汉明距离的包。两个向量之间的汉明距离x and y可以计算如下：

x <- c(356739, 324074, 904133, 1025460, 433677, 110525, 576942, 526518, 299386,
       92497, 977385, 27563, 429551, 307757, 267970, 181157, 3796, 679012, 711274,
       24197, 610187, 402471, 157122, 866381, 582868, 878)

y <- c(356739, 324042, 904133, 959893, 433677, 110269, 576942, 2230, 267130,
       92496, 960747, 28587, 429551, 438825, 267970, 181157, 36564, 677220,
       711274, 24485, 610187, 404519, 157122, 866413, 718036, 876)

xm <- sapply(x, intToBits)
ym <- sapply(y, intToBits)

distance <- sum(sapply(1:ncol(xm), function(i) hamming.distance(xm[,i], ym[,i])))

结果距离是 25。但是我需要对所有行执行此操作df1 and df2。一个简单的方法需要一个双循环嵌套，看起来非常慢。

有什么想法可以更有效地做到这一点吗？最后我需要附加到df2:

• 具有行 id 的列df1给出最短距离；
• 距离最近的一列；
• 具有行 id 的列df1这给出了第二短的距离；
• 距离第二短的列。

Thanks.

快速计算两个等长整数向量之间的汉明距离

正如我在评论中所说，我们可以这样做：

hmd0 <- function(x,y) sum(as.logical(xor(intToBits(x),intToBits(y))))

计算之间的汉明距离两个长度相等的整数向量 x and y。这仅使用 R 基，但比e1071::hamming.distance, 因为它是矢量化的！

举个例子x and y在你的帖子中，这给出了 25。（我的另一个答案将展示如果我们想要成对汉明距离，我们应该做什么。)

矩阵和向量之间的快速汉明距离

如果我们想计算单个之间的汉明距离y和多个xs，即向量和矩阵之间的汉明距离，我们可以使用以下函数。

hmd <- function(x,y) {
  rawx <- intToBits(x)
  rawy <- intToBits(y)
  nx <- length(rawx)
  ny <- length(rawy)
  if (nx == ny) {
    ## quick return
    return (sum(as.logical(xor(rawx,rawy))))
    } else if (nx < ny) {
    ## pivoting
    tmp <- rawx; rawx <- rawy; rawy <- tmp
    tmp <- nx; nx <- ny; ny <- tmp
    }
  if (nx %% ny) stop("unconformable length!") else {
    nc <- nx / ny  ## number of cycles
    return(unname(tapply(as.logical(xor(rawx,rawy)), rep(1:nc, each=ny), sum)))
    }
  }

注意：

1. hmd执行计算逐列。它的设计目的是CPU缓存友好。这样，如果我们想做一些按行计算，我们应该先转置矩阵；
2. 这里没有明显的循环；相反，我们使用tapply().

两个矩阵/数据帧之间的快速汉明距离计算

这就是你想要的。以下功能foo需要两个数据框或矩阵df1 and df2，计算之间的距离df1和每一行df2。争论p是一个整数，显示您想要保留多少个结果。p = 3将保持最小的 3 个距离及其行 iddf1.

foo <- function(df1, df2, p) {
  ## check p
  if (p > nrow(df2)) p <- nrow(df2)
  ## transpose for CPU cache friendly code
  xt <- t(as.matrix(df1))
  yt <- t(as.matrix(df2))
  ## after transpose, we compute hamming distance column by column
  ## a for loop is decent; no performance gain from apply family
  n <- ncol(yt)
  id <- integer(n * p)
  d <- numeric(n * p)
  k <- 1:p
  for (i in 1:n) {
    distance <- hmd(xt, yt[,i])
    minp <- order(distance)[1:p]
    id[k] <- minp
    d[k] <- distance[minp]
    k <- k + p
    }
  ## recode "id" and "d" into data frame and return
  id <- as.data.frame(matrix(id, ncol = p, byrow = TRUE))
  colnames(id) <- paste0("min.", 1:p)
  d <- as.data.frame(matrix(d, ncol = p, byrow = TRUE))
  colnames(d) <- paste0("mindist.", 1:p)
  list(id = id, d = d)
  }

注意：

1. 换位是在开始时根据之前的原因进行的；
2. a for这里使用了循环。但这实际上是有效的，因为每次迭代都会进行大量计算。它也比使用更优雅*applyfamily，因为我们要求多个输出（行 idid和距离d).

实验

这部分使用小数据集来测试/演示我们的功能。

一些玩具数据：

set.seed(0)
df1 <- as.data.frame(matrix(sample(1:10), ncol = 2))  ## 5 rows 2 cols
df2 <- as.data.frame(matrix(sample(1:6), ncol = 2))  ## 3 rows 2 cols

Test hmd首先（需要转置）：

hmd(t(as.matrix(df1)), df2[1, ])  ## df1 & first row of df2
# [1] 2 4 6 2 4

Test foo:

foo(df1, df2, p = 2)

# $id
#   min1 min2
# 1    1    4
# 2    2    3
# 3    5    2

# $d
#   mindist.1 mindist.2
# 1         2         2
# 2         1         3
# 3         1         3

如果您想附加一些列df2，你知道该怎么做，对吗？