メモ化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/09/10 08:00 UTC 版)
構文解析
ピーター・ノーヴィグは1991年、構文解析戦略にメモ化を応用し、単純なバックトラッキング式の再帰下降構文解析に自動メモ化を適用することでアーリー法のようなアルゴリズムになることを示した[2]。1995年には Johnson と Dörre も構文解析でのメモ化の応用を提案した[5][6]。2002年、Ford はこれのパックラット構文解析への応用をかなり詳細に論じた[7]。
ノーヴィグは構文解析器をメモ化によって強化したが、時間計算量はアーリー法と同じであった。つまりこれは、速度的性能の最適化以外にメモ化を応用した例である。Johnson と Dörre[6] も同様に時間短縮以外の応用を示した。それは、言語的制約の解決を必要な情報が構文解析によって十分集まった時点にまで遅延されることにメモ化を利用するものだった。一方、Ford は時間的性能の最適化にメモ化を応用し、パックラット構文解析が最悪ケースのバックトラッキングが必要な形式言語でも線形時間で構文解析できることを示した[7]。
次のような形式文法を考えてみよう。
S → (A c) | (B d) A → X (a|b) B → X b X → x [X]
ここで、生成規則 S → (A c) | (B d) の意味は、「S は、A の後に1つの c が続くか、あるいは B の後に1つの d が続くかのどちらかである」となる。また、生成規則 X → x [X] の意味は、「X は、1つの x の後にオプションの X が続く」となる。
この文法が生成する文字列は、xac、xbc、xbd（なお、x は1つ以上の x の連続となりうる）のいずれかである。次にこの文法から構文解析の仕様をトップダウンでかつ左から右に解析するものとしたとき、文字列 xxxxxbd の解析がどうなるかを考える。
- トップダウンであるから、まず全体が S に置換可能であるとの前提で、S の規則から、まず全体が (A c) であると仮定する。最後の文字がここで既に違っていることは明らかだが、左から右に構文解析するので、構文解析器にはまだ最後の文字が見えていない。次に A の生成規則を見て、さらに X の生成規則を見ていく。ここで初めて先頭の文字が一致する。そして、x が続いている間は X の規則を再帰的に適用し、次の文字 b も A の規則に一致するが、その次の d と c が一致しない。ここでバックトラックが発生し、S のもう一方の選択肢である B の規則を適用し、同様に X を必要な回数適用して、最終的に最後の文字まで一致する。以上によりこの文字列は、この文法で認識される。
ここで重要となるのは、以上の説明の中で X の繰り返し適用が2回出現することである。このように処理を進めていって失敗し、元に戻って別の選択肢に移って処理を再開することをバックトラッキングと呼ぶ。そして、構文解析におけるバックトラッキングにメモ化を応用する余地があることがわかる。ここで、関数 RuleAcceptsSomeInput(Rule, Position, Input) を考える。引数の意味は次の通りである。
Ruleは、検討中の生成規則の名前Positionは、現在検討中の入力上のオフセット位置Inputは、検討中の入力
関数 RuleAcceptsSomeInput のリターン値は Rule が受理した入力の長さとする。その生成規則が指定されたオフセット位置の入力文字を受理しなかった場合は 0 を返す。バックトラッキングとメモ化を使う場合、構文解析は次のようになる。
- オフセット 0 で、生成規則 A から生成規則 X へと下降していき、そこでその位置と生成規則 X について長さ 5 をメモ化（記録）する。d の位置で生成規則の適用に失敗すると、生成規則 B が選ばれ、再び X を適用するのではなく、メモ化エンジンに対して位置 0 と生成規則 X についての記録があるかを訊ねる。メモ化エンジンは長さ 5 が記録されているのでそれを返す。これにより実際に X を適用することなく処理を省略でき、前回と同じぶんだけ X を適用したのと同じ効果を得る。
この例では、X は再帰的に何度でも適用可能であるため、xxxxxxxxxxxxxxxxbd のような文字列もありうる。従って S を始点として X まで下降して再帰的に生成規則の適用を繰り返すが、バックトラックして B に移行した後は RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd) のリターン値が 16 であることが分かっている（メモ化済みである）ので、実際に X を適用する必要がない。
統語的述語（syntactic predicate）を使った構文解析器でも、述語の構文解析結果をメモ化できる。例えば次のような構文規則があるとする。
S → (A)? A A → /* 何らかの規則 */
これは、入力の先頭で A で受理できるなら A で受理することを表している。述語部分 (A)? の結果をメモ化しておけば、実際の生成規則適用時は省略できる。
構文解析時に構文木を構築する場合、メモ化ではマッチした入力の長さだけでなく、その位置と生成規則によって生成された部分木も記憶しておく必要がある。同様に、生成規則がマッチしたときに外部のコードを呼び出す方式の構文解析器の場合、その呼び出し順序が本来期待されている順序になるよう注意してメモ化する必要がある。
全ての文法でバックトラッキングや統語的述語が必要となるわけではないので、個々の生成規則について結果を記憶しておくことで構文解析の性能が低下する可能性がある。これは、メモ化する生成規則を明示的に選択することで問題を限定することができる[8]。
- ^ Michie, Donald, "Memo Functions and Machine Learning," Nature, No. 218, pp. 19-22, 1968.
- ^ a b Norvig, Peter, "Techniques for Automatic Memoization with Applications to Context-Free Parsing," Computational Linguistics, Vol. 17 No. 1, pp. 91-98, March 1991.
- ^ Hoffman, Berthold, "Term Rewriting with Sharing and Memoïzation," Algebraic and Logic Programming: Third International Conference, Proceedings, H. Kirchner and G. Levi (eds.), pp. 128-142, Volterra, Italy, 2-4 September 1992.
- ^ Mayfield, James, et al, Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems, TBD, 1995.
- ^ Johnson, Mark, "Memoization of Top-Down Parsing,” Computational Linguistics, Vol. 21 No. 3, pp. 405-417, September 1995.
- ^ a b Johnson, Mark & Dörre, Jochen, "Memoization of Coroutined Constraints," Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics, Cambridge, Massachusetts, 1995.
- ^ a b Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, September, 2002.
- ^ Acar, Umut A. A. et al., "Selective Memoization," Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New Orleans, Louisiana, pp. 14-25, 15-17 January 2003.
- メモ化のページへのリンク
