构造有向无环词图的最佳方法(DAWG)

Question

我目前正在研究DAWGs，但我还没有找到一个构建非循环自动机的好方法。

所以基本上，我想做的是：

​

​

它基本上是一棵树，其中状态的数量减少了。我会把它用在数字上，但概念是完全相同的。

我想知道最快的方法是什么，我的实际计划是构建左侧所示的图形，然后查看低级别的状态，当它们相似时将它们合并。

虽然，我不确定这是最好的方法，但有谁知道如何构建它。

致以问候。

Answer 1

DAWGs是它们存储的特定集合的最小状态有限自动机。您可以通过将您拥有的trie视为非最小有限自动机并在其上运行标准的DFA最小化算法来构建它们。这可能是构建DAWG最简单的方法，也可能是最快的。

希望这能有所帮助！