We analyze the grammar generation algorithm of the RePair compression algorithm and show the relation between a grammar generated by RePair and maximal repeats. We reveal that RePair replaces step by step the most frequent pairs within the corresponding most frequent maximal repeats. Then, we design a novel variant of RePair, called MR-RePair, which substitutes the most frequent maximal repeats at once instead of substituting the most frequent pairs consecutively. We implemented MR-RePair and compared the size of the grammar generated by MR-RePair to that by RePair on several text corpora. Our experiments show that MR-RePair generates more compact grammars than RePair does, especially for highly repetitive texts.

In this study, we address the problem of compacting Church numerals. Church numerals appear as a representation of the repetitive part of data in higher-order compression. We propose a novel decomposition scheme for a natural number using tetration, which leads to a compact representation of lambda terms equivalent to the original Church numerals. For natural number n, we prove that the size of the lambda term obtained by the proposed method is O((slog2n)log n/log log n). Moreover, we quantitatively confirmed experimentally that the proposed method outperforms a binary expression of Church numerals when n is less than approximately 10000.

In this paper, we propose a statistical model for relevance-dependent biclustering to analyze relational data. The proposed model factorizes relational data into bicluster structure with two features: (1) each object in a cluster has a relevance value, which indicates how strongly the object relates to the cluster and (2) all clusters are related to at least one dense block. These features simplify the task of understanding the meaning of each cluster because only a few highly relevant objects need to be inspected. We introduced the Relevance-Dependent Bernoulli Distribution (R-BD) as a prior for relevance-dependent binary matrices and proposed the novel Relevance-Dependent Infinite Biclustering (R-IB) model, which automatically estimates the number of clusters. Posterior inference can be performed efficiently using a collapsed Gibbs sampler because the parameters of the R-IB model can be fully marginalized out. Experimental results show that the R-IB extracts more essential bicluster structure with better computational efficiency than conventional models. We further observed that the biclustering results obtained by R-IB facilitate interpretation of the meaning of each cluster.

The edge partition model (EPM) is a fundamental Bayesian nonparametric model for extracting an overlapping structure from binary matrix. The EPM adopts a gamma process ($\Gamma$P) prior to automatically shrink the number of active atoms. However, we empirically found that the model shrinkage of the EPM does not typically work appropriately and leads to an overfitted solution. An analysis of the expectation of the EPM's intensity function suggested that the gamma priors for the EPM hyperparameters disturb the model shrinkage effect of the internal $\Gamma$P. In order to ensure that the model shrinkage effect of the EPM works in an appropriate manner, we proposed two novel generative constructions of the EPM: CEPM incorporating constrained gamma priors, and DEPM incorporating Dirichlet priors instead of the gamma priors. Furthermore, all DEPM's model parameters including the infinite atoms of the $\Gamma$P prior could be marginalized out, and thus it was possible to derive a truly infinite DEPM (IDEPM) that can be efficiently inferred using a collapsed Gibbs sampler. We experimentally confirmed that the model shrinkage of the proposed models works well and that the IDEPM indicated state-of-the-art performance in generalization ability, link prediction accuracy, mixing efficiency, and convergence speed.

The Re-Pair algorithm (Re-Pair), proposed by Larsson and Moat, is a simple grammar-based compression method that achieves a good compression ratio. Although Re-Pair runs in O(n) time and space for an input of length n, it cannot be used with a large input, because it runs oine and consumes substantial memory space. In this paper, we propose an online grammar transformation algorithm based on a modied Re-Pair along with a compression method using the algorithm. The proposed algorithm runs in O(n log^ h) time using O(g) space, where g and ^h are the number of production rules in a grammar and the maximum height of syntax trees generated by the rules, respectively. We implemented our method and demonstrated that it signicantly reduces memory usage with little sacrice of compression ratio in comparison with the original Re-Pair.

Latent variable models for relational data enable us to extract a co-cluster structure underlying observed relational data. The Infinite Relational Model (IRM) is a well-known relational model for discovering co-cluster structures with an unknown number of clusters. The IRM and several related models commonly assume that link probability between two objects depends only on their cluster assignment. However, relational models based on this assumption often lead us to extract many non-informative and unexpected clusters. This is because the cluster structures underlying real-world relationships are often blurred by biases that are inherent to individual objects. To overcome this problem, we propose a multilayered framework that extracts a clear co-cluster structure in the presence of objects' biases. Then, we propose a new model which is a special instance of the proposed framework that incorporates the IRM. Furthermore, we reveal that some relational models can be regarded as special cases of the proposed model. We present an efficient Gibbs sampler for posterior inference. Experiments conducted using real-world datasets confirm that the proposed model successfully extracts clear and interpretable cluster structures from blurred relational data.

We address the problem of applying the Re-Pair [LM99] algorithm to large texts. The Re-Pair algorithm (Re-Pair) proposed by Larsson and Moffat in 1999 is a simple grammar-based compression method that achieves an extremely good compression ratio. However, Re-Pair is not applicable to a large text because it consumes much memory and runs in an offline manner. Dividing the input into a consecutive sequence of smaller blocks works well for the problem, but this solution makes the compression ratio worse. In our previous research we proposed a method that shares a part of dictionaries of Re-Pair among blocks in order to reduce the decrease, where the shared dictionary is constructed at the beginning. In this paper we present a new method that adaptively reconstructs the shared dictionary. We implemented our method and investigated its performance through several experiments. The results show that our method runs much faster than an existent method and obtains a good compression ratio comparable to well-known compression tools.

In this paper, we propose a simple method for direct access to variable-to-fixed length codes (VF codes) by adding an auxiliary succinct index structure to the encoded text. The method solves the substring decompression problem in O(N/n+l) time in the average case, where N, n, and l are the original text length, the encoded text length, and the length of the target substring, respectively. We implemented our method with exploiting Re-Pair-VF and showed that our method solves the substring decompression problem much faster than FOLCA proposed by Maruyama et al. in 2013.

