基于非排序数据的可更新DAWG库或DAWG构造

Question

dawgdic是一个很棒的DAWG库，但它有一个很大的缺点，因为它是静态的(不可更新)，并且必须由按字母顺序排序的字符串构建。如果用来构造DAWG的原始数据很大(几is )，那么DAWG的初始构造涉及对大量字符串数组进行排序，可能需要太多的资源。

有没有一个库可以提供像dawgdic这样的内存高效结构，允许从非排序字典进行构造？

Answer 1

目前，我不认为有任何库允许从未排序的字典中构造DAWGs。

但是，经过大量的搜索，我找到了这篇论文， ，我认为它正是你想要的。也许你可以在读完这篇文章后制作自己的库，并与大家分享！

编辑：你看过this question吗？

Answer 2

我发现了一些很棒的库，它们允许从未排序的数据进行在线构建，尽管它们不是基于DAWG：

1. cedar -一个非常快的双数组trie
2. marisa-trie -

的а非常节省空间的字符串匹配库

Answer 3

据我所知，目前还没有支持从非排序数据构造的DAWG的C++实现，但如果你愿意创建自己的解决方案，它具有这样的功能，Incremental Construction of Minimal Acyclic Finite-State Automata (2000)是一篇基本上展示了它背后的算法的论文。

或者，如果您愿意移植来自其他语言的解决方案，那么可能值得花时间查看MDAG，这是一种数据结构的Java实现。它支持动态字符串添加和字符串删除，这正是您正在寻找的。代码也很容易理解，并且有广泛的注释，所以移植它应该是一项相当简单的任务。

免责声明:我是MDAG :)的作者。