Find longest pattern of [1 0] in array.

I have Bits0 array of 1's and 0's. I would like to get the start/stop indices of the largest sequence of 1 0's. Actually, I expect at least 4 repetitions of [1 0].

I know there are file exchange functions that I have heard about (but I am in an air-gap environment). Is it possible to get just a few more lines of code to solve this problem? Here is what I have so far.

b_PATTERN = [1 0 1 0 1 0 1 0 ];
Bits0 = [0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0];
patternLocs = uint32(strfind(Bits0, b_PATTERN ))

patternLocs = 1×17

6 8 10 12 22 24 26 28 30 32 34 36 38 47 49 51 53

if isempty(patternLocs)
    Bits0_start = []; % cannot find pattern
end
patternDiffLocs = diff( patternLocs )

patternDiffLocs = 1×16

2 2 2 10 2 2 2 2 2 2 2 2 9 2 2 2

% Problem now reduced to finding longest pattern of 2's.
% Need patIdx = 5; num_2s = 8
% Need Bits0_start = 22; Bits0_stop = 45 (at least close - counted by hand)

Answer 1

[Walter Roberson]

The below code will find all of the subsets of maximum length (I do not assume that it will be unique)

The union() are present because the pattern can be ended by having immediately the wrong bit at an end of a subset, but also by having the right next bit at the end of a subset but having the wrong bit on the other side of that.

repeat_count = 4;
b_PATTERN = repmat([1 0], 1, repeat_count);
Bits0 = [0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0];

Bits0_start = union(strfind([0 0 Bits0], [0 0 b_PATTERN]), strfind([1 Bits0], [1 b_PATTERN]))

Bits0_start = 3×1

6 22 47

Bits0_stop = union(strfind([Bits0 1 1], [b_PATTERN 1 1]), strfind([Bits0 0], [b_PATTERN 0])) + length(b_PATTERN) - 1

Bits0_stop = 1×3

19 45 60

durations = Bits0_stop(:) - Bits0_start(:) + 1

durations = 3×1

14 24 14

longest_idx = find(durations == max(durations))

longest_idx = 2

T  = table(Bits0_start(longest_idx).', Bits0_stop(longest_idx).', 'VariableNames', {'Start', 'Stop'})

T = 1×2 table
    Start    Stop
    _____    ____

     22       45 

[Paul Hoffrichter]

Thank you Walter. Took me awhile to understand your Bits0_start line on without Matlab on my phone, but I'm starting to get it. Will study more when I get back to my desk tomorrow. Nice to be able to immediately eliminate all those overlapping matches so simply.

[Walter Roberson]

The Bits0_start line works by searching for the minimum pattern preceeded by something that is not the pattern.

The Bits0_stop line works by searching for the minimum pattern followed by something that is not the pattern.

The code does not explicitly check that everything between the start and the stop matches the pattern, but the code does not have to do that. The code finds all of the boundaries, which requires that strfind() examines every location; if there was something between the start and stop that does not match the pattern then strfind() would have reported the pattern boundary.

This is a programming technique that is surprisingly useful. For example you can find rising edges by looking for places that start with the appropriate low conditions, and by looking for places that end with the appropriate high conditions, and the code does not need to be concerned with anything else. (Though in that particular case you would be wanting a check for the edge falling far enough again before it reaches the required peak.)

[Paul Hoffrichter]

Spent Thursday with coworker leaving Friday for knowledge transfer. Hopefully tomorrow will continue.

[Paul Hoffrichter]

No specialized Matlab code here. Just a simple, elegant, and most probably very efficient algorithm good in any programming language. Not sure how you thought of it! Wish I had. Thank you!

(If this is an algorithm that is in a textbooks, I would appreciate the reference - might be worth getting it for other algorithms.)

Re: "you can find rising edges by looking for places that start with the appropriate low conditions, and by looking for places that end with the appropriate high conditions"

I think I see what you are getting at here. With noisy signals, I have been determining a threshold to convert to 1's and 0's. Then I take the diff to get the 0-crossings. Then I have to deal with 0-crossings that shouldn't be there due to noise. I think using this technique, I'll be able to find the start/stop of a burst of energy without a diff and without too much concern about the extra 0-crossings (but not positive - will have to think about this more). But now, I am expecting to reduce the number of bogus 0-crossings significantly. Thanks so much @Walter Roberson!

[Walter Roberson]

See also findpeaks and islocalmax