我曾经为一个客户在C语言中实现过这样的结构。最终的结构是从一个描述字符集和dawg的xml文件中加载的,另一个进程从单词列表创建了该xml文件。
步骤1:构建第一个dawg并将其序列化为xml文件
我们使用了:
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;
node_t* root;
} build_dawg_t;
子串按升序排序,单词结束特殊字符小于任何其他字符。
算法非常简单:
foreach word in wordlist
insert(dawg, word)
compact(dawg)
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>
步骤二:最终的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;
这里的根节点是dawg.nodes [0],而first_child / next_sibling是节点数组中的索引。从xml文件创建这样的结构很容易。主要缺点是任何单词列表修改都会触发生成新的xml文件。