Efficient/Fastest pattern matching on integer vector

Hello,

Problem Staement:

Given a uint16 data vector vec in format [ID1 ID2 data ID1 ID2 data ...] and ID pairs mat pattern, find data associated with each ID pair and fill the 3rd column of output vector out with first 2 columns containing ID pairs.

Assumption:

It is assumed that the data in vec has both noise and missing because of which an ID pair is searched ([0 6]) and then the previous ([0 4]) and next ([0 8]) ID pairs are also searched to reliably get the data value of each ID pair.

Goal:

Find the most time efficient method to fill the output vector out.

Methods:

1. A simple nested loop based method which first searches for an ID pair in data vector vec and then matches its previous and next ID pairs for confirmation and get the associated data. The code is given below which takes roughly 2300 sec on my computer.

load vec;
load pattern;
load out;

len = length(out);
no_of_IDs_to_search = 1000;

tic
for j = 2:no_of_IDs_to_search % skip searching for ID pairs at 1st location
    ind = strfind(vec,pattern(j*2-1:j*2)); % firstly, find all indices of a single ID pair e.g. [0 2] or [0 6]
    ind(ind<4 | ind>((len-1)*3)) = []; % remove indices to aviod errors
    if (~isempty(ind))
        for k = 1:length(ind) % search through all indices and determine if previous and next IDs are a match
            if (isequal(vec(ind(k)-3:ind(k)-3+1), pattern((j-1)*2-1:(j-1)*2)) && isequal(vec(ind(k)+3:ind(k)+3+1), pattern((j+1)*2-1:(j+1)*2)))
                out(j,3) = vec(ind(k)+2); %update the corresponding index in output vector
                break; % break if previous, current and next IDs are a match
            end
        end
    end
end
toc

2. Some algorithm based on regular expressions, specifically Lookaround Assertions?

3. Maybe some C/C++ based mex implementation?

Thank you.

Answer 1

[Image Analyst]

You could also try normalized cross correlation. A 2-d demo is atached that finds a template inside a larger image.

[Haider Ali]

@Image Analyst Are you suggesting looping over 3 ID pairs [previousID1 previousID2 NaN currentID1 currentID2 NaN nextID1 nextID2 NaN] at a time and finding normalized correlation for each of them?

[Image Analyst]

No, I'm not. Honestly your scanning and using isequal() at each window location should be fine. I was just thinking that normxcorr2 might be a little faster since it's normalized but I was thinking to use it on the 1-D vector. Most Image Processing Toolbox functions can also be used on 1-D vectors as well as 2-D images.