Re: Two-dimensional pattern matching/compression

On Wednesday 12 July 2006 05:52, Herbert Glarner wrote:
My intuition does suggest,
that eliminating the largest patterns first (by merging into the
hypermatrix) leads to less comparisons for the later smaller patterns:
the "hypermatrix" already is a compressed representation in either case,
but initially it is small and thus there is not much to check. As it
grows, I certainly would be thankful for smaller patterns reducing the
overall number of comparisons.

However, the efficiency question still remains, as with n patterns I
need to compare n(n-1)/2 patterns, and comparing two two-dimensional
patterns isn't quite effective, as both Boyer-Moore and KPM seem to be a
large overhead.

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-
--
Paul E. Black (p.black@xxxxxxx)
.

Relevant Pages

  • Re: Two-dimensional pattern matching/compression
    ... hypermatrix) leads to less comparisons for the later smaller patterns: ... the "hypermatrix" already is a compressed representation in either case, ... No when composite join found merge and give composite id, ... the hashes still are valid for them. ...
    (comp.theory)
  • Re: Two-dimensional pattern matching/compression
    ... join to all of increasing size (if possible and give composite id ... My intuition does suggest, that eliminating the largest patterns first (by merging into the hypermatrix) leads to less comparisons for the later smaller patterns: the "hypermatrix" already is a compressed representation in either case, but initially it is small and thus there is not much to check. ...
    (comp.theory)