string - 构造trie的并行算法？

Question

因为 trie 数据结构具有如此巨大的分支因子并且每个子树都完全独立于其他子树，似乎应该有一种方法可以通过并行添加所有单词来极大地加快给定字典的 trie 构造.

关于如何做到这一点，我最初的想法如下:将一个互斥体与 trie 中的每个指针(包括指向根的指针)相关联，然后让每个线程按照正常算法将单词插入 trie 中。但是，在跟踪任何指针之前，线程必须首先获取该指针上的锁，这样如果它需要向 trie 添加新的子节点，它就可以这样做而不会引入任何数据竞争。

这种方法的问题在于它使用了大量 的锁 - 一个用于 trie 中的每个指针 - 并且进行了大量 的获取和释放 -每个输入字符串中的每个字符一个。

有没有一种方法可以在不使用几乎所有锁的情况下并行构建 trie？

Answer 1

一个明显的无锁算法是:

1. 按长度-k 前缀对输入字符串进行桶排序(通常，k=1，但对于小字母，增加k ).
2. 对于每个字母，构造一个包含以该字母开头的所有字符串的 k 后缀的 trie。
3. 合并上一步的尝试(当k=1时，只需添加一个根节点)。

假设前缀均匀分布，这可以使您线性加速到字母表大小的 k 次方。