## 4 Encoding Technique
### Encoded Representation of CFG  
For the grammar \(G\) deriving \(w\), we create the _partial parse tree_ (This concept was introduced by [PERSON] [23].) \(PTree(G)\), which is obtained by the following operation: Let \(T\) be the parsing tree for \(w\) by \(G\). If \(T\) contains a maximal subtree rooted by \(A\in N\) appearing in \(T\) at least twice, replace all occurrences of the subtree by a single node labeled by \(A\) except the leftmost occurrence of the subtree. When we continue this replacement, the final tree is denoted by \(PTree(G)\). Figure 5 shows an example of the partial parse tree. \(PTree(G)\) has \(g\) internal nodes and \(g+1\) leaves because \(PTree(G)\) is a binary tree, where \(g=|N|\). The construction of \(PTree(G)\) can be in \(O(g)\) time/space by expanding each nonterminal only once.  
The skeleton of \(PTree(G)\) is represented by a sequence of parentheses.  
Let \(x_{1},x_{2},\ldots,x_{2g+1}\) be a sequence of nodes sorted by post-order. We represent the sequence of nodes by \(2g+1\) parentheses as follows:  
\[F[i]=\left\{\begin{array}{ll}{}^{\prime}(^{\prime}&\text{if $x_{i}$ is a leaf}\\ {}^{\prime})^{\prime}&\text{otherwise}\end{array}\right. \tag{1}\]We then make a sequence of leaf labels of \(PTree(G)\) to keep the information of the original string \(w\). Let \(E[1,g]\in N^{g}\) be the sequence of internal node labels of \(PTree(G)\) in post-order. Let \(M[1,g+1]\in(\Sigma\cup N)^{g+1}\) be the sequence of leaf labels of \(PTree(G)\) in post-order. We note that \(E[1,g]\) is a permutation on \(N\) because every internal node has a different label from each other. Let \(E^{-1}(N)\) be a function that maps any nonterminal \(z\in N\) to the position \(i\) such that \(E[i]=z\). Hereby, we define the sequence \(L[1,g+1]\), which consists of renamed nonterminals for \(M\) by the following:  
\[L[i]=\begin{cases}E^{-1}(M[i])+\sigma&(M[i]\in N)\\ M[i]&(M[i]\in\Sigma)\end{cases} \tag{2}\]  
We then create the pair \((F,L)\) as an encoded representation of CFG. Clearly the time/space to compute \((F,L)\) is \(O(g)\).  
We estimate the bits of space required for \((F,L)\). The space required for \(F\) is \(2g+1\) bits because \(F\) is the sequence over a binary alphabet representing \(g\) internal nodes and \(g+1\) leaves. Because \(L\) is the sequence over \(\{1,2,\ldots,g+\sigma\}\) whose length is \(g+1\), \(L\) can be represented in \((g+1)[\log(g+\sigma)]\) bits of space. Thus, the total space for \((F,L)\) is approximately \(g[\log(g+\sigma)]+2g\) bits. A naive encoding represented by a sequence of right-hand sides of \(g\) production rules requires \(2g[\log(g+\sigma)]\) bits of space. Thus, our representation reduces the space to almost half.  
We note two array \(F\) and \(L\) can be combined into one array such that each symbol \(L[i]\) is embedded after \(i\)th open parenthesis of \(F\). The representation of the combined array has an advantage that the decoding processing can be done in one pass over the compressed text. We can also apply simple variable-length coding like LZW [30] for each element of \(L\) because the number of allocatable  
Figure 5: The example of the encoding process for CFG \(G=(\{a,b\},\{A,B,C,S\},\mathcal{D},S)\): (**1**) the dictionary \(\mathcal{D}\); (**2**) the partial parse tree \(PTree(G)\); (**3**) the parentheses representation of the tree and renamed labels where \(Y_{i}=i+\sigma\); and (**4**) the encoded representation of \(G\).  
nonterminals for any leaf node is limited by the number of internal nodes that appear before the leaf node in post-order. The efficiency of compression is further improved using such variable-length coding.