分かち書き (Interpunctio Verborum)

空白も句読点もない外国語の文章を単語ごとに区切りたいとします。例えば次の文章は、Lucius Licinius Murena (ルシウス・リキニウス・ムレナ) を弁護するために Cicero (キケロ) が紀元前 62 年に行った有名な演説を、古典ラテン語の標準的な記法 scriptio continua で表したものです1:

PRIMVSDIGNITASINTAMTENVISCIENTIANONPOTESTESSERESENIMSVNTPARVAEPROPEINSINGVLISLITTERISATQVEINTERPVNCTIONIBUSVERBORVMOCCVPATAE

ラテン語が流暢な読者は、この文字列を (現代的な正書法で) Primus dignitas in tam tenui scientia non potest esse; res enim sunt parvae, prope in singulis litteris atque interpunctionibus verborum occupatae とパースできるでしょう2。

このような文字列の分割のことを "分かち書き" と言います。分かち書きの問題は古典ラテン語と古典ギリシャ語だけが持つ問題ではなく、バリ語、ビルマ語、中国語、日本語、ジャバ語、クメール語、ラオス語、タイ語、チベット語、ベトナム語などの現代の言語でも同様の問題が発生します。似たような問題は他にも、句読点のない英語の文章の文への分割3、段落ごとに分割された文章を組版するときの行への分割、音声認識、手書き文字認識、曲線の単純化、そして一部の時系列解析などで生じます。ここでは可視化のしやすさを考えて、現代英語のアルファベットからなる文字列を英単語ごとに分割する問題を考えます。

まず明らかなのは、複数の方法で分割できる文字列もあるということです。例えば \(\color{maroon} \texttt{BOTH} \)\( \color{maroon} \texttt{EART} \)\( \color{maroon} \texttt{HAND} \)\( \color{maroon} \texttt{SATU} \)\( \color{maroon} \texttt{RNSPIN}\) は \(\color{maroon} \texttt{BOTH} \cdot {} \)\( \color{maroon} \texttt{EARTH} \cdot {} \)\( \color{maroon} \texttt{AND} \cdot {} \)\( \color{maroon} \texttt{SATURN} \cdot {} \)\( \color{maroon} \texttt{SPIN}\) にも \(\color{maroon} \texttt{BOT} \cdot {} \)\( \color{maroon} \texttt{HEART} \cdot {} \)\( \color{maroon} \texttt{HANDS} \cdot {} \)\( \color{maroon} \texttt{AT} \cdot \texttt{URNS} \cdot {} \)\( \color{maroon} \texttt{PIN}\) にも分割できますし、他にも分割方法があります。しかしまずは、一番単純な問題「入力の文字列を英単語ごとに分割する方法は一つでも存在するか？」を考えることにします。

問題を具体的に (そして違う言語でも使えるように) するために、サブルーチン \(\textsc{IsWord}(w)\) が使えると仮定します。このサブルーチンは文字列 \(w\) を受け取り、その文字列が "単語" ならば \(\textsc{True}\) を、そうでなければ \(\textsc{False}\) を返します。例えば右から読んでも左から読んでも同じになる単語ごとに文字列を分割しようとしているのなら、右から読んでも左から読んでも同じになる単語が "単語" になり、\(\textsc{IsWord} ({\color{maroon}{ \texttt{ROTATOR}}}) ={}\)\(\textsc{True}\) および \(\textsc{IsWord} ({\color{maroon}{ \texttt{PALINDROME}}}) ={}\)\(\textsc{False}\) です。

部分和問題と同じように、分かち書き問題への入力も列 (sequence) という構造を持ちます。ただこの問題の入力は数字の列ではなくて文字の列なので、アルゴリズムが入力を左から右に読むとした方が自然です。同様に、出力の構造は単語の列であり、アルゴリズムは左から右に単語を出力するとしましょう。分割アルゴリズムの途中に放り込まれたところを想像すると、次の画像のような状態になります。

これまでの決断の列 ――最初の 17 文字の 4 つの単語への分割―― とこれから処理する文字列が、黒いバーによって分かれています。

この想像上の処理で次に行われるのは、次に出力する単語の終端の決断です。今考えている例では、次に出力する単語の選択肢が四つ (\(\color{maroon}{\texttt{HE}}\), \(\color{maroon}{\texttt{HEAR}}\), \(\color{maroon}{\texttt{HEART}}\), \(\color{maroon}{\texttt{HEARTH}}\)) あります。これらのうちどれを選べば入力文字列全体の分割が上手く行くのか、あるいはどれを選んでも上手く行かないのかは全く分かりません。もちろん "賢く" なってどの選択肢が良いのかを調べることもできますが、それをするにはいろいろと考えなくてはいけません！ そうする代わりに、ここでは "愚直に" 全ての選択肢を総当たりで試すことにします。こうすると、残りの処理は再帰の妖精に任せることができます:

再帰の妖精が少なくとも一回成功を報告したら、この処理も成功を報告します。そうでなくて全ての再帰の妖精が失敗を報告したとき ――どうやっても次の語が作れない場合も含む―― には、失敗を報告します。

