範囲最小クエリ

コンピュータサイエンスでは、範囲最小クエリ( RMQ ) は、比較可能なオブジェクトの配列のサブ配列内の最小値を見つける問題を解決します。範囲最小クエリには、最低共通祖先問題や最長共通接頭辞問題(LCP) など、コンピュータサイエンスにおけるいくつかの使用例があります。

意味

範囲最小クエリを解決するために、対応するカルテシアンツリーを構築します。 — 範囲最小クエリは、最小共通祖先問題に縮小されます。

整数などの完全に順序付けられたセットから取得された $n 個$ のオブジェクトの配列 $A$ $[1 \dots$ $n$ $]が与えられた場合、範囲最小クエリ$ $RMQ$ $A$ $($ $l$ $,$ $r$ $) =arg min$ $A$ $[$ $k$ $]$ ( $1 \leq$ $l$ $\leq$ $k$ $\leq$ $r$ $\leq$ $n ) は、指定されたサブ配列$ $A$ $[$ $l$ $\dots$ $r$ $]$ 内の最小要素の位置を返します。

例えば、 $A = [0,5,2,5,4,3,1,6,3]$ の場合、サブ配列 $A [3 \dots 8] = [2,5,4,3,1,6]$ の範囲最小クエリの答えは次のようになります。7、 $A [7] = 1$ である。

アルゴリズム

素朴な解決策

典型的な設定では、配列 $A は$ 静的です。つまり、一連のクエリ中に要素が挿入または削除されることはなく、クエリはオンラインで回答されます（つまり、クエリのセット全体がアルゴリズムに事前に通知されることはありません）。この場合、配列を適切に前処理してデータ構造にすることで、クエリへの回答が速くなります。単純な解決策は、すべての可能なクエリ、つまり $A$ のすべてのサブ配列の最小値を事前に計算し、これを配列 $Bに格納して$ $B [i, j] = min(A [i \dots j])$ とすることです。すると、範囲が最小のクエリは、 $B$ の配列検索によって定数時間で解決できます。長さ $n の配列には$ $Θ(n ²)$ の可能なクエリがあり、これらの回答は動的計画法によって $Θ($ $n$ $²)$ 時間で計算できます。^[1]

一定時間後の解線形空間と時間の事前計算

上記のソリューションと同様に、結果を事前計算することで、定数時間でクエリに応答できます。ただし、配列には、すべての範囲 $[i, j]$ ではなく、サイズが 2 の累乗である範囲に対してのみ、事前計算された範囲最小クエリが格納されます。各開始位置 i に対して O(log n ) 個のこのようなクエリがある $ため、動的プログラミングテーブル B のサイズは O( n log n ) です。B [ i$ $,$ $j] の$ 値 $は$ 、 $範囲$ $A$ $[$ $i$ $\dots$ i $+2$ $j$ $-1$ $]$ $の$ 最小 $値$ $の$ $インデックス$ $です$ $。$ $テーブル$ $を$ $埋める$ には $O($ $n$ $log$ $n$ $)$ の時間がかかり、最小値のインデックスは次の再帰式を使用します^[1]^[2]

A [B [i, j -1]] \leq A [B [i +2 j -1, j -1]]

の場合、

B [i, j] = B [i, j -1]

です。

それ以外の場合、

B [i, j] = B [i +2 j -1, j -1]

。

この事前計算ステップの後、クエリ $RMQ A (l, r) は$ 、 2 つの別々のクエリに分割することで定数時間で回答できるようになりました。1 つは、 $lから$ $r$ より小さい最大のメモ化された値までの範囲の事前計算済みクエリです。もう 1 つは、 $r を$ 右の境界とする同じ長さの間隔のクエリです。これらの間隔は重なる場合がありますが、たとえば配列内の数値の合計ではなく最小値を計算しようとしているため、これは問題になりません。したがって、線形時間の事前計算の後、全体の結果は定数時間で取得できます。つまり、2 つのクエリは定数時間で回答でき、残っているのは 2 つの結果のうち小さい方を選択することだけです。

線形時間と空間の事前計算後の対数クエリ時間を使用したソリューション

このソリューションは、事前計算を $O (n)$ 時間で行います。そのデータ構造は $O (n)$ 空間を使用し、そのデータ構造は対数時間でクエリに応答するために使用できます。^[2]配列はまず概念的にサイズ $s = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠のブロックに分割されます。ログn/4⁠ . その後、各ブロックの最小値は全体で$ $O (n)$ 時間で計算され、最小値は新しい配列に格納されます。

