DAWG/DAFSA中的元信息

Question

我想为动态字符串实现一个字符串查找数据结构，它将支持高效的搜索和插入。目前，我正在使用trie，但如果可能的话，我想减少内存占用。This Wikipedia article描述了DAWG/DAFSA，它通过压缩后缀显然会比trie节省大量空间。然而，虽然它会清楚地测试字符串是否合法，但对于我来说，是否有任何方法可以排除非法字符串还不是很明显。例如，使用单词"cite“和"cat”，其中"t“和"e”是终端状态，DAWG/DAFSA将如下所示：

      c
     / \
    a   i
     \ /
      t
      |
      e

如果没有元信息，"cit“和"cate”将被错误地识别为合法字符串。

问题：

1)在DAWG/DAFSA中是否有更好的方式来存储有关字符串/路径的元信息(例如合法性)？

2)如果DAWG/DAFSA与需求(有效的搜索/插入和存储元信息)不兼容，那么使用什么是最好的数据结构？最小的内存占用会很好，但可能不是绝对必要的。

Answer 1

在DAWG中，只有在状态之间完全无法区分的情况下，才能将它们压缩在一起。这意味着您实际上不会将CAT和CITE的T节点组合在一起，这正是您所提到的原因-这会给出CIT上的假阳性或CAT上的假阴性。

当你有大量带有公共后缀的单词时，DAWGs对于静态字典通常是最有效的。例如，一个适用于所有英语的DAWG可以通过组合复数单词末尾的所有后缀“s”和动名词中的大多数"ING“后缀来节省大量空间。如果你要做大量的插入或删除操作，DAWGs几乎肯定是错误的数据结构，因为在DAWG中添加或删除一个单词会产生连锁反应，这需要许多以前组合在一起的分支被拆分，反之亦然。

老实说，对于大小合理的数据集，trie是一个不错的选择。一个用于所有英语的trie只会使用大约26MB，这并不是很多。我只会选择DAWG，如果空间使用真的很重要，而且你不会做太多的插入或删除操作。

希望这能有所帮助！