未処理の文字列の接頭語だけが次の決断の選択肢を決めるので、これまでの決断が現在の選択肢に影響することはありません。例えば異なる決断の結果としてこれから処理する文字列が同じになることがありますが、この場合の選択肢は同じになります。

このため、再帰的な処理を表す画像の黒いバーよりも左側は全て無視できます。

こうするとバックトラッキングを使ったアルゴリズムの単純な基本構造がはっきりします:

次の語を選び、残りの文字列を再帰的に分割する。

再帰的なアルゴリズムを完全なものにするには、ベースケースの処理が必要です。この再帰的な戦略が終了するのは処理が入力文字列の終端に達してこれ以上単語を作れなくなったときです。もちろん、空文字列はゼロ個の単語へとユニークに分割できます！

以上をまとめると、次のシンプルな再帰的アルゴリズムが手に入ります:

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

if \(n = 0\) then

return \( \textsc{True} \)

else

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

if \(\texttt{IsWord}\)(\(A[1..i]\)) then

if \(\texttt{Splittable}\)(\(A[i+1..n]\)) then

return \( \textsc{True} \)

return \( \textsc{False} \)

添え字による定式化

実際のプログラムでアルゴリズムの入力パラメータに配列をコピーして渡すと時間がかかってしまうので、再帰的な小問題を組み立てるためのもっとコンパクトな方法を考えた方が良さそうです。このような状況でアルゴリズムを設計するときには、最初の問題に対する入力をグローバル変数として扱い、実際の小配列ではなくて元の配列に対する添え字を使うように問題とアルゴリズムを変形してしまうのがとても有用です。

今考えている分かち書き問題では、再帰呼び出しの引数は常に最初の問題に対する入力配列の接尾部分 \(A[i..n]\) です。よって \(A[1..n]\) をグローバル変数とみなせば、再帰的な問題を次のように変形できます:

与えられた添え字 \(i\) よりも後ろの部分 \(A[i..n]\) の分割を見つけよ。

このアルゴリズムを説明するために二つの真偽値関数を導入します:

例えば \(\mathit{IsWord}(1, n) = \textsc{True}\) となるのは入力全体が一つの単語であるときであり、\(\mathit{Splittable}(1) = \textsc{True}\) となるのは入力文字列全体が分割できるときです。これまで説明してきた再帰的な戦略から、次の再帰方程式を得ます: \[ \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} \] これはついさっき見たアルゴリズムと表記が変わっただけで全く同じです。再帰方程式を疑似コードにすると似ていることがさらに分かりやすくなります:

⟨⟨接尾部 \(A[i..n]\) は分割できるか？⟩⟩

procedure \(\texttt{Splittable}\)(\(i\))

if \(i > n\) then

return \( \textsc{True} \)

else

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

if \(\texttt{IsWord}\)(\(i, j\)) then

if \(\texttt{Splittable}\)(\(j + 1\)) then

return \( \textsc{True} \)

return \( \textsc{False} \)

表記の違いは自明で何も変わらないと思うかもしれません。しかし表記を変えることでプログラムを実装したときの実行時間が小さくなるだけではなく、線形計画法のアルゴリズムの設計も容易になります。線形計画法については次の章で扱います。

❤ 解析

バックトラッキングを使ったアルゴリズムの多くは最悪ケースにおける実行時間が指数時間となりますが、特に驚くようなことではないでしょう。こういったアルゴリズムの実行時間の正確な解析はこの本の範囲を超えます。しかし幸いにも、この本に出てくるバックトラッキングを使ったアルゴリズムはもっと効率的なアルゴリズムのための中間的な結果に過ぎないので、最悪ケースにおける正確な実行時間はあまり重要ではありません ("まず動くようにせよ。それから速くせよ")。

ただ面白そうなので、再帰的なアルゴリズム \(\textsc{Splittable}\) の実行時間の解析をしてみることにします。\(\textsc{IsWord}\) がどんな動作をしてどれくらい時間がかかるのかわからないので4、実行時間の解析は \(\textsc{IsWord}\) の呼び出し回数を通して行います。

\(\textsc{Splittable}\) は入力文字列の全ての接頭辞に対して \(\textsc{IsWord}\) を呼びます。また出力文字列の接尾語全てに対して再帰呼び出しをする可能性があります。よって \(\textsc{Splittable}\) の "実行時間" は次のぎょっとする形の再帰方程式に従います: \[ T(n) \leq \sum_{i=0}^{n-1}T(i) + O(n) \] しかし次に説明するトリックを理解してしまえば、この式は見た目ほど恐ろしいものではありません。

