Re: Two-dimensional pattern matching/compression

A 2D analog of suffix trees may be useful. Create all "suffix" (say,
lower right) sub-matrixes of the matrixes to be merged. If there is
overlap (not totally disjoint or totally embedded), the "prefix" of
one must match some "suffix" of the other.
http://www.nist.gov/dads/HTML/suffixtree.html

There are a number of spatial access methods that may help search
matrixes:
http://www.nist.gov/dads/HTML/spatialAccessMethod.html

-paul-


Yes, meanwhile I agree, that the submatrices need to be "made searchable" in one way or the other, prior any actual merging activity, reason being that otherwise I would not be able to find the best match (largest overlap) and possibly miss out "the better".

Although this trades comparing all the positions of submatrices multiple times for a comparison of a one-time-creation of the "searchable" structure (thus reducing the activity in the innermost loops, which presumerably counts most in terms of performance), it comes at the cost of an increased space-complexity.

The suggested prefix/suffix(and "infix" *g*) trees may indeed prove to be superior to hashing. Although both have the same basic space complexity (a node is a node), a "p/s/i tree" may be arranged more compact and has not to deal with wasted space and hash collisions. It even offers the possibility to include a "foreword" prior the actual path to designate for which edge the actual path is valid (L, R, T, B or "inner area"), making it easy to immediately find the most promising route (the opposite edge(s) if any). Yes, I think that this is the way to go.

First I need to do some more homework, though, before I miss out something proving to be essential: I must confess that I am absolutely unfamiliar with the "Spatial Access Methods". So... back to study :)

Thanks for your input, Paul.

Regards
//Herbert

--
http://herbert.wikispaces.com
.