12/6 第9回 パターン認識入門(2)

前回までの補足

• 講義のスライド(PDF形式)は，cfiveの「情報科学(水4)」のコースの「教材」のところからダウンロード可能にしてある．講義受講者以外への再配布は許可されないので注意すること．

前回の課題について

• 12/6 13:30の時点で2名が提出．ただし，残念ながら2名とも講義で説明したのよりも効率の悪いアルゴリズムを用いている．間違った答えを出す可能性のあるアルゴリズムもある．
• 部分文字列同士の類似度を講義の説明のように配列で持つのが動的計画法の肝で，メソッドにすると効率が非常に悪くなる．ただし，メモ化という手段で動的計画法と同じ レベルまで持ってくることは可能．

# s0 のi-1文字目と s1のj文字目の類似度を返す
def q(s0,s1,i,j)
  if s0[i-1]==s1[j-1]
    return 2
  else
    return -1
  end
end

# 文字列sをi文字目の前に"-"をgap[i]個出力しながら出力する．
def show_align s,gap
  for i in 0..(s.length-1)
    # "-"をgap[i]個出力する
    ?(1)?
    print s[i..i]
  end
  puts "-"*gap[s.length]
end

# 文字列s0とs1のalignmentを出力後に類似度を返す
def alignment s0,s1
  m=s0.length
  n=s1.length
  g=-2
  a=Array.new(m+1)
  for i in 0..m
    a[i]=Array.new(n+1,0)
  end
  for i in 1..m
    # 「境界条件」のスライドに従って設定
    ?(2)?
  end
  for j in 1..n
    # 「境界条件」のスライドに従って設定
    ?(3)?
  end
  for i in 1..m
    for j in 1..n
      # 「アラインメントの動的計画法の」のスライドに従って，値を設定
      a[i][j]= ?(4)?
    end
  end
  gap0=Array.new(m+1,0);
  gap1=Array.new(n+1,0);
  # 「トレースバック」のスライドを元に gap0, gap1 を埋める
  # スライドでは省略されていたが，最後に
  # gap0[0]=j
  # gap1[0]=i
  # を入れる必要がある．
  ?(5)?
  show_align s0,gap0
  show_align s1,gap1
  a[m][n]
end