找到一个字符串和一个长字符串向量之间的最小汉明距离（快速）

Question

我需要计算输入字符串和大型字符串数据集之间的汉明距离。（数据集中的所有字符串与输入字符串的长度相同。）

例如，如果

input <- "YNYYEY"
dataset <- c("YNYYEE", "YNYYYY", "YNENEN", "YNYYEY")

input和dataset中每个字符串之间的海明距离是1,1,3,0所以最小值是0。我写了一个函数来计算两个字符串之间的海明距离:

HD <- function(str1, str2){

   str1 <- as.character(str1)
   str2 <- as.character(str2)

   length.str1 <- nchar(str1)
   length.str2 <- nchar(str2)

   string.temp1 <- c()
   for (i in 1:length.str1){
     string.temp1[i] = substr(str1, start=i, stop=i)
   }
   string.temp2 <- c()
   for (i in 1:length.str2){
     string.temp2[i] = substr(str2, start=i, stop=i)
   }
   return(sum(string.temp1 != string.temp2))
   }

但是数据集太大了，所以我需要加快速度，你知道我可以快速完成吗？感谢您的帮助。

Answer 1

你不能比 O(n) 更好地改进它，这意味着你必须检查所有数据集，并计算每个观察的距离。

如果您 sort 基于给定点的所有观察结果，唯一的改进可能发生在您的数据集上。在这种情况下，您可能更容易在数据集中找到字符串（0 距离结果）。这是您唯一可以做的改进。

Answer 2

在 R 级别，您可以使用 strsplit、cbind、!=、colSums 和 min。他们都是"vectorized".

a <- "YNYYEY"
b <- c("YNYYEE", "YNYYYY", "YNENEN", "YNYYEY")
A <- strsplit(a, split = "")[[1]]
#[1] "Y" "N" "Y" "Y" "E" "Y"
B <- do.call("cbind", strsplit(b, split = ""))
#     [,1] [,2] [,3] [,4]
#[1,] "Y"  "Y"  "Y"  "Y" 
#[2,] "N"  "N"  "N"  "N" 
#[3,] "Y"  "Y"  "E"  "Y" 
#[4,] "Y"  "Y"  "N"  "Y" 
#[5,] "E"  "Y"  "E"  "E" 
#[6,] "E"  "Y"  "N"  "Y" 
D <- colSums(A != B)
#[1] 1 1 3 0
min(D)
#[1] 0

。但希望这是值得的。

在 C/C++ 级别你可以做得更好（参见 here 的案例研究），但我今天并不热衷于编写 C/C++ 代码。

我遇到了 stringdist 包（甚至还有一个 stringdist 标签）。函数stringdist依赖于一个主力例程stringdist:::do_dist，它是用C语言编写的。它节省了我的精力。

library(stringdist)
d <- stringdist(a, b, method = "hamming")
#[1] 1 1 3 0
min(d)
#[1] 0

stringdist() runs almost ten times slower than colSum().

这真的很有趣。可能它的 C 代码或 R 代码正在做其他复杂的事情。

找到一个字符串和一个长字符串向量之间的最小汉明距离（快速）

Find the minimum hamming distance between a string and a long vector of strings (fast)

r

string

performance

vectorization

hamming-distance