# Dictionary Encoding Based on Tagged Sentential Decision Diagrams
## 5 Experimental Results
\begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Dictionary**} & \multirow{2}{*}{**Word**} & \multirow{2}{*}{**Decision**} & \multirow{2}{*}{**Compact, One-Hot**} & \multirow{2}{*}{**Compact, Binary**} & \multirow{2}{*}{**ASCII, One-Hot**} & \multirow{2}{*}{**ASCII, Binary**} \\  & & & & **Node** & & & & & \\  & & **Count** & & **Time/s** & & **Node** & & & \\  & & & **Count** & & **Count** & & & & \\ \hline \multirow{8}{*}{xato-net-10-million} & \multirow{8}{*}{755,995} & BDD & – & – & 3,055,697 & 760.534 & – & – & 3,022,307 & 659.394 \\  & & ZDD & 853,731 & 499.188 & 1,372,273 & 270.62 & **850,452** & 198.032 & 1,944,759 & 396.952 \\  & & CBDD & 854,287 & 1364.918 & 1,372,115 & 467.862 & 850,973 & 1130.453 & 1,944,325 & 678.649 \\ \cline{1-1}  & & CZDD & **853,731** & 492.349 & 1,372,123 & 262.815 & **850,452** & 236.005 & 1,944,387 & 664.089 \\ \cline{1-1}  & & SDD & - & - & 2,409,752 & 1056.438 & - & - & 2,313,320 & 1,074.787 \\ \cline{1-1}  & & ZSDD & 859,361 & 538.169 & 1,358,287 & 662.663 & 860,536 & 570.875 & 1,877,647 & 793.756 \\ \cline{1-1}  & & TSDD & 1,055,763 & 1537.339 & **665,174** & 629.051 & 1,052,745 & 1745.605 & **1,279,015** & 776.298 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: _Cont._the TSDD. Although the encoding time of the TSDD is not the smallest among all decision diagrams, we believe that it is worth taking more time to encode the dictionaries into the TSDD, which has the minimum node count. Hence, we conclude that TSDDs are the most suitable decision diagrams for representing dictionaries in a binary way. Finally, we make the following conclusions: (1) There is no decision diagram that has the minimum node count and encoding time for all dictionaries with all encoding methods. (2) TSDDs must have the minimum node count if we encode in a binary way, and the node count of TSDDs can be much smaller than those of other decision diagrams. (3) The node count of the TSDD is not more than 1.5 times that of the minimum node count for all dictionaries, except for _walk-the-line_, if we encode in the one-hot way. (4) Although the encoding time of TSDDs is not the best, for all dictionaries, we can encode them into TSDDs in four ways within half an hour, while it may take more than one hour for some dictionaries if we want to encode them into BDDs or SDDs in a one-hot way. Based on point 1, we find that there is no decision diagram that can perform better than all other decision diagrams in our experiments. Therefore, we need to find a decision diagram that is suitable for representing dictionaries among the seven decision diagrams. Based on points 2 and 3, we believe that, overall, TSDDs have the best performance in terms of the node count among all decision diagrams. Based on point 4, we believe that it is worthwhile to exchange some time for excellent performance in terms of the node count, which means that we intend to take more time to encode dictionaries into a more compact representation. In addition, we know that the number of variables of Boolean functions representing dictionaries encoded in a one-hot way is much larger than that in a binary way. With the increase in the word length, the number of variables will increase quickly. When we need to represent a large number by a Boolean function, a lot of variables are required if we represent it in a one-hot way. If a large number is represented in a binary way, only a small number of variables are required. Too many variables not only make management difficult but also require a lot of space to store. In general, people tend to represent large numbers in a binary way. We can see that TSDDs are the decision diagrams with the minimum node count and a suitable encoding time among the seven decision diagrams. Hence, we believe that TSDDs are more suitable for representing dictionaries.