## 1 Introduction  
Grammar-based compression [1] finds a small _context-free grammar_ (_CFG_) that generates a given string uniquely. Let us express grammar-based compression by an intuitive example. If a string \(w\) contains many occurrences of a substring \(\gamma\), we can replace all of them by a single variable \(A\) which is associated with \(\gamma\) like \(A\rightarrow\gamma\). The text is thus compressed to a shorter one according to the frequency of \(\gamma\). The expression of grammar-compressed strings is simple, yet it is powerful because they can derive a string of its exponential length. In fact, it was recently reported that grammar-based and LZ77-based [2] compressors can achieve effective compression for _highly-repetitive text_[3; 4; 5] by comparison with entropy-based encoders. Grammar-compressed strings are also suitable for accelerating string processing, for examples, combinatorial pattern matching [6; 7; 8; 9; 10; 11], edit-distance computation [12], \(q\)-gram computation [13; 14], mining characteristic patterns [15; 16], and so on. We note above compressed string algorithms, mainly from theoretical approaches, are considered on the _straight-line programs_ (_SLPs_). An SLP is a CFG in the Chomsky normal form that derives a single string. This situation is reasonable because any CFG deriving a single string can be straightforwardly converted into an SLP without paying significant time and space penalties. The smaller a given CFG is, the more these compressed string algorithms are accelerated to running time, so they desire effective compression algorithms which can guarantee to produce small CFGs in any case. Also, we should pay attention to working costs for the compression phase when we need to consider total time and space. One of our interests is, therefore, to translate an input string into a good CFG under the conditions of efficient working time and space. In a theoretical sense, the NP-hardness and its approximation hardness for finding the smallest CFG from the input text was proved [17]. For this reason, there exist many characteristic compression algorithms proposed so far. In the grammar-based compression, some algorithms based on greedy strategies are known to achieve high compression ratios for the real-world texts, e.g., Sequitur[18], Re-Pair[19], Greedy[20], LFS2[21], _etc_. Their upper bound of approximation ratios were theoretically analyzed in [22]. The best approximation ratio among greedy algorithms is \(O((n/\log n)^{1/2})\), where \(n\) is the input string length (In this paper, \(\log\) stands for \(\log_{2}\)). On the other hand, several algorithms achieving a logarithmic approximation ratio were proposed. For the minimum grammar size \(g_{*}\), the first \(O(\log(n/g_{*}))\)-approximation algorithm was developed by [PERSON] _et al_[22]. Independently, [PERSON] [23] presented another \(O(\log(n/g_{*}))\)-approximation algorithm using the suffix tree. [PERSON] [24] also proposed a linear-time \(O(\log(n/g_{*}))\)-approximation algorithm based on Re-Pair. However, these algorithms require \(\Omega(n)\) space and this weakness prevents us from applying them to huge texts. This space complexity was improved by several multi-pass algorithms over read/write streams. [PERSON] _et al._[25] proposed the LCA algorithm that requires \(O(g_{*}\log g_{*})\) space with linear running time and \(O(\log n\log g_{*})\)-approximation ratio. LCA was modified to achieve \(O(\log n\log^{*}\!n)\)-approximation ratio within \(O(n\log^{*}\!n)\) running time [26], where \(\log^{*}\!n\), called the iterated logarithmic function, is the number of times the \(\log\) function is applied to \(n\) to produce a constant. On the other hand, [PERSON] and [PERSON] [27] proposed \(O(\min(g_{*},\sqrt{n\log n}))\)-approximation algorithm in a streaming model where the algorithm works in constant space and logarithmic passes over a constant number of streams.