日本ソフトウェア科学会第 32 回大会 (2015 年度) 講演論文集

最適部分列問題に対する統一的な並列アルゴリズム
森畑 明昌

最適部分列問題は、要素列が与えられたとき、その連続した部分列であって、与えられた条件の下で最適なものを求めるものであり、データベースからの相関ルールの発見、画像処理、DNA の解析など、様々な応用をもつ。広い範囲の最適部分列問題に対して線形時間の逐次アルゴリズムが知られているが、その多くについては効率の良い並列アルゴリズムは知られていない。本稿では、最適部分列問題に対して効率の良い並列アルゴリズムを与えるための一般的なアプローチを示す。骨子は最適部分列問題を saddleback search と呼ばれる問題に帰着することである。このために、まず、saddleback search の効率の良い分割統治並列アルゴリズムを示す。さらに、広い範囲の最適部分列問題を saddleback search に帰着する手法を示す。

Optimal segment problems require us to locate the best consecutive subsequence of a sequence according
to a given criterion of optimality. They have several applications including association-rule mining, image
processing, and DNA analyses. For a large class of them, linear-time sequential algorithms are known;
however, it is largely unknown whether they have eﬃcient parallel algorithms as well. In this paper, we
propose an approach to eﬃcient parallel algorithms for optimal segment problems. Our approach is basedon a reduction from optimal segment problems to saddleback search problems. Our major contributions are
the following two. First, we propose an eﬃcient parallel saddleback search algorithm. Second, we study amethod of reducing a large class of optimal segment problems to saddleback search problems.

る [5, 15, 16, 20, 21]。よく用いられる手法は動的計

1 はじめに画法と windowing であり、これらの手法により広い

最適部分列問題は、要素列が与えられたとき、その範囲の最適部分列問題を効率よく解くことができるこ

連続した部分列であって、与えられた条件の下で最とが知られている。動的計画法 [5,16] は、最適性の原

適なものを求めるものである。最も基本的な問題は理に基づく枝刈りを行いながら、最適解になりうる解

最大和部分列問題であり、Bentley の Programming

候補を列挙する。これに対し、windowing [15, 20, 21]

Pearls [2, 3] で紹介されて有名となった。Bentley は

では、現在の解候補から得られる情報なども用い、よ画像処理に関する問題として紹介しているが、似たり注意深く解候補の延長・短縮を繰り返し、最適解を問題は様々な文脈で現れている。Fukuda ら [9, 10] は得る。一般に、動的計画法は広い範囲の問題に適用でデータベースからの知識発見に最適部分列問題が利用き、系統的な導出も比較的容易だが、問題によってはできることを指摘しており、また、Huan ら [11, 12]

windowing に比べ効率が悪くなる。

は DNA の解析への応用を述べている。

一方、最適部分列問題に対する並列アルゴリズムに

最適部分列問題に対する逐次アルゴリズムについての研究は比較的少ない。最大和部分列問題 [18]

つ い て は 、上 記 の も の を 含 め 、多 く の 研 究 が あや長さ制約つき最大和部分列問題 [14] など、個々の問題を扱った研究はある。また、動的計画法で解くこA Parallel Algorithm for Optimal Segment Problems.
Akimasa Morihata, 東 京 大 学 大 学 院 総 合 文 化 研 究 科,
Graduate School of Arts and Sciences, The University of Tokyo.

とのできる問題に対しての統一的なアプローチも存在する [7, 8, 13]。しかし、著者の知る限り、windowing
でのみ効率の良い解法が知られているクラスの問題

に対する、統一的な並列アルゴリズムは知られてい数に比例する並列速度向上が期待できる。

ない。
本稿では、広い範囲の最適部分列問題、特に Zan-

2 準備

tema [20] や Zhao ら [21] が議論した、windowing に

2. 1 列の操作よる線形時間解法が知られている問題に対して、効率

本稿では、列の操作に以下の記法を用いる。要素の良い並列アルゴリズムを導くための手法を与える。

a0 , . . . , an からなる列を [a0 , . . . , an ] で表す。特に断提案手法の骨子は、前原によって指摘された最適部分

らない限り空列は考えない。列 x および列 y に対し、列問題と saddleback search との相似 [22] に基づき、その連結を x ++ y で表す。列 x の長さを |x| で表す。

最適部分列問題を Bird による分割統治 saddleback

列 x の i 番目から j 番目まで (i ≤ j) の要素からなる

