Port-based teleportation is a variant of quantum teleportation, where the receiver can choose one of the ports in his part of the entangled state shared with the sender, but cannot apply other recovery operations.We show that the optimal fidelity of deterministic port-based teleportation (dPBT) using <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> = <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> + 1 ports to teleport a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</i>-dimensional state is equivalent to the optimal fidelity of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</i>-dimensional unitary estimation using n calls of the input unitary operation. From any given dPBT, we can explicitly construct the corresponding unitary estimation protocol achieving the same optimal fidelity, and vice versa. Using the obtained one-to-one correspondence between dPBT and unitary estimation, we derive the asymptotic optimal fidelity of port-based teleportation given by 1 − <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(d⁴)N−2</i> ≤ <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F</i> ≤ 1−Ω(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</i>4)<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>−2, which improves the previously known result given by 1 − <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(d⁵)N−2</i> ≤ F ≤ 1 − Ω(d2)N−2. We also show that the optimal fidelity of unitary estimation for the case n ≤ d − 1 is <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F</i> = n+1/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d²</i> , and this fidelity is equal to the optimal fidelity of unitary inversion with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> ≤ <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</i> − 1 calls of the input unitary operation even if we allow indefinite causal order among the calls.

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.