個人的なプロジェクト用にコーディングしている検索機能のために、線形時間で直接 DAWG を作成する一連の関数を実装しようとしています。この論文を読んで、たまたま DAWG の背後にあるアイデアを詳述し、線形時間での構築のための疑似コードさえ提供しています!
ただし、疑似コードに従うと、(私の目には)トライのような構造が得られるようです。具体的には、サフィックスが明示的に共有されているようには見えません (実際にはグラフのエッジで接続されています)。代わりに、グラフの実際のトラバーサルに実際には関係のない接尾辞ポインターによって表されます。
たとえば、セット内の単語の DAWG のこの図を見てください{tap, taps, top, tops}( DAWG ウィキペディアのページから)。
ここで、前述の論文で詳述されているこれらの手順に従って得られる構造と比較してください (この一連の単語を使用して手動で行うには、ごくわずかな時間がかかります)。
Note: Edges are labeled by letters
Nodes are labeled by the concatenation of the labels of the primary edges
used to reach them
Suffix pointers are not visually represented on the graph
primary edges: solid edges used to traverse graph
secondary edges: dotted edges implying a suffix relationship between
the letter labeling the edge and the substring
represented by the target node
builddawg(S)
1. Create a node named source.
2. Let activenode be source.
3. For each word w of S do:
A. For each letter 'a' of w do:
Let activenode be update (activenode, a).
B. Let activenode be source.
4. Return source.
update (activenode, a)
1. If activenode has an outgoing edge labeled 'a', then
A. Let newactivenode be the node that this edge leads to.
B. If this edge is primary, return newactivenode.
C. Else, return split (activenode, newactivenode).
2. Else
A. Create a node named newactivenode.
B. Create a primary edge labeled 'a' from activenode to newactivenode.
C. Let currentnode be activenode.
D. Let suflxnode be undefined.
E. While currentnode isn’t source and sufixnode is undefined do:
i. Let currentnode be the node pointed to by the suffix
pointer of currentnode.
ii. If currentnode has a primary outgoing edge labeled 'a',
then let sufixnode be the node that this edge leads to.
iii. Else,if currentnode has a secondary outgoing edge labeled 'a' then
a. Let childnode be the node that this edge leads to.
b. Let suffixnode be split (currentnode, childnode).
iv. Else, create a secondary edge from currentnode to newactivenode
labeled 'a'.
F. If sufixnode is still undefined, let suffixnode be source.
G. Set the suffix pointer of newactivenode to point to sufixnode.
H. Return newactivenode.
split (parentnode, childnode)
1. Create a node called newchildnode.
2. Make the secondary edge from parentnode to childnode into
a primary edge from parentnode to newchildnode (with the same label).
3. For every primary and secondary outgoing edge of childnode,
create a secondary outgoing edge of newchildnode with the
same label and leading to the same node.
4. Set the suffix pointer of newchildnode equal to that of childnode.
5. Reset the suffix pointer of childnode to point to newchildnode.
6. Let currentnode be parentnode.
7. While currentnode isn’t source do:
A. Let currentnode be the node pointed to by the
suffix pointer of currentnode.
B. If currentnode has a secondary edge to childnode,
then make it a secondary edge to newchildnode (with the same label).
C. Else, break out of the while loop.
8. Return newchildnode.
私が得た構造は、上に描かれたものと同等ではありません。実際、二次エッジを一次エッジに変換することによって余分なノードが生じることを除けば、トライとほとんど同じように見えます。上記の DAWG に相当するトライは次のとおりです。
アルゴリズムを間違って適用しているだけですか、DAWGSにはいくつかのタイプがありますか、それともDAWGがどのように見えるべきかを誤解しているだけですか?
DAWG の詳細を調べたほとんどの論文には、アルゴリズムによって作成されたように見える構造がありますが、オンラインで読んだほとんどの資料 (および私が見た写真) には、共通の接尾辞を接続する実際のエッジがあります。何を信じればいいのか、実際に同等かどうかはわかりません。