如何从特里构建DAWG? [英] How to construct a DAWG from a trie?

问题描述

我只是为一个词汇构建了 trie ，然后我发现有很多分支共享相同的结构.我想将它们组合在一起，结果成为 DAWG .

i just construct a trie for a vocabulary, and then I found that there are many branches shared the same struct. i want to combine them together result to be a DAWG.

我将使用哪种算法将特里转换为DAWG?

What algorithm would I use to convert a trie to a DAWG?

推荐答案

将Trie转换为DAWG的标准算法通过将Trie视为 minimum-状态DFA .

The standard algorithm for converting a trie into a DAWG works by treating the trie as a deterministic finite automaton, then converting the trie into a minimum-state DFA.

执行此转换的算法很多.我最熟悉的算法是 Hopcroft的算法，该算法通过查找对来工作区分可区分的状态并将不可区分的状态组合在一起.

There are many algorithms for performing this conversion. The algorithm I'm most familiar with is Hopcroft's algorithm, which works by finding pairs of distinguishable states and combining indistinguishable states together.

希望这会有所帮助！

这篇关于如何从特里构建DAWG?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！