从二进制字符串中获取模式

Question

我有一个长度为 N 的二进制字符串，它是 2 的幂 (N = 2^n)。

我需要提取长度为 L 的特定模式，它是 2 (L = 2^l) 的幂。

在满二叉树中，这些模式应该

从左叶节点（偶数索引）开始并且
以右叶节点（奇数索引）结尾。

这些模式应该包括 整个子树 的叶子。我需要提取的模式是

(1). 0 0 --- 0  (All zero)
(2). 1 1 --- 1  (All one)
(3). 0 0 --- 1  (Only the last right leaf is one).

比如我有一个二进制字符串N=16,(n=4)比如 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 ，我需要提取

索引 0 to 7 作为模式 (3)，
索引 8 to 11 作为模式 (2) 和
last 4 索引作为模式 (1)。

我需要将其作为通道解码算法的一部分，以修剪二叉树。在 Matlab 中有没有有效的方法来做到这一点？

Answer 1

我想最简单的解决方案是使用 regular expression 和 regexp

%binary string example
s = '0000000111110000'

%Get the start Index (SI) and the end Index (EI)
[SI,EI] = regexp(s,'0+$')       %pattern 1
[SI,EI] = regexp(s,'0+1')       %pattern 2
[SI,EI] = regexp(s,'(?<!0)1+')  %pattern 3

注意到 matlab 上的索引以 1 而不是 0 开头。

您也可以一次使用多个正则表达式：

[SI,EI] = regexp(s,{'0+$','0+1','(?<!0)1+'})

结果：

SI = 
{
  [1,1] =  13
  [1,2] =  1
  [1,3] =  9
}
EI = 
{
  [1,1] =  16
  [1,2] =  8
  [1,3] =  12
}

Answer 2

我已经递归地实现了如下解决方案，

s = [0  0  0  1  0  0  0  1  0  0  0  1  0  1  1  1  0  0  0  1  0  1  1  1  0  1  1  1  0  1  1  1 ];
N=length(s);
n = log2(N);

mask = zeros(1,N);
pattern1_indices = [];
pattern2_indices = [];
pattern3_indices = [];


for l= n:-1:1
    L = 2^l;
    t  = 2^(n-l); % Number of strings of size L

    pattern1= zeros(1,L);
    pattern3= pattern1;
    pattern3(end) = 1;
    pattern2 = ones(1,L);

    for i = 1:t
        st = (i-1)*L+1 ;
        ed = i*L ; 
        if(mask(st)==1)
            continue
        end
        chunk =  s(st:ed) ;

        if chunk == pattern3 % Only the last bit is one
            mask(st:ed) = 1;
            pattern3_indices = [pattern3_indices ; [st,ed]];
        elseif chunk == pattern1
            mask(st:ed) = 1; % All zero
            pattern1_indices = [pattern1_indices ; [st,ed]];
        elseif chunk == pattern2
            mask(st:ed) = 1; % All one
            pattern2_indices = [pattern2_indices ; [st,ed]];
        end         
    end
end

我得到每个模式的开始和结束索引如下，

pattern1_indices

pattern1_indices =

     []

>> pattern2_indices

pattern2_indices =

    15    16
    23    24
    27    28
    31    32

>> pattern3_indices

pattern3_indices =

     1     4
     5     8
     9    12
    17    20
    13    14
    21    22
    25    26
    29    30

从二进制字符串中获取模式

Getting patterns out of a binary string

matlab

binary-tree