A framework of context-sensitive grammar transform for speeding-up compressed pattern matching (CPM) is proposed. A greedy compression algorithm with the transform model is presented as well as a Knuth-Morris-Pratt (KMP)-type compressed pattern matching algorithm. The compression ratio is a match for gzip and Re-Pair, and the search speed of our CPM algorithm is almost twice faster than the KMP-type CPM algorithm on Byte-Pair-Encoding by Shibata et al., and in the case of short patterns, faster than the Boyer-Moore-Horspool algorithm with the stopper encoding by Rautio et al., which is regarded as one of the best combinations that allows a practically fast search.

This paper addresses the problem of finding, evaluating, and selecting the best set of codewords for the 4b/10b line code, a dependable line code with forward error correction (FEC) designed for real-time communication. Based on the results of our scheme [1], we formulate codeword search as an instance of the maximum clique problem, and enumerate all candidate codeword sets via maximum clique enumeration as proposed by Eblen et al. [2]. We then measure each set in terms of resistance to bit errors caused by noise and present a canonical set of codewords for the 4b/10b line code. Additionally, we show that maximum clique enumeration is #P-hard.

We propose online prediction algorithms for data streams whose characteristics might change over time. Our algorithms are applications of online learning with experts. In particular, our algorithms combine base predictors over sliding windows with different length as experts. As a result, our algorithms are guaranteed to be competitive with the base predictor with the best fixed-length sliding window in hindsight.