algorithm - 如何构建增量有向无环词图来存储和搜索字符串？

Question

我试图以简洁的方式存储大量字符串，以便可以非常快速地分析/搜索它们。

有向无环词图 (DAWG) 非常适合这个目的。但是，我首先没有要包含的字符串列表，因此它必须是可逐步构建的。此外，当我在其中搜索一个字符串时，我需要取回与结果相关的数据(不仅仅是一个 bool 值，说明它是否存在)。

我在这里找到了有关修改 DAWG 以进行字符串数据跟踪的信息:http://www.pathcom.com/~vadco/adtdawg.html它看起来非常非常复杂，我不确定我是否有能力编写它。

我还发现了一些描述增量构建算法的研究论文，尽管我发现研究论文通常不是很有帮助。

我认为我还不够先进，无法自己组合这两种算法。是否已有具有这些特征的算法的文档，或者具有良好内存使用和速度的替代算法？

Answer 1

我编写了 ADTDAWG 网页。在构建之后添加单词不是一种选择。该结构无非是4个无符号整数类型的数组。它被设计为不可变的，以实现总 CPU 缓存包含和最小的多线程访问复杂性。

该结构是一个自动机，形成一个最小的和完美的散列函数。它是为速度而构建的，同时使用显式堆栈递归遍历。

发布时，它最多支持 18 个字符。包括所有 26 个英文字符将需要进一步扩充。

我的建议是使用标准的 Trie，每个节点中存储一个数组索引。是的，它看起来很幼稚，但每个 END_OF_WORD 节点只代表一个单词。 ADTDAWG 是对传统 DAWG 中代表很多很多词的每个 END_OF_WORD 节点的解决方案。

最小和完美的哈希表不是那种你可以即时组合在一起的东西。

我正在寻找其他工作或工作，请联系我，我会尽力而为。目前，我只能说，对一个经常变化的结构进行大量优化是不现实的。