# Dictionary Encoding Based on Tagged Sentential Decision Diagrams
## 4 Encoding Dictionaries into TSDDs
### Encoding with Tries
The tries before and after merging the nodes are shown in Figure 2. There are two special nodes in the graph, namely, the root node with a depth of 0 and the tail node represented by a solid circle without a depth. Except for these two nodes, each other node stores a letter, and we stipulate that all paths representing words start at the root node and end at the tail node. Except for the tail node, all other nodes have a depth, and the maximum depth on a path is the number of letters in the word represented by that path. After we merge the nodes, we can see that the number of nodes has significantly decreased. We then transform this trie into a TSDD, and the algorithm is shown in Algorithm 3. We first compute the number of variables in the TSDD and suppose that the maximum length of all words in the dictionary is \(n\) and the number of different letters in the dictionary is \(m\). The number of variables is \(128^{*}n\) if we use the ASCII code in a one-hot way and \(7^{*}n\) if we use the ASCII code in a binary way. The number of variables is \(m^{*}n\) if we use the compact code in a one-hot way and \(\lceil log_{2}m\rceil*n\) if we use the compact code in a binary way. Here, we explain the method that transforms a trie node into a TSDD node by using the ASCII code in a binary way, and we save the corresponding TSDD in the trie node. There are three steps in total. Let \(\widetilde{P}\) be a trie node. The steps are as follows: (1) We access each node \(\widetilde{n}(d,l)\) from bottom to top and compute the result of applying disjoin on all the TSDDs that are saved in the successor nodes of the trie node \(\widetilde{n}(d,l)\) and record this result as \(G\), and \(\textit{successor}(\widetilde{n})\) represents all the successor nodes of the trie node \(\widetilde{n}\) (Lines 1-4). (2) We compute the TSDD \(\textit{GetTSDD}(\widetilde{n})\), which represents the letter saved in the trie node (Line 5). For example, if the letter \(l\) is 'a', the binary representation of the letter is '1100001', and the related variables are \(x_{(d-1)\sigma+1},x_{(d-1)\sigma+2},x_{(d-1)\sigma+3},x_{(d-1)\sigma+4},x_{( d-1)\sigma+5},x_{(d-1)\sigma+6},x_{(d-1)\sigma+7}\). Of these variables, the variables that are marked as \(7^{i}\) are \(x_{(d-1)\sigma+1},x_{(d-1)\sigma+2},x_{(d-1)\sigma+3}\). We need to construct the TSDD G that represents the Boolean function \(f=x_{(d-1)\sigma+1}\wedge x_{(d-1)\sigma+2}\wedge\overline{x}_{(d-1)\sigma+3} \wedge\overline{x}_{(d-1)\sigma+4}\wedge\overline{x}_{(d-1)\sigma+5}\wedge \overline{x}_{(d-1)\sigma+6}\wedge x_{(d-1)\sigma+7}\). (3) We compute the TSDD \(G=Apply(G,\textit{GetTSDD}(\widetilde{n}),\wedge)\) (Line 5). Then, we save this TSDD G in the trie node (Line 6). Similarly, we group all trie nodes based on depth and transform the nodes into TSDDs in the group in descending order of depth. We should note that if \(\widetilde{P}\) is the tail trie node, the TSDD saved in it is not fixed. The TSDD saved in the tail trie node is decided based on the depth of its parent node. Let the depth of the parent node be \(d\) and the TSDD saved in the tail node be \(G\); then, \(\langle G\rangle=\bigwedge\limits_{i=d\sigma+1}^{n}\overline{x}\). In addition, not all words consist of n letters. If a  
Figure 2: Trie. word consists of fewer than n letters, we use null characters to supplement the remaining positions. For the above example, if the letter saved in the trie node is a null character, then the Boolean function in step 2 is \(f=\overline{x}_{(d-1)*7+1}\wedge\overline{x}_{(d-1)*7+2}\wedge\overline{x}_{(d- 1)*7+3}\wedge\overline{x}_{(d-1)*7+4})\wedge\overline{x}_{(d-1)*7+5}\wedge \overline{x}_{(d-1)*7+6}\wedge\overline{x}_{(d-1)*7+7}\). Finally, the TSDD saved in the head trie node is the TSDD that represents the whole dictionary (Line 7). ```
Input:\(\widetilde{P}\): A Trie; Output:\(F\): The resulting TSDD.