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.
7
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.
8
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.