search アルゴリズム [6] に帰着することである。この部分列を x[i : j] で表す。列 x の先頭部分列の集合をアプローチを採るにあたっては 2 点の技術的な問題

inits(x)、末尾部分列の集合を tails(x)、部分列の集を解決しなければならない。まず、Bird のアルゴリ

合を segs(x) で表す。それぞれの定義を以下に示す。

ズムは逐次評価を前提としており、そのまま並列アル

inits(x) = {x[0 : j] | 0 ≤ j ≤ |x| − 1}

ゴリズムとして利用すると効率が悪い。そのため、並

inits(x) = {x[i : |x| − 1] | 0 ≤ i ≤ |x| − 1}

列化に適した分割統治アルゴリズムへの変換が必要

segs(x) = {x[i : j] | 0 ≤ i ≤ j ≤ |x| − 1}である。さらに、少なくない最適部分列問題は直裁には saddleback search に帰着できない。前原はいくつかのケースについて議論を行っているが、を取り扱う

2. 2 リスト準同型と範囲問い合わせための手法を示しているが、その一般性は不明瞭で列に対して値を計算する際には、リスト準同型 [4]あった。しかも、前原の議論は windowing を用いたを用いるのが便利である。リスト準同型は、要素の重逐次アルゴリズムのためのものであり、分割統治並列

み和、列の長さ、最大要素の値や最小要素の値など、アルゴリズムを用いる場合には直接は利用できない。

標準的な計算を表現できる。

以上の問題点を解決するのが本稿の目標である。
本稿の技術的な貢献は以下にまとめられる。以下プ
ロセッサ数を p とする。

• Bird の ア ル ゴ リ ズ ム を 改 良 し 、n × m の二 次 元 配 列 (n ≤ m) に 対 す る saddleback

search を O(n/p log(m/n) + log m) 時 間 で 行

定義 1 リスト準同型 ([⊕, f ]) とは、列に対して以下の等式で定義される関数である。

([⊕, f ])([a])

=

f (a)

([⊕, f ])(x ++ y)=([⊕, f ])(x) ⊕ ([⊕, f ])(y)ここで ⊕ は結合的な演算子である。
リスト準同型は特に並列計算に有用であることがう 並 列 ア ル ゴ リ ズ ム を 与 え る 。こ の 計 算知られている。以下はよく知られた事実である。

量 は p ∈ O(n log(m/n)/ log m) の 範 囲 で は定理 2 列 に 対 す る 関 数 h = g ◦ ([⊕, f ]) を 考 えO(n/p log(m/n)) であり最適である。

る 。g 、f 、⊕ が 定 数 時 間 関 数 で あ る と き 、h(x)、• 最適部分列問題を saddleback search に帰着する手法を示す。さらに、直裁には帰着できない問題に対しても、それが saddleback search に基づ{h(y) | y ∈ inits(x)}、{h(y) | y ∈ tails(x)} はいず
れも O(|x|/p + log p) 時間で並列計算できる。
一般に、与えられた列の部分列に対して何らかのき効率よく解けるための十分条件を与える。

計算を繰り返し行うことを範囲問い合わせ (range

これらの技術を組み合わせることで、広い範囲の最query) [1, 17] と呼ぶ。定理 2 は、先頭部分列や末尾

適部分列問題に対し、p ≪ n の仮定の下で、O(n/p)

部分列に対する範囲問い合わせが効率よく並列計算

時間で解を求める並列アルゴリズムが得られる。よっできることを示している。より一般的な事実として、て、高々定数倍のオーバーヘッドを除けば、この並列

本稿では以下の事実を用いる。なお、詳細は本稿の範

アルゴリズムは逐次アルゴリズムに比べてプロセッサ

囲を超えるためここでは述べない。

定理 3 列 x、列 に 対 す る 関 数 h = g ◦ ([⊕, f ])、多くの場合は演算子 ⊘ から容易に判断できる。このお よ び 問 い 合 わ せ 範 囲 の 集 合 S ⊆ {(i, j) |とき、端的に言えば、各 ϕi の値の増減が、ポジティ

0 ≤ i ≤ j ≤ |x| − 1} が与えられたとする。このとブかネガティブかもふまえれば一貫性を持っていれば′

き、k = ⌊|x|/p⌋ として、局所的な問い合わせ S ⊆ S

ϕ は単調である。

を以下で定義する。

補題 5 関数群 {ϕi | i ∈ I} によって関数 ϕ が定義さ′

