Re: Two-dimensional pattern matching/compression


Herbert Glarner wrote:
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

Problem is that you allow "."
There is no way how avoid this because hole can be created during
algorithm
When DFA match pattern 1......(n times)1 He need at least 2**n states
At Regular expresions I dont know complexity
somewhere I see that we can use O(MN) but most languages use
backtrack.
except perl regex where is algorithm impossible
suffix trees -patterns are ambigouos, For suffix at first pattern you
must find list of suffixes from second which match

I would use straight--forward search and say anybody who complains to
buy better computer

.