World's most popular travel blog for travel bloggers.

Heuristics for space-efficient storing of Unordered Finite Sets in a DFA

, , No Comments
Problem Detail: 

I've got an algorithm I'm working on that generates, stores, and iterates through a large number of finite sets. I'm finding that memory is a bottleneck long before time is.

The finite sets are subsets of the vertices $V$ in my graph, so each finite set is small, there's just a lot of them.

In an effort to save space, I've started representing the finite sets as binary words of length $|V|$, with a 0 indicating the element is not in the set, a 1 indicating that it is. I'm storing the collection of these words as an acyclic deterministic automaton (also known as DAWG, directed acyclic word graph).

However, this requires a fixed ordering of the potential elements, which is fine, but arbitrary. If a different ordering were more likely to produce a smaller output set, I'd be happy to use it.

I'm wondering:

  • Is there a known, efficient algorithm for finding the permutation which gives the smallest DFA representing a set of finite sets?
  • If not, has any research been done on heuristics for orderings which have been shown to often produce smaller DFAs?
Asked By : jmite
Answered By : D.W.

It sounds like you are describing a binary decision diagram, also known as a BDD. BDD's have been studied extensively in the literature, so you might take a look at the literature.

In particular, the question of finding the best permutation is known as the "variable ordering" problem for BDDs. Finding the optimal variable ordering is NP-hard. There are some heuristics, but they don't always work. See Probably the easiest approach is to use an existing BDD library (the standard ones will typically incorporate some variable ordering heuristics).

You might also be interested in ZDDs.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback