检测有序字符串的序列并使用 R 对它们进行分组

Question

我有一个包含大约 500K 个元素的字符串向量，我想为每个元素分配一个值以显示每个元素的组号。

分组标准是这样的：

从列表顶部开始连续分配一个组号
每个元素都应分配到不同的组，除非至少有 3 个连续元素按字母升序排列，其中这些连续元素将在一组中。

我如何在 R 中执行此操作？

例如和预期输出：

> my_strings <- c("xx1", "1xxx", "abc.xyz", "a", "ad022", "ghj1", "kf1", "991r",
+                 "jdd", "12vd", "r34o", "z", "034mh")
> expected_output <- c(1, 2, 3, 4, 4, 4, 4, 5, 6, 7, 7, 7, 8)
> (df <- data.frame(input = my_strings, output = expected_output))
     input output
1      xx1      1
2     1xxx      2
3  abc.xyz      3
4        a      4
5    ad022      4
6     ghj1      4
7      kf1      4
8     991r      5
9      jdd      6
10    12vd      7
11    r34o      7
12       z      7
13   034mh      8

到目前为止，我尝试使用 dplyr::lead 并根据两个连续元素分配顺序。不过我不知道如何从这里开始。

res <- as_tibble(my_strings) %>%
  mutate(after = lead(my_strings))
res$pre_group = apply(res, 1, function(x) order(c(x[1], x[2]))[2])

Answer 1

（该死，这是一个艰难的过程:-)

整洁宇宙

library(dplyr)
df %>%
  mutate(r1 = cumsum(c(TRUE, diff(rank(input)) < 0)) + 0) %>%
  group_by(r1) %>%
  mutate(r2 = r1 + seq(0, 0.9*(n() < 3), len = n()) / n()) %>%
  ungroup() %>%
  mutate(r1 = with(list(rl = rle(r2)$lengths), rep(seq_along(rl), times = rl))) %>%
  select(-r2)
# # A tibble: 13 x 3
#    input   output    r1
#    <chr>    <dbl> <int>
#  1 xx1          1     1
#  2 1xxx         2     2
#  3 abc.xyz      3     3
#  4 a            4     4
#  5 ad022        4     4
#  6 ghj1         4     4
#  7 kf1          4     4
#  8 991r         5     5
#  9 jdd          6     6
# 10 12vd         7     7
# 11 r34o         7     7
# 12 z            7     7
# 13 034mh        8     8

（mutate 中冗长的 with(...) 只是 data.table::rleid 的内联版本。）

`data.table`

library(data.table)
as.data.table(df)[
, r1 := cumsum(c(TRUE, diff(rank(input)) < 0)) + 0 ][
, r1 := r1 + seq(0, 0.9*(.N < 3), len = .N), by = .(r1) ][
, r1 := rleid(r1) ]

如果你想模糊R-dialects的线条，那么

library(data.table)
library(magrittr)
as.data.table(df) %>%
  .[, r1 := cumsum(c(TRUE, diff(rank(input)) < 0)) + 0 ] %>%
  .[, r1 := r1 + seq(0, 0.9*(.N < 3), len = .N), by = .(r1) ] %>%
  .[, r1 := rleid(r1) ]

备注：

as.numeric(...)

... + 0 是 short-hand。这是因为 data.table 在更新列时强制执行列的原始 class；由于 r1（没有 +0）的第一个定义将是 integer，r1 returns numeric 的下一个重新分配。但是，由于 data.table 保留原始 class，数字将被强制（trunc 化）为整数，我的努力停止了。

当一组中有三个或更多时，
seq(0, 0.9*(...)) 会减少到 seq(0,0)，这会导致该组出现 no-op。（这使用 dplyr 的 n() 和 data.table 的 .N 用于 group-size。）

实现略有不同，因为 dplyr 禁止修改分组变量； data.table 对此没有问题。（我不确定哪个方向是正确的或更好的...）

Answer 2

不如 r2evans 好，但似乎也能给出结果。

x <- my_strings
n <- length(x)
c(FALSE,x[-1L] > x[-n]) &
c(FALSE,FALSE,x[-1L][-1L] > x[-n][-(n-1)]) &
c(FALSE,FALSE,FALSE,x[-1L][-1L][-1L] > x[-n][-(n-1)][-(n-2)])

(lead(x, 1) > x & lead(x,2) > lead(x,1)) |
  (lag(x, 1) < x & lead(x,1) > x) |
  (lag(x, 1) < x & lag(x,2) < lag(x,1)) -> condition

condition[is.na(condition)] <- FALSE # remove NAs

#to visualize
tibble(lag(x,2), lag(x,1), x, lead(x,1), lead(x,2), condition)

# There may be a better way than a loop
cur_class <- 0
classes <- integer(n)
for(i in 1:(n)){
  if(!condition[i]){ #not in a sequence
    cur_class <- cur_class + 1
    classes[i] <- cur_class
  } else if(!condition[i-1]){ #first of a sequence
    cur_class <- cur_class + 1
    classes[i] <- cur_class
  } else{ #mid-sequence
    classes[i] <- cur_class
  }
}

tibble(x, classes, condition*1L)

# A tibble: 13 x 3
#   x       classes `condition * 1L`
#  <chr>     <dbl>            <int>
# 1 xx1           1                0
# 2 1xxx          2                0
# 3 abc.xyz       3                0
# 4 a             4                1
# 5 ad022         4                1
# 6 ghj1          4                1
# 7 kf1           4                1
# 8 991r          5                0
# 9 jdd           6                0
# 10 12vd          7                1
# 11 r34o          7                1
# 12 z             7                1
# 13 034mh         8                0

检测有序字符串的序列并使用 R 对它们进行分组

Detect sequences of ordered strings and group them using R

string

r

sequence

整洁宇宙

data.table

`data.table`