A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
复制标题
一种简单但时间最优的线性空间算法，用于最短唯一子串查询
DOI：
10.1016/j.tcs.2014.11.004
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Bojian Xu
中科院分区：
文献类型：
--
作者：
Atalay Mert Ileri;M. Külekci;Bojian Xu
我们重新审视 Pei 等人最近提出的寻找最短唯一子串（SUS）的问题（2013）[12]。我们提出了一种最优的 O(n) 时间和空间算法，可以为大小为 n 的字符串的每个位置找到 SUS，从而显着提高其 O(n 2) 时间复杂度。我们的方法还支持查找覆盖每个位置的所有 SUS，而他们的方法只能为每个位置找到一个 SUS。此外，我们的解决方案更简单、更容易实现，并且在实践中更节省空间，因为我们只使用字符串的逆后缀数组和最长公共前缀数组，而他们的算法使用字符串的后缀树和其他辅助数据结构。我们的理论结果通过现实世界数据的实证研究得到了验证，该研究表明我们的方法至少快 8 倍，并且使用的内存至少减少 20 倍。当字符串大小由于其二次时间复杂度而增加时，我们的方法相对于 Pei 等人的方法所获得的加速可能会变得更加显着。我们还将我们的方法与最近的 Tsuruta 等人 (2014)[14] 的提案进行了比较，这是另一种用于 SUS 查找的独立 O(n) 时间和空间算法。实证研究表明两种方法的处理速度几乎相同。然而，我们的查找一个 SUS 所用的内存至少减少了 4 倍，查找所有 SUS 所用的内存至少减少了 2 倍，两者都覆盖了每个字符串位置。
We revisit the problem of finding shortest unique substring (SUS) proposed recently by Pei et al.(2013)[12]. We propose an optimal O (n) time and space algorithm that can find an SUS for every location of a string of size n and thus significantly improve their O (n 2) time complexity. Our method also supports finding all the SUSes covering every location, whereas theirs can find only one SUS for every location. Further, our solution is simpler and easier to implement and is more space efficient in practice, since we only use the inverse suffix array and the longest common prefix array of the string, while their algorithm uses the suffix tree of the string and other auxiliary data structures. Our theoretical results are validated by an empirical study with real-world data that shows our method is at least 8 times faster and uses at least 20 times less memory. The speedup gained by our method against Pei et al.'s can become even more significant when the string size increases due to their quadratic time complexity. We also have compared our method with the recent Tsuruta et al.'s (2014)[14] proposal, another independent O (n) time and space algorithm for SUS finding. The empirical study shows that both methods have nearly the same processing speed. However, ours uses at least 4 times less memory for finding one SUS and at least 2 times less memory for finding all SUSes, both covering every string location.