java - 简单的 DAWG 创建算法？

Question

我需要为我的拼字游戏播放器创建一个 DAWG ( http://en.wikipedia.org/wiki/Directed_acyclic_word_graph) 结构，给定文件中的单词列表。我正在使用 Java。我只需要执行一次，然后将其存储在一个或多个文件中。到目前为止，我已经看到了 2 种方法:1) 构建一个 Trie 并将其缩减为 DAWG 或 2) 立即构建一个 DAWG。因为我只需要做一次，所以我想我只想要最简单的算法来实现它。速度和内存要求无关紧要。

我还想知道在运行时应该如何将结构存储在内存中以及如何将其保存在文件中？ DAWG 基本上是一个图表，它建议使用我编写的一些非常简单的类的一些节点和边/指针，但我看到使用数组和偏移量(在此数组中)的实现看起来复杂且难以辨认。这次我关心内存大小(在运行时和保存的文件)和加载 DAWG/使用 DAWG 的速度。

Answer 1

this paper 中定义了最简单、最高效的 DAWG 构造算法。 ，并要求对 DAWG 表示的词集进行排序。鉴于您计划从预先存在的单词列表构建 DAWG，该列表可能已经排序，或者可以用于此目的。

我粗略地以比论文中给出的格式更“程序员友好”的格式转录了该算法的伪代码(免责声明:我可能犯了一些转录错误；您可能应该看看原文判断是否有):

Given:
        startState is the state from which traversal of the DAWG is to start
        register is a map of representations (hint: hashes) OF graphs which extend 
        from states in the DAWG TO said states

While there is newWord in wordList
    Get newWord from wordList
    Determine longestPrefix of newWord, starting from startState, which already exists in DAWG
    Get longestPrefixEndState, the state which the sequence of transitions defined by longestPrefix leads to
    Get suffix of newWord, the substring of newWord after longestPrefix
    if longestPrefixEndState has children 
        replace_or_register(longestPrefixEndState)
    endIf
    Create the sequence of transitions and states defined by suffix, starting from longestPrefixEndState
endWhile
replace_or_register(startState)


function replace_or_register(argState)
    Get greatestCharEndState of argState, the state which the lexicographically-greatest-char-labelled-transition in the outgoing transition set of argState leads to
    if greatestCharEndState has children
        replace_or_register(greatestCharEndState)
    endIf
    if there exists state in DAWG that is in the register and is equivalent (has an identical graph extending from it) to greatestCharEndState
        Redefine the transition that extends from argState to greatestCharEndState, as one that extends from argState to state
        Delete greatestCharEndState
    endIf
    else 
        add greatestCharEndState to the register
    endElse

鉴于您使用的是 Java，您可以利用 Serializable接口(interface)来处理您所有的序列化和反序列化需求。

如果您对实现上述算法的现有 Java DAWG 实现感兴趣，请查看 MDAG ，它还提供了一些其他实现所没有的漂亮功能(包括即时添加和删除字符串)，并且由我维护!