分かち書き (Interpunctio Verborum) 再訪

次に考える動的計画法の例は、前章で触れた文字列分割の問題です。この問題の入力は文字列が (何らかの意味で) 単語かどうかを判定するサブルーチン \(\textsc{IsWord}\) と検査する文字列 \(A[1..n]\) であり、出力は \(A\) を単語列に分割できるかどうかでした。

この問題を解いたときに使ったのは接尾部分 \(A[i..n]\) が分割できる場合に限って \(\textsc{True}\) を返す関数 \(\mathit{Splittable}(i)\) であり、\(\mathit{Splittable}(1)\) を計算することで問題を解きました。この関数は次の再帰方程式を満たします: \[ \mathit{Splittable}(i) = \begin{cases} \textsc{True} & \text{if } i > n \\ \bigvee\limits_{j = i}^{n}(\mathit{IsWord} (i, j) \land \mathit{Splittable}(j + 1)) & \text{それ以外} \end{cases} \] ここで \(\mathit{IsWord}(i, j)\) は \(\mathit{IsWord}(A[i..j])\) を省略して書いたものです。この再帰方程式はバックトラッキングを使った再帰的なアルゴリズムに直接書き換えることができ、その場合 \(\mathit{IsWord}\) は最悪ケースで \(O(2^{n})\) 回呼ばれます。

しかし考えてみると、\(A[1..n]\) という決められた長さの配列に対して関数 \(\mathit{Splittable}(i)\) を呼ぶ異なる方法は \(i = 1..n+1\) の \(n+1\) 個しかなく、\(\mathit{IsWord}\) を呼ぶ異なる方法の個数は \(1 \leq i \leq j \leq n\) を満たす添え字の組 \((i, j)\) の個数なので \(O(n^{2})\) しかありません。どうして多項式個しかない物の値を求めるのに指数的な時間をかけているのでしょうか?

小問題への再帰的な呼び出しは \(1\) から \(n+1\) の整数で特定できるので、\(\mathit{Splittable}\) 関数の値は配列 \(\mathit{SplitTable}[1..n+1]\) に格納できます。小問題 \(\mathit{Splittable}(i)\) は \(j > i\) を満たす \(\mathit{Splittable}(j)\) にのみ依存するので、メモ化された再帰的なアルゴリズムは配列を最後から降順に埋めます。これと同じ順番で配列を埋めるようにすれば、次に示す動的計画法を使ったアルゴリズムとなります:

procedure \(\texttt{FastSplittable}\)(\(A[1..n]\))

\(\mathit{SplitTable}[n+1] \leftarrow \textsc{True}\)

for \(i \leftarrow n\) downto \(1\) do

\(\mathit{SplitTable}[i] \leftarrow \textsc{False}\)

for \(j \leftarrow i\) to \(n\) do

if \( \textsc{IsWord}(i, j)\) かつ \(\mathit{SplitTable}[j+1]\) then

\(\mathit{SplitTable}[i] \leftarrow \textsc{True}\)

return \(\mathit{SplitTable}[1]\)

図 3.3. Interpunctio verborum velox

このアルゴリズムは \(\mathit{IsWord}\) を \(O(n^{2})\) 回しか呼び出さないので、以前のバックトラッキングを使ったアルゴリズムから指数的に高速化されています。