最大總和區間與最大平均值區間相關問題的線上演算法和區域查詢技術

Abstract

Range Minima Query 問題 (或簡稱 RMQ 問題)定義為, 先對一個 A[1...n] 的實數數列作些處理, 之後我們希望能有效地回答一連串像這樣的區域查詢: ``給任意兩個位置 i 和 j, 在子數列 A[i...j] 中, 最小作的位置在哪?', 這個問題已被証明和 LCA 問題等價 (LCA 問題是對一個樹結構先處理完後, 回答任兩個節點最近的共同祖先位置在哪? ), 這兩個問題在 RAM model 下都已有最佳解. 我們的動機來自一些生物序列分析的相關問題, 這篇論文的前半部分, 探討了一個類似上面的區域查詢問題, 在這個新問題中, 我們希望回答像這樣的區域查詢: ``給兩個位置 i 和 j, 在子數列 A[i...j] 中, 最大總和區間位置在哪?', 透過証明這個問題等價於 RMQ 問題, 我們得到了一個線性處理時間和常數回答時間的演算法, 經由進一步延伸後, 我們可以用所發展出來的區域查詢技術來解決三個跟最大總和區間相關的序列分析問題, 這也說明了此區域查詢技術在此類問題中的潛在應用. 至於論文的後半部分, 我們針對其中一個和最大總和區間相關的問題做了進一步的探討: ``給一個實數序列, 分別找出最長和最短有總和或平均值限制的區間位置', 我們設計了兩個擁有線上運算特性的最佳演算法, 這改進了以往演算法無法有效處理資料串流的缺點.

The range minima query problem, RMQ for short, is to preprocess a sequence of real numbers A[1...n] for subsequent queries of the form: ``Given indices i, j, what is the index of the minimum value of A[1...n]?' This problem is shown to be equivalent to the LCA problem in which a tree is preprocessed for answering the lowest common ancestor of two nodes. It is also shown that both the RMQ and LCA problem can be solved optimally under the RAM model. Motivated by some biological string problems, the first part of the paper considers a similar query problem, in which we wish to answer queries of the form: ``Given indices i, j, where is the maximum-sum segment of A[1...n]?' By showing the equivalence between this problem and RMQ, we obtain a linear preprocessing time and constant query time solution. We extend this result to solve in linear time three biological string problems related to maximum-sum segments. These variations on the basic theme demonstrate the utilities of the techniques developed in this thesis. As for the second part of the paper, we devise two linear time online algorithms for the following biological string problems: ``Given a sequence of real numbers, locate the longest and shortest segment satisfying a sum or an average constraint.' Our algorithms improve on previous algorithms by providing the capability of handling data string inputs.