『入門 自然言語処理』の4.7.3、動的計画法のところ

　結構難しい…多分ここだけで理解するものでもないんだろう。動的計画法ってそれだけで教科書があるし。

virahanka2() の挙動

def virahanka2(n):
    lookup = [[""] , ["S"]]
    for i in range(n-1):
        s = ["S" + prosody for prosody in lookup[i+1]]
        l = ["L" + prosody for prosody in lookup[i]]
        lookup.append(s + l)
    return lookup[n]

　小さい値を使ってより大きな値を構築していくようになっている。
　n=0, n=1ははじめから用意しておく。n=2以降をn=0、n=1の値のときの値を使って構築し、リストに保存しておく。最終的に引数で指定された値を返すんだけど、余分に一つ上の値（n=2を与えられたらn=3まで）を計算するようになっている。
　あと、こういう式を考えだす方法がわからない…
　

virahanka3()の挙動

def virahanka3(n, lookup={0:[""], 1:["S"]}):
    if n not in lookup:
        s = ["S" + prosody for prosody in virahanka3(n-1)]
        l = ["L" + prosody for prosody in virahanka3(n-2)]
        lookup[n] = s + l
    return lookup[n]

　デフォルト引数はpythonインタプリタが関数を読み込んだ一回にしか生成されないことを利用して、途中の値を保存している。（デフォルト引数については「4.6.3　エラーの原因」の170pに載ってる）
　再帰呼び出しのとき、引数を指定してないから、関数内で更新されたリストが毎回使われる。さらに、lookupリストに求める値がすでにあるなら計算せずに返す。よく知らないけどクロージャってこういう動きをするのかな。

virahanka4()の挙動

from nltk import memoize
@memoize
def virahanka4(n):
    if n == 0:
        return [""]
    elif n == 1:
        return ["S"]
    else:
        s = ["S" + prosody for prosody in virahanka4(n-1)]
        l = ["L" + prosody for prosody in virahanka4(n-2)]
        return s + l

　「メモ化」を使っているらしい。それ以外は普通の再帰の virahanka1() と同じ。
同じ引数で呼ばれた関数は、前回の値を使う？
http://www.kmonos.net/wlog/52.php#_0308050827
分かったような分からないような……

　ちなみにpythonのデコレータを使ったmemoizeの実装。
http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize
　これを見ると、関数呼び出された時に引数を key にしてディクショナリを調べて、存在してたらその value （関数を与えられた引数で呼び出した返り値）を返す。なかったらその場で関数呼び出しをして、引数を key 、返り値を value にしてディクショナリに挿入しつつ value を返す。なんか普通にキャッシュしてるように見える。