Re: Two-dimensional pattern matching/compression


Herbert Glarner wrote:
jacko wrote:
all given prime number identifier
start with smallest
join to all of increasing size (if possible and give composite id
number)


Is there a qualitative reason for proceding from the smallest pattern to
the largest instead of the other way round? 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.
overlap percentage!
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. If I understand your approach correctly, you suggest to
compare "all-with-all" prior any actual merging.
No when composite join found merge and give composite id, but nust
continue as there may be a more optimal merge.
In this case I would
tend to hash a sequenced array's possible windows to avoid multiple
comparisions of the same patterns over and over again. However, then
there is the issue of storage. A single exemplary 10*10 matrix produces
2000 possibly matching subarrays involving edges, not counting the inner
"edge free" submatrices. Assuming 10000 patterns, we already get 20m
possible matches.
you have to compare them :-)
> delete the smallest when all joins tried with bigger
> loop with next smallest until generated composite of all (id)

"Deletion" sounds fine to me, only that the hypermatrix has grown due to
merging operation. All remaining patterns then still are existent, and
the hashes still are valid for them. But the hypermatrix' hashes are
pretty much obsolete now, as the linearization has changed, so it will
require a new hashing process with more submatrices than before.
?? when all merges of one to all rest found why keep it?
As you can see: I'm still trying to find a way to reduce this enormous
comparison overhead. *g*
good luck
Thanks for your input, though
//Herbert

--
http://herbert.wikispaces.com

.

Relevant Pages

  • Re: Composition with an Adapter?
    ... etc. Do you agree that this seems like a good usage of the GoF Composite ... Is the time aggregation over incrementally added allocations associated ... I think the use of design patterns is the other way around. ...
    (comp.object)
  • Re: Composition with an Adapter?
    ... And LeaveTime can itself be part of Non-Project Time, as opposed to total Project Time (a different leaf class in the Composite which has a project). ... I'm not a great artist at this point though, and I haven't decided yet on this one which is why I'm looking to bounce the idea off of others with more experience in applying patterns. ... One tends to look for design patterns when one encounters specific problems in the design. ... In my company, a Project can be thought of as something that accumulates all kinds of Quantities of resource allocations, with quantities of Money and Time always of interest. ...
    (comp.object)
  • 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)
  • 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, ... A 2D analog of suffix trees may be useful. ... overlap (not totally disjoint or totally embedded), ...
    (comp.theory)