S = {(i, j) | (i, j) ∈ S ∧ ⌊i/k⌋ = ⌊j/k⌋}

れているとする。このとき、y ∼ y ′ または y ∼ y ′ な

S ′ に対する問い合わせ結果、すなわち {h(x[i : j]) |る任意の y および y ′ について以下が満たされれば、(i, j) ∈ S ′ } を得るのに要する時間が T (|x|, p) であ

ϕ は単調である。

LR

る と き 、S に 対 す る 問 い 合 わ せ 結 果 {h(x[i : j]) |• あるポジティブな ϕi について ϕi (y) < ϕi (y ′ ) な(i, j) ∈ S} を O(|x|/p + T (|x|, p) + |S \ S ′ | + log p)

らば、全ての ϕj について、ϕj がポジティブなら時間で計算できる。

ϕj (y) ≤ ϕj (y ′ )、ネガティブなら ϕj (y) ≥ ϕj (y ′ )。
• あるネガティブな ϕi について ϕi (y) < ϕi (y ′ ) な

2. 3 単調性

らば、全ての ϕj について、ϕj がポジティブなら我々の議論では、列に対する関数の単調性が重要な

ϕj (y) ≥ ϕj (y ′ )、ネガティブなら ϕj (y) ≤ ϕj (y ′ )。

役割を果たす。本稿では、最適部分列問題での必要性をふまえた、限定的な定義を行う。2 つの列 y およびz について、y ∈ inits(z) ∨ z ∈ inits(y) であるとき、Ly ∼ z と記述する。同様に、y ∈ tails(z)∨z ∈ tails(y)Rであるとき、y ∼ z と記述する。y と z が共に x の部
L

証明 単調性の定義から明らかである。
単調性は、最大の先頭部分列・末尾部分列を効率よく行うための求めるための十分条件でもある。
定理 6 h の値が最大の列を返す関数を maxh と表記する。h が単調のとき、以下の等式が成り立つ。

分列であるとき、y ∼ z は y と z の左端が、y ∼ z はRmaxh ◦ inits = π1 ◦ ([⊗, λx. ([x], [x])])

右端がそれぞれ一致していることを意味する。

maxh ◦ tails = π1 ◦ ([⊕, λx. ([x], [x])])定義 4 関数 ϕ が単調であるとは、以下の性質を共に

where満たすことである。

(ml , l) ⊗ (mr , r) = (maxh {ml ++ r, mr }, l ++ r)L• y ∼ z かつ ϕ(y) ≥ ϕ(z) ならば、ϕ(l ++ y) ≥ϕ(l ++ z)。

(ml , l) ⊕ (mr , r) = (maxh {ml , l ++ mr }, l ++ r)
π1 (a, b) = aR• y ∼ z かつ ϕ(y) ≥ ϕ(z) ならば、ϕ(y ++ r) ≥ϕ(z ++ r)。

3 Saddleback Search

我々はしばしば関数が単調であることを要求する。こまずは、saddleback seach 問題と、それに対するのことの確認は、多くの場合でそれほど難しくない。

Bird の解法を紹介する。以降の議論の簡便のため、

まず、関数 ϕ = g ◦ ([⊕, f ]) を満たす場合、⊕ お

以下では通常議論されるものよりも一般的な問題をよび g が単調であれば ϕ は単調である。例えば、

考える

sum = ([+, id ])・length = ([+, λx. 1])・maximum =定義 7 (Saddleback Search) Saddleback search([max , id ]) などはいずれも単調である。

SS(A, h, p) は 3 つ組である。A は 2 次元配列である。

次 に 関 数 ϕ が 単 調 な 関 数 ϕ1 と ϕ2 を 用 い て

以下、特に断らない限り、A は m × n (n ≤ m) であϕ(x) = ϕ1 (x) ⊘ ϕ2 (x) と表される場合を考える。

るとする。h は評価関数、p は制約条件であり、以下

このような場合、ϕ1 および ϕ2 がポジティブかネの性質を満たす。

ガ ティブ か が 問 題 と な る 。ϕi が ポ ジ ティブ と は 、• i ≤ i′ 、j ≤ j ′ のとき h(A[i][j]) ≤ h(A[i′ ][j ′ ])。

ϕi (x) ≥ ϕi (y) ⇒ ϕ(x) ≥ ϕ(y) を満たすことであ• i ≤ i′ 、j ≤ j ′ のとき p(A[i′ ][j ′ ]) ⇒ p(A[i][j])。

