On shortest unique substring queries
On shortest unique substring queries
复制标题
关于最短唯一子串查询
DOI：
10.1109/icde.2013.6544887
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Mi
中科院分区：
文献类型：
--
作者：
J. Pei;W. Wu;Mi
在本文中，我们解决了一种新类型的有趣的查询-最短的唯一子串查询。给定一个（长）字符串S和字符串中的一个查询点q，我们能否找到一个包含q的最短子串，该子串在S中是唯一的？我们说明了最短的唯一子串查询有许多潜在的应用，如信息检索，生物信息学，和事件上下文分析。我们开发了有效的在线查询回答算法。首先，我们提出了一个算法来回答一个最短的唯一子串查询在O（n）的时间使用后缀树索引，其中n是字符串S的长度。其次，我们证明了，使用O（n·h）时间和O（n）空间，我们可以计算一个最短的唯一子串的每个位置在一个给定的字符串，其中h是可变的理论上在O（n），但在真实的数据集往往比n小得多，可以被视为一个常数。一旦最短的唯一子串被预先计算，最短的唯一子串查询可以在恒定的时间内在线回答。除了坚实的算法结果，我们经验证明的有效性和效率最短的唯一子串查询真实的数据集。
In this paper, we tackle a novel type of interesting queries - shortest unique substring queries. Given a (long) string S and a query point q in the string, can we find a shortest substring containing q that is unique in S? We illustrate that shortest unique substring queries have many potential applications, such as information retrieval, bioinformatics, and event context analysis. We develop efficient algorithms for online query answering. First, we present an algorithm to answer a shortest unique substring query in O(n) time using a suffix tree index, where n is the length of string S. Second, we show that, using O(n·h) time and O(n) space, we can compute a shortest unique substring for every position in a given string, where h is variable theoretically in O(n) but on real data sets often much smaller than n and can be treated as a constant. Once the shortest unique substrings are pre-computed, shortest unique substring queries can be answered online in constant time. In addition to the solid algorithmic results, we empirically demonstrate the effectiveness and efficiency of shortest unique substring queries on real data sets.