3

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

      c
     / \
    a   i
     \ /
      t
      |
      e

并且“cit”和“cate”将被错误地识别为没有一些元信息的合法字符串。

问题：

1) 是否有一种首选方法可以在 DAWG/DAFSA 中存储有关字符串/路径（例如合法性）的元信息？

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

4

1 回答 1

3

在 DAWG 中，只有当它们彼此完全无法区分时，才能将它们压缩在一起。这意味着您实际上不会将 CAT 和 CITE 的 T 节点组合在一起，这正是您所指出的原因 - 这会给您在 CIT 上的假阳性或在 CAT 上的假阴性。

当您有大量具有共同后缀的单词时，DAWG 通常对静态词典最有效。例如，适用于所有英语的 DAWG 可以通过将复数词末尾的所有后缀“s”和动名词中的大多数“ING”后缀组合起来来节省大量空间。如果您要进行大量插入或删除操作，DAWG 几乎肯定是不适合这项工作的数据结构，因为从 DAWG 中添加或删除单个单词会导致涟漪效应，需要之前合并的大量分支分裂或反之亦然。

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

希望这可以帮助！

于 2014-12-17T20:13:29.043 回答