5

我目前正在研究 DAWG，但我还没有找到一种构建无环自动机的好方法。

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

工作组

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

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

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

问候。

4

1 回答 1

3

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

希望这可以帮助！

于 2013-10-08T18:06:03.123 回答