查找包含一小部分0的最大长度的子向量

Question

我有一个包含序列1和0的向量.假设它的长度为166,它是

  y <- c(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1, 1,1,1,1,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,1,1,1,1)

现在我想从上面的向量中提取一个最长的可能的子向量,使它满足两个属性

(1)子矢量应从1开始,以1结束.

(2)它可以包含最多5%的子矢量总长度的零.

我从rle功能开始.它计算每一步的1和0.所以它会是这样的

z <- rle(y)
d <- data.frame(z$values, z$lengths)
colnames(d) <- c("value", "length")

它给了我

> d
   value length
1      1     22
2      0      1
3      1     13
4      0      1
5      1      2
6      0      1
7      1      1
8      0      1
9      1      1
10     0      5
11     1      1
12     0      3
13     1      2
14     0      1
15     1      1
16     0      1
17     1     74
18     0      2
19     1     17
20     0      1
21     1      2
22     0      1
23     1      3
24     0      5
25     1      4

在这种情况下,74 + 2 + 17 + 1 + 2 + 3 = 99是必需的子序列,因为它包含2 + 1 + 1 = 4个零,小于99的5%.如果我们向前移动,序列将变为99 + 5 + 4 = 108,零将是4 + 5 = 9,这将超过108的5%.

Answer 1

我认为通过计算这个向量的游程编码你已经非常接近了。剩下的就是考虑所有 1 的游程对，并选择长度最长且符合“零不超过 5%”规则的对。这可以通过完全向量化的方式来完成，用于combn计算所有 1 的游程对并cumsum从输出中获取游程的长度rle：

ones <- which(d$value == 1)
# pairs holds pairs of rows in d that correspond to runs of 1's
if (length(ones) >= 2) {
  pairs <- rbind(t(combn(ones, 2)), cbind(ones, ones))
} else if (length(ones) == 1) {
  pairs <- cbind(ones, ones)
}

# Taking cumulative sums of the run lengths enables vectorized computation of the lengths
#   of each run in the "pairs" matrix
cs <- cumsum(d$length)
pair.length <- cs[pairs[,2]] - cs[pairs[,1]] + d$length[pairs[,1]]
cs0 <- cumsum(d$length * (d$value == 0))
pair.num0 <- cs0[pairs[,2]] - cs0[pairs[,1]]

# Multiple the length of a pair by an indicator for whether it's valid and take the max
selected <- which.max(pair.length * ((pair.num0 / pair.length) <= 0.05))
d[pairs[selected,1]:pairs[selected,2],]
#    value length
# 15     1      1
# 16     0      1
# 17     1     74
# 18     0      2
# 19     1     17
# 20     0      1
# 21     1      2
# 22     0      1
# 23     1      3

我们实际上发现了一个比 OP 发现的子向量稍长的子向量：它有 102 个元素和 5 个 0 (4.90%)。