ESP-index: A compressed index based on edit-sensitive parsing
ESP-index: A compressed index based on edit-sensitive parsing
复制标题
DOI：
10.1016/j.jda.2012.07.009
复制
发表时间：
2011-10
期刊：
影响因子：
--
通讯作者：
Shirou Maruyama;Masaya Nakahara;Naoya Kishiue;H. Sakamoto
中科院分区：
文献类型：
--
作者：
Shirou Maruyama;Masaya Nakahara;Naoya Kishiue;H. Sakamoto
提出了一种基于编辑敏感句法分析的自索引ESP-INDEX。给定一个字符串S，ESP树等价于一个仅派生出S的CFG，它可以表示为一个受限的DAG。在S中发现模式P归结为将P的解析树嵌入到G中。采用几种简洁的数据结构，将G分解成两个比特串和一个单独的数组，需要(1+ε)nlogn+4n+o(N)比特的空间，其中n是G和0<；ε<的变量数；1.S中P的出现次数的统计时间为O((1/ε)(mlogn+occlogmlogu)log⁎u)，其中m=|P|，u=|S|，occc是P和S的ESP树中最大公共子树出现的次数。通过增加nlogu位空间数组，我们的索引支持定位和提取。对于任何长度为m的子串，定位时间与计数时间相同，提取时间为O((1/ε)(m+logu))。
We propose ESP-index, a self-index based on edit-sensitive parsing. Given a string S, ESP tree is equivalent to a CFG deriving just S, which can be represented as a restricted DAG G. Finding pattern P in S is reduced to embedding the parsing tree of P into G. Adopting several succinct data structures, G is decomposed into two bit strings and a single array, requiring (1+ε)nlogn+4n+o(n) bits of space, where n is the number of variables of G and 0<ε<1. The counting time for the occurrences of P in S is in O((1/ε)(mlogn+occclogmlogu)log⁎u), where m=|P|, u=|S|, and occcis the number of the occurrences of a maximal common subtree in ESP trees of P and S. With the additional array of nlogu bits of space, our index supports the locating and extracting. Locating time is the same as counting time and extracting time for any substring of length m is O((1/ε)(m+logu)).