# Efficient/Fastest pattern matching on integer vector

2 views (last 30 days)
Haider Ali on 19 Jun 2022
Commented: Image Analyst on 20 Jun 2022
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.
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.

Image Analyst on 19 Jun 2022
You could also try normalized cross correlation. A 2-d demo is atached that finds a template inside a larger image.
##### 2 CommentsShowHide 1 older comment
Image Analyst on 20 Jun 2022
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.

### Categories

Find more on Tables in Help Center and File Exchange

R2018b

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!