り、ネガティブとは、ϕi (x) ≥ ϕi (y) ⇒ ϕ(x) ≤ ϕ(y)SS(A, h, p) の解はを満たすことである。ポジティブかネガティブかは、

max{h(A[i][j]) | 0 ≤ i < m ∧ 0 ≤ j < n ∧ p(A[i][j])}以下ではコスト最適な並列アルゴリズムを示す。逐次

図1

2

4

7

8

9

16

25

3

6

10

13

15

18

26

5

9

13

14

16

22

27

6

10

17

19

22

24

30

7

15

20

25

28

33

34

9

16

24

27

31

34

40

分割統治 saddleback search アルゴリズムの概要

での時間計算量が f (n)、並列アルゴリズムの時間計
算量が O(f (n)/p) であるとき、これをコスト最適であるという。以下では、説明の簡単のため、n およびm は p + 1 で割り切れるとする。
1. m/(p + 1), . . . , pm/(p + 1) 行目のそれぞれについて、p を満たし h が最大となる要素 e1 , . . . , ep
を二分探索で発見する。

2. n/(p + 1), . . . , pn/(p + 1) 列目のそれぞれにつすなわち p(A[i][j]) を満たす範囲での h(A[i][j]) の最

いて、p を満たし h が最大となる要素 e′1 , . . . , e′p

大値である。

を二分探索で発見する。

一般的な saddleback search では、二次元配列中から特定の値 c があるかどうかを調べる。この場合、h は恒等関数、p は値 c 以下かどうかを判定する述語ととればよい。

3. e1 , . . . , ep および e′1 , . . . , e′p を、その行をもとに整列し、e∗1 , . . . , e∗2p とする。

4. 各 i について e∗i から e∗i+1 までの矩形領域の最適値を求め、vi+1 とする。また、これに加え、

A[0][m − 1] から e∗0 まで、e∗2p から A[n − 1][0]3. 1 Saddleback search に対する分割統治並列
アルゴリズムまでの矩形領域の最適値を求め、それぞれ v0 ・

v2p+2 とする。

Saddleback search に対しては、O(n + m) 時間の

5. v0 , . . . , v2p+2 のうち最大のものが最適値である。

古典的な解法がよく知られている。Bird [6] は、この定理 8 SS(A, h, p) は、h および p が定数時間であれ問題に対する O(n log(m/n)) 時間の解法を示した。

ば、O(n/p log(m/n) + log m) 時間で実行できる。た

これを以下に示す。

だし n ≥ p とする。

1. j = ⌊m/2⌋ 列目で、p を満たし h が最大となる
要素 e∗ を二分探索で発見する。

証明 手順 (1) および手順 (2) は、それぞれの二分探索を並列に行うことで、それぞれ O(log n) 時間、

2. e∗ が i 行 目 の 要 素 だ と す る 。こ の と き 、O(log m) 時間で実現できる。手順 (3) は、e1 , . . . , ep

A[0][m − 1] から A[i + 1][j − 1] までの矩形領および e′1 , . . . , e′p がそれぞれ整列されていること、ま域、及び A[i][j + 1] から A[n − 1][0] までの矩形

た e1 , . . . , ep の行番号が既知であることをふまえる

領域、の両者の最適値を求める (v1 および v2 とと、e′1 , . . . , e′p の行番号からバケツソートの要領でする) 。

O(log p) で整列が可能である。手順 (4) で扱うのは、

3. h(e)、v1 、v2 のうち最大のものが最適値である。

高々n/(p + 1) + 1 行 m/(p + 1) + 1 の矩形領域 2p + 2

図 1 に概要を示す。図に示した 6 × 7 の配列が与え個であり、それぞれを並列に逐次アルゴリムで処理すられており、値 20 を発見したいとする。まず、j = 3

れば O(n/p + log(m/n)) 時間で扱うことができる。

列目の要素で 20 より小さく最大の要素を発見する。

手順 (5) は標準的な並列アルゴリズムにより O(log p)

この場合は i = 3 列目の 19 である。このとき、19 の時間で十分である。

左下ないし右上の、破線で囲まれた 2 領域が解がある可能性のある領域であり、再帰的に探索される。

Bird のアルゴリズムは逐次アルゴリズムとしては高速である。しかし、分割統治で得られる 2 つの矩形

4 最適部分列問題の saddleback search への帰着
本節では、最適部分列問題について議論する。まず領域の大きさが必ずしも均等ではないため、そのまま