RMQ は、左クエリ境界、右クエリ境界、およびその間のすべてのブロックを含むブロックを調べることで、対数時間で回答できるようになりました。

境界を含む 2 つのブロックは単純に検索できます。境界外の要素を調べる必要すらありません。これは対数時間で実行できます。
クエリに回答するには、範囲内に完全に含まれるすべてのブロックの最小値と、上記の 2 つの最小値を比較する必要があります。
配列はサイズのブロックに分割されているため $、$ $ログ n / 4 ⁠$ 、最大で $⁠$ $4 位 / ログ n ⁠$ クエリに完全に含まれるブロック。
線形解法を使うことで、これらのブロックの全体的な最小値を見つけることができます。このデータ構造のサイズは $O （ ⁠ ん / ログ n ⁠ ログ (⁠ ん / ログ n ⁠)) = O (n)$ です。
ここで、比較する必要があるのは 3 つの最小値だけです。

例えば、配列 $A = [0,5,2,5,4,3,1,6,3]$ とブロックサイズ3（説明のみを目的としています）は、最小配列 $A' = [0,3,1]$ を生成します。

定数時間と線形空間を使用したソリューション

上記のソリューションを使用すると、クエリに完全に含まれていないブロック内のサブクエリは、依然として定数時間で回答される必要があります。これらのブロックは最大で 2 つあります。l を含むブロック $と$ $r を$ 含むブロックです。定数時間は、配列内のすべてのブロックのカルテシアンツリーを保存することで実現されます。いくつかの観察事項:

同型カルテシアンツリーを持つブロックは、そのブロック内のすべてのクエリに対して同じ結果を返します。
$s$ 個のノードの異なる直交木の数は $C s$ であり、これは $s$ 番目のカタラン数である。
$したがって、ブロックの異なるカルテシアンツリーの数は4$ $秒$ の範囲です。

このようなツリーごとに、すべてのクエリの可能な結果を保存する必要があります。これは $s 2$ または $O (log 2 n)$ エントリになります。つまり、テーブル全体のサイズは $O (n)$ です。

結果を効率的に検索するには、特定のブロックに対応するデカルトツリー (行) を定数時間でアドレス指定できる必要があります。解決策は、すべてのツリーの結果を配列に格納し、バイナリツリーから整数への一意の投影を見つけてエントリをアドレス指定することです。これは、ツリーを幅優先検索し、デカルトツリー内の既存のノードごとに 2 つの子ノードが存在するようにリーフノードを追加することで実現できます。次に、すべての内部ノードを 0 ビットとして、すべてのリーフをビットワードの 1 ビットとして表すことによって整数が生成されます (ツリーをレベル順に再度トラバースすることにより)。これにより、サイズは $⁠$ $ログ n / 4 ⁠すべてのツリーに対して。任意のツリーに定数時間でランダムアクセスできるようにするには、元$ $の$ 配列に含まれていないツリーも含める必要があります。⁠ のインデックスを持つ配列は、 $ログ n / 4 ⁠$ ビット長は $2です ⁠ ログ n / 4 ⁠ = O (n)$ 。

アプリケーション

RMQは、正確な文字列マッチングや近似文字列マッチングの多くのタスクのツールとして使用されています。いくつかのアプリケーションは、FischerとHeun（2007）で見つけることができます。^[3]^{: 3}

ツリー内の最下位共通祖先の計算

^{RMQは最小共通祖先問題[1]} ^[2]を解決するために使用でき、正確な文字列照合と近似文字列照合の多くのタスクのツールとして使用されます。根付き木 $S$ $= ($ $V$ $,$ $E$ $)$ と2つのノード $v$ $、$ $w$ $\in$ $V$ $のLCAクエリLCA S (v, w)は、ルートから$ $w$ と $vの$ 両方へのパス上の最も深いノード $u$ （ $v$ または $w$ ）を返します。Gabow、Bentley、およびTarjan（1984）は、LCA問題が線形時間でRMQ問題に還元できることを示しました。したがって、RMQ問題と同様に、LCA問題も定数時間と線形空間で解決できます。^[3]

文字列内の最長共通接頭辞を計算する

