# Dictionary Encoding Based on Tagged Sentential Decision Diagrams
## 4 Encoding Dictionaries into TSDDs
### Four Encoding Methods  
The key to our method is to establish the correspondence between letters and numbers so that we can use a string of numbers to represent a word. For example, the ASCII code, a famous encoding system, uses a number ranging from 0 to 127 to represent 128 characters. With the help of the ASCII code, we represent a letter with some variables by transforming the code into its binary representation. As we know, the ASCII code of the letter 'A' is 65, whose binary representation is '1000001' with 7 bits. We represent the letter 'A' by 7 variables, '\(x_{1}x_{2}x_{3}x_{4}x_{5}x_{6}x_{7}\)', and consider the variable to be '0' when the value is _false_ and '1' when the value is _true_. Hence, a letter needs 7 variables to be represented in the ASCII code. If a word consists of n letters, it needs 7\"n variables in total to be represented.  
However, there are many characters in the ASCII code that are often not used in most dictionaries, which means that it will cause significant redundancy if we use 7 bits to represent every letter. Suppose that a dictionary consists only of lowercase letters; that is, there are only 26 different letters in this dictionary. We number each letter in alphabetical order starting from 1, with the maximum number being 26, representing z. The number 26 just needs 5 bits to be represented, and its binary representation is '11010', which means that a letter needs 5 variables to be represented. In this way, we reduce the number of variables required to represent a letter, and this code is called the compact code.  
Compared with the ASCII code, the compact code can reduce the number of variables required to represent a letter. However, we need to make a protocol that specifies the correspondence between letters and numbers if we apply the compact code and records this correspondence in a table. This table is necessary for both encoding and decoding. Therefore, this table should be known as necessary information by all those who use compact encoding. The ASCI code is an international standard that does not require additional space to store the correspondence between letters and codes. Hence, the universality of the ASCCI code is better than that of the compact code.  
We use binary numbers to represent both the ASCII code and compact code for each letter, which means that the number of variables is the number of binary digits. Hence, we call this the binary way of encoding dictionaries. If the maximum value of the code is \(n\), we can also use \(n\) variables to represent the code. For example, given the word _zoo_, there are two different letters, 'z' and 'o', in this word, and the word consists of three letters. Hence, we need six variables, \(x_{1},x_{2},x_{3},x_{4},x_{5}\), and \(x_{6}\), to represent it. \(x_{1}\) and \(x_{2}\) represent the first letter, and the first letter is 'z' if \(x_{1}=true\) and \(x_{2}=false\), while it is 'o' if \(x_{1}=false\) and \(x_{2}=true\). The other variables have similar meanings. Therefore, the word 'zoo' is represented by \(x_{1}x_{2}x_{3}x_{4}x_{5}x_{6}=100101\). We call this the one-hot way of encoding the dictionary. A word consisting of \(m\) letters needs \(n^{*}m\) variables in total to represent it in one-hot encoding, while it just needs \(\lceil log_{2}n\rceil*m\) variables in total to represent it in a binary way.