An Efficient Index Data Structure with the Capabilities of Suffix Trees and Suffix Arrays for Alphabets of Non-negligible Size
An Efficient Index Data Structure with the Capabilities of Suffix Trees and Suffix Arrays for Alphabets of Non-negligible Size
复制标题
一种具有后缀树和后缀数组功能的高效索引数据结构，适用于不可忽略大小的字母表
DOI：
10.1007/978-3-540-30213-1_22
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Heejin Park
中科院分区：
文献类型：
--
作者：
Dong Kyue Kim;Jeong;Heejin Park
后缀树和后缀数组是全文索引的基本数据结构，在它们的基础上已经开发了许多算法来解决字符串处理和信息检索中出现的问题。使用后缀树可以更有效地解决一些问题，使用后缀数组可以更有效地解决其他问题。我们认为索引数据结构的后缀树和后缀数组的能力，而不需要太多的空间。对于大小可以忽略不计的字母表，Abouelhoda等人为此开发了增强后缀数组。它由后缀数组和子表组成。子表存储后缀树中节点之间的父子关系，以便在后缀树上开发的每个算法都可以通过小而系统的修改来运行。由于子表占用适度的空间，并且构造速度非常快，因此增强的后缀数组几乎与后缀数组一样具有时间/空间效率。然而，当字母表的大小不可忽略时，增强后缀阵列失去后缀树的能力。在扩展后缀数组中进行模式搜索的时间为O（m），其中m是模式的长度，m是字母表，而在后缀树中进行模式搜索的时间为O（mlog）.本文改进了扩展后缀数组，使其在字母表大小不可忽略的情况下也具有后缀树和后缀数组的能力.我们通过提出一个新的子表来实现这一点，该子表改进了增强的后缀数组，以支持O（mlog数组）时间内的模式搜索。我们的索引数据结构几乎与增强的后缀数组一样具有时间/空间效率。它消耗与增强后缀数组相同的空间，其构造时间比增强后缀数组稍慢（< 4%）。从另一个角度来看，它可以被认为是第一个实用的一个促进后缀树的能力时，字母表的大小是不可忽略的，因为后缀树supportingO（mlog的后缀树）-时间模式搜索是不容易实现的，因此它很少在实践中使用。
The suffix tree and the suffix array are fundamental full-text index data structures and many algorithms have been developed on them to solve problems occurring in string processing and information retrieval. Some problems are solved more efficiently using the suffix tree and others are solved more efficiently using the suffix array. We consider the index data structure with the capabilities of both the suffix tree and the suffix array without requiring much space. For the alphabets whose size is negligible, Abouelhoda et al. developed the enhance suffix array for this purpose. It consists of the suffix array and the child table. The child table stores the parent-child relationship between the nodes in the suffix tree so that every algorithm developed on the suffix tree can be run with a small and systematic modification. Since the child table consumes moderate space and is constructed very fast, the enhanced suffix array is almost as time/space-efficient as the suffix array. However, when the size of the alphabet is not negligible, the enhance suffix array loses the capabilities of the suffix tree. The pattern search in the enhanced suffix array takesO(m∣Σ∣) time wheremis the length of the pattern and Σ is the alphabet, while the pattern search in the suffix tree takesO(mlog∣Σ∣) time.In this paper, we improve the enhanced suffix array to have the capabilities of the suffix tree and the suffix array even when the size of the alphabet is not negligible. We do this by presenting a new child table, which improves the enhanced suffix array to support the pattern search inO(mlog∣Σ∣) time. Our index data structure is almost as time/space-efficient as the enhanced suffix array. It consumes the same space as the enhanced suffix array and its construction time is slightly slower (< 4%) than that of the enhanced suffix array. In a different point of view, it can be considered the first practical one facilitating the capabilities of suffix trees when the size of the alphabet is not negligible because the suffix tree supportingO(mlog∣Σ∣)-time pattern search is not easy to implement and thus it is rarely used in practice.
影响因子：
2.5
作者：
MCCREIGHT, EM
通讯作者：
MCCREIGHT, EM