实现内存高效的单词列表搜索树

摘要

本文介绍了一种将词汇表（字典中列出的所有单词，但不包含它们的定义）以压缩形式存储，同时提供相对快速的单词查找功能的方法。

动机和背景

在某个时候，我正在一个嵌入式平台上实现一个文字游戏，它要求玩家从字母中创建有效的单词，并因此获得分数。游戏进行的方式要求每秒进行几次单词查找。有必要有一个某种字典来验证单词，我们既有大小限制，也有速度限制。

我们最初使用的词汇表（后来稍微修改了一下）大约有 1 MB 大小。虽然在现代计算机上这看起来很小，但在嵌入式平台（如我们的情况）上，这相当大。

关于我们使用的平台的一些细节：可用内存略小于 8 MB，CPU 速度不快，而且它还必须处理许多其他任务（图形、声音等）；所有这些都意味着查找例程必须相当快。由于游戏只有英文版本，因此不需要多语言支持。

在应用程序层面，平台运行的是基于 LUA 的虚拟机。LUA 语言有表的概念，可以作为关联数组使用（内部使用哈希表实现），这在当时似乎是实现词汇表的非常合适的方法。使用 LUA 表，以单词作为键，查找函数将非常简单，类似于

function Lookup(w)
    if wordlist[w] == nil then 
        return false
    end

    return true;
end

使用精简词汇表进行的初步测试表明，查找速度确实很快，并且表的字节码表示大约是词汇表本身大小的 1.5 到 2 倍。

然而，当使用几乎完整的词汇表并运行程序时，发现一个 1 MB 的表会占用大约 8 MB 的内存，这实际上几乎是系统所有可用的内存。显然，存在问题，必须找到解决方案。

首先，需要了解内存去了哪里。经过一番研究，很明显问题出在系统使用的内存分配器以及 LUA 中表的实际实现方式。

首先，内存分配器将每个分配的块向上舍入到 4 的倍数大小，并且在内部使用两个额外的指针来管理内存块（这将是另外 8 字节）。因此，一个四个字母的单词最终会使用 16 字节（4 字节用于字母，1 字节用于终止空字符，3 字节用于填充，8 字节用于保存分配器的内部指针）。仅此一项就会使内存使用量平均增加约 4 倍。

其次，VM 表的实现是使用哈希表完成的，而哈希表固有地浪费内存，这与内存分配器问题相结合，导致在我们的情况下使用这种方法实际上是不可能的。

那时，由于语言学上的原因，决定精简词汇表，新的词汇表大小约为 600 KB——然而内存使用问题仍然存在，因为游戏需要系统的大部分内存来存储图形纹理。

最初的想法是将所有单词一个接一个地放入内存中，并通过列表进行线性搜索，这在某种程度上解决了内存问题，但完全忽略了问题的速度方面。搜索速度当然很糟糕，所以我开始将列表首先分成 26 个列表，每个列表包含以相同字母开头的单词。虽然这确实加快了搜索速度，但仍然很慢，所以我开始添加第二个索引，用于单词中的第二个字母，现在有 26*26 = 676 个表。这又增加了一个速度提升，但仍然不够。很快我意识到许多单词都有一个共同的前缀，甚至更多，有时它们在末尾只有 1 或 2 个字母不同（例如 buzz, buzzed, buzzer, buzzers, buzzes, buzzing）。这让我觉得树结构对我来说更合适，所以我开始实现一个。

第一次实现（搜索树）

考虑以下单词：abc, abd, abcd, abcde, abcdf, abcdfa, abcdfb, abcdfc。

它们可以以下列方式表示为树

当从根向下遍历树时，每层只选择一个字母，将形成单词，圆形字符将标记有效单词的结尾。

请注意，共同的后缀（例如 abc）实际上只存储一次，并被所有它形成的单词重用。

该树可以（在 C++ 中）这样实现

struct Node
{
    char ch;
    bool b_fullword;
    Node * next;
    Node * down;
};

要将单词添加到树中，我们将执行类似以下操作

