Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am designing a logic analyzer and I would like to implement some Matrix Algorithm. I have several channels each one represented by a row in the matrix and every element in the column would be the state, for example:

Channel 1   1 0 0 1 0 1 1 0 1
Channel 2   1 1 0 1 1 0 0 1 1
Channel 3   0 1 0 1 1 0 1 0 0

I would like to detect a pattern inside my matrix for example, detect ALL the matches of the bitmap inside the matrix:

1 0
1 1

I think it can be accomplished testing element by element but I think there should be a better way of doing it. Is there any Java API or any way to do it ? If there is a API ARM optimized for NEON instructions would be great also but not mandatory.

They will be about 8 matrix of 3 or 2 rows by 20000 columns approximately, the matrix is not fixed, it change every time I scan it because I am constantly receiving data. I need to process them in 500mS or less. I am working on an ARM platform, dual core, 1.2GHz, 1Gb RAM, Android 4.1.2

Thank you very much in advance.

share|improve this question
    
It would be helpful if you tell us the expected sizes of your matrixes, the number of them and how fast you need it to be. –  Doc Brown Dec 18 '12 at 7:26
    
They will be about 8 matrix of 3 or 2 rows by 20000 columns approximately. I need to process them in 500mS or less. I am working on an ARM platform, dual core, 1.2GHz, 1Gb RAM, Android 4.1 –  Andres Dec 18 '12 at 15:15
    
What exactly do you mean by pattern? A submatrix (e.g. pick rows 1 and 3 and columns 2 and 5) or a bitmap like structure (e.g. a row and col index i,j such that for all x,y : p(x,y) = m(i+x, j+y) with p as pattern and m as "channel matrix")? –  scarfridge Dec 18 '12 at 17:10
    
I want to know if B sub-matrix exist in A matrix but it has to be a sub-matrix I don't want it to recognize the pattern if one match is in column 1 and the other match is in column 5 it must be all together like a matrix. Hope you understand :) –  Andres Dec 18 '12 at 17:15
    
Maybe then you should remove the word submatrix. A submatrix of a matrix is usually build by choosing arbitrary columns and rows. See en.wikipedia.org/wiki/Submatrix –  scarfridge Dec 18 '12 at 17:17
show 2 more comments

2 Answers

up vote 1 down vote accepted

EDIT: after you clarified things a bit, I see you are after some kind of different thing I was thinking of first. When your matrix changes for every search, creating some kind of lookup structure beforehand won't help you much - instead you probably may need some low-level optimized bitmap processing library (or write your own native code in C, analogous to this example). Even then, there is still the problem that you will have to convert your input data to the bitmap format used by that library, each time, for each single search. So you definitely will have to loop once over all the bits of your matrix.

For that reason, I doubt you can much improve the simple brute-force search which iterates over the whole matrix and just compares the values to the values of the given submatrix.

share|improve this answer
    
Yes the maximum pattern I want to match is 3x3. I want to detect ALL matches not only the first one. For that reason I wanted to avoid loops because it will be slow that's why I am asking if there is another method with matrix operations. –  Andres Dec 18 '12 at 16:19
    
If you don't have loops, then you are left with recursion or GOTO. Recursion can use a lot of memory. And as far as my ignornat mind knows, both recursion and a loop compile to a goto statement, so why not just use a loop. –  AedonEtLIRA Dec 18 '12 at 16:37
    
@Andres: you missed the point - please read my answer again, especially the "independent of the algorithm" part. Even if you would have enough memory available to build some kind of dictionary to find all submatrices instaneously, and even if you could ignore the running time to build the dictionary, you will run into problems either when processing the result set. –  Doc Brown Dec 18 '12 at 16:58
    
Yes but my pattern to search will never be a sub-matrix full of 1 and my matrix of 3x20000 will never be full of 1 also. I know that number will be algorithm independent, but some algorithms are faster than others. I want to know if there is any way, method, operation to for example by multiplying by a Matrix get a Matrix with only the pattern I am searching for or something like that, that should speed up things I think. I am not an expert only a 18 years teen trying to learn ;) –  Andres Dec 18 '12 at 17:02
    
@DocBrown OP is not really interested in a submatrix but is thinking more of a bitmap. This reduces the number of possible pattern positions in your example to 2*(20000-1) –  scarfridge Dec 18 '12 at 17:19
show 3 more comments

I don't know whether there's a Java API to do it, but a search for "two-dimensional string matching" or "two-dimensional pattern matching" turns up plenty of papers. For example, the master's thesis of Martijn van de Rijdt (PDF) reviews several algorithms and (being a thesis rather than a journal paper) is probably more readable than the original papers.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.