r-непрерывное сопоставление, MATLAB


Я хочу сравнить эти две строки по R-смежному правилу соответствия. Поэтому в этом примере, если мы зададим r как 6, то он вернет true для первого примера и false для второго примера.

Пример 1:

A='ABCDEFGHIJKLM'
B='XYZ0123EFGHIJAB'
return true (since it they both have 6 contiguous match 'EFGHIJ')

Пример 2:

A='ABCDEFGHJKLM'
B='XYZ0123EFGHAB'
return false (since they both have only 4 contiguous match 'EFGH')

Какой самый быстрый способ в MATLAB, так как мои данные огромны? Спасибо.

1   3   2015-11-23 15:57:12

1 ответ:

Случай: входные строки с уникальными символами

Вот один подход с ismember & strfind -

matches = ismember(A,B) %// OR any(bsxfun(@eq,A,B.'),1)
matches_ext = [0 matches 0]

starts = strfind(matches_ext,[0 1])
stops = strfind(matches_ext,[1 0])    
interval_lens = stops - starts

out = any(interval_lens >= r)

Вот еще один с diff & find вместо strfind -

matches = ismember(A,B) %// OR any(bsxfun(@eq,A,B.'),1)
matches_ext = [0 matches 0]

df = diff(matches_ext)
interval_lens = find(df == -1) - find(df == 1)

out = any(interval_lens >= r)

Вот еще один с 1D convolution -

matches = ismember(A,B) %// OR any(bsxfun(@eq,A,B.'),1)
out = any(conv(double(matches),ones(1,r)) == r)

Случай: входные строки с неуникальными символами

Вот один подход, использующий bsxfun -

matches = bsxfun(@eq,A,B.');  %//'
intv = (0:r-1)*(size(matches,1)+1)+1
idx = find(matches)
idx = idx(idx <= max(idx) - max(intv))
out = any(all(matches(bsxfun(@plus,idx,intv)),2))