Beautiful trees, without the landscaping. Bonsai is a Scala library for transforming arbitrary tree structures into read-only versions that take up a fraction of the space.
Bonsai compresses trees in 2 ways: by using significantly less space to store the tree structure itself (tree compression), and by encoding the node labels in a memory efficient structure (label compression).
Bonsai works over arbitrary trees, so it assumes a fairly generic interface for interacting with trees. In Bonsai a tree;
- has 0 or 1 root nodes
- each node has 0 or more children
- each node has a label attached to it
The actual type of the node is unimportant. What is important is the node labels and the relationships between the nodes (parent, child, sibling, etc). This structure is enough to describe most of the types of trees you are familiar with.
Bonsai encodes this notion of trees with the TreeOps type class. Here is a truncated version of the type class:
trait TreeOps[Tree, Label] {
/** The type of the nodes in the tree. */
type Node
/**
* Returns the root node of the tree.
*/
def root(t: Tree): Option[Node]
/**
* Returns all the direct children of the given node. The order may or may
* not matter. TreeOps does not provide any guarantees here.
*/
def children(node: Node): Iterable[Node]
/**
* Returns the label attached to the given node.
*/
def label(node: Node): Label
...
}The type T is our actual tree type. The Node type is the way we reference
internal nodes in our tree T. The actual type of Node isn't important,
however, and is mostly an implementation detail. The important bit is the
Label type, which is the user-facing data associated with each node.
The bonsai-example subproject has an example of a Huffman tree.
A Huffman tree is used to store a Huffman coding for decoding a compressed
message (a bitstring). We decode the bitstring, bit-by-bit, using the tree.
Starting at the root of the tree, we follow the left child if the current bit is a 0 and the right child if it is a 1. We continue until reaching a leaf node, at which poitn we output the symbol associated with it, then start back at the beginning of the tree. When we've exhausted the entire bitstring, we'll have our decoded message.
Here is how we may implement a Huffman tree in Scala:
sealed trait HuffmanTree[+A]
case class Branch[+A](zero: HuffmanTree[A], one: HuffmanTree[A]) extends HuffmanTree[A]
case class Leaf[+A](value: A) extends HuffmanTree[A]And here is how we would implement its TreeOps instance:
import com.stripe.bonsai.TreeOps
object HuffmanTree {
implicit def huffmanTreeOps[A]: TreeOps[HuffmanTree[A], Option[A]] =
new TreeOps[HuffmanTree[A], Option[A]] {
type Node = HuffmanTree[A]
def root(tree: HuffmanTree[A]): Option[HuffmanTree[A]] = Some(tree)
def children(tree: HuffmanTree[A]): Iterable[HuffmanTree[A]] = tree match {
case Branch(l, r) => l :: r :: Nil
case _ => Nil
}
def label(tree: HuffmanTree[A]): Option[A] = tree match {
case Leaf(value) => Some(value)
case _ => None
}
}
}As long as we are careful to implement all our operations on a Huffman tree by
using its more generic TreeOps interface, rather than HuffmanTree directly,
we can then swap out the actual tree data structure, without affecting the code
using it.
For example, below we implement a decode operation as an implicit class using just TreeOps.
import scala.collection.immutable.BitSet
implicit class HuffmanTreeOps[T, A](tree: T)(implicit treeOps: TreeOps[T, Option[A]]) {
// Importing treeOps gives us some useful methods on `tree`
import treeOps._
def decode(bits: BitSet, len: Int): Vector[A] = {
val root = tree.root.get
val (_, result) = (0 until len)
.foldLeft((root, Vector.empty[A])) { case ((node, acc), i) =>
node.label match {
case Some(value) => (root, acc :+ value)
case None if bits(i) => (node.children.head, acc)
case None => (node.children.iterator.drop(1).next, acc)
}
}
result
}
}The goal of this indirection through TreeOps is to let us use a compressed
version of the tree instead of an actual HuffmanTree, which will see below.
Bonsai's tree compression is based off of a succinct data structure for binary trees. Bonsai supports k-ary trees by first transforming the original tree into a left-child right-sibling tree, which preserves all the relationships from the original tree, but ensures we have at most 2 children per node. You can read more about the details of the actual compression algorithm used in "Practical Implementation of Rank and Select Queries". The upshot is that we can store the entire structure of a tree in only ~2.73bits per node. This replaces the normal strategy of using JVM objects for nodes and references to store the relationships.
We actually compress trees by transforming them into Bonsai Trees.
Bonsai's Tree constructor takes any arbitrary tree T that has a
TreeOps[T] available and will return a Tree with the same structure
and labels (and Label type) as the original tree. However, the entire
structure and labels of the tree will have been compressed, so this new tree
requires significantly less space.
In the example in bonsai-example, we use the Huffman encoding described above
to construct a simple Huffman tree for the printable ASCII characters (0x20 ->
0x7E) and compress it using Bonsai's Tree. The result is a 11x reduction
in memory requirements. Since our decode operation was implemented using
TreeOps, we can use this compressed tree just as we would've used the
original tree.
This example is a bit contrived, since the trees are small to begin with, but you can imagine that applying this to a large random forest yields great results.
Bonsai provides a Layout type class, along with some simple
combinators, for describing how to (de)serialize your labels. At the lowest
level are a set of Layout "primitives" that can encode simple data types into
compact data structures. The combinators then allow more complex structures to
be described (tuples, Either, mappings to case classes, etc), without adding
much, if any, overhead.
Here is an example of a Layout for some Widget type we made up:
import com.stripe.bonsai.Layout
sealed trait Widget
case class Sprocket(radius: Int, weight: Option[Double]) extends Widget
case class Doodad(length: Int, width: Int, weight: Option[Double]) extends Widget
object Widget {
implicit val WidgetLayout: Layout[Widget] = {
Layout[Either[(Int, Option[Double]), ((Int, Int), Option[Double])]].transform(
{
case Left((r, wt)) => Sprocket(r, wt)
case Right(((l, w), wt)) => Doodad(l, w, wt)
},
{
case Sprocket(r, wt) => Left((r, wt))
case Doodad(l, w, wt) => Right(((l, w), wt))
}
)
}
}You can see the full Widget code/example in the bonsai-example sub
project. In that example, we compress a Vector[Option[Widget]] using the
layout and end up with over a 6x reduction in memory requirements.
Currently, Bonsai focuses mainly on compressing the overhead of the structure your data requires (eg options, eithers, tuples), rather than the data itself. This will likely change in future releases, and we'll support better compression for primitive types, as well as things like dictionary encoding for all types.
Bonsai is published on sonatype. To use it in your SBT project, you can add the
following to your build.sbt:
libraryDependencies += "com.stripe" %% "bonsai" % "0.3.0"Bonsai is Open Source and available under the MIT License.
For more help, feel free to contact the authors or create an issue.