A Compressed Enhanced Suffix Array Supporting Fast String Matching
A Compressed Enhanced Suffix Array Supporting Fast String Matching
复制标题
一种支持快速字符串匹配的压缩增强后缀数组
DOI：
10.1007/978-3-642-03784-9_6
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Simon Gog
中科院分区：
文献类型：
--
作者：
Enno Ohlebusch;Simon Gog
像后缀树或后缀数组这样的索引结构在字符串学中非常重要，尤其是在精确的字符串匹配中。在过去的十年中，压缩索引结构的研究蓬勃发展，因为在许多应用中的主要问题是索引的空间消耗。通过使用范围最小查询或所谓的子表，可以模拟模式与增强后缀数组上的后缀树的匹配。在本文中，我们表明，超笛卡尔树的LCP数组（后缀数组增强）非常自然地解释了子表。然而，更重要的是，该树的平衡括号表示构成了子表的非常自然的压缩形式，该子表允许在O（mlog）中定位长度为m的模式P的所有occ出现|Σ| + occ）time，其中，x是底层字母表。我们的压缩子表比以前的解决方案使用更少的空间。实现是可用的。
Index structures like the suffix tree or the suffix array are of utmost importance in stringology, most notably in exact string matching. In the last decade, research on compressed index structures has flourished because the main problem in many applications is the space consumption of the index. It is possible to simulate the matching of a pattern against a suffix tree on an enhanced suffix array by using range minimum queries or the so-called child table . In this paper, we show that the Super-Cartesian tree of the LCP-array (with which the suffix array is enhanced) very naturally explains the child table. More important, however, is the fact that the balanced parentheses representation of this tree constitutes a very natural compressed form of the child table which admits to locate all occ occurrences of pattern P of length m in O (m log|Σ| + occ ) time, where Σ is the underlying alphabet. Our compressed child table uses less space than previous solutions to the problem. An implementation is available.