我想为动态字符串实现一个字符串查找数据结构，该结构将支持有效的搜索和插入。当前，我正在使用Trie，但我想尽可能减少内存占用。 This Wikipedia article描述了DAWG / DAFSA，它显然可以通过压缩后缀来节省大量的空间。但是，尽管它可以清楚地测试字符串是否合法，但对于我来说，是否有任何方法可以排除非法字符串，这并不明显。例如，使用单词“cite”和“cat”，其中“t”和“e”是终端状态，DAWG / DAFSA看起来像这样:
c
/ \
a i
\ /
t
|
e
而“cit”和“cate”将被错误地识别为合法字符串，而没有某些元信息。
问题:
1)是否有一种首选的方式可以在DAWG / DAFSA中存储有关字符串/路径(例如合法性)的元信息？
2)如果DAWG / DAFSA与要求(有效的搜索/插入和存储元信息)不兼容，那么最佳的数据结构是什么？最小的内存占用量会很好，但可能并非绝对必要。
最佳答案
在DAWG中，仅在状态彼此完全无法区分时才将它们压缩在一起。这就是说，您实际上并不会因为您指出的原因而将CAT和CITE的T节点组合在一起-这会给您带来CIT误报或CAT误报。
当您有大量带有常见后缀的单词时，DAWG通常对于静态词典最有效。例如，针对所有英语的DAWG可以通过将复数单词末尾的所有后缀“s”与动名词中的大多数“ING”后缀组合在一起来节省大量空间。如果您要进行很多插入或删除操作，DAWG几乎可以肯定是错误的数据结构，因为从DAWG中添加或删除单个单词可能会引起涟漪效应，而这种涟漪效应需要先前合并成许多分支分裂，反之亦然。
老实说，对于合理大小的数据集来说，trie并不是一个坏电话。对于所有英语而言，一次尝试只会消耗大约26MB的内存，这不是很多。如果空间使用确实非常宝贵，并且您没有进行太多插入或删除操作，那么我只会选择DAWG。
希望这可以帮助!