Найти минимальное расстояние Хемминга между строкой и длинным вектором строк (быстро)

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

На уровне R вы можете использовать strsplit, cbind, !=, colSums а также min, Они все "векторизованы".

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++ вы можете сделать намного лучше (см. Пример здесь), но я не заинтересован в написании кода на 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() работает почти в десять раз медленнее, чем colSum(),

Это действительно интересно. Возможно, его C-код или R-код делают что-то еще более сложное.

Answer 2

Вы не можете улучшить это лучше, чем O(n) это означает, что вам нужно просмотреть весь набор данных и рассчитать расстояние для каждого наблюдения.

Единственное улучшение может произойти в вашем наборе данных, если вы sort все наблюдения основаны на данной точке. В этом случае вам может быть проще найти строку в наборе данных (0 результатов на расстоянии). Это единственное улучшение, которое вы можете сделать.