DAWG 和 Trie 有什么区别？为什么能压缩重复后缀？
简化版
DAWG 可以理解成把 Trie 中等价的后缀状态合并后的有向无环图。
普通 Trie 主要共享前缀，不共享后缀；DAWG 不仅共享前缀，还会合并相同后缀结构，所以空间更紧凑。
它适合大词典、拼写检查、词形查询等场景，但构建复杂度比普通 Trie 高，理解成本也更高。
详细版
Trie 是树结构，一个节点只有一个父节点。
DAWG 是有向无环图，一个状态可能被多个前缀共享。它会把「从某个节点往后能接受的字符串集合完全相同」的状态合并。
| 结构 | 共享能力 |
|---|---|
| Trie | 共享前缀 |
| DAWG | 共享前缀和等价后缀状态 |
例如很多单词都有后缀 ing，普通 Trie 可能重复存储多条 i -> n -> g 路径，而 DAWG 可以把等价后缀状态合并。
完整版教学
1. Trie 的压缩边界在哪里
Trie 最大的优势是共享前缀。
例如：
car
cat
cap它们共享 ca。
但如果很多单词共享后缀，普通 Trie 通常帮不上忙，因为后缀来自不同父路径。
2. DAWG 的核心思想
DAWG，全称 Directed Acyclic Word Graph，是有向无环词图。
它不要求每个节点只有一个父节点，而是允许多个前缀指向同一个等价后缀状态。
DAWG 的关键不是随便合并节点，而是合并「后续可接受字符串集合相同」的状态。
3. 什么叫等价后缀状态
如果两个节点往后能匹配的所有后缀集合完全一样，就可以合并。
例如两个节点后面都只能接受：
ing并且结束标记和分支结构也一致，那么它们代表的后续语言相同，可以共享。
这和最小化确定有限自动机的思想很接近。
4. Trie 和 DAWG 的结构差异
Trie 是树：
每个节点只有一个父节点DAWG 是 DAG：
一个节点可以有多个入边| 维度 | Trie | DAWG |
|---|---|---|
| 结构 | 树 | 有向无环图 |
| 构建 | 简单 | 复杂 |
| 查询 | 逐字符走 | 逐字符走 |
| 空间 | 可能重复后缀 | 更紧凑 |
查询过程仍然类似自动机转移，但构建和维护更复杂。
5. 为什么 DAWG 能省空间
假设有很多后缀相同的单词：
walking
talking
running普通 Trie 可能为不同前缀分别建立后缀路径。
DAWG 可以把相同的后续状态合并，让多个路径共享后半段。
这会显著减少大词典里的重复结构。
6. 代价是什么
DAWG 不是白捡空间。
它的代价包括：
- 构建算法更复杂；
- 动态插入删除更麻烦；
- 调试和理解成本更高；
- 节点合并需要严格等价判断；
- 不如 Trie 容易手写。
因此面试中通常要求理解思想，不太会要求现场完整实现。
7. 适合什么场景
DAWG 适合大规模静态词典。
| 场景 | 原因 |
|---|---|
| 拼写检查 | 词典大且查询多 |
| 单词游戏 | 需要快速判断词是否存在 |
| 词形分析 | 后缀重复多 |
| 只读索引 | 构建一次，多次查询 |
如果词典频繁变化，普通 Trie 或压缩 Trie 可能更简单。
8. 常见误区与追问
- 误区：DAWG 只是压缩 Trie 的另一种名字。 压缩 Trie 合并单孩子路径，DAWG 合并等价后缀状态。
- 误区：DAWG 仍然是一棵树。 它是有向无环图，节点可以有多个父节点。
- 误区：DAWG 查询一定比 Trie 快很多。 空间更小不代表一定更快，查询常数和实现有关。
- 追问：为什么能合并后缀？ 因为某些节点的后续可接受字符串集合完全相同。
- 追问：什么时候不适合 DAWG？ 词典频繁动态更新、规模不大、开发成本敏感时不适合。