第14章
最後の接尾辞
（やさしい版）
Pearls of Functional Algorithm Design（関数プログラミングによるアルゴリズム設計の真珠）
どんな問題？
ある文字列（あるいはリスト）に対して、そのすべての接尾辞（tail、うしろ側の部分）を辞書順に並べたとき、いちばん最後に来る接尾辞は何かを求める問題です。
いくつか例を見てみましょう。
- “introduction” の接尾辞をすべて辞書順に並べると、最後は “uction” になります（“u” で始まるものが一番後ろに来るから）。
- “tomato” の接尾辞では、意外にも “tomato” そのものが最後になります。理由は、“to” と “tomato” を比べたとき、辞書順では短い “to” の方が先に来る（=“tomato” の方が後）からです。
この章のゴール
この問題を線形時間 Θ(n) で解くアルゴリズムを組み立てます。以前の章（第12章）で接尾辞の順位付けを Θ(n log n) で解いていましたが、それを一段速くします。ただし、こんなに単純な問題なのに、導出はかなり込み入っていて長くなります。覚悟してください。
帰納的定義を目指す
基本のアイデア
やりたいことは、次の関数 maxtail を計算することです。
maxtail :: Ord a ⇒ [a] → [a]
maxtail = maximum · tails
Dart
// 素朴版: すべての接尾辞を作って辞書順で最大のものを返す（Θ(n^2) 最悪）
List<T> maxtailNaive<T extends Comparable<T>>(List<T> xs) {
List<List<T>> tails(List<T> xs) =>
[for (var i = 0; i <= xs.length; i++) xs.sublist(i)];
int cmpList(List<T> a, List<T> b) {
final n = a.length < b.length ? a.length : b.length;
for (var i = 0; i < n; i++) {
final c = a[i].compareTo(b[i]);
if (c != 0) return c;
}
return a.length.compareTo(b.length);
}
final ts = tails(xs);
return ts.reduce((m, t) => cmpList(t, m) > 0 ? t : m);
}
tails: リストのすべての接尾辞（空の接尾辞も含む）を並べる関数。maximum: そのうち辞書順で最大のものを返す。
そのまま実行すると、最悪ケースで二乗時間かかります。たとえば同じ文字を n 個並べただけの入力でも遅くなってしまいます。
作戦：1文字ずつ足すときの関係を作る
長さ n の答えから、長さ n+1 の答えを作る方法（=帰納的定義）を目指します。ただし「先頭に足す」やり方だとうまくいきません。たとえば “zebra” の最大接尾辞は “zebra” そのものですが、これを “z” と “ebra” の答え（“ra”）から作ることはできないからです。
そこで、末尾に1文字 x を足す方向で、次のような関数 op を探します。
maxtail (xs ⧺ [x]) = op (maxtail xs) x -- (14.1)
言いかえると、maxtail = foldl op [ ] になる op です。
op はどんな形になる？
細かい議論を追うと、次のことが分かります。
重要な観察
ys = maxtail xs、zs ⧺ [x] を maxtail (xs ⧺ [x]) とすると、zs は ys の「接頭辞」であり「接尾辞」でもある。
この観察から、op は次の2通りに書けます。
op ys x = maximum [zs ⧺ [x] | zs ← tails ys]
op ys x = maximum [zs ⧺ [x] | zs ← tails ys, zs ⊑ ys] -- (14.2)
Dart
// 1 番目: ys のすべての tails に [x] を継ぎ足して、辞書順で最大のものを返す。
// 2 番目: さらに zs が ys の接頭辞（zs ⊑ ys）であるものだけに絞る。
List<T> opViaTails<T extends Comparable<T>>(
List<T> ys, T x, {bool prefixFilter = false}) {
int cmpList(List<T> a, List<T> b) {
final n = a.length < b.length ? a.length : b.length;
for (var i = 0; i < n; i++) {
final c = a[i].compareTo(b[i]);
if (c != 0) return c;
}
return a.length.compareTo(b.length);
}
bool isPrefix(List<T> p, List<T> s) {
if (p.length > s.length) return false;
for (var i = 0; i < p.length; i++) {
if (p[i] != s[i]) return false;
}
return true;
}
final cands = [
for (var i = 0; i <= ys.length; i++)
if (!prefixFilter || isPrefix(ys.sublist(i), ys)) [...ys.sublist(i), x]
];
return cands.reduce((m, t) => cmpList(t, m) > 0 ? t : m);
}
2番目の方が構造がリッチなので、こちらを深掘りします。
borders：接頭辞かつ接尾辞のリスト
borders とは
あるリスト xs の borders とは、xs の接頭辞にもなっている接尾辞のことです。文字列アルゴリズム論（ストリンゴロジー）ではおなじみの概念です（Crochemore and Rytter, 2003）。
borders "7412741274" = ["7412741274", "741274", "74", ""]
borders "mammam" = ["mammam", "mam", "m", ""]
これは次のように再帰的にも書けます。
borders [ ] = [[ ]]
borders xs = xs : borders (border xs)
Dart
// borders: xs の「接頭辞かつ接尾辞」を長い順に列挙。
// border は「xs 自身を除いた最長の接頭辞かつ接尾辞」を返す仮想関数
// （素朴実装: 前から順に該当する接尾辞を探す）。
List<T> borderNaive<T>(List<T> xs) {
for (var k = 1; k < xs.length; k++) {
final suf = xs.sublist(k);
var ok = true;
for (var i = 0; i < suf.length; i++) {
if (xs[i] != suf[i]) { ok = false; break; }
}
if (ok) return suf;
}
return <T>[];
}
List<List<T>> borders<T>(List<T> xs) {
if (xs.isEmpty) return [<T>[]];
return [xs, ...borders(borderNaive(xs))];
}
ここで border xs は、xs 自身は除いた「最長の共通接頭辞かつ接尾辞」です。tails と同じ形をしていることに注目してください。
tails [ ] = [[ ]]
tails xs = xs : tails (tail xs)
Dart
// tails: xs のすべての接尾辞を長い順に列挙。
List<List<T>> tails<T>(List<T> xs) {
if (xs.isEmpty) return [<T>[]];
return [xs, ...tails(xs.sublist(1))];
}
borders を使うと (14.2) は次のようになります。
op ys x = maximum [zs ⧺ [x] | zs ← borders ys]
Dart
// borders ys の各要素 zs に対し zs ++ [x] を作り、辞書順で最大のものを返す。
List<T> opViaBorders<T extends Comparable<T>>(List<T> ys, T x) {
int cmpList(List<T> a, List<T> b) {
final n = a.length < b.length ? a.length : b.length;
for (var i = 0; i < n; i++) {
final c = a[i].compareTo(b[i]);
if (c != 0) return c;
}
return a.length.compareTo(b.length);
}
final cands = [for (final zs in borders(ys)) [...zs, x]];
return cands.reduce((m, t) => cmpList(t, m) > 0 ? t : m);
}
2つのカギとなる不等式
borders ys = [zs0, zs1, …, zsn] と並べます（大きい順で zs0 = ys、zsn = 空）。ここで us ↓ vs（“us after vs”）を「us のうち末尾の vs を取り除いた前半分」と定義します。すると次が示せます。
式(14.4)
0 ≤ i < j ≤ n について、
zsi ⧺ [x] ≥ zsj ⧺ [x] ≡ head (zsi ↓ zsj) ≥ x
すなわち「短い方に [x] を継ぎ足したものが勝つかどうか」は 先頭文字と x の比較で決まる。
式(14.5)
ys がすでに最大接尾辞のときは、head (zsi−1 ↓ zsi) が i について単調非減少である。
この2つを組み合わせると、次のシンプルな探索で op が計算できます。
op ys x | null ys = [x]
| head (ys ↓ zs) ≥ x = ys ⧺ [x]
| otherwise = op zs x
where zs = border ys
Dart
// ys ↓ zs = ys のうち末尾 zs を取り除いた前半分。
// head(ys ↓ zs) は「ys の先頭から (|ys|-|zs|) 番目までの最初の文字」= ys[0]。
// ただし border を辿って zs を短くしていく再帰では、head(ys ↓ zs) = ys[|ys|-|zs|-1] ではなく
// 「ys ↓ zs」の先頭、すなわち ys[0] を毎回見るのではないことに注意（詳細は本文参照）。
List<T> opGuarded<T extends Comparable<T>>(List<T> ys, T x) {
if (ys.isEmpty) return [x];
final zs = borderNaive(ys);
// us ↓ vs = us から先頭の vs を取り除いた残り。
// head(ys ↓ zs) は ys の |zs| 番目の文字。
final h = ys[zs.length];
if (h.compareTo(x) >= 0) return [...ys, x];
return opGuarded(zs, x);
}
これで op は書けました。あとは border の再帰的定義が必要です。
border の再帰的定義
末尾に1文字足したときの border
接頭辞順序に関して次が成り立ちます。
zs ⧺ [x] ⊑ ys ⧺ [x] ≡ zs ⊑ ys ∧ (zs ≠ ys ⇒ x = head (ys ↓ zs))
これを使って計算すると、次の再帰的定義が得られます。
border (ys ⧺ [x]) | head (ys ↓ zs) == x = zs ⧺ [x]
| otherwise = border (zs ⧺ [x])
where zs = border ys
Dart
// border(ys ++ [x]) を再帰式に沿って計算する。
// ys の border を zs として、ys ↓ zs の先頭（= ys[0]）と x を比較。
// 一致すれば zs ++ [x] が答え。
// さもなければ zs ++ [x] に対して再帰。
List<T> borderRec<T>(List<T> ysWithX) {
if (ysWithX.length <= 1) return <T>[];
final ys = ysWithX.sublist(0, ysWithX.length - 1);
final x = ysWithX.last;
final zs = borderRec([...ys]); // border(ys) を再帰計算
// head(ys ↓ zs) は ys の |zs| 番目の文字
if (ys[zs.length] == x) return [...zs, x];
return borderRec([...zs, x]);
}
maxtail の仮定のもとでの最適化
もし ys = maxtail xs という仮定があれば、(14.5) を使って探索を3分岐に絞れます。
border (ys ⧺ [x]) | head (ys ↓ zs) < x = border (zs ⧺ [x])
| head (ys ↓ zs) == x = zs ⧺ [x]
| head (ys ↓ zs) > x = [ ]
where zs = border ys
Dart
// ys が maxtail の場合、head(ys ↓ zs) が単調非減少という性質から
// 3 分岐で border を決められる。
List<T> borderOpt<T extends Comparable<T>>(List<T> ysWithX) {
if (ysWithX.length <= 1) return <T>[];
final ys = ysWithX.sublist(0, ysWithX.length - 1);
final x = ysWithX.last;
final zs = borderOpt([...ys]);
final h = ys[zs.length]; // head(ys ↓ zs) = ys[|zs|]
final c = h.compareTo(x);
if (c < 0) return borderOpt([...zs, x]);
if (c == 0) return [...zs, x];
return <T>[];
}
ポイント
maxtail と border の再帰式が似た形になっています。次のステップとして、この2つを1つの関数にまとめます。
cocktail：2つを混ぜて1つに
定義
cocktail（材料2つを混ぜた1杯!）は次のように定義します。
cocktail xs = if null xs then ([ ], [ ]) else
(border (maxtail xs), maxtail xs ↓ border (maxtail xs))
Dart
// cocktail(xs) = (zs, ws) where zs = border(maxtail(xs)), ws は残り部分。
// maxtail = zs ++ ws を満たす。
(List<T>, List<T>) cocktailSpec<T extends Comparable<T>>(List<T> xs) {
if (xs.isEmpty) return (<T>[], <T>[]);
final ys = maxtailNaive(xs);
final zs = borderNaive(ys);
// ws = ys ↓ zs は「ys から先頭の zs を取り除いた残り」。zs ++ ws = ys。
final ws = ys.sublist(zs.length);
return (zs, ws);
}
つまり cocktail xs は組 (zs, ws) を返し、zs = border (maxtail xs)、ws はその残り部分です。すると maxtail = uncurry (⧺) · cocktail です。
末尾に1文字足したときの場合分け
cocktail xs = (zs, ws) として、末尾に x を足したときの (zs′, ws′) = cocktail (xs ⧺ [x]) を計算します。ws の先頭 w と x の大小で場合分けします。
- ws = [ ]: 空リストの拡張。結果は ([ ], [x])。
- w < x: x の方が大きい。maxtail が短くなるので、cocktail (zs ⧺ [x]) に帰着。
- w = x: 一致。両方に x を継ぎ足せる。結果は (zs ⧺ [x], tail ws ⧺ [x])。
- w > x: w の方が大きい。境界（border）は空になる。結果は ([ ], zs ⧺ ws ⧺ [x])。
まとめると次のプログラムになります。
maxtail = uncurry (⧺) · cocktail
cocktail = foldl op ([ ], [ ])
op (zs, ws) x | null ws = ([ ], [x])
| w < x = cocktail (zs ⧺ [x])
| w == x = (zs ⧺ [x], tail ws ⧺ [x])
| w > x = ([ ], zs ⧺ ws ⧺ [x])
where w = head ws
Dart
// (zs, ws) を状態として左畳み込みで cocktail を計算する（まだ O(n^2)）。
(List<T>, List<T>) cocktailFold<T extends Comparable<T>>(List<T> xs) {
(List<T>, List<T>) op((List<T>, List<T>) st, T x) {
final (zs, ws) = st;
if (ws.isEmpty) return ([x], [x]); // 空リストの拡張
final w = ws[0];
final c = w.compareTo(x);
if (c < 0) return cocktailFold([...zs, x]); // 再帰: 短くなった候補で再スタート
if (c == 0) return ([...zs, x], [...ws.sublist(1), x]);
return (<T>[], [...zs, ...ws, x]);
}
var state = (<T>[], <T>[]);
for (final x in xs) state = op(state, x);
return state;
}
List<T> maxtailFold<T extends Comparable<T>>(List<T> xs) {
final (zs, ws) = cocktailFold(xs);
return [...zs, ...ws];
}
でもまだ遅い
ここまで来ても、これは
二乗時間です。理由は2つあります。
- (⧺) が定数時間ではない。
- 仮に定数時間だとしても、入力 1n2（1 が n 個続いた後 2）に対して、cocktail (zs ⧺ [x]) の呼び出しが再帰的に何度も走ってしまう。
問題サイズを半分に絞る
zs の長さを制限したい
問題は cocktail (zs ⧺ [x]) の呼び出しにあります。もし zs の長さを現在の最大接尾辞 ys = zs ⧺ ws の長さの半分以下に抑えられれば、線形時間になります（「線形時間かけて問題を半分に縮小」できれば全体でも線形時間になる、というよくある話です）。
キーとなる観察
|zs| ≥ |ws| の場合、ws は zs の接尾辞にもなっています。たとえば ys = “7412741274” では zs = “741274”、ws = “1274” で、確かに ws は zs の末尾です。
ここで q, r を次で定義します。
(q, r) = (|zs| div |ws|, |zs| mod |ws|)
zs′ = take r zs とすると、zs′ もまた ys の border になり、zs = zs′ ⧺ wsq（ws を q 回繰り返し）と分解できます。しかも zs′ = drop (|ws| − r) ws と ws の一部から取り出せます。
重要
途中の border（zs′ ⧺ wsp, 1 ≤ p < q）は、head ws < x の場合には調べる必要がない。全部飛ばして zs′ に直接ジャンプできます。
これで op を次のように改良できます。
op (zs, ws) x | null ws = ([ ], [x])
| w < x = cocktail (take r zs ⧺ [x])
| w == x = (zs ⧺ [x], tail ws ⧺ [x])
| w > x = ([ ], zs ⧺ ws ⧺ [x])
where w = head ws
r = (length zs) mod (length ws)
Dart
// 改良: w < x のときは take r zs だけを持って再帰。これで問題サイズが半分以下に。
(List<T>, List<T>) cocktailImproved<T extends Comparable<T>>(List<T> xs) {
(List<T>, List<T>) op((List<T>, List<T>) st, T x) {
final (zs, ws) = st;
if (ws.isEmpty) return ([x], [x]);
final w = ws[0];
final r = zs.length % ws.length;
final c = w.compareTo(x);
if (c < 0) return cocktailImproved([...zs.sublist(0, r), x]);
if (c == 0) return ([...zs, x], [...ws.sublist(1), x]);
return (<T>[], [...zs, ...ws, x]);
}
var state = (<T>[], <T>[]);
for (final x in xs) state = op(state, x);
return state;
}
これで線形時間になる
2r < |zs ⧺ ws| なので、帰納法で cocktail xs の op 呼び出し回数は高々 2n − m 回であることが示せます（n = |xs|、m = |maxtail xs|）。したがって length と ⧺ のコストを無視すれば、線形時間です。
最後の仕上げ
長さ計算を排除する（データ精緻化）
まず op の中の長さ計算をなくすため、状態 (zs, ws) を四つ組 (p, q, ys, ws) に置き換えます。
- ys = zs ⧺ ws（連結済みのものを持っておく）
- p = length zs
- q = length ws
zs 自身は落とせます（take r zs = drop (q−r) ws なので）。thd は四つ組の3番目を取り出す関数です。
maxtail = thd · cocktail
cocktail = foldl op (0, 0, [ ], [ ])
op (p, q, ys, ws) x
| q == 0 = (0, 1, [x], [x])
| w < x = cocktail (drop (q−r) ws ⧺ [x])
| w == x = (p+1, q, ys ⧺ [x], tail ws ⧺ [x])
| otherwise = (0, p+q+1, ys ⧺ [x], ys ⧺ [x])
where w = head ws
r = p mod q
Dart
// データ精緻化: 状態を (p, q, ys, ws) の 4 つ組に置き換え、長さ計算を排除。
// p = |zs|, q = |ws|, ys = zs ++ ws（連結済み）。
typedef Quad<T> = (int p, int q, List<T> ys, List<T> ws);
Quad<T> cocktailRefined<T extends Comparable<T>>(List<T> xs) {
Quad<T> op(Quad<T> st, T x) {
final (p, q, ys, ws) = st;
if (q == 0) return (0, 1, [x], [x]);
final w = ws[0];
final r = p % q;
final c = w.compareTo(x);
if (c < 0) return cocktailRefined([...ws.sublist(q - r), x]);
if (c == 0) return (p + 1, q, [...ys, x], [...ws.sublist(1), x]);
return (0, p + q + 1, [...ys, x], [...ys, x]);
}
Quad<T> state = (0, 0, <T>[], <T>[]);
for (final x in xs) state = op(state, x);
return state;
}
List<T> maxtailRefined<T extends Comparable<T>>(List<T> xs) {
final (_, _, ys, _) = cocktailRefined(xs);
return ys;
}
図 14.1 データ精緻化の結果
(⧺[x]) を排除する（反復化）
残る問題は (⧺[x])（末尾に1要素追加）が定数時間でないこと。キューを使ってもよいですが、ここでは別のアプローチを取ります。
キーとなる発想
計算中に現れる ys や ws は、いずれも元の入力 xs の接尾辞です。だから、これらを毎回作り足す代わりに、最初から xs 全体を持っておいて、必要な位置を指すだけにすればよい。
そのために us ↑ vs（“us before vs”）を「us のうち末尾の vs を取り除いた前半分」と定義します（つまり us = (us ↑ vs) ⧺ vs）。そして次の step を導入します。
step (p, q, ys′, ws′, xs) = thd (foldl op (p, q, ys′ ↑ xs, ws′ ↑ xs) xs)
すると、
maxtail (x : xs) = step (0, 1, x : xs, x : xs, xs)
step の場合分け
元の op の3ケースに対応して、step も3つのケースに整理されます。詳細を展開すると、驚くほどシンプルな最終形が得られます。
maxtail [ ] = [ ]
maxtail (x : xs) = step (0, 1, x : xs, x : xs, xs)
step (p, q, ys, ws, [ ]) = ys
step (p, q, ys, w : ws, x : xs)
| w < x = maxtail (drop (q−r) (w : ws))
| w == x = step (p+1, q, ys, ws, xs)
| w > x = step (0, p+q+1, ys, ys, xs)
where r = p mod q
Dart
// 最終版: 入力 input 全体を保持し、ys / ws は input 内の「開始位置」で表現する。
// これで (⧺[x]) を毎回行う必要がなくなり、Θ(n) を達成できる。
// 変数対応: iYs = ys の開始位置, iWs = ws の開始位置, iX = 次に見る x の位置。
// アルゴリズム終了時、maxtail = input.sublist(iYs, iX)。
List<T> maxtail<T extends Comparable<T>>(List<T> input) {
if (input.isEmpty) return <T>[];
final n = input.length;
var iYs = 0; // maxtail の開始位置
var iWs = 0; // ws の開始位置
var iX = 1; // 次に見る文字の位置（x）
var p = 0; // |zs|
var q = 1; // |ws|
while (iX < n) {
final w = input[iWs];
final x = input[iX];
final c = w.compareTo(x);
if (c < 0) {
// ys を捨て、drop (q-r) ws から再スタート
final r = p % q;
iYs = iWs + (q - r);
iWs = iYs;
// 次のイテレーションで maxtail(...) を呼ぶ状態に相当
// ここで p, q, iX を再初期化
// 新しい入力は input[iYs..n)、その先頭を初期 ys とする
if (iYs >= n) break;
p = 0;
q = 1;
iX = iYs + 1;
} else if (c == 0) {
p += 1;
iWs += 1;
iX += 1;
} else {
q = p + q + 1;
p = 0;
iWs = iYs;
iX += 1;
}
}
return input.sublist(iYs, iX);
}
まとめ
最終アルゴリズムは、実質的に整数 p, q と2本のポインタ ys, ws を動かすだけの while ループになります。線形時間 Θ(n) を達成しました。
おわりに
最終版の maxtail を while ループに書き換えるのは簡単です。それもそのはずで、foldl は本質的に「関数型の衣をまとった while ループ」だからです。それでも、この最終アルゴリズムはとても手続き型っぽい雰囲気があり、ループ不変量を使った手続き型スタイルでの導出を見てみるのも面白いでしょう。
今回の導出はかなり長く、細かな推論が続きました。問題そのものに豊かな構造が隠れているためです。でも、これほど短く言える仕様に対して、もっと単純な解がどこかに眠っているかもしれません。
Dart
// 動作確認: 文字列を文字（int コードポイント）のリストに変換して呼び出す。
void main() {
String mt(String s) {
final chars = s.codeUnits.map((c) => _CI(c)).toList();
final r = maxtail(chars);
return String.fromCharCodes(r.map((c) => c.v));
}
print(mt('introduction')); // uction
print(mt('tomato')); // tomato
print(mt('mammam')); // mmam
print(mt('7412741274')); // 7412741274 の最大接尾辞
}
// int を Comparable として扱うための小ラッパ。
class _CI implements Comparable<_CI> {
final int v;
const _CI(this.v);
@override int compareTo(_CI other) => v.compareTo(other.v);
@override bool operator ==(Object o) => o is _CI && o.v == v;
@override int get hashCode => v.hashCode;
}
参考文献
Crochemore, M. and Rytter, W. (2003). Jewels of Stringology. Hong Kong: World Scientific.