Node * d = root;
char * s = lookup_word;
while (! b_done)
{
    // look horizontally
    while ( ( d->ch != *s ) && (d->next != NULL) )
    {
        d = d->next;
    };
    
    // we verify if we found the letter
    if ( d->ch != *s )
    {
        // letter not found, we start adding it
        d->next = CreateNode();
        d->next->ch = *s;
        d = d->next;
        s++;
        AddDown(d, s);
        b_done = 1;
    }
    else
    {
        // letter found, go to next letter
        s++;

        if (*s == 0)
        {
            // it was the last letter
            d->b_fullword = 1;
            b_done = 1;
        }
        else
        {
            // there are still letters in the word
            if (d->down)
            {
                d = d->down;
            }
            else
            {
                AddDown(d, s);
                b_done = 1;
            }
        }
    }
}

AddDown 函数看起来像这样

    while (*s != 0)
    {
        d->down = CreateNode();
        d->down->ch = *s;
        s++;
        d = d->down;
    }
    d->b_fullword = 1;

查找函数将从根开始横向查找当前字母。一旦找到它，它就会向下并重复该过程，直到字符串结束，或者它找不到字母，或者不再有向下链接。例程必须检查最后访问的节点是否终止一个单词（b_fullword 为 true），然后才能返回成功。

复杂性分析

显然，搜索速度将取决于字母表中的字母数量和查找单词的长度。前者是常数，后者也有限（在我们的例子中，我们将单词限制为 8 个字母，但一般来说，单词将具有少量有限的字母）。最坏的理论情况是遍历 26 个节点 8 次，即 208 个节点，但平均而言，一次查找只进行 20 到 40 次节点遍历，这在我们的情况下是合理的。

然而，内存需求却相当高。我们使用的词汇表生成了大约 150,000 个节点，每个节点使用 12 字节内存（bool 类型在该机器上使用 4 字节，结构向上舍入到 4 字节边界），并且分配器为每个节点额外消耗 8 字节，我们实际上使用了大约 3 MB 内存。

幸运的是，该结构远未优化，因为我们实际上可以在不牺牲搜索速度的情况下减少内存使用。

第二次实现（序列化搜索树）

我们能做的第一件事是实际消除内存分配器的开销，它为每个节点消耗 8 字节（在我们的例子中，其他一些分配器可能会使用更多或更少），这表示节点使用的内存不到一半。

为此，我们必须将节点按顺序放置在内存中，放置在预分配的内存块中，并让指向下一个和向下元素的指针反映新的节点内存位置。

实现此操作的细节超出了本文的范围，因为它没有什么特别之处。

然而，在内存方面，我们现在有 150 K 个只有 12 字节的节点，现在只占用 1.8 MB 内存。

更好的实现（序列化搜索树，分组和打包字母）

快速查看实现，我们意识到我们为每个节点浪费了 4 字节（sizeof (Node*)）来保存指向下一个横向字母的指针，而我们实际上可以有一个节点数组形成一个字母节点块，每个节点只包含一个字母、一个完整单词标志和向下指针。

此外，英文字母只使用 26 个字母，在我们的范围内我们不区分大小写，所以我们实际上只需要 5 位来存储字母，1 位来存储完整单词标志，因此我们可以将它们组合成一个字节。

一个节点现在将包含一个字节（包含字母和标志）和四个字节用于向下指针，并且同一级别上所有继续前缀的字母都将分组到块中。这些块将以一个字节开头，该字节保存块中的字母数量，后面是每个字母的五个字节。目前我们将考虑一个节点占用五个字节（它最多占用六个字节，平均介于两者之间），所以我们现在使用 150 K * 5 字节 = 750 KB 内存！

这比我们最初开始使用的好得多，但我们可以做得更好。

更优的实现（打包字母和可变长度指针）

现在我们使用 5 字节在树中存储一个字母，1 字节用于字母和标志，4 字节用于向下指针。但是我们真的需要 4 字节来存储指针吗？如果我们使用相对于内存块开头的指针，我们只需要 20 位来表示距离（20 位可以寻址 1 MB 内存）。

