構建有向非循環詞圖（DAWG）的最佳方法

我目前正在研究DAWG，但我一直未能找到一種構建非循環自動機的好方法。構建有向非循環詞圖（DAWG）的最佳方法

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

DAWG

它基本上是一棵樹，其中減少狀態的數目。我會用它與數字，但概念是完全一樣的。

我不知道什麼是最快的方式來做到這一點，我的實際計劃是構建如左圖所示的圖形，然後查看低級別的狀態以及何時將它們合併。

雖然，我不確定這是做這件事的最好方法，但是沒有人有關於如何構建它的想法。

問候。

來源

2013-10-08 Anoracx

您有DFA的表示形式。你可以將它減少到最小的DFA（有相當標準的算法） – SheetJS

我知道，但我實際上正在尋找一種方法來做那一個（或僞代碼） – Anoracx

https://en.wikipedia.org/wiki /DFA_minimization#Hopcroft.27s_algorithm – SheetJS

DAWGs是特定集合的最小狀態有限自動機，如果它們存儲的是字符串。您可以通過將您擁有的樹作爲非最小有限自動機並對其運行標準DFA最小化算法來構造它們。這可能是構建DAWG最簡單的方法，也可能是最快的。

希望這會有所幫助！

來源

2013-10-08 18:06:03 templatetypedef

嗯，是的，但有多種最小化算法，我寧願建立DAWG「我自己」，因爲我需要將它存儲在數組中有一點。我實際上正在尋找一個僞代碼來獲取樹 - > DAWG。 – Anoracx

@ Anoracx-我想我對你在問什麼感到困惑。 trie-> DAWG步驟是DFA最小化步驟。「你自己構建DAWG是什麼意思？」 – templatetypedef

嗯，我從閱讀維基百科想到，DAWG（DAFSA）是一種從普通樹/ DFA構建的樹。所以我實際上認爲會有一個特定的算法來做到這一點。而不僅僅是最小化算法。所以當我說我想自己做，我實際上是在尋找一種將它從DFA轉換爲DAFSA（DAWG）的方式，並且如果從底層開始的想法是一個好主意。 – Anoracx

構建有向非循環詞圖（DAWG）的最佳方法

回答

相關問題