Accessing the Suffix Array via $\phi^-1$-Forest
Accessing the Suffix Array via $\phi^-1$-Forest
复制标题
通过 $phi^-1$-Forest 访问后缀数组
DOI：
10.1007/978-3-031-20643-6_7
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Christina Boucher and Dominik Koeppl and Herman Perera and Massimiliano Rossi
中科院分区：
文献类型：
--
作者：
Tomohiro I;Dominik Koeppl;Dominik Koeppl;Dominik Koeppl and Simon J. Puglisi and Rajeev Raman;Daiki Hashimoto and Diptarama Hendrian and Dominik Koeppl and Ryo Yoshinaka and Ayumi Shinohara;Christina Boucher and Dominik Koeppl and Herman Perera and Massimiliano Rossi
Kärkkainen等人。(CPM，2009)定义了信息技术的概念，这后来成为构建信息技术指标的关键。给定一个字符串[1..n]、它的后缀数组和它的逆后缀数组，我们定义这些数组的排列，以此类推。Gagie等人(JACM，2020)表明，存储单词是可能的，以便及时评估排列和评估，这一点不时得到Nishimoto和Tabe的改进(ICALP，2021)。在本文中，我们引入了森林的概念，它是一种使用采样值来加速随机访问的数据结构。我们实现了我们的方法，并将其性能与ther-index进行了比较。
Kärkkainen et al. (CPM, 2009) defined the concept ofthat later became key to the construction of ther-index. Given a stringS[1..n], its suffix arrayand its inverse suffix array, we defineas the permutation ofsuch thatif, andotherwise. Gagie et al. (JACM, 2020) showed that it is possible to storewords such that the permutationsandare evaluated in-time, which was improved to-time by Nishimoto and Tabei (ICALP, 2021). In this paper, we introduce the concept of-forest, which is a data structure using sampledvalues to speed up random access to. We implemented our approach and compared its performance with respect to ther-index.