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

发布时间：2020-12-16 05:05:19 所属栏目：百科来源：网络整理

导读：我目前正在研究DAWG,但我找不到一种构建非循环自动机的好方法. 所以基本上,我想要做的是：它基本上是一棵树,其中状态的数量减少了.我会将它用于数字,但概念完全相同. 我想知道最快的方法是什么,我的实际计划是构建如左图所示的图形,然后查看低级别的状态以

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

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

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

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

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

问候.

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

希望这可以帮助！

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!