我们可以只用 3 字节来表示指针，从而节省更多内存。然而，根据节点在内存中的排列方式，我们可能实际上需要更少的寻址位来表示指针。

还记得字母+标志字节中剩下 2 位吗？我们可以用它们来实际存储向下指针的大小。我们暂时称它们为 psize 位。

对于没有向下指针的节点，我们将设置 psize = 0。

• 如果下一个节点的相对位置适合一个字节，我们将设置 psize = 1。
• 如果下一个节点的相对位置适合两个字节，我们将设置 psize = 2。
• 如果下一个节点的相对位置适合三个字节，我们将设置 psize = 3。
• 如果下一个节点的相对位置不适合三个字节，我们将中止该过程（在我们的词汇表案例中，这是不可能的）。

当然，我们将节点放入内存块中的顺序将影响它们之间的相对距离。在一般情况下，我们可以尝试找到最优的节点排列方式，以最小化指针大小，但我不知道有任何快速（实用）的算法可以做到这一点。

一种方法是暴力破解——生成所有可能的排列并尝试所有，这样我们肯定能找到最优解。另一种方法是使用蒙特卡罗方法——尝试随机排列直到结果看起来接近最优解。虽然我没有实际尝试过，但这种方法可能实际上会提供一些结果。

另一种更实用的方法是按“自然”顺序将节点布置在内存中。为此，我们必须记住我们放入的数据——单词。在一个有序的单词列表中，大多数单词将与下一个单词有一个共同的前缀，因此如果我们把所有后缀在树中相互靠近，指向彼此的指针将相对较短。实现这一点的一个简单方法是从根向下遍历树，添加一个节点，然后从左到右访问其向下后代。

在我们的案例中，以这种方式遍历树会得到以下结果

• psize == 0 : 56131 个元素
• psize == 1 : 91064 个元素
• psize == 2 : 6696 个元素
• psize == 3 : 28 个元素

现在我们对 psize == 0 的元素使用 1 字节，对 psize == 1 的元素使用 2 字节，依此类推。

只有大约 5% 的元素使用 3 或 4 字节内存，大约 58% 使用 2 字节，大约 36% 使用 1 字节。

现在词汇表的内存使用量已降至 345 KB，这几乎是原始树内存使用量的 10 倍，同时我们仍然可以进行快速单词查找！

结论

我们上面展示了如何设法压缩词汇表大小，同时仍然提供相对快速的查找例程。还有其他可能的改进可以加快搜索速度并进一步减少内存，我们将在下面介绍其中的一些

1. 树的根节点和第 2 级节点可能包含字母表中的大部分字母。对于这些节点来说，拥有一个特殊的节点结构可能会很有价值，其中我们可以为字母表中的每个字母分配 4 字节，3 字节用于存储向下指针，1 字节用于存储完整单词标志和用于确定字母是否存在 的标志。在该节点中查找字母将在恒定时间内完成（因为它只是数组中的一个索引）。这将略微增加词汇表的大小，但会大大加快搜索速度。
2. 树中的大多数节点（超过 50%）只包含一个字母，并且它们使用 2 字节 + psize 来表示。针对这种情况的特殊处理可以节省大量内存。一种方法是在向下指针中添加一个标志（这当然会增加向下指针的大小，但平均而言仍然会显著节省内存）。
3. 词汇表的大小现在可以用 19 位指针完全寻址，但我们有时使用 24 位。更改数据结构，使其使用半字节而不是完整字节（并进一步对节点进行位打包）可能会获得一些额外的内存。然而，这种方法必须克服一些其他问题（指针大小现在需要 3 位，并且它将不适合两个半字节“内存单元”；内存地址空间将翻倍，需要一个额外的地址位；搜索会因为额外的位解包要求而变慢）。

然而，无论出于何种原因需要使用词汇表，将其组织成这种结构将节省一些内存并加快搜索速度。即使在现代机器上，拥有一个低内存使用量的词汇表也会更利于缓存，从而提高应用程序的性能。