は最適部分列問題を定義する。

並列アルゴリズムとして実行すると効率が良くない。

定義 9 最適部分列問題 OSP(x, h, p) は 3 つ組である。x は要素列である。特に断らない限り、この長さ定理 13 最適部分列問題 OSP(x, h, p) が以下の条件

を n とする。h は評価関数である。p は制約条件であを満たすとする。

る。OSP(x, h, p) の解は• h = ρ1 ◦ ([⊕, f ]) は longer-better

max{h(x[i : j]) | 0 ≤ i ≤ j < n ∧ p(x[i : j])}• p = ρ2 ◦ ([⊗, g]) は segment-closedすなわち p(x[i : j]) を満たす範囲での h(x[i : j]) の最• ρ1 、ρ2 、⊕、⊗、f 、g は定数時間で評価可能
このとき、OSP(x, h, p) の解を O(T (n/p) + log n)大値である。
それでは、前原 [22] の述べた関係に従い、最適部分列

時間で発見できる。ここで T (m) は長さ m の列 y に問題 OSP(x, h, p) を saddleback search SS(A, h, p)

対して 1 プロセッサで最適部分列問題 OSP(y, h, p)に帰着する基本的な戦略は、x[i : j] を A[i][j] に対応の解を求めるのに要する時間であり、T (m) ≥ m とさせることである。この対応の元で、h や p が sad-する。

dleback search に要求される要件を満たすためには証明 (概略) 定理 12 により並列 saddleback search

以下の条件が成り立つ必要がある。

に帰着する。定理 3 より、各部分列に対する h や p

定義 10 列に対する評価関数 h が longer-better であの計算を O(1) 時間で実行できる。そのため、行・列

るとは、以下を満たすことである。

に対する二分探索は O(log n) 時間で処理できる。

∀x, y, z : h(x) ≤ h(y ++x++ z)
定義 11 列に対する制約条件 p が segment-closed で

5 Longer-better でない、または segmentclosed でない問題の取り扱いあるとは、以下を満たすことである。

∀x, y, z : p(y ++x++ z) ⇒ p(x)前節では最適部分列問題が saddleback search に

最 適 部 分 列 問 題 OSP(x, h, p) は 、h が longer-

帰着できることを述べた。最も重要な要請は、目的

better かつ p が segment-closed であれば、saddle-

関数が longer-better であること、および制約条件がback search に帰着できる。

segment-closed であることである。しかし、既存研′定理 12 最適部分列問題 OSP(x, h, p) に対し、A・h ・′

究で議論されている問題の多くはいずれかの性質を

p を以下の通り定義する。ただし h は longer-better、

満たさない。以下に例を 2 つ述べる。

p は segment-closed であるとする。

例 14 長さ制約付き最大重み和問題 [12, 14, 15] は、• 任意の 0 ≤ i ≤ j < n に対し、A[i][j] = x[i : j]。

特定の長さ以下の部分列の中で重み和が最大となるもまた、j < i に対し、A[i][j] = ⊥。ここで ⊥ は xのを求める問題である。この問題は、segment-closedの部分列とは区別できる特別な値である。

ではあるが longer-better ではない。目的関数 sum は、′′• h (⊥) = −∞ かつ y ̸= ⊥ のとき h (y) = h(y)。

例えば sum([3]) = 3 ̸≤ sum([3, −2]) = 1 である。

• p′ (⊥) = True かつ y ̸= ⊥ のとき p′ (y) = p(y)。

例 15 Leftmost at most rightmost 問題 [20, 21] は、

このとき、SS(A, h′ , p′ ) は saddleback search であり、左端の要素が右端の要素以下である部分列の中で最その解は、OSP(x, h, p) に解があればそれと一致す

長のものを求める問題である。この問題は、longer-

る。なお、後者に実行可能解がなければ、前者の解はbetter であるが segment-closed ではない。[−1, 2, 1]−∞ である。

は条件を満たすが、この部分列である [2, 1] は条件を証明 自明。

満たさない。

しかし、saddleback search に帰着するだけでは不この問題に対し、前原 [22] は、windowing 技法に十分である。帰着先での評価関数や制約条件は列を入基づき、最適解があり得る領域を詳細に解析しながら力とするため、これを単純に評価すると、各要素につ部分列を延長・短縮する方法を述べ、それが最適解をいての計算に列長に比例する時間がかかってしまう。

効率よく発見するための十分条件を示した。しかし、

