How can I find 4 or more character pattern in number array

I have an array like this A=[1 2 3 2 5 12 3 9 12 3 5 6 3 2 5 11 10 9] (array size (1,275)

I am trying to find 4 or more character pattern in this array.

how can I do this?

[Thomas]

how would you define character pattern?

[alicin]

pattern is not known. I start to search all 4 number sub-array. then goes on.

[Walter Roberson]

Well for example your array contains [5 12 3 9]. Would '5123' be considered a 4-character pattern of that, or would the 4 character pattern be '5 12' ?

[alicin]

array consist of numbers between 1-12. there is whitespace between numbers. so 5 12 3 9 is my pattern.

[Image Analyst]

So it's really a number pattern, not a character pattern.

[alicin]

yes number pattern.

Answer 1

[Wayne King]

See Loren's blog here:

http://blogs.mathworks.com/loren/2008/09/08/finding-patterns-in-arrays/

You can use strfind with an array of numbers

    A = [1 2 3 2 5 12 3 9 12 3 5 6 3 2 5 11 10 9];
    % find
    B = [9 12 3];
    K = strfind(A,B);

K is the starting index of the pattern in the array, A.

    A(K:K+1+length(K))

[alicin]

but there is no spesific B. I have to try all sub-array

[Walter Roberson]

So how do you know if you have found the pattern or not?

[alicin]

I start with beginning of array. I use first 4 element of array then compare with sliding the array. then I continue this operation until I reach end of the array.

[Walter Roberson]

So you keep sliding until you find another copy of the first 4 elements of the array? And if it is found within the buffer, what do you want done? If there are multiple copies of it within the buffer, what do you want done?

And then after you did the searching for the first 4 elements, you want to do the same thing but looking for the second 4 elements??

[alicin]

When I found another copy, I want to store in a different array.

Multiple copy will be ignored. when I found it first time, I quit searching.

When I finish searching first 4 element(1,4), I continue with (2,5) then (3,6) then (4,7) vs.

[Walter Roberson]

Sounds very inefficient...

[alicin]

There is a song with music notes. 12 different notes. total 275 notes.

I am trying to find same note-groups in this song.

Answer 2

[Laura Proctor]

If you define the pattern that you're looking for as x, for example

x = [3 9 12 3]

then you can find the starting index value for this pattern by using the following code:

n = length(x);

ind = 1:length(A);
for k = 1:n
    i1 = find(A==x(k));
    ind = intersect(ind,i1-k+1);
end

[alicin]

What is A

[Laura Proctor]

The original array in which you are searching for the pattern.

[alicin]

 there is no known pattern. I have to search all sub-arrays. so how can I do this?

[Image Analyst]

That doesn't make sense. You have to be searching A for some pattern. Otherwise, you might as well just pick any 4 adjacent indexes from A at random.

Answer 3

[Cedric]

And here is a funny solution:

 A = [1 2 3 2 5 12 3 9 12 3 5 6 3 2 5 12 3 9] ;      % Notes
 p = [5 12 3 9] ;                                    % Pattern

 nA = numel(A) ; np = numel(p) ;
 buffer = ~any(spdiags(repmat(A(:), 1, np), 0:np-1, nA, nA) - ...
               spdiags(repmat(p, nA, 1), 0:np-1, nA, nA), 2) ;
 loc = find(full(buffer(1:nA-np+1)))

This code gives loc = 5, 15.

Cheers,

Cedric

Answer 4

[Image Analyst]

If you have the Image Processing Toolbox you can use normxcorr though it looks like Loren's method is simpler:

% Define sample data.
A=[1 2 3 2 5 12 3 9 12 3 5 6 3 2 5 11 10 9]
% Define the sequence of numbers we want to find.
patternToFind = [5 12 3 9]
% Compute the normalized cross correlation.
normCrossCorr = normxcorr2(patternToFind, A)
% Find index where the sequence starts.
% This is where the normalized cross correlation = 1.
startingIndexOfSequence = find(normCrossCorr >= 0.999999) - length(patternToFind) + 1

Answer 5

[Walter Roberson]

At each step, K,

conv(A(K+4:end), -1./A(K:K+3), 'valid')

should, I think, become within round-off of 0 at each point at which there is a match.

Or,

B = A(K:K+3);
T = A(K+4:end);
find(T(1:end-3) == B(1) & T(2:end-2) == B(2) & T(3:end-1) == B(3) & T(4:end) == B(4), 1, 'first')

There is a vectorized solution for the entire similarity search all at once, that involves constructing a comparison array (it might have to be multidimensional); it might become impractical for larger input vectors.

Answer 6

[Jan]

According to Wayne King's answer:

data = randi([1,12], 1, 275);
for k = 1:length(data) - 3
  search = data(k:k+3);
  match  = k - 1 + strfind(data(k:end), search);
  if length(match) > 1
    fprintf('Match: [ ');
    fprintf('%d ', search);
    fprintf(']: \n  ');
    fprintf(' %d', match);
    fprintf('\n');
  end
end