|
2
|
1 \chapter{Differential Jungle Tree}
|
|
15
|
2 Jungleは木の編集時、編集を行うノードと、経路にあるノードの複製を行う。
|
|
|
3 そのため、木の編集の手間は、木構造の形によって異なる。
|
|
|
4 特に線形の木は、全てのノードの複製を行うため、変更の手間がO(n)になってしまう。
|
|
|
5 そこで、Jungle は、線形の木をO(1)で変更する、PushPopの機能を持つ。
|
|
|
6 PushPopとは、ルートノードの上に新しいルートノードを付け加えるAPIである(図\ref{fig:pushpop})。
|
|
|
7 すると、木の複製を行う必要が無いため、木の変更の手間がO(1)でノードの追加を行える。
|
|
|
8
|
|
2
|
9
|
|
|
10 \begin{figure}[htpb]
|
|
|
11 \begin{center}
|
|
|
12 \includegraphics[scale=0.3]{figures/PushPopDemerit.pdf}
|
|
15
|
13 \caption{PushPop}
|
|
2
|
14 \label{fig:pushpop}
|
|
|
15 \end{center}
|
|
|
16 \end{figure}
|
|
|
17
|
|
15
|
18 しかし、PushPopはルートノードを追加していくため、図\ref{fig:pushpop}のようにノードの並びが逆順になってしまう。
|
|
|
19 Logなどの正順の木でなければデータを表現できない場合、木の編集時 PushPop を使用できない。
|
|
2
|
20 その問題を解決するために、木の編集の手間をO(1)で、正順の木を構築できるDifferential Jungle Treeの実装を行った。
|
|
|
21 Differential Jungle Treeは、木のバージョンごとに、自身の木の最後尾を表す末尾のノードを保持する。
|
|
|
22
|
|
15
|
23 \newpage
|
|
2
|
24
|
|
|
25 \section{Differential Tree Context}
|
|
15
|
26 Jungleの木はTreeContextというオブジェクトに自身の木の情報を保持している。
|
|
|
27 Differential Jungle Treeでは、現在の版の木構造の末尾ノード保持することが可能な Differential Tree Context 作成した。
|
|
13
|
28
|
|
15
|
29
|
|
|
30 \section{Differential Jungle Treeの作成}
|
|
|
31 Differential Jungle Treeを作成するためにJungleに、新しいAPIを実装した(表\ref{createDifTreeAPI})。
|
|
2
|
32
|
|
|
33 \begin{table}[htb]
|
|
|
34 \begin{center}
|
|
15
|
35 \caption{Jungleに新しく実装したAPI}
|
|
|
36 \begin{tabular}{|p{15em}|p{24em}|} \hline
|
|
|
37 {\small {\tt JungleTree createNewDifferentialTree(String treeName)}} &{\small Jungleに新しくDifferential Jungle Tree を生成する。木の名前が重複した場合、生成に失敗しnullを返す。} \\ \hline
|
|
|
38 \end{tabular}
|
|
|
39 \label{createDifTreeAPI}
|
|
|
40 \end{center}
|
|
|
41 \end{table}
|
|
6
|
42
|
|
2
|
43
|
|
|
44 ソースコード\ref{newDifferentialTree}に新しいDifferential Jungle Treeを作成するサンプルコードを記載する。
|
|
6
|
45 \begin{lstlisting}[frame=lrbt,numbers=left,label=newDifferentialTree,caption=Differential Jungle Treeの生成]
|
|
15
|
46 Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser());
|
|
|
47 String treeName = "difTree";
|
|
|
48 JungleTree tree = jungle.createNewDifferenceTree(treeName);
|
|
2
|
49 \end{lstlisting}
|
|
|
50
|
|
15
|
51
|
|
6
|
52 Jungle では、{\tt TreeMap<String,Jungle Tree>} を用いて Jungle Tree を管理している。
|
|
|
53 Differential Jungle Tree と Default Jungle Tree は、同じ TreeMap に保持されるため、別々の木に同じ名前をつけることはできない(ソースコード\ref{src:nameFail})。
|
|
|
54 \begin{lstlisting}[frame=lrbt,numbers=left,label=src:nameFail,caption=名前の重複]
|
|
15
|
55 Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser());
|
|
|
56 String treeName = "treeName";
|
|
|
57 JungleTree defaultTree = jungle.createNewTree(treeName)
|
|
|
58 JungleTree dfTree = jungle.createNewDifferenceTree(treeName);
|
|
6
|
59 \end{lstlisting}
|
|
2
|
60
|
|
6
|
61 ソースコード\ref{src:nameFail}では、4行目で Differentail Jungle Tree の名前が、3行目で生成した Default Jungle Tree の名前と重複するため、木の生成に失敗する。
|
|
2
|
62
|
|
13
|
63
|
|
2
|
64 \section{末尾ノードを使用した木の編集}
|
|
|
65 Differential Jungle Treeの木の編集は、Differential Jungle Tree Editorを使用して行う。
|
|
15
|
66 Differential Jungle Tree Editor は、Default Jungle Tree Editor と違い、生成時に新しい木構造(Sub Tree)を自身の中に構築する。
|
|
|
67 そして、木の編集は、Editor が保持している木構造に対して行う。
|
|
|
68 編集後、Commitを行う際に構築した木構造を、 Differential Jungle Tree の末尾ノードにAppendする。
|
|
6
|
69 そうすることで、木の複製を行う必要がないため、木の変更の手間はO(1)で行える。
|
|
2
|
70
|
|
15
|
71 また、Differential Treeは自身が保持している木構造に対する変更しか行えないため、一度Commitした木に対して変更は行えない。
|
|
2
|
72 図\ref{fig:EditDifTree}にDifferential Jungle Treeの編集の流れを記述する。
|
|
|
73
|
|
|
74 \begin{figure}[htpb]
|
|
|
75 \begin{center}
|
|
|
76 \includegraphics[scale=0.28]{figures/EditDifferencialTree.pdf}
|
|
|
77 \caption{末尾ノードを使用した木の編集}
|
|
|
78 \label{fig:EditDifTree}
|
|
|
79 \end{center}
|
|
|
80 \end{figure}
|
|
|
81
|
|
|
82 \begin{enumerate}
|
|
15
|
83 \item 木から{\tt getJungleTreeEditor}でEditorを取得する。(このときEditorは新しい木構造(Sub Tree)を持つ)。
|
|
|
84 \item Editor が保持している木構造に対して{\tt addNewChild(<-1,0>)}を実行し、ノードの追加を行う。
|
|
|
85 \item Commitを行い、Treeの末尾ノードに Editor が保持している木構造をAppendする。
|
|
2
|
86 \end{enumerate}
|
|
|
87
|
|
15
|
88 Editor が保持している木構造に最後に追加したノードが、新しい木の末尾ノードとなる。
|
|
|
89 また、Differential TreeのIndexのアップデートは、Commit 時に Editor が保持している木構造のデータをIndexに追加するだけで良い。
|
|
|
90
|
|
|
91
|
|
|
92
|
|
|
93 \section{Differential Jungle Treeの検索}
|
|
|
94 Differential Jungle Tree は、末尾ノードを使って、現在の木構造を表現している。
|
|
|
95 なので、過去の木に対して、Indexを使わずに全探索を行った場合、その版の木には無いはずのノードが取得できてしまう。
|
|
|
96 例として、編集前の木である {\tt Tree ver1} と編集後の木である {\tt Tree ver2}があるとする(図\ref{fig:multiTree})。
|
|
|
97 ここで、{\tt Tree ver1}に対して、検索をIndexを使わず行った場合、
|
|
|
98 本来{\tt Tree ver1}に存在しないノード3・4も検索対象に含まれてしまう。
|
|
|
99
|
|
|
100 そこで、その版の木が持つ末尾ノード以下のSub Treeを検索対象から除外する検索を持つ、Differential Interface Traverser を実装した。
|
|
|
101 Differential Interface Traverser を用いて Index を使用せず木の全探索を行った場合、{\tt Tree ver1}に存在しないノード3・4は検索対象から省かれる。
|
|
|
102
|
|
|
103 \begin{figure}[htpb]
|
|
|
104 \begin{center}
|
|
|
105 \includegraphics[scale=0.25]{figures/findDifTree.pdf}
|
|
|
106 \caption{複数の版の木の表現}
|
|
|
107 \label{fig:multiTree}
|
|
|
108 \end{center}
|
|
|
109 \end{figure}
|
|
|
110
|
|
|
111
|
|
|
112 Indexを使用した検索を行う場合、各版の木に対応したIndexがあるため、Default Treeと検索のアルゴリズムは変わらない。
|
|
|
113 これらの実装により Differential Jungle Tree は木構造の構築・検索を行う。
|
|
2
|
114
|
|
|
115
|
|
|
116 \section{Differential Jungle Treeの整合性}
|
|
15
|
117 Default Jungle Tree への Commit は、 編集後の木のデータを持つ TreeContext を作り、編集前の木が持つ TreeContext と入れ替えることで行われる。
|
|
|
118 しかし、Differentail Jungle Tree への Commit は、Default Jungle Tree のCommit と異なり、
|
|
|
119 TreeContext の入れ替えと、Editor が保持している木構造の末尾ノードへの Append の２つのプロセスからなる。
|
|
|
120 TreeContext の入れ替えに関しては、 Default Jungle Tree と同じように行う。
|
|
2
|
121
|
|
15
|
122 末尾ノードへの Editor が持っている木構造の Append は、 TreeContext の入れ替えが成功した際に行う。
|
|
|
123 そうすることで、TreeContext を入れ替えた Thread と別 Thread が Append を行い、木の整合性が崩れることを回避している。
|
|
2
|
124
|
|
|
125
|
|
15
|
126 また、過去の版の木に対して、編集を加え Commit を行った場合、木の整合性が崩れてしまう問題もある。
|
|
|
127 図\ref{fig:multiTree}・\ref{fig:badDifTree2}を例に解説する。
|
|
|
128 最新版の木が {\tt Tree ver2}とする。
|
|
2
|
129
|
|
15
|
130 図\ref{fig:multiTree}の過去の版の木 {\tt Tree ver1}に新しいノード5を追加・Commit を行うと、新しい木 {\tt Tree ver`2} が構築される。
|
|
|
131 ここで、木である{\tt Tree ver`2} に対して Index を使用しないで検索を行う。
|
|
|
132 Differential Jungle Tree に対する Index を使用しない検索は、末尾ノードより上にあるノードを検索対象にする。
|
|
|
133 しかしノード3・4という、本来存在しないはずのノードが検索対象に含まれてしまう。
|
|
2
|
134
|
|
15
|
135 \begin{figure}[htpb]
|
|
|
136 \begin{center}
|
|
|
137 \includegraphics[scale=0.25]{figures/badDifTree2.pdf}
|
|
|
138 \caption{木の整合性が崩れる例}
|
|
|
139 \label{fig:badDifTree2}
|
|
|
140 \end{center}
|
|
|
141 \end{figure}
|
|
2
|
142
|
|
15
|
143 この問題を解決するために、Differential Jungle Tree では、過去の木に対する変更を禁止している。
|
|
|
144 具体的には、末尾ノードは子を１つしか持つことができない。
|
|
|
145 そうすることで木の整合性を保証している。
|