しかし、リスト準同型で定義される評価関数・制約条

前原の議論は以下の欠点があった。

件については、定理 3 を用いてこれを改善できる。

• 彼の議論は windowing に基づいており、分割統治法を用いる場合にはそのまま適用できない。

らば ϕ(l′ ++y++ r′ ) ≤ ϕ(l′′ ++y++ r′′ ) が満たされる• 彼は重み和問題の場合と segment-closed でないため、この判定には l の末尾部分列、r の先頭部分列

場合は考えたが、一般に longer-better でない場の中で ϕ 値が最小となるものを求めれば良い。定理

合は議論していない。

3 および定理 6 より、ϕ がリスト準同型で実装されて本節では、より一般的でより使いやすい条件を与える

いる場合、これは O(n/p + log p) 時間の前処理を行ことを目指す。

えば、それぞれ O(1) 時間で得ることができる。
例 16 Leftmost at most rightmost 問題を考える。制5. 1 Segment-closed でない場合

約 p は、列の左端の要素を返す関数 left と右端の要素をまず、制約条件 p は segment-closed ではないが、返す関数 right を用いて、p(y) = left(y) − right(y) ≤目的関数 h は longer-better である最適部分列問題

0 と記述できる。left と right はリスト準同型で定義

OSP(x, h, p) について考える。

でき、かつ単調である。しかも補題 5 が適用できる。

実は、3 節で述べた分割統治 saddleback search ア

なぜなら、y ∼ y ′ なら right(y) = right(y ′ ) であり、ルゴリズムは、より弱い条件下でも利用することがy ∼ y ′ なら left(y) = left(y ′ ) であるためである。よっできる。このアルゴリズムの本質は、二分探索によって、left(y) − right(y) は単調であり、提案手法が適用て、その右下、およびその左上の矩形領域には最適解できる。このとき、オラクルは「右方にある最大の値が存在しないことが保証できることである。このことが左方にある最小の値より大きい」ことを確認する。

L

R

から、以下の条件が満たされるなら、分割統治アルゴ

5. 2 Longer-better でない場合

リズムは利用できる。
添え字 i および j に対し、p(A[i′ ][j ′ ]) が成り′次に、目的関数が longer-better でない最適部分′

立つ i ≤ i、j ≤ j が存在するか否かを判定

列問題 OSP(x, h, p) について考える。ただし p はするオラクルが存在する。

segment-closed であるとする。このとき、以下の戦

このとき、「p を満たし h が最大となる要素」ではな
′

′

′

′

略に基づいて最適解を発見する。

く「p(A[i ][j ]) が成り立つ i ≤ i、j ≤ j が存在する

1. h が longer-better である場合のアルゴリズム

中で h が最大となる要素」を発見する。このとき、こを用いて、各要素に対し、その要素から始まる最の要素の右下の矩形領域は制約条件を満たす解はな

適な部分列を発見する。

い。さらに、この要素の真下または真右には制約条件を満たす要素 (仮に e とする) があり、それゆえ左上

2. その最適な部分列の先頭部分列で h の値が最大となるものを発見する。

領域の要素は e より目的関数値が小さいため考える戦略の要旨は p を満たす部分列の発見と h の値の最必要が無い。以上のことから、分割統治アルゴリズム

大化を別々に扱うことである。まず、第 1 ステップでの正しさが保証される。これを最適部分列問題に翻訳は、どの長さの部分列まで p を満たすのかを調べる。

すれば、リスト x 中の y (x = l ++y++ r) に対し、

次に、第 2 ステップでは、それより短い列の中で h の

′

′

′

′

∃l ∈ inits(l), r ∈ tails(r). p(l +
+y+
+r )

値を最大化する。

を効率よく判定できれば良い、となる。これは一般に第 1 ステップは今まで述べたとおり、効率よく計算は難しいため、効率的な評価のための十分条件が求めできる。しかも、前小節の議論と同様にして、h が単られる。

調性を満たしリスト準同型で実装されている場合、定

既存で議論されてきた多くの問題において、制約

理 3 と定理 6 より、これは O(n/p + log p) 時間の前

条件 p は p(y) = ϕ(y) ≤ C の形で表現される。この処理を行えば、各部分列に対する先頭部分列を O(1)とき、上記条件は、y を含む部分列に対する ϕ の値のならし時間で得ることができる。

の最小値が C 以上であるか否かの確認となる。ϕ が例 17 長さ制約付き最大和部分列問題を考える。目