まず \(O(n)\) を適当な定数 \(\alpha\) を使って \(\alpha n\) と明示的に書き直します (\(\alpha\) の実際の値は重要ではありません)。さらに最悪ケースの実行時間を解析していることから、全ての再帰呼び出しが行われると仮定します5。そうした上で \(T(n)\) から \(T(n-1)\) を引くと、"全ての \(n\) に対する" 再帰方程式を、"直前の \(n\) に対する" 再帰的方程式に変形できます: \[ \begin{aligned} T(n) & = \sum_{i=0}^{n-1}T(i) + \alpha n \\ T(n-1) & = \sum_{i=0}^{n-2}T(i) + \alpha (n - 1) \\ \therefore T(n) - T(n - 1) & = T(n - 1) + \alpha \end{aligned} \] 最後の式は \(T(n) = 2\ T(n - 1) + \alpha\) と変形できます。ここまでくれば、\(T(n) = O(2^{n})\) と自信をもって予想できます (あるいは再帰木を使って実際に計算してもいいですし、Hanoi の塔の例を思い出してもいいでしょう)。元々の全ての \(n\) に対する再帰方程式がこの上界を持つことを帰納法で証明するのは難しくありません。

さらに言えば、この解析は最良です。長さ \(n\) の文字列を分割する方法は ――最後の文字を除くそれぞれの文字で単語が終わるかどうかという選択肢があるので―― ちょうど \(2^{n-1}\) 通りあり、最悪ケースにおいて \(\textsc{Splittable}\) は \(2^{n-1}\) 個の選択肢全てを探索するからです。

変種

部分和問題と同様に、一番単純な分かち書き問題の再帰的な構造を理解すれば、様々な変種を同じ構造を使って解くことができます。ここではその一つを説明して、練習問題でさらにいくつかを考えます。いつも通り、最初の問題に対する入力は \(A[1..n]\) であるとします。

文字列が複数の単語列に分割できるときに、何らかの基準に従って最も良い分割を選択したい場合があります。また逆に文字列が単語列に分割できないときにも、失敗を報告するのではなくて一番良い分割を選択したい場合があります。これら両方を達成するために、文字列を受け取ってそのスコアを数値として返す二つ目の外部関数 \(\mathit{Score}\) が利用できると仮定します。例えばめったに表れない長い単語には高い正の点数、頻繁に登場する短い単語には低い正の点数、スペルミスには多少の負の点数、長くて単語にもなっていない文字列にはかなり低い負の点数が付けられるでしょう。ここでの目標は入力文字列の単語列への分割であってスコアの和が最大のものを求めることです。

任意の添え字 \(i\) に対して、入力文字列の接尾部分 \(A[i..n]\) の分割のうちスコアが最大のものを \(\mathit{MaxScore}(i)\) で表すことにします。この関数は次の再帰方程式を満たします: \[ \mathit{MaxScore}(i) = \begin{cases} 0 & \text{if } i > n \\ \max\limits_{i \leq j \leq n} \left( \mathit{Score}(A[i..j]) + \mathit{MaxScore}(j + 1) \right) & \text{それ以外} \end{cases} \] この関数は \(\mathit{Splittable}\) に対して得たものと本質的に同一です。唯一の違いは真偽値演算 \(\vee, \wedge\) が数値演算 \(\max, +\) に代わっている点です。

  1. 古典ラテン語の・たいていの・写本は・ interpunct と・呼ばれる・小さな点を・使って・単語の・区切りを・表して・いました。しかし scriptio continua が好まれたことで、紀元三世紀ごろには interpunct はほとんど見られなくなりました。単語の間に空白を入れる記法はアイルランド人の僧侶達によって八世紀ごろに導入され、数世紀をかけて少しずつヨーロッパ全体に広がっていきました。 scriptio continua は二十一世紀の英語でも URL とハッシュタグに生き残っています。 #octotherps4lyfe[return]

  2. 大雑把に翻訳すると: 「まず、そのような取るに足らない知識に品位などありえない。そんな知識は自明なことであって、ほとんどが個々の文字と単語の間の点の配置に関するものである」Cicero は彼の友人 (！) の法律に関する専門知識を公然と侮辱しています。このあと彼は、領事の選挙で敗れた Murena を贈賄の罪で訴えていた法学者 Servius Sulpicius Rufus (セルウィウス・スルピキウス・ルフス) に言及します。Cicero の鋭い弁護によって、ほぼ間違いなく有罪だった Murena は無罪を勝ち取りました。 #librapondo #nunquamestfidelis[return]

  3. St. Augustine による De doctrina Christiana には、句読点を入れることでラテン語聖書から曖昧さを取り除くことだけについて書かれた章があります。[return]

  4. 正確なことを言うと、 \(\textsc{IsWord}\) が多項式時間で実行される限り、 \(\textsc{Splittable}\) は \(O(2^{n})\) 時間で実行されます。[return]

  5. アルファベットをランダムに並べた文字列のほとんどは英単語ではないために、文字列を英単語ごとに分割する問題でこの仮定をすると、実行時間が実際よりもとても大きく見積ることになります。しかし英語の単語列を文法的に正しい英語の文に分割する問題ではそうではありません。例えば正の整数 \(n\) について \(n\) 個の "buffalo" や \(n\) 個の "police"、\(n\) 個の "can" が並んだ単語列を考えてみてください (At the Moulin Rouge, dances that are preservable in metal cylinders by other dances have the opportunity to fire dances that happen in prison restroom trash receptacles.)。[return]

広告
このページの文章はテキストゆれないくんを使って校正されました。