Algorithms like LZW and others compress data sequences. What I'm looking is an algorithm that compress multiple Sets. if possible online algorithm. For example :


becomes :

 Rule1 : 2,4,5
 Rule2: 8,7
 Rule3 : 3,1
 Rule4 : R1,R2


.. Rules are hierarchical .. which will be better compression... this is one example of compression .. i'm looking for online algorithm.

The hard thing is to do compression on the fly ... and be optimal i.e. maximize compression.

  • $\begingroup$ One idea would be to maintain a list of $(a, b, f)$ triples, where $a$ and $b$ are either base elements or rules, and $f$ is the frequency -- the number of sets seen so far that contain both $a$ and $b$. To process a set, look through this list in decreasing frequency order for $(a,b)$ pairs that fit within the set, until no elements in the set remain uncovered. For each pair found: (1) record its index using some variable-length integer encoding; (2) increment its frequency; (3) for all other elements $x$ in the set, increment the frequency of $(R,x)$, where $R=(a,b)$ is a possibly new rule. $\endgroup$ – j_random_hacker Apr 16 at 4:56
  • $\begingroup$ This will produce a large number of triples with low frequencies, but some strategy can be used to forget triples whose frequencies stay low -- e.g., to throw out triples whose frequencies remain below some given threshold for $k$ sets, maintain an array $P[]$ of $k$ lists of triples, and before processing the $i$-th set, delete from the main list all triples in $P[i \% k]$ having below-threshold frequencies; during processing of the $i$-th set, add each newly created triple to $P[i \% k]$ (as well as to the main list). $\endgroup$ – j_random_hacker Apr 16 at 5:07
  • $\begingroup$ (Why does this look like min cover?) $\endgroup$ – greybeard Apr 16 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.