c++ - 如何创建DAWG？

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center。
                            
                        
                    
                
                                6年前关闭。
            
                    
DAWG如何创建？我发现有两种方法：一个正在将特里转换成dawg，另一个正在立即创建新的DAWG？哪一个最简单？您能否详细说明两者并提供一些链接？

最佳答案

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


首先，为单词集合构造一个trie。
将一个新节点添加到trie，并在所有输入上使其自身具有边缘。
对于特里树中每个丢失的字母过渡，添加从起始节点到该新的死节点的过渡。
（此时，这组单词现在有一个（可能不是最小的）DFA。）
使用the standard algorithm for DFA state minimization最小化DFA。


完成此操作后，您将获得DAWG，以获取您感兴趣的一组单词。

该算法的运行时间如下。可以通过为所有原始单词构造一个trie（花费时间O（n），其中n是所有输入字符串中的字符总数）来构造初始DFA，然后填写缺少的过渡（花费时间） O（n |Σ|），其中|Σ|是字母表中不同字符的数量）。从那里开始，最小化算法在时间O（n2 |Σ|）上运行。这意味着该算法的总运行时间为O（n2 |Σ|）。

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

希望这可以帮助！