The Re-Pair algorithm proposed by Larsson and Moffat in 1999 is a simple grammar-based compression method that achieves an extremely high compression ratio. However, Re-Pair is an offline and very space consuming algorithm. Thus, to apply it to a very large text, we need to divide the text into smaller blocks. Consequently, if we share a part of the dictionary among all blocks, we expect that the compression speed and ratio of the algorithm will improve. In this paper, we implemented our method with exploiting variable-to-fixed-length codes, and empirically show how the compression speed and ratio of the method vary by adjusting three parameters: block size, dictionary size, and size of shared dictionary. Finally, we discuss the tendencies of compression speed and ratio with respect to the three parameters.

Summary form only given. We address the problem of improving variable-length-to-fixed-length codes (VF codes). A VF code is an encoding scheme that uses a fixed-length code, and thus, one can easily access the compressed data. However, conventional VF codes usually have an inferior compression ratio to that of variable-length codes. Although a method proposed by T. Uemura et al. in 2010 achieves a good compression ratio comparable to that of gzip, it is very time consuming. In this study, we propose a new VF coding method that applies a fixed-length code to the set of rules extracted by the Re-Pair algorithm, proposed by N. J. Larsson and A. Moffat in 1999. The Re-Pair algorithm is a simple off-line grammar-based compression method that has good compression-ratio performance with moderate compression speed. Moreover, we present several experimental results to show that the proposed coding is superior to the existing VF coding.

This paper discusses pattern matching problem on Variable-to-Fixed-length codes (VF codes). A VF code is a coding scheme whose codeword lengths are fixed, and thus it is suitable for comprssed pattern matching. However, there are few reports showing its efficiency so far. We have investigated into the compression ratios and encoding/decoding speeds besides pattern matching performance on Tunstall codes and STVF codes. We have also done how an entropy coding affects to VF codes. In our experiments, we tested Huffman coding and Range coding for entropy codings.

Almost Instantaneous VF code proposed by Yamamoto and Yokoo in 2001, which is one of the variable-length-to-fixed-length codes, uses a set of parse trees and achieves a good compression ratio. However, it needs much time and space for both encoding and decoding than an ordinary VF code does. In this paper, we proved that we can multiplex the set of parse trees into a compact single tree and simulate the original encoding and decoding procedures. Our technique reduces the total number of nodes into O(2lk - k2), while it is originally O(2lk), where l and k are the codeword length and the alphabet size, respectively. The experimental results showed that we could encode and decode over three times faster for natural language texts by using this technique.

We propose an efficient variable-length-to-fixed-length code (VF code for short), called ST-VF code. It utilizes a frequency-base-pruned suffix tree as a parse tree. VF codes as typified by Tunstall code have a preferable aspect to compressed pattern matching. It is unnecessary to distinguish code boundaries on compressed texts since all codewords have the same length.

Approximate string matching on compressed text was an open problem for almost a decade. The two existing solutions are very new. Despite that they represent important complexity breakthroughs, in most practical cases they are not useful, in the sense that they are slower than uncompressing the text and then searching the uncompressed text. We present a different approach, which reduces the problem to multipattern searching of pattern pieces plus local decompression and direct verification of candidate text areas. We show experimentally that this solution is 10-30 times faster than previous work and up to three times faster than the trivial approach of uncompressing and searching, thus becoming the first practical solution to the problem.

Addresses the problem of approximate string matching on compressed text. We consider this problem for a text string described in terms of a collage system, which is a formal system proposed by T. Kida et al. (1999) that captures various dictionary-based compression methods. We present an algorithm that exploits bit-parallelism, assuming that our problem fits in a single machine word, e.g. (m-k)(k+1)/spl les/L, where m is the pattern length, k is the number of allowed errors and L is the length, in bits, of the machine word. For a class of simple collage systems, the algorithm runs in O(k/sup 2/(/spl par//spl Dscr//spl par/+|/spl Sscr/|)+km) time using O(k/sup 2//spl par//spl Dscr//spl par/) space, where /spl par//spl Dscr//spl par/ is the size of dictionary /spl Dscr/ and |/spl Sscr/| is the number of tokens in the sequence /spl Sscr/. The LZ78 (Lempel-Ziv, 1978) and the LZW (Lempel-Ziv-Welch, 1984) compression methods are covered by this class. Since we can regard n=/spl par//spl Dscr//spl par/+|/spl Sscr/| as the compressed length, the time and space complexities are O(k/sup 2/n+km) and O(k/sup 2/n), respectively. For general k and m, they become O(k/sup 3/mn/L+km) and O(k/sup 3/mn/L). Thus, our algorithm is competitive to the algorithm proposed by J. Ka/spl uml/rkka/spl uml/inen, et al. (2000), which runs in O(km) time using O(kmn) space, when k=O(/spl radic/L).

We address the problem of searching in LZW compressed text directly, and present a new algorithm for finding multiple patterns by simulating the move of the Aho-Corasick (1975) pattern matching machine. The new algorithm finds all occurrences of multiple patterns whereas the algorithm proposed by Amir, Benson, and Farach (see Journal of Computer and System Sciences, vol.52, p.299-307, 1996) finds only the first occurrence of a single pattern. The new algorithm runs in O(n+m/sup 2/+r/sub a/) time using O(n+m/sup 2/) space, where n is the length of the compressed text, m is the length of the total length of the patterns, and r is the number of occurrences of the patterns. We implemented a simple version of the algorithm, and showed that it is approximately twice faster than a decompression followed by a search using the Aho-Corasick machine.