# Dictionary Encoding Based on Tagged Sentential Decision Diagrams
## 5 Experimental Results  
In this section, we first compare the speed of encoding a dictionary with and without tries to demonstrate the acceleration effect of tries on encoding a dictionary. We then encode 14 dictionaries into BDDs, ZDDs, CBDDs, CZDDs, SDDs, ZSDDs, and TSDDs with tries and compare the node count of decision diagrams and the time required for encoding the dictionaries into decision diagrams. All experiments were carried out on a machine equipped with an Intel Core i7-8086K 4 GHz CPU and 64 GB RAM. We used four encoding methods to conduct all experiments: compact code in a one-hot way, compact code in a binary way, ASCII code in a one-hot way, and ASCII code in a binary way. The dictionaries we used are the English words in the file /usr/shar/dict/words on a MacOS system with 235,886 words with a length of up to 24 from 54 symbols, a password list with 979,247 words with a length of up to 32 from 79 symbols [10], and other word lists from the website at [11]. To compare the time for encoding dictionaries into TSDDs with and without tries, we separated the first 20,000, 30,000, and 40,000 words from the dictionary _words_ to form four new dictionaries and encoded them into TSDDs. This is because, without the help of a trie, the encoding time would exceed two hours when the number of words exceeds 40,000. We used the same right linear vtree to complete the first experiment. Hence, the size and node count of TSDDs must be the same in this experiment with the same encoding method, and we only compared the encoding time. The results are shown in Table 1.  
We can see that all the experiments were completed within 10 s with the help of tries for these three dictionaries. When we did not rely on the help of tries, even the minimum encoding time reached 251.86 s (the compact code in a one-hot way for the dictionary with 20,000 words). When the number of words reaches 40,000, it even takes over 1000 s to encode the dictionary, which exceeds the time required for encoding the dictionary with the help of tries by more than a hundred times. It can be inferred that for dictionaries with more words, encoding them will take more time, which we cannot tolerate. Therefore, we can see that tries have excellent acceleration effects when we encode a dictionary, and it is necessary to rely on the help of tries when encoding dictionaries. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Word Count** & \multicolumn{3}{c}{**Compact, One-Hot Compact, Binary ASCII, One-Hot ASCII, Binary**} \\ \hline \multirow{2}{*}{20,000} & with trie & 3.527 & 2.228 & 4.23 & 3.119 \\  & without trie & 251.86 & 412.156 & 292.52 & 842.622 \\ \hline \multirow{2}{*}{30,000} & with trie & 5.509 & 3.326 & 5.084 & 3.702 \\  & without trie & 650.39 & 994.768 & 677.524 & 1511.209 \\ \hline \multirow{2}{*}{40,000} & with trie & 7.141 & 3.927 & 7.677 & 5.503 \\  & without trie & 1125.327 & 1682.585 & 1100.168 & 2500.582 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The time (secs.) for encoding dictionaries with and without tries. Then, the second experiment is as follows. Ref. [1] encoded two dictionaries, _words_ and _password_, into four decision diagrams, i.e., BDDs, ZDDs, CBDDs, and CZDDs, in four ways and gave the number of nodes of decision diagrams and the encoding times for some data. Here, we use their data and record them in Table 2. For the other 12 dictionaries, they did not conduct any relevant experiments. Therefore, we extended their experiment by encoding the remaining twelve dictionaries into BDDs, ZDDs, CBDDs, and CZDDs in four ways and recording the node count and encoding time. We also encoded the 14 dictionaries into SDDs, ZSDDs, and TSDDs in four ways and then compared all decision diagrams using two categories of benchmarks: _node count_, the node count of decision diagrams, and _time_, the time for encoding a dictionary. The initial vtrees are all right linear trees.