Re: Two-dimensional pattern matching/compression

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.

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

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

As you can see: I'm still trying to find a way to reduce this enormous comparison overhead. *g*

Thanks for your input, though
//Herbert

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

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
    ... 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)
  • 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)