盆栽：树木的紧凑表示

摘要 本文展示了如何使用哈希表将树以一种非常紧凑的形式存储，称为“盆栽”。描述了一种适合在预定义最大尺寸限制内单调生长的大树的方法。使用它时，任何树中的指针可以在每个节点中用 6 + log 2 n 位表示，其中 n 是节点可以拥有的最大子节点数。我们首先描述了在哈希表中存储树的一般方法，然后介绍了构成盆栽结构基础的紧凑哈希思想。这两种技术结合在一起，提供了树的紧凑表示，并制定了一种实用的方法论，以允许这些结构的设计。新的表示方式与两种传统树实现的每个节点所需存储空间进行了比较。那些必须在严格最大尺寸内存储大树的程序示例包括操作从自然语言文本衍生的字典树结构的程序。我们描述了盆栽技术如何应用于文本压缩和自适应预测中出现的树，并讨论了在实践中效果良好的设计参数。