4
$\begingroup$

(The question is an extension of this unanswered question on stackoverflow)

If we have a set of strings, we can efficiently represent them with tries. Common branches can also be merged, resulting in a DAG instead of a tree that is even more compact.

However, if we have a set of sets (i.e. the order does not matter), there are a lot of possible tries that represent the same set of elements. An example can be found in the stackoverflow question I linked above.

Edit: For example, assume that we are given the following sets of integers.

{1,2,3,4,5}
{1,2,6,7}
{1,2,4,7}
{1,3,5,7}

Two possible representations are shown below (trie on the left, DAG on the right)

enter image description here

My questions are:

  1. How hard is the problem of finding an optimal (i.e minimal) such trie?
  2. Are there any fast algorithms for solving this problem?
  3. If not, are there any fast algorithms that find "good" tries?
  4. What about the DAG case?

In the scenario I have in mind there is an additional constraint that no set is a subset of another set.

Any link/paper that is even slightly relevant to any of the questions is helpful.

Improve this question
$\endgroup$
8
  • $\begingroup$ I'm confused: what exactly are the objects to be stored? Sets of strings? Which operations do you want to have which runtime? $\endgroup$
    – Raphael
    Commented Mar 19, 2014 at 15:32
  • $\begingroup$ They can be of any type (in my case they are integers). I don't want to have any operations at runtime. I just want to output a compact, easy-to-read representation of the sets (like a tree or a DAG). $\endgroup$
    – George
    Commented Mar 19, 2014 at 15:46
  • $\begingroup$ Would a context-free grammar also be a easy-to-read representation? $\endgroup$
    – john_leo
    Commented Mar 19, 2014 at 16:27
  • $\begingroup$ Yes, it would. Although I'm not sure if that would allow for more compact representations (in this case) than a DAG. Intuitively, it seems to me that they would be equivalent if we allow nodes in the DAG to contain multiple values (e.g. the right-most leaf on the DAG in the example can be merged with the previous node, resulting in a node containing {3,5}). $\endgroup$
    – George
    Commented Mar 19, 2014 at 16:58
  • $\begingroup$ "easy to read" is not an objective measure. Can you give a better one? (Personally, I'd just use bit matrices, every row a bit vector for one set.) $\endgroup$
    – Raphael
    Commented Mar 19, 2014 at 21:33

3 Answers 3

Reset to default
3
$\begingroup$

I suggest you start by looking at BDDs and ZDDs.

Your problem is similar to the problem of finding an optimal BDD.

I'll explain. Suppose we have sets $S_1,\dots,S_k$ over a universe $U$ containing $n$ items (so $S_i \subseteq U$). A BDD is a finite-state automaton (a DAG) for recognizing the language of all of the allowed sets, where each set is presented to the finite-state automaton as the $n$-bit string that is the characteristic function of that set. In other words, given a total order on $U$, each set $S \subseteq U$ corresponds to a binary string $[S] \in \{0,1\}^n$: $[S]_i=1$ if $S$ includes the $i$ element of $U$, otherwise not. (This order is known in the BDD literature as a "variable ordering".) Then define the language $L$ by $L=\{[S_1],[S_2],\dots,[S_k]\}$. A BDD is a finite-state automaton that recognizes the language $L$.

Notice that you have the freedom of what "variable ordering" to choose. The choice of the variable ordering determines how each set is represented as a binary function, which can affect the size of the BDD. It is well-known that the problem of choosing the optimal variable ordering (the one that leads to the smallest BDD) is NP-hard. Nonetheless, there are various heuristics for trying to find a good variable ordering, and in real-world problems, they often work reasonably well.

So, your problem can be framed as the problem of choosing the optimal variable ordering to represent your sets as a BDD.

ZDDs are a variant of BDDs that are better in some circumstances. ZDDs are especially oriented at representing a set of sets, so they might be particularly helpful for your needs. ZDDs are especially handy if you need to represent a bunch of sets that are related to each other in some way; ZDDs provide a compact and efficient encoding for that situation.

Improve this answer
$\endgroup$
3
  • $\begingroup$ note BDDs/ZDDs are trees & not DAGs. $\endgroup$
    – vzn
    Commented Mar 20, 2014 at 5:17
  • 1
    $\begingroup$ @vzn, that is not correct. BDDs/ZDDs are DAGs, not necessarily trees. In fact the use of DAGs is essential to the compactness and efficiency of BDDs/ZDDs. $\endgroup$
    – D.W. ♦
    Commented Mar 20, 2014 at 6:17
  • $\begingroup$ oops thx was maybe thinking of straight line programs. note that there are very few papers that consider optimal BDDs/ZDDs, usually it is more heuristics. $\endgroup$
    – vzn
    Commented Mar 20, 2014 at 15:07
2
$\begingroup$

I'm not 100% sure, but I'd guess it's at least NP-hard to find the best dag that represents your set of sets.
Essentially you're trying to find the best permutations of the given sets, to then apply a DAG-algorithm on those permutations. So it might be possible to find a reduction via Binary decision diagrams, for which it is known to be NP-hard to find the best ordering.

Similarly, if you consider your set of sets as a string $S$ and hope to find a nice CNF-grammar that generates $S$, then again you're at an NP-hard problem (finding the shortest CNF-grammar for a given string). Of course that does not consider the fact that you might need to consider different permutations of the sets, but that should only make things harder.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for that answer. I was not aware of the BDD problem. I agree that it's probably NP-hard. It seems to me that one can reduce the problem of finding an optimal BDD to my problem. I think this can be done by simple representing each clause as a set of integers, finding an optimal set of sets representation and then (somehow) convert it to a BDD. I will think about the details in the next few days. $\endgroup$
    – George
    Commented Mar 19, 2014 at 21:04
-1
$\begingroup$

there is a close connection of the complexity of finding optimal DAGs as "compressions" of sets of sets (hypergraphs) to the P/Poly?=NP question sketched out here. basically/roughly speaking circuits are closely connected to DAGs and if one can find small circuits for sets-of-sets (hypergraphs) built out of NP complete patterns, one could "compress" those patterns into P-size computations. another close angle is that this is also related to hypergraph decompositions (via DAGs). more discussion in chat for anyone interested.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What are NP-complete patterns? $\endgroup$
    – Juho
    Commented Mar 20, 2014 at 8:53
  • $\begingroup$ informal concept of patterns (string sets or sets of sets) built via NP complete functions. eg the poster asks about a specific instance. note there is also a link to grammar compression $\endgroup$
    – vzn
    Commented Mar 20, 2014 at 15:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.