# Dictionary Encoding Based on Tagged Sentential Decision Diagrams
## 4 Encoding Dictionaries into TSDDs
### Encoding with Tries  
We can first encode every word in the dictionary into a TSDD one by one and then apply disjunction to these TSDDs to obtain the resulting TSDD that represents the whole dictionary. However, the process of encoding takes too much time, which is unacceptable to us. If the number of words in the dictionary exceeds 100,000, the encoding time will exceed two hours. Therefore, we first transform the dictionary into a trie, which is a multibranch tree, and then transform it into a TSDD. This can greatly accelerate the speed of encoding a dictionary. A trie is a multibranch tree whose every node saves a letter, except for two special nodes. We know that a tree is a directed acyclic graph, and every node has its in- and out-degrees. In general, the in- and out-degrees of each node in a trie are both greater than 0, and these nodes all save a letter in them. However, there are two special nodes, one with an in-degree of 0 and the other with an out-degree of 0. We call the node with an in-degree of 0 the _head_ and the node with an out-degree of 0 the _tail_. Both nodes do not save any letters. We can easily know that all paths in the trie must start from the _head_ and end at the _tail_. A path represents a word in the dictionary, which means that the number of paths is the number of words in the trie. We first introduce the algorithm for transforming a dictionary into a trie in Algorithm 2. We need to initialize the two special nodes, that is, the head node \(\widetilde{h}\) and the tail node \(\widetilde{t}\), and a node \(\widetilde{v}\), which is an empty node (Line 1). Then, we traverse each word in the dictionary, and in a loop, we let \(\widetilde{v}\) be the node \(\widetilde{h}\) (Lines 2-3). We perform the following operations on the letters in the word in order. The operation \(Find(l,\widetilde{v})\) means we look for a node from successor nodes of \(\widetilde{v}\) that save the letter \(l\). If such a node does not exist, we create a new node with _NewNode(l)_ and let it be the successor node of _trace_ with \(Append(\widetilde{v},\widetilde{n})\) (Lines 4-8), and then we let \(\widetilde{v}\) be the node \(\widetilde{n}\) (Line 9). After all the letters have been accessed, we let \(\widetilde{t}\) be the successor node of \(\widetilde{v}\) (Line 10). Finally, the node \(\widetilde{h}\) is the resulting trie. ```
Input:\(D\): A dictionary containing several words; Output:\(P\): The resulting Trie. \(Init(\widetilde{h},\widetilde{t},\widetilde{v})\) foreachword\(w\) of \(D\)do \(\widetilde{v}\leftarrow\widetilde{h}\) foreachletter\(l\) of \(w\)do \(\widetilde{n}\gets Find(l,\widetilde{v})\) if\(\widetilde{n}\) is an empty nodethen \(\widetilde{n}\gets NewNode(l)\) \(Append(\widetilde{v},\widetilde{n})\) \(Append(\widetilde{v},\widetilde{n})\) \(Append(\widetilde{v},\widetilde{t})\) \(P\leftarrow\widetilde{h}\) return\(P\)
```  
**Algorithm 2**ToTrie\((D)\)  
After we obtain the trie, we need to compress it further. Firstly, the nodes in the trie need to be assigned an important parameter: depth; we denote a node as \(\widetilde{P}(d,l)\), where \(d\) stands for depth and \(l\) stands for letter. We first give the following definition. **Definition 4**. : _A trie node \(\widetilde{P}(d,l)\) is defined as follows:_  
* \(d=0\) _if the node_ \(\widetilde{P}(l,d)\) _is the node head._
* _If_ \(\widetilde{P}(d,l)\) _is a node and_ \(\widetilde{P}^{\prime}(d^{\prime},l^{\prime})\) _is one of its children, then_ \(d^{\prime}=d+1\)_._
* _Letters that appear sequentially in the path from the root to the leaf form a word._  
The step of compressing the trie entails merging two nodes that have the same depth and meet certain conditions into one node. The conditions are as follows: (1) The two nodessave the same letter. (2) The two nodes have the same children nodes. We group all nodes by depth and merge nodes by group, starting from the deepest group. Here, we give an example using a dictionary that contains six words: aco, cat, dot, purple, ripple, and zoo.