メモ化

メモ化（）とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である。メモ化は構文解析などでも使われる（必ずしも高速化のためだけとは限らない）。キャッシュはより広範な用語であり、メモ化はキャッシュの限定的な形態を指す用語である。
概要.
メモ化という用語は1968年にドナルド・ミッキーがラテン語の （覚えておく）から作った造語である。"memorization"（記憶、暗記）は同根語であってよく似ているが、メモ化という言葉は情報工学では特別な意味を持つ。
メモ化された関数は、以前の呼び出しの際の結果をそのときの引数と共に記憶しておき、後で同じ引数で呼び出されたとき、計算せずにその格納されている結果を返す。メモ化可能な関数は参照透過性を備えたものに限られる。すなわち、メモ化されたことで副作用が生じない場合に限られる。メモ化の実装ではルックアップテーブルなどの参照方式が使われるが、メモ化では参照されるテーブルの内容は必要に応じて格納されるという点で、通常のテーブル参照とは異なる。
メモ化は関数の時間コストを領域コストに交換して、時間コストを低減させる手段である。すなわち、メモ化された関数は速度の面で最適化され、記憶装置の領域という面ではより多く消費する。計算複雑性理論は、アルゴリズムの時間と領域のコストを扱う。全ての関数には時間と領域についての複雑性が定義される。
このようにトレードオフが発生するが、同様のトレードオフがある最適化とは異なる。というのも、演算子強度低減などの最適化はコンパイル時のものだが、メモ化は実行時の最適化であるためである。さらに言えば、演算子強度低減は例えば、乗算を加算の組合せで表すことで性能を改善しようとするもので、プラットフォームのアーキテクチャに深く依存している。一方、メモ化はプラットフォームからは独立した戦略である。
例.
次の擬似コードは "n" の階乗を計算する関数である。
 function factorial ("n") // n は非負整数
 if "n" == 0 then
 return 1
 else 
 return factorial(n - 1) * "n" // 再帰呼び出し
 end if
 end function
"n" ≥ 0 であるような全ての整数 "n" について、関数 codice_1 の結果は不変である。つまり、codice_2 としたとき、"x" の値は常に 6 である。上記のメモ化する前のコードでは、結果を得るのに "n + 1" 回の再帰呼び出しが必要であり、それが計算における時間コストに相当する。プラットフォームのアーキテクチャにも依存するが、時間コストは以下のコストの総和である。
メモ化していない実装では、これらのコストのうち 2 番から 6番が "n" に比例した回数かかることになる。
codice_1 をメモ化したバージョンを以下に示す。
 function factorial ("n") // n は非負整数
 if "n" == 0 then
 return 1
 else if (テーブルに "n" の階乗が格納されている) then
 return (テーブルに格納された "n" の階乗の値)
 else 
 x = factorial(n - 1) * "n" // 再帰呼び出し
 "x" を "n" の階乗の値としてテーブルに格納する
 return x
 end if
 end function
