树编码

引言

最近，我正在用 C++ 实现一个 RandomForest 算法。 如果您对机器学习不太熟悉，没关系；这是一个非常简单的算法。 我得到一些二叉树，在我的例子中有 200 个，它们都指向一个值向量。 树中的每个节点都有一个该向量的索引和一个用于比较的阈值，如果向量中该索引处的值高于阈值，我们遍历节点的右边缘，否则我们遍历左边缘。 所有叶子都是值，通常是 1 或 0。最后，我们平均从所有 200 棵树获得的所有值，并将其与检测阈值进行比较。

很简单，不是吗？
在这篇文章中，我将重点介绍它在 C++ 中的实现。 我不会谈论首先创建这些树的机器学习部分，即所谓的训练或学习过程，但我将从我以某种规范的 ASCII 方式编码树的点开始，例如

(<100,2.0>0.0|(<111,5.0>(<112,3.0>1.0|0.20000000298)|(<113,6.0>2.5|1.20000004768)))

定义为

(<vector index, value threshold>left node|right node)

起初，我决定使用 Python 对树进行一些预处理，将其转换为某种二进制格式，这样可以更容易地实时加载，并且在 C++ 中需要更少的解析代码。 我认为尽可能避免实时解析是一个好的做法。 根据我的经验，用于解析的代码更容易出现错误和安全问题。 我将树编码为以下格式

Byte: 0x01 - Tree start symbol
Byte: 0x02 - Node symbol
Uint32: Vector index
Double (64bit Floating Point): Threshold
Left Sub Tree...
Right Sub Tree…
    Byte: 0x03 - Leaf
        Double: Tree score
Byte: 0x0ff - End of data

每日提示：我创建了一个反向函数，用于从二进制形式构建规范形式。 我用它来验证我得到的文件与输入文件完全相同，从而大大减少了错误的数量。

C++ 代码用于解析，它会将树简单地构建到节点向量中，其中 Node 是

class RandomForestNode
{
    public:
        bool isLeaf;
        uint32_t vectorIndex;
        union {
            double threshold;
            double prob;
        };
        uint32_t left;
        uint32_t right;
};

显然，这种非常直接的幼稚方法是

• 慢的。 在运行时加载新树花费了太多时间
• 浪费内存
• 浪费磁盘空间，磁盘上的二进制编码

因此，我做的第一个改进是将二进制编码更改为我可以加载到内存中的编码，而无需进行太多解析。

uint32: number of trees
uint32: number of nodes in tree
    uint16: is_leaf - [0, 1]
    if not leaf:
        uint16: vectorIndex
        uint16: index of left node
        uint16: index of right node
        double: threshold
    else:
        uint16: 0
        uint16: 0
        uint16: 0
        double: tree score
    .
    .
    .

在 C++ 中，一个节点 struct 看起来像

struct RandomForestNode
{
    uint16_t isLeaf;
    uint16_t vectorIndex;
    uint16_t left;
    uint16_t right;
    union {
        double threshold;
        double prob;
    };
};

现在，只需将树的数据读入内存，然后用指向数据中不同位置的指针填充树的向量，我就完成了树的加载。

但它仍然占用太多的磁盘和内存空间，所以我想压缩它。
我为阈值和树分数的值创建了一个查找表。 许多值，例如 0 和 1，重复了很多次，因此使用 16 位索引到值表而不是 64 位 double 节省了大量空间。
isLeaf 只有两个可能的值，True 或 False，所以 1 位就足够了。 我从左索引和右索引中各取一位，并用它来判断左节点是否是叶子以及右节点是否是叶子。 因为分数现在是我可以用 15 位编码的索引，如果节点是叶子，则索引可以是该值。 这使我可以完全删除叶节点。

新的 struct 如下

16 bits: vectorIndex
15 bits: leftIndex / scoreIndex
    1 bit: isLeftLeaf
15 bits: rightIndex / scoreIndex
    1 bit: isRightLeaf
16 bits: thresholdIndex

并且它仍然以与存储在内存中相同的方式存储在磁盘上，因此加载根本不花费任何时间。
接下来，我正在开发一种算法，用于剪切树之间相同的部分并仅存储一次，但就目前而言，这似乎是一个罕见的情况，不值得为此付出努力。
如果您对如何进一步改进此 struct 有任何想法，请分享。