1
$\begingroup$

I have a table consisting of some headers $P, Q, R, S$ (shown in blue in Table 1). According to the headers, the column $T$ is populated using some predefined logic.

Now, any of the headers $P,Q,R,S$ may be wildcarded to match all values. The aim to to compress the table using wildcards so that column $T$ is not affected.

As shown in Table 2, Table 3 and Table 4, choosing a combination of fields as key (shown in orange) and wildcarding the rest can be used to compress the table.

However, the choice of key (combination of header fields which are not wildcarded) affects the size of the compressed table.

Given a table, my aim is to automatically detect which combination of headers will yield the smallest table size (compressed) while not affecting column $T$.

So this problem can be split in two parts : 1. Given that you have to have $k$ header fields in the key, what combination will yield smallest table size? 2. What would be the optimal value of $k$?

Note: If case of conflict arising in column $T$ from using wildcards, a non-wildcarded row must be placed above it. (E.g. see Table 4, rows 3 and 4)enter image description here

So what are some good approaches towards solving this problem? Other than iterating over all combinations and choosing the best? Any help in this regard is appreciated.

$\endgroup$
  • $\begingroup$ "Given that you have to have $k$ header fields in the key, what combination will yield smallest table size?" is an easier question than what you seem to be asking at the start, since an optimal use of asterisks could put asterisks in different columns on each row (so it doesn't make sense to talk about a single "combination of $k$ header fields"). $\endgroup$ – j_random_hacker May 24 '18 at 11:54
  • $\begingroup$ Yes. I agree. That is why I split the question into two parts. $\endgroup$ – Niloy Saha May 24 '18 at 11:57
  • $\begingroup$ If column T contains only 2 distinct values, then your problem is basically Boolean logic minimization, with each row corresponding to a minterm. The problem is NP-hard. The Quine-McCluskey algorithm will give you an optimal solution, and there are also faster heuristics. If T contains more than 2 distinct values, it might be possible to adapt one of these algorithms. $\endgroup$ – j_random_hacker May 24 '18 at 12:03
  • $\begingroup$ The two parts still don't give the flexibility you need, if you are allowed to have a different number of asterisks in each row (as you already do in your examples). $\endgroup$ – j_random_hacker May 24 '18 at 12:05

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.