c++ - 如何创建 DAWG？

Question

如何创建DAWG？我发现有两种方法；一个是将 trie 转换为 dawg，另一个是立即创建一个新的 DAWG？哪一个最容易？您能否详细说明两者并提供一些链接？

Answer 1

考虑 DAWG 的一种方法是作为单词列表中所有单词的最低状态 DFA。因此，构建 DAWG 的传统算法如下：

1. 首先为单词集合构建一个 trie。
2. 将一个新节点添加到特里树中，所有输入的边都从自身到自身。
3. 对于 trie 中的每个缺失字母转换，添加从开始节点到这个新死节点的转换。
4. （此时，您现在有一个（可能不是最小的）单词集的DFA。）
5. 使用DFA 状态最小化的标准算法来最小化 DFA。

完成此操作后，您将得到一个 DAWG，用于您感兴趣的一组单词。

该算法的运行时间如下。构造初始 DFA 可以通过为所有原始单词构造一个 trie 来完成（这需要时间 O(n)，其中 n 是所有输入字符串中的字符总数），然后填充缺失的转换（这需要时间O(n|Σ|)，其中 |Σ| 是字母表中不同字符的数量）。从那里，最小化算法在时间 O(n ² |Σ|) 中运行。这意味着算法的整体运行时间为 O(n ² |Σ|)。

据我所知，没有直接的算法可用于增量构建 DAWG。通常，只有在您已经预先拥有所有单词的情况下，您才会为一组单词构建 DAWG。直观地说，这是正确的，因为插入一个在 DAWG 中已经存在一些后缀的新词可能需要对 DAWG 进行大量重组，以使某些旧的接受状态不接受，反之亦然。从理论上讲，这是因为插入一个新词可能会极大地改变 DFA 的可区分性关系的等价类，这可能需要对 DFA 的结构进行重大更改。

希望这可以帮助！