2
$\begingroup$

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 :

 1,2,3,4,5
 2,8,7,5,4
 3,1,8,9,7
 2,4,5,8,7

becomes :

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

 R1,R3
 R1,R2
 R2,R3,9 
 R4

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

Improve this question
$\endgroup$
3
  • $\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
    Commented Apr 16, 2021 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
    Commented Apr 16, 2021 at 5:07
  • $\begingroup$ (Why does this look like min cover?) $\endgroup$
    – greybeard
    Commented Apr 16, 2021 at 5:09

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.