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

Question

我目前正在研究DAWG,但我找不到一种构建非循环自动机的好方法.

所以基本上,我想要做的是:

它基本上是一棵树,其中状态的数量减少了.我会将它用于数字,但概念完全相同.

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

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

问候.

Answer 1

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

希望这可以帮助！