テキスト索引付けの文脈では、RMQ は LCP (最長共通接頭辞) を見つけるために使用できます。ここで、 $LCP T (i, j)は、$ $T$ 内の索引 $i$ および $j$ で始まる接尾辞の LCP を計算します。これを行うには、まず接尾辞配列 $A$ と逆接尾辞配列 $A$ $-1$ $を計算します。次に、 A$ 内の隣接する接尾辞の LCP を与えるLCP 配列 $H$ を計算します。これらのデータ構造が計算され、RMQ の前処理が完了すると、一般的な LCP の長さは、次の式によって定数時間で計算できます。 $LCP($ $i$ $,$ $j$ $) = RMQ$ $H$ $($ $A$ $-1$ $[$ $i$ $] + 1,$ $A$ $-1$ $[$ $j$ $])ここで、簡単にするために、$ $A$ $-1$ $[$ $i$ $] + 1 <=$ $A$ $-1$ $[$ $j$ $]$ (そうでない場合はスワップ)と仮定します。^[4]

参照

範囲クエリ（データ構造）

参考文献

Berkman, Omer; Vishkin, Uzi (1993). 「再帰的スターツリー並列データ構造」. SIAM Journal on Computing . 22 (2): 221–242. doi :10.1137/0222017. 2017年9月23日時点のオリジナルよりアーカイブ。
Johannes Fischer (2009 年 12 月)。範囲最小クエリの最適な簡潔性(技術レポート)。テュービンゲン大学、バイオインフォマティクスセンター。arXiv : 0812.2775。Bibcode : 2008arXiv0812.2775F。
^[2]

^ abc Bender, Michael A.; Farach-Colton, Martín ; Pemmasani, Giridhar; Skiena, Steven ; Sumazin, Pavel (2005). 「ツリーと有向非巡回グラフにおける最小共通祖先」(PDF) . Journal of Algorithms . 57 (2): 75–94. doi :10.1016/j.jalgor.2005.08.001.
^ abcd Bender, Michael; Farach-Colton, Martín (2000). 「LCA問題の再考」. LATIN 2000: 理論情報学. LATIN 2000: 理論情報学. LNCS. Vol. 1776. Springer. pp. 88–94. doi :10.1007/10719839_9. ISBN 978-3-540-67306-4。
^ ab Fischer, Johannes; Heun, Volker (2007)。「RMQ 情報の新しい簡潔な表現と拡張サフィックス配列の改善」。組合せ論、アルゴリズム、確率論および実験的方法論。組合せ論、アルゴリズム、確率論および実験的方法論に関する国際シンポジウムの議事録。LNCS。第 4614 巻。Springer。pp. 459–470。doi : 10.1007 /978-3-540-74450-4_41。ISBN 978-3-540-74449-8。
^ Fischer, J. および V. Heun (2006)。「RMQ 問題の理論的および実践的改善、LCA および LCE への応用」。組み合わせパターンマッチング。コンピュータサイエンスの講義ノート。第 4009 巻。36 ～ 48 ページ。CiteSeerX 10.1.1.64.5439。doi : 10.1007 / 11780441_5。ISBN 978-3-540-35455-0。

外部リンク

TopCoder の範囲最小クエリに関する記事
PEGWiki / P3G の範囲最小クエリの記事
スタンフォード CS166 RMQ 紹介スライド

[bender-jalg-1] Bender, Michael A.; Farach-Colton, Martín ; Pemmasani, Giridhar; Skiena, Steven ; Sumazin, Pavel (2005). 「ツリーと有向非巡回グラフにおける最小共通祖先」(PDF) . Journal of Algorithms . 57 (2): 75–94. doi :10.1016/j.jalgor.2005.08.001.

[bender-latin-2] Bender, Michael; Farach-Colton, Martín (2000). 「LCA問題の再考」. LATIN 2000: 理論情報学. LATIN 2000: 理論情報学. LNCS. Vol. 1776. Springer. pp. 88–94. doi :10.1007/10719839_9. ISBN 978-3-540-67306-4。

[fischer07-3] Fischer, Johannes; Heun, Volker (2007)。「RMQ 情報の新しい簡潔な表現と拡張サフィックス配列の改善」。組合せ論、アルゴリズム、確率論および実験的方法論。組合せ論、アルゴリズム、確率論および実験的方法論に関する国際シンポジウムの議事録。LNCS。第 4614 巻。Springer。pp. 459–470。doi : 10.1007 /978-3-540-74450-4_41。ISBN 978-3-540-74449-8。

[10.1007/11780441_5-4] Fischer, J. および V. Heun (2006)。「RMQ 問題の理論的および実践的改善、LCA および LCE への応用」。組み合わせパターンマッチング。コンピュータサイエンスの講義ノート。第 4009 巻。36 ～ 48 ページ。CiteSeerX 10.1.1.64.5439。doi : 10.1007 / 11780441_5。ISBN 978-3-540-35455-0。