このメモ化バージョンでは、「テーブル」は広域の永続性のある変数であり、"n" をキーとする連想配列のようなものである。このルックアップテーブルが領域（すなわちコンピュータのメモリ）を使うことによって、codice_1 を同じ引数で繰り返し呼び出したときに要する時間が削減される。
例えば、codice_1 を最初に引数 5 で呼び出すと、その後 5 以下の引数で呼び出したとき、それらの値は既にメモ化されている。なぜなら、codice_1 は引数 5、4、3、2、1、0 で再帰的に呼び出され、それぞれの呼び出しについて結果が記憶されるからである。また、引数 5 で呼び出された後に引数 7 で呼び出されると、再帰呼び出しは 2 回で済み（7 と 6）、5! の値は既に記憶されているのでそれが使われる。このように、メモ化された関数は呼び出される度により効率化されていき、結果として全体の高速化が図られる。
自動メモ化.
上述の codice_1 の例のように、メモ化は一般にプログラマが関数内部に明示的に施すものであるが、参照透過性のある関数は外部で自動的にメモ化することもできる。ピーター・ノーヴィグが採用した技法は Common Lisp （ノーヴィグの論文で自動メモ化の例に使われていた言語）だけでなく、様々なプログラミング言語で応用可能である。自動メモ化は項書き換えや人工知能の研究でも応用が模索されている。
関数が第一級か第二級オブジェクトであるようなプログラミング言語（例えば Lua）では、自動メモ化は関数を特定の引数付きで実行するたびに、その結果の値で（実行時に）置き換えてやることで実装される。このような置き換えを行う汎用関数を本来の関数を呼び出す代わりに呼び出せばよい。擬似コードを以下に示す（この例では関数は第一級オブジェクトであると仮定している）。
 function memoized-call ("F"） // F は関数オブジェクト
 if ("F" には対応する配列 "values" がない) then
 allocate an associative array called "values";
 attach "values" to "F";
 end if;
 if F."values[arguments]" is empty then
 F."values[arguments]" = "F"(arguments);
 end if;
 return F."values[arguments]"; 
 end function
codice_1 を自動メモ化する場合もこの戦略を使い、codice_1 を直接呼び出すのではなく、codice_10 を呼び出す。呼び出されると、まず結果を格納する配列が確保されているかどうかを調べ、なければ配列を確保して割り当てる。次に、codice_11 の位置にエントリが無ければ（ここで codice_12 は連想配列のキーとして使われている）、実際の codice_1 を呼び出す。最後に、配列のキー位置のエントリが呼び出し側に返される。
この戦略では、メモ化される関数を呼び出す箇所で明示的な対処が必要となる。クロージャが可能な言語では、メモ化はメモ化関数オブジェクトをラップする functor オブジェクトとして暗黙的に実現できる。これを擬似コードで表すと、次のようになる。
 function construct-memoized-functor ("F"） // F は関数オブジェクト
 allocate a function object called "memoized-version";
 let memoized-version(arguments) be
 if ("self" に対応する連想配列 values がない) then // self は いわゆる this オブジェクト
 allocate an associative array called "values";
 attach "values" to "self";
 end if;
 if self."values[arguments]" is empty then
 self."values[arguments]" = "F"(arguments);
 end if;
 return self."values[arguments]"; 
 end let;
 return "memoized-version";
 end function
codice_1 の代わりに使われる新たな関数オブジェクト codice_15 は次のように生成される。
 memfact = construct-memoized-functor(factorial)
この例では、関数 codice_1 は codice_17 を呼び出す前に定義されているものとしている。そしてそれ以降、"n" の階乗を計算したい場合は常に codice_18 を呼び出す。Luaなどの言語では、関数名を変えずに置き換えることも可能であり、次のようにできる。
 factorial = construct-memoized-functor(factorial)
基本的にこのような技法では、生成された functor にオリジナルの関数オブジェクトをアタッチし、必要な場合（無限の再帰呼び出しを避けるため）にオリジナルの関数をエイリアスを通して呼び出す。これを擬似コードで表すと次のようになる。
 function construct-memoized-functor ("F") // F は関数オブジェクト
 allocate a function object called "memoized-version";
 let "memoized-version"(arguments) be
 if ("self" に対応する連想配列 values がない) then // self は いわゆる this オブジェクト
 allocate an associative array called "values";
 attach "values" to "self";
 allocate a new function object called "alias";
 attach "alias" to "self"; // F を後で間接的に呼び出すため
 self."alias" = "F";
 end if;
 if self."values[arguments]" is empty then
 self."values[arguments]" = self."alias"(arguments); // F の直接呼出しではない
 end if;
 return self."values[arguments]"; 
 end let;
 return "memoized-version";
 end function
なお、言語によってはこれらのステップの一部は言語の機能として実装されている。上記はあくまで説明のための擬似コードである。
構文解析.
ピーター・ノーヴィグは1991年、構文解析戦略にメモ化を応用し、単純なバックトラッキング式の再帰下降構文解析に自動メモ化を適用することでアーリー法のようなアルゴリズムになることを示した。1995年には Johnson と Dörre も構文解析でのメモ化の応用を提案した。2002年、Ford はこれのパックラット構文解析への応用をかなり詳細に論じた。
ノーヴィグは構文解析器をメモ化によって強化したが、時間計算量はアーリー法と同じであった。つまりこれは、速度的性能の最適化以外にメモ化を応用した例である。Johnson と Dörre も同様に時間短縮以外の応用を示した。それは、言語的制約の解決を必要な情報が構文解析によって十分集まった時点にまで遅延されることにメモ化を利用するものだった。一方、Ford は時間的性能の最適化にメモ化を応用し、パックラット構文解析が最悪ケースのバックトラッキングが必要な形式言語でも線形時間で構文解析できることを示した。
次のような形式文法を考えてみよう。
 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" の解析がどうなるかを考える。
ここで重要となるのは、以上の説明の中で "X" の繰り返し適用が2回出現することである。このように処理を進めていって失敗し、元に戻って別の選択肢に移って処理を再開することをバックトラッキングと呼ぶ。そして、構文解析におけるバックトラッキングにメモ化を応用する余地があることがわかる。ここで、関数 codice_19 を考える。引数の意味は次の通りである。
関数 codice_23 のリターン値は codice_20 が受理した入力の長さとする。その生成規則が指定されたオフセット位置の入力文字を受理しなかった場合は 0 を返す。バックトラッキングとメモ化を使う場合、構文解析は次のようになる。
この例では、"X" は再帰的に何度でも適用可能であるため、"xxxxxxxxxxxxxxxxbd" のような文字列もありうる。従って "S" を始点として "X" まで下降して再帰的に生成規則の適用を繰り返すが、バックトラックして "B" に移行した後は codice_25 のリターン値が 16 であることが分かっている（メモ化済みである）ので、実際に "X" を適用する必要がない。
統語的述語（syntactic predicate）を使った構文解析器でも、述語の構文解析結果をメモ化できる。例えば次のような構文規則があるとする。
 S → (A)? A
 A → /* 何らかの規則 */
これは、入力の先頭で "A" で受理できるなら "A" で受理することを表している。述語部分 (A)? の結果をメモ化しておけば、実際の生成規則適用時は省略できる。
構文解析時に構文木を構築する場合、メモ化ではマッチした入力の長さだけでなく、その位置と生成規則によって生成された部分木も記憶しておく必要がある。同様に、生成規則がマッチしたときに外部のコードを呼び出す方式の構文解析器の場合、その呼び出し順序が本来期待されている順序になるよう注意してメモ化する必要がある。
全ての文法でバックトラッキングや統語的述語が必要となるわけではないので、個々の生成規則について結果を記憶しておくことで構文解析の性能が低下する可能性がある。これは、メモ化する生成規則を明示的に選択することで問題を限定することができる。