string - 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 上出现漏报。

当您有大量带有共同后缀的单词时，DAWG 通常对静态词典最有效。例如，用于所有英语的 DAWG 可以通过组合复数单词末尾的所有后缀“s”和动名词的大部分“ING”后缀来节省大量空间。如果您要进行大量插入或删除操作，DAWG 几乎肯定是不适合这项工作的数据结构，因为在 DAWG 中添加或删除单个单词会引起链式 react ，需要大量分支，而这些分支以前组合在一起 split 或相反。

老实说，对于大小合理的数据集，trie 树是个不错的选择。对所有英语进行一次 trie 只会用掉大约 26MB，这并不是很多。如果空间使用确实非常宝贵并且您没有进行很多插入或删除操作，我只会选择 DAWG。

希望这对您有所帮助!