We propose a new indexing structure for parameterized strings, called parameterized position heap. Parameterized position heap is applicable for parameterized pattern matching problem, where the pattern matches a substring of the text if there exists a bijective mapping from the symbols of the pattern to the symbols of the substring. We propose an online construction algorithm of parameterized position heap of a text and show that our algorithm runs in linear time with respect to the text size. We also show that by using parameterized position heap, we can find all occurrences of a pattern in the text in linear time with respect to the product of the pattern size and the alphabet size.

Summary form only given. Compression via Substring Enumeration (CSE) is a lossless universal data compression scheme, introduced by Dube and Beaudoin [1]. CSE compresses a target binary string by enumerating substrings occurred in it, and encodes the numbers of occurrences effectively, by calculating its upper-bound and lower-bound based on the previous numbers. They used a data structure called Compacted Substring Tree (CST) for counting the occurrences. Instead of CST, Kanai et al. [2] proposed an elegant and efficient implementation for CSE by utilizing Burrows-Wheeler Transform (BWT) Matrix and several auxiliary arrays. In this paper, we extend it in two ways, (1) to deal with the explicit phase awareness for byte-oriented source, and (2) to treat multiple characters for a finite alphabet source. Extension for Explicit Phase Awareness The original CSE is not effective for non-textual and byte-oriented data. Beliveau et al. [3] improved CSE to deal with the phase unaware problem, by categorizes the substrings based on the positions that start in a byte, and counting the occurrences separately. We adopt it and naturally extend Kanai's method. The running time is O(n). Extension for CSE with Finite Alphabet. The original CSE is intended for binary strings, and no experimental results are shown to deals with multiple characters explicitly so far, for the best of our knowledges. We extend Kanai's method for a finite alphabet, by utilizing some additional auxiliary arrays and the Wavelet Tree (or Wavelet Matrix). It also runs in O(n) time assuming that alphabet size is constant.

Most existing reinforcement learning algorithms require many trials until they obtain optimal policies. In this study, we apply transfer learning to reinforcement learning to realize greater efficiency. We propose a new algorithm called TR-MAX, based on the R-MAX algorithm. TR-MAX transfers the transition and reward probabilities from a source task to a target task as prior knowledge. We theoretically analyze the sample complexity of TR-MAX. Moreover, we show that TR-MAX performs much better in practice than R-MAX in maze tasks.