単調であるとき ϕ(l′ ) ≤ ϕ(l′′ ) かつ ϕ(r ′ ) ≤ ϕ(r ′′ ) な的関数 sum は単調であるため、上記アルゴリズムを利用できる。この場合、長さが長さ制約 k に等しい

題は入力が多次元配列であれば最適部分超立方体問

各部分リストに対して、最大和となる部分リストを求

題へと自然に拡張できる。最も単純な問題である最大めることになる。

和部分超立方体問題については、Wen [19] が効率の良い並列アルゴリズムを与えている。本稿の議論と5. 3 Longer-better でも segment-closed でもない場合

Longer-better でも segment-closed でもない問題を

Wen の手法を組み合わせることで、より高次元の問題に対して並列アルゴリズムを与えることができるかどうかは、今後の課題である。

上述の手法で扱うのは困難である。例えば、前小節で謝辞 本研究は日本学術振興会学術研究助成基金助は、条件を満たす最長の部分列に対し、目的関数値が成金 (若手研究 (B) 15K15965) の助成を受けている．

最大となる部分列を求めたが、条件が segment-closed
でない場合、一般にはこうやって求めた部分列が制約

参 考 文 献条件を満たすとは限らない。この点についてのさらな[ 1 ] Agarwal, P. K. and Erickson, J.: Geometric Range Searching and Its Relatives, Advancesin Discrete and Computational Geometry: Proceedings of the 1996 AMS-IMS-SIAM Joint Summer Research Conference, Discrete and Computational Geometry–Ten Years Later, July 14-18,
1996, Mount Holyoke College, Chazelle, B., Goodman, J. E., and Pollack, R.(eds.), Contemporary
Mathematics, Vol. 223, American Mathematical Society, 1999, pp. 1–56.
[ 2 ] Bentley, J. L.: Algorithm Design Techniques,
Commun. ACM, Vol. 27, No. 9(1984), pp. 865–871.
[ 3 ] Bentley, J. L.: Perspective on Performance,
Commun. ACM, Vol. 27, No. 11(1984), pp. 1087–
1092.
[ 4 ] Bird, R. S.: An Introduction to the Theory of
Lists, Logic of Programming and Calculi of Discrete
Design, Broy, M.(ed.), NATO ASI Series F, Vol. 36,
Springer-Verlag, New York, NY, USA, 1987, pp. 3–
42. Technical Monograph PRG-56.
[ 5 ] Bird, R. S.: Maximum marking problems,
Journal of Functional Programming, Vol. 11,
No. 4(2001), pp. 411–424.
[ 6 ] Bird, R. S.: Improving Saddleback Search:
A Lesson in Algorithm Design, Mathematics ofProgram Construction, 8th International Conference, MPC 2006, Kuressaare, Estonia, July 3-5,
2006, Proceedings, Uustalu, T.(ed.), Lecture Notes
in Computer Science, Vol. 4014, Springer, 2006,
pp. 82–89.
[ 7 ] Emoto, K., Fischer, S., and Hu, Z.: Filterembedding semiring fusion for programming with
MapReduce, Formal Asp. Comput., Vol. 24, No. 46(2012), pp. 623–645.
[ 8 ] Emoto, K., Hu, Z., Kakehi, K., Matsuzaki, K.,
and Takeichi, M.: Generators-of-Generators Librarywith Optimization Capabilities in Fortress, EuroPar 2010 - Parallel Processing, 16th International
Euro-Par Conference, Ischia, Italy, August 31 September 3, 2010, Proceedings, Part II, D’Ambra,
P., Guarracino, M. R., and Talia, D.(eds.), Lecture
Notes in Computer Science, Vol. 6272, Springer,

る探求は今後の課題である。

6 まとめと今後の課題
本稿では、最適部分列問題に対する効率的な並列アルゴリズムについて議論した。このアルゴリズムはBird の分割統治 saddleback search を基礎としている。さらに、単調性に基づき、直裁には saddleback

search に帰着できない問題の取り扱いについても議論をした。このアルゴリズムは、最長部分列問題、最大和部分列問題に限らず、広い範囲の部分列問題に対して適用できる。

