标签: run-length-encoding

假设我有一维数组:

a = [1, 2, 3];

例如,n应该返回replicate(a, 3).

请注意,这与...完全不同[1,1,1,2,2,2,3,3,3].我当然可以repmat通过replicate对每个元素进行实现并连接结果来实现,但我想知道是否有更高效的内置函数.

我正在尝试使用'values'数组和'counter'数组将多个值插入到数组中.例如,如果:

a=[1,3,2,5]
b=[2,2,1,3]

我想要一些功能的输出

c=somefunction(a,b)

成为

c=[1,1,3,3,2,5,5,5]

其中a(1)重复b(1)次,a(2)重复b(2)次等等...

MATLAB中是否有内置函数来执行此操作？如果可能的话,我想避免使用for循环.我尝试过'repmat()'和'kron()'的变体无济于事.

这基本上是Run-length encoding.

data.tablerleid为游程编码提供了一个很好的便利功能:

library(data.table)
DT = data.table(grp=rep(c("A", "B", "C", "A", "B"), c(2, 2, 3, 1, 2)), value=1:10)
rleid(DT$grp)
# [1] 1 1 2 2 3 3 3 4 5 5

我可以在以下基础R上模仿这个:

df <- data.frame(DT)
rep(seq_along(rle(df$grp)$values), times = rle(df$grp)$lengths)
# [1] 1 1 2 2 3 3 3 4 5 5

有没有人知道dplyr等效(？)或创建rleid行为的"最佳"方法dplyr是执行以下操作

library(dplyr)

my_rleid = rep(seq_along(rle(df$grp)$values), times = rle(df$grp)$lengths)

df %>%
  mutate(rleid = my_rleid)

为了巧妙地使用线性索引accumarray,我有时觉得需要根据游程编码生成序列.由于没有内置函数,我要求最有效的方法来解码在RLE中编码的序列.

规格:

为了使这个公平比较,我想为该功能设置一些规范:

• 如果values指定了相同长度的可选第二个参数,则输出应该根据这些值,否则只是值1:length(runLengths).
• 优雅处理:
  • 零 runLengths
  • values 是一个单元阵列.
• 输出向量应具有相同的列/行格式 runLengths

简而言之:该函数应该等效于以下代码:

function V = runLengthDecode(runLengths, values)
[~,V] = histc(1:sum(runLengths), cumsum([1,runLengths(:).']));
if nargin>1
    V = reshape(values(V), 1, []);
end
V = shiftdim(V, ~isrow(runLengths));
end

例子:

以下是一些测试用例

runLengthDecode([0,1,0,2])
runLengthDecode([0,1,0,4], [1,2,4,5].')
runLengthDecode([0,1,0,2].', [10,20,30,40])
runLengthDecode([0,3,1,0], {'a','b',1,2})

和他们的输出:

>> runLengthDecode([0,1,0,2])
ans =
     2     4     4

>> runLengthDecode([0,1,0,4], [1,2,4,5].')
ans =    
     2     5     5     5     5

>> runLengthDecode([0,1,0,2].', [10,20,30,40])
ans =
    20
    40
    40

>> runLengthDecode([0,3,1,0],{'a','b',1,2})
ans …

在R中,我想在基于变量的运行对数据进行分组之后对其进行汇总x(也就是说,每组数据对应于连续x值相同的数据的子集).例如,考虑以下数据框,我想计算y每次运行中的平均值x:

(dat <- data.frame(x=c(1, 1, 1, 2, 2, 1, 2), y=1:7))
#   x y
# 1 1 1
# 2 1 2
# 3 1 3
# 4 2 4
# 5 2 5
# 6 1 6
# 7 2 7

在此示例中,x变量的长度为3,然后是2,然后是1,最后是1,在这四次运行中取值1,2,1和2.y这些组中相应的手段是2,4.5,6和7.

在基础R中使用tapply,dat$y作为数据传递,使用rle从中计算运行编号dat$x,并传递所需的汇总函数,很容易执行此分组操作:

tapply(dat$y, with(rle(dat$x), rep(seq_along(lengths), lengths)), mean)
#   1   2   3   4 
# 2.0 4.5 6.0 7.0 

我想我可以直接将这个逻辑转移到dplyr,但到目前为止我的尝试都以错误结束了: …

我想总结而不是以类似的方式压缩运行长度编码,但是在嵌套意义上.

例如,我想:ABCBCABCBCDEEF成为:(2A(2BC))D(2E)F

我并不担心在两个相同的可能嵌套之间选择一个选项

ABBABBABBABA可以是(3ABB)ABA或A(3BBA)BA,它们具有相同的压缩长度,尽管具有不同的结构.

但是我确实希望选择最贪婪.例如:

ABCDABCDCDCDCD将选择(2ABCD)(3CD) - 原始符号中长度为6的小于ABCDAB(4CD),其在原始符号中长度为8.

在背景方面,我有一些重复的模式,我想总结一下.这样数据就更容易消化了.我不想破坏数据的逻辑顺序,因为它很重要.但是我想总结它,通过说,符号A次出现3次,其次是符号XYZ 20次出现等等,这可以用嵌套的方式在视觉上显示.

欢迎的想法.

是否有矢量化方式来执行以下操作？(以示例显示):

input_lengths = [ 1 1 1 4       3     2   1 ]
result =        [ 1 2 3 4 4 4 4 5 5 5 6 6 7 ]

我已经间隔了input_lengths,因此很容易理解如何获得结果

合成矢量的长度为:sum(lengths).我目前result使用以下循环计算:

result = ones(1, sum(input_lengths ));
counter = 1;
for i = 1:length(input_lengths)
    start_index = counter;
    end_index = counter + input_lengths (i) - 1;

    result(start_index:end_index) = i;
    counter = end_index + 1;
end

编辑:

我也可以使用arrayfun(虽然这不是一个矢量化函数)

cell_result = arrayfun(@(x) repmat(x, 1, input_lengths(x)), 1:length(input_lengths), 'UniformOutput', false);
cell_result : …

我有以下带有 0 和 1 的向量：

test1 <- c(rep(0,20),rep(1,5),rep(0,10),rep(1,15)) 

test1
[1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
                                                                          ^
test2 <- c(rep(0,8),rep(1,4),rep(0,5),rep(1,5),rep(0,6),rep(1,10),rep(0,2)) 

test2
[1] 0 0 0 0 0 0 0 0 1 1 1 1 0 0 …

看起来像一个简单的任务,无法弄清楚一个更简单的方法.我在x下面有一个向量,需要为连续值创建组名.我的尝试是使用rle更好的想法？

# data
x <- c(1,1,1,2,2,2,3,2,2,1,1)

# make groups
rep(paste0("Group_", 1:length(rle(x)$lengths)), rle(x)$lengths)
# [1] "Group_1" "Group_1" "Group_1" "Group_2" "Group_2" "Group_2" "Group_3" "Group_4"
# [9] "Group_4" "Group_5" "Group_5"

问题:给定原子矢量,找到矢量中运行的起始和结束索引.

运行示例向量:

x = rev(rep(6:10, 1:5))
# [1] 10 10 10 10 10  9  9  9  9  8  8  8  7  7  6

输出来自rle():

rle(x)
# Run Length Encoding
#  lengths: int [1:5] 5 4 3 2 1
#  values : int [1:5] 10 9 8 7 6

期望的输出:

#   start end
# 1     1   5
# 2     6   9
# 3    10  12
# 4    13  14
# 5    15  15

基rle类似乎不提供此功能,但类Rle和函数rle2 …