Efficient/Fastest pattern matching on integer vector

1 view (last 30 days)
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.
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.
Find the most time efficient method to fill the output vector out.
  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;
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
2. Some algorithm based on regular expressions, specifically Lookaround Assertions?
3. Maybe some C/C++ based mex implementation?
Thank you.

Answers (1)

Image Analyst
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.
Image Analyst
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.

Sign in to comment.




Community Treasure Hunt

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

Start Hunting!