Получение шаблонов из двоичной строки

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) и

• последний 4 индексы в виде шаблона (1).

Мне нужно это как часть алгоритма декодирования канала, чтобы обрезать двоичное дерево. Есть ли эффективный способ сделать это в Matlab?

Answer 1

Я реализовал решение рекурсивно, как показано ниже,

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

Answer 2

Полагаю, что наиболее простым решением будет использование регулярного выражения с 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
}