4 節で述べた saddleback search への帰着は基本的に前原 [22] の結果である。さらに、5 節で議論した十分条件は、細部において多少の違いはあるものの、前原のものに非常に近いものとなっている。そのため、本稿の結果は前原の議論が並列アルゴリズムの導出
へと拡張できることを示したと言える。このことは、この議論が windowing 技法に限るものではなく、より広く最適部分問題の構造を捉えている可能性があるこことを示唆している。
本稿のアルゴリズムを与える上では、範囲問い合わ
せの効率的な手法が肝となっている。範囲問い合わせの逐次アルゴリズムについては非常に多くの研究があるが、並列アルゴリズムについての研究は少ない。
より広い範囲の最適部分列問題に対する解法を与える上では、範囲問い合わせの並列アルゴリズムを発展させることが不可欠だと言える。
また、本稿では最適部分列問題を考えたが、この問2010, pp. 26–37.
[ 9 ] Fukuda, T., Morimoto, Y., Morishita, S., andTokuyama, T.: Mining Optimized Association
Rules for Numeric Attributes, J. Comput. Syst.
Sci., Vol. 58, No. 1(1999), pp. 1–12.
[10] Fukuda, T., Morimoto, Y., Morishita, S.,
and Tokuyama, T.: Data Mining with optimized
two-dimensional association rules, ACM Trans.
Database Syst., Vol. 26, No. 2(2001), pp. 179–213.
[11] Huang, X.: An algorithm for identifying regionsof a DNA sequence that satisfy a content requirement, Comput. Appl. Biosci., Vol. 10, No. 3(1994),
pp. 219–225.
[12] Lin, Y.-L., Jiang, T., and Chao, K.-M.: Eﬃcient algorithms for locating the length-constrained
heaviest segments with applications to biomolecularsequence analysis, J. Comput. Syst. Sci., Vol. 65,
No. 3(2002), pp. 570–586.
[13] Matsuzaki, K., Hu, Z., and Takeichi, M.: Derivation of Parallel Programs for Maximum Marking
Problems on Lists, IPSJ Transaction of Programming, Vol. 49(2008), pp. 16–27. In Japanese.
[14] Morihata, A.:
Calculational Developmentsof New Parallel Algorithms for Size-Constrained
Maximum-Sum Segment Problems, Functional and
Logic Programming - 11th International Symposium, FLOPS 2012, Kobe, Japan, May 2325, 2012. Proceedings, Schrijvers, T. and Thiemann, P.(eds.), Lecture Notes in Computer Science,Vol. 7294, Springer, 2012, pp. 213–227.
[15] Mu, S.-C.: Maximum segment sum is back: deriving algorithms for two segment problems withbounded lengths, Proceedings of the 2008 ACM
SIGPLAN Symposium on Partial Evaluation and
Semantics-based Program Manipulation, PEPM

2008, San Francisco, California, USA, January 78, 2008, Glück, R. and de Moor, O.(eds.), ACM,
2008, pp. 31–39.
[16] Sasano, I., Hu, Z., Takeichi, M., and Ogawa, M.:
Make it practical: a generic linear-time algorithm
for solving maximum-weightsum problems, Proceedings of the 5th ACM SIGPLAN International
Conference on Functional Programming, ICFP’00,
ACM, 2000, pp. 137–149.
[17] Skala, M.: Array Range Queries, Space-Eﬃcient
Data Structures, Streams, and Algorithms - Papers
in Honor of J. Ian Munro on the Occasion of His
66th Birthday, Brodnik, A., López-Ortiz, A., Raman, V., and Viola, A.(eds.), Lecture Notes in Computer Science, Vol. 8066, Springer, 2013, pp. 333–
350.
[18] Smith, D. R.: Applications of a Strategy for Designing Divide-and-Conquer Algorithms, Sci. Comput. Program., Vol. 8, No. 3(1987), pp. 213–229.
[19] Wen, Z.: Fast Parallel Algorithms for the Maximum Sum Problem, Parallel Computing, Vol. 21,
No. 3(1995), pp. 461–466.
[20] Zantema, H.:
Longest Segment Problems,
Science of Computer Programming, Vol. 18,
No. 1(1992), pp. 39–66.
[21] Zhao, H., Hu, Z., and Takeichi, M.: A Compositional Framework for Mining Longest Ranges, Discovery Science, 5th International Conference, DS
2002, Lübeck, Germany, November 24-26, 2002,
Proceedings, Lange, S., Satoh, K., and Smith,
C. H.(eds.), Lecture Notes in Computer Science,Vol. 2534, Springer, 2002, pp. 406–413.
[22] 前原貴憲: プログラム運算による Windowing 技法の定式化とその応用, 卒業論文. 東京大学工学部. 2007.