Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
复制标题
RMQ 问题的理论和实践改进及其在 LCA 和 LCE 中的应用
DOI：
10.1007/11780441_5
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Volker Heun
中科院分区：
文献类型：
--
作者：
J. Fischer;Volker Heun
最低范围 - 问题问题是预处理阵列，以便可以有效地获得两个指定索引之间的最小元素的位置。我们为一般RMQ问题提供了直接算法，该算法具有线性预处理时间和恒定查询时间，而无需使用任何动态数据结构。它消耗了伯克曼和维斯金方法所需的空间的一半。我们将新算法用于RMQ来改进二进制树的LCA计算，并仅基于阵列提供了恒定的LCE-Algorithm。 LCA和LCE都有重要的应用，例如在计算生物学中。实验研究表明，在实践中，我们的新方法几乎是以前的方法的两倍，并且对于当今常见的问题大小而言，恒定时间算法的变体的渐近变体速度较慢。
The Range-Minimum-Query-Problem is to preprocess an array such that the position of the minimum element between two specified indices can be obtained efficiently. We present a direct algorithm for the general RMQ-problem with linear preprocessing time and constant query time, without making use of any dynamic data structure. It consumes less than half of the space that is needed by the method by Berkman and Vishkin. We use our new algorithm for RMQ to improve on LCA-computation for binary trees, and further give a constant-time LCE-algorithm solely based on arrays. Both LCA and LCE have important applications, e.g., in computational biology. Experimental studies show that our new method is almost twice as fast in practice as previous approaches, and asymptotically slower variants of the constant-time algorithms perform even better for today's common problem sizes.