Обнаружить расхождения между двумя последовательностями

Question

У меня есть два вектора временных рядов: complete_data и incomplete_data. данные в векторе состоят из 6 возможных событий, которые происходят случайным образом по всему вектору. В принципе, они должны быть одинаковыми, потому что с каждым событием в complete_data это же событие добавлялось к incomplete_data. однако в действительности в системе были некоторые аномалии, и не все события в complete_data были отправлены в incomplete_data. Таким образом, complete_data длиннее incomplete_data. Мне нужно найти различия в схеме между ними и отметить их. Я предпринял попытку, но она предполагает, что расхождение между двумя векторами происходит в одном фрагменте, тогда как в действительности существуют различные «пропущенные события», разбросанные в incomplete_data.

Вот моя попытка:

complete_data <- c('a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c')
dfcomplete <- as.data.frame(complete_data)
incomplete_data <- c('a', 'b', 'c', 'a','c', 'a', 'b', 'a', 'b', 'c')
dfincomplete <- as.data.frame(incomplete_data)

findMatch <- function(complete_data, incomplete_data){

  matching_inorder <- NULL
  matching_reverseorder <- NULL

  for (i in 1:length(complete_data)){
    matching_inorder[i] <- complete_data[i] == incomplete_data[i]
    matching_reverseorder[i] <- rev(complete_data)[i] == rev(incomplete_data)[i]
  }

  is_match <- ifelse(matching_inorder == FALSE & 
                       rev(matching_reverseorder) == FALSE, 'non_match', 'match')
  is_match
}

dfcomplete$is_match_incorrect <- findMatch(dfcomplete$complete_data,
                                 dfincomplete$incomplete_data)

А вот что я хотел бы получить:

dfcomplete$expected_output <- c('match', 'match', 'match', 'match', 'non-match', 'match',
                 'match', 'match', 'non_match', 'match', 'match', 'match')

В действительности мои данные намного больше, чем в этих примерах, с множеством различных расхождений, разбросанных по всему вектору. Хотя не обязательно слишком много расхождений, чтобы сделать задачу бессмысленной, например, в одном случае вектор complete имеет 320 точек данных, тогда как вектор incomplete имеет 309.

Любая помощь, которая может быть предложена, будет принята с благодарностью.

Answer 1

Если вы можете позволить себе иметь имена событий длиной только одну букву, вот решение с использованием сопоставления строк. Хитрость заключается в том, чтобы преобразовать неполные данные в шаблон, включая места для вставки новых символов.

complete_data <- c('a', 'b', 'c', 'a', 'B', 'c', 'a', 'b', 'C', 'a', 'b', 'c')
dfcomplete <- as.data.frame(complete_data,stringsAsFactors=FALSE)
incomplete_data <- c('a', 'b', 'c', 'a','c', 'a', 'b', 'a', 'b', 'c')

y <- paste0('^(.*)',paste(incomplete_data,collapse='(.*)'),'(.*)$')
x <- paste(complete_data,collapse="")
z <- str_length(str_match(x,y)[-1])

data.frame(incomplete_data=c("",incomplete_data),stringsAsFactors=FALSE) %>%
  mutate(n=ifelse(incomplete_data=="",z,z+1)) %>%
  filter(n>0) %>%
  uncount(n) %>%
  mutate(incomplete_data=ifelse(str_detect(rownames(.),"\\."),"",incomplete_data)) %>%
  bind_cols(dfcomplete) %>%
  mutate(match=complete_data==incomplete_data)
#   incomplete_data complete_data match
#1                a             a  TRUE
#2                b             b  TRUE
#3                c             c  TRUE
#4                a             a  TRUE
#5                              B FALSE
#6                c             c  TRUE
#7                a             a  TRUE
#8                b             b  TRUE
#9                              C FALSE
#10               a             a  TRUE
#11               b             b  TRUE
#12               c             c  TRUE

Answer 2

Существуют различные способы сделать это, но вот рекурсивный, где x предполагается полной последовательностью и y неполной.

compare <- function(x, y) {
  if (length(x) > 0) {
    if (x[1] == y[1]) {
      x[1] <- "match"
      c(x[1], compare(x[-1], y[-1]))
    } else {
      x[1] <- "no match"
      c(x[1], compare(x[-1], y))
    }
  }
}
compare(complete_data, incomplete_data)
# [1] "match"    "match"    "match"    "match"    "no match" "match"   
# [7] "match"    "match"    "no match" "match"    "match"    "match" 

Другой, который, возможно, более читабелен и использует простой цикл, будет

out <- rep(NA, length(incomplete_data))
gap <- 0
for(i in seq_along(complete_data)) {
  if (complete_data[i] == incomplete_data[i - gap]) {
    out[i] <- "match"
  } else {
    out[i] <- "no match"
    gap <- gap + 1
  }
}
out
# [1] "match"    "match"    "match"    "match"    "no match" "match"   
# [7] "match"    "match"    "no match" "match"    "match"    "match"