4 ms·
BDDs / ZDDs are really cool, but this isn't a good link for Hacker News IMO. And the title is clickbait: its not the famous Knuth quote (and the famous Knuth qu
by dragontamer 6y ago
BDDs / ZDDs are really cool, but this isn't a good link for Hacker News IMO. And the title is clickbait: its not the famous Knuth quote (and the famous Knuth quote isn't even in the blogpost).
Maybe the Wikipedia page is a better start. Or maybe a blogpost out there is a better description of BDDs.
-------
Okay, so what is a BDD? Lets start with what problem we're trying to solve.
https://www.hillelwayne.com/post/decision-table-patterns/ https://www.hillelwayne.com/post/decision-table-patterns/
"Decision Tables are useful". Lets start with that. They're useful in a variety of algorithms and situations. The above blogpost is your "ELI5" introduction to this subject.
Now lets start talking HARD problems, I'm talking NP-hard, like traveling salesman. We can use "decision tables" to decide if "CityA + CityB" should be in a certain order in the path, or if it should be "CityB -> CityA", and the like. Ultimately, its all a table of decisions, but this table starts getting big. Very, very, very big.
Exponentially big even. Every "column" you add doubles the size of the table. We can't fundamentally get around this, but we can offer a kind of "compression". Lets start with a 3-bit table and think about things.
ABC | True / False bit
----+-----------
000 | 1
001 | 0
010 | 0
011 | 0
100 | 1
101 | 1
110 | 1
111 | 1
Okay, simple enough. But what if... we "collapsed" the table to compress the values?
ABC | True / False bit
----+-----------
000 | 1
001 | 0
01* | 0
1** | 1
Now instead of taking up 8-rows, the table only takes up 4-rows. That's the general gist of the problem: these "tables" clearly have compression available.
Now Binary Decision Trees are a compression methodology. Instead of storing a table, you store a graph. One such graph is...
A=1 -> 1
A=0 -> B=1 -> 0
A=0 -> B=0 -> C=0 -> 1
B=0 -> C=1 -> 0
Its the same information as the table, but now in graph form. It achieves the "compression" thing we're looking for.
Ultimately: that's the goal. To "compress" these tables so that they take up less RAM. But we still want to perform operations on them (such as AND/OR/NOT, but also cross-joins and a bunch of relational-algebra). The overall discovery was that the graph-form, the Binary Decision Tree, is actually pretty efficient with a large number of operations.
----
EDIT: Ah right. And the "key feature" of BDDs is the ability to share "subtables" between different tables. Notice that B=0 has two links, so there is substantial "column-savings" compared to the original table.
The "compressed table" had to store 000 and 001 in two different rows. But the A=0 -> B=0 link is "redundant information" in that situation, and itself can be compressed.
The graph form compresses that information, while the "compressed table" doesn't. These small savings don't matter on 3-bit examples. But on a 16-bit or 32-bit or larger graph, those sorts of things really add up to huge amounts of compression.
And once you start sharing subtables among "unrelated" tables (ex: lets say you have 100-such tables. The graph form provides an obvious "common subtable" that can be shared between say 20+ tables at a time. The "compressed table" cannot share such subtables in any obvious way).
You don't want to go too crazy: the optimal sub-table compression is itself an NP complete problem. But don't worry about that: this is quite common on NP-hard situations. You need to solve NP-hard subproblems to solve the greater NP-hard problem efficiently...
Instead, find a greedy, "decent" solution to compression. Simple heuristics (column ordering heuristics, variable-ordering heuristics, etc. etc.) and the like are common here. As long as it works kinda-sorta okay, you're probably fine.
- Zanni 6y agoThis is a fantastic comment, much more valuable than the linked article, and more clear and the concise than the Wikipedia article. Maybe the better blogpost out there is the one you write based on this comment? You're most of the way there ...
- dragontamer 6y agoThe secret is to use little inaccuracies, and then not sweat the details, lol. Ehh, I've got it close enough at this point. Its no where near a rigorous description of BDDs, but... sometimes an inaccurate but simple explanation is more useful than a fully accurate description.
- abecedarius 6y agoHere's an article I wrote along those lines with Python code and examples: https://codewords.recurse.com/issues/four/the-language-of-choice https://codewords.recurse.com/issues/four/the-language-of-ch...