Индексирование вектора внутри большего в MATLAB

Question

Я пытаюсь найти позицию индекса меньшего вектора внутри большего.

Я уже решил эту проблему, используя strfind и bind2dec, но не хочуиспользуйте strfind, я вообще не хочу преобразовывать в строковые или десятичные числа.

Учитывая более длинный вектор

a=[1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];

Я хочу найтииндекс меньшего вектора b внутри

b=[1,1,1,0,0,0];

Я бы ожидал найти как результат :

result=[15,16,17,18,19,20];

Спасибо

Answer 1

Более аккуратный метод, использующий for, выглядел бы так: нет необходимости во внутреннем цикле проверки, поскольку мы можем векторизовать это с помощью all ...

a = [1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];
b = [1,1,1,0,0,0];

idx = NaN( size(b) ); % Output NaNs if not found
nb = numel( b );      % Store this for re-use

for ii = 1:numel(a)-nb+1
    if all( a(ii:ii+nb-1) == b )
        % If matched, update the index and exit the loop
        idx = ii:ii+nb-1;
        break
    end
end

Выход:

idx = [15,16,17,18,19,20]

Обратите внимание, я считаю, что это немного легче читать, чем некоторые из вложенных решений, но это не обязательно быстрее, поскольку сравнение выполняется для всех элементов в b каждый раз.

Answer 2

Решение с for петлями:

a=[1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];
b=[1,1,1,0,0,0];
c = [];
b_len = length(b)
maxind0 = length(a) - b_len + 1 %no need to search higher indexes 

for i=1:maxind0
  found = 0;
  for j=1:b_len
    if a(i+j-1) == b(j)
      found = found + 1;
    else
      break;
    end
  end

  if found == b_len  % if sequence is found fill c with indexes
    for j=1:b_len
      c(j)= i+j-1;
    end

    break
  end
end

c %display c

Answer 3

Вот как решение с использованием 1D свертки. Он может найти несколько совпадений, поэтому start содержит начальные индексы субвекторов:

f = flip(b);

idx = conv(a,f,'same')==sum(b) & conv(~a,~f,'same')==sum(~b);

start = find(idx)-ceil(length(b)/2)+1;

result = start(1):start(1)+length(b)-1;

Answer 4

Должен ли он быть вычислительно эффективным?

Не очень эффективным, но коротким решением было бы следующее:

a=[1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];;
b=[1,1,1,0,0,0];
where = find(arrayfun(@(n) all(a(n+1:n+length(b))==b),0:length(a)-length(b)));

... дает вам 15. Ваш result будетвектор where:where+length(b)-1.

edit : я попробовал это сделать, и я исправлен.Вот версия с циклами:

function where = find_sequence(a,b)

na = 0;
where = [];
while na < length(a)-length(b)
    c = false;
    for nb = 1:length(b)
        if a(na+nb)~=b(nb)
            na = na + 1;  % + nb
            c = true;                        
            break
        end

    end
    if ~c
        where = [where,na+1];
        na = na + 1;
    end   
end

Несмотря на свои циклы и плохую репутацию в Matlab, она намного быстрее:

a = round(rand(1e6,1));
b = round(rand(10,1));

tic;where1 = find(arrayfun(@(n) all(a(n+1:n+length(b))==b),0:length(a)-length(b)));toc;
tic;where2 = find_sequence(a,b);toc;


>> test_find_sequence
Elapsed time is 4.419223 seconds.
Elapsed time is 0.042969 seconds.