简单的 DAWG 创建算法？

Question

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

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

Answer 1

我曾经不得不用 C 语言为我的一位客户实现这样的结构。最终结构是从描述字符集和 dawg 的 xml 文件加载的，另一个进程从单词列表创建 xml 文件。

步骤 1：构建序列化为 xml 文件的第一个 dawg 的结构

我们用了 ：

typedef struct _s_build_node build_node_t;
struct _s_build_node {
  char_t letter;
  build_node_t* first_child;
  build_node_t* right_sibling;

  hash_t hash;
  size_t depth;
  size_t ID;
};
typedef struct _s_build_dawg {
  charset_t charset;
  node_t* all_nodes; // an array of all the created nodes
  node_t* root;
} build_dawg_t;

siblibgs 按升序排列，词尾特殊字符少于任何其他字符。该算法非常简单：

// create the build dawg
foreach word in wordlist
  insert(dawg, word)
// compact the dawg
compact(dawg)
// generate the xml file
xml_dump(dawg)

为了压缩 dawg，我们计算每个节点的哈希值。具有相同散列的两个节点可以被分解。这部分可能很棘手。仅保留深度最低的节点，其他节点将被删除，并且它们的父节点现在指向保留的节点。
压缩后，我们为每个节点分配一个唯一的 ID（通过 bfs，ID 介于 0 到 N-1 之间，N 是压缩后的 dawg 中的节点数）。xml 文件简单地描述了 trie ：

<dawg>
  <charset ....>
    ...
  </charset>

  <node ID="node_id" letter="letter" fist_child="first_child_ID" next_sibling="next_sibling_id" />
  <node .... />
  <node .... />
  <node .... />
</dawg>

步骤 2：最终的 dagw

结构稍微简单一点

typedef struct {
  char_t letter;
  size_t first_child;
  size_t next_sibling;
} node_t;

typedef struct {
  node_t nodes[];
  ... whatever you need ...
} dawg_t;

这里的 root 是 dawg.nodes[0]，first_child/next_sibling 是节点数组中的索引。从 xml 文件创建这样的结构很容易。主要缺点是任何单词列表修改都会触发新 xml 文件的生成。