2

それで、前にこれを尋ねてみましたが、私が探していたものについて十分に明確ではなかったと思います. 私は最適な文字列配置アルゴリズムを作成しています。これは実際には動的プログラミングの問題です。なので、再帰的に書くことにしました。このプログラムは、次の 2 つの部分で構成されています。

  • 関連するコストに基づいてアラインメントを最小化する、2 つの単語間の「編集距離」を見つける。たとえば、同じ文字を並べるとコストは 0、2 つの母音を並べるとコストは 0.5 ですが、ギャップのある文字を並べるとコストは 1 になります。
  • アラインメントの視覚化: つまり、文字列とギャップの最適なアラインメントを使用して文字列を相互に重ねます。

私の編集距離は機能すると思います。私は同僚と同じ値を取得しており、差し迫った問題はないようです。ただし、一致、挿入、および削除のシーケンスを復元してアライメントを視覚化する方法を理解するのに苦労しています。私の問題は、最低 3 回の再帰呼び出しを行う再帰関数があるという事実に起因しています。そのため、再帰呼び出しごとに「移動」(一致、挿入、削除) が追加されるため、必要以上に長いシーケンスになってしまいます。これは、最もコストがかからないため使用されない可能性があります。

これが私のコードです：

newseq = []
@memoize
def opt(a, b):
    global newseq # Visual Alignment 'move' sequence
    gap = 1 # Gap cost
    if not a: 
        return len(b)
    if not b: 
        return len(a)

    if a and b:
        p1 = a[0] in v   # First letters vowells?
        p2 = b[0] in v   
        if a[0] == b[0]: # First letters equal each other?
            alpha = 0
        elif p1 ^ p2:    # Vowel and Consonant?
            alpha = 1.2
        elif p1 and p2:  # Vowel and Vowel?
            alpha = 0.5
        else:            # Consonant and Consonant?
            alpha = 0.6

    r1 = opt(a[1:], b[1:]) + alpha
    r2 = opt(a[1:], b) + gap
    r3 = opt(a, b[1:]) + gap
    # Reset newseq
    newseq = newseq[:-3]

    # Takes min of recursive calls, and gives associated 'move'
    res = min((r1, 'Match'),      # Match
              (r2, 'Insertion'),  # Insertion
              (r3, 'Deletion'),   # Deletion
              key = lambda x: x[0])

    newseq.append(res[1])
    return res[0]

そうそう、私は自分が持っているものが機能していないことを知っています。newseq再帰呼び出し中に発生するすべての追加を削除してリセットしようとするため、現在のグローバル変数の長さは 1 です。この再帰アルゴリズムで最適なアライメントを構成する一連の「移動」を記録する方法を設定するにはどうすればよいですか?

編集:これが私の memoize デコレータ関数です:

def memoize(f):
    cache = {}
    def decorated_function(*args):
        if args in cache:
            return cache[args]
        else:
            cache[args] = f(*args)
            return cache[args]
    return decorated_function
4

1 に答える 1

1

1）スタック（または他のコレクション）を再帰関数に引数として渡します。

2) 再帰的に自分自身を呼び出すときは、実行中のステップもスタックにプッシュします (たとえば、ステップ タイプの列挙と ints/chars/strings/何をしているかを示すものを使用)。

3) 2) の呼び出しから戻ったら、スタックをポップして 2) を繰り返します。

4) 解決策がある場合、その結果/スコアに関連付けられたスタックを保存できます。

于 2013-03-03T23:42:47.797 に答える