Direct Access to Variable-to-Fixed Length Codes with a Succinct Index
Satoshi Yoshida, Hirohito Sasakawa, Kei Sekine, Takuya Kida · 2014
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.