クライアントの 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)
仲の良い友達をコンパクトにするために、各ノードのハッシュ値を計算しました。同じハッシュを持つ 2 つのノードは因数分解できます。この部分は難しい場合があります。深さが最も低いノードのみが保持され、他のノードは削除され、それらの親は保持されたノードを指すようになります。
圧縮したら、各ノードに一意の 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;
ここでルートはdawg.nodes[0]で、first_child/next_siblingはnodes配列のインデックスです。このような構造体は、xml ファイルから簡単に作成できます。主な欠点は、単語リストを変更すると、新しい xml ファイルが生成されることです。