Exact-matchとINexact-match、バックトラッキング

• Exact-match
  • BW行列は辞書式順序で並んでいる
  • これを利用する
    • あるクエリー配列の末尾の１文字を見て、その文字がBW行列の左端に来ている行を選択する
    • それを満足する行数を数える(それらは固まって存在している）
    • 次いで、クエリー配列の末尾から１、２文字目を見て、一致する行を確認する。このとき、一致する行数は前のステップの一致行数以下である
    • 繰り返しの仮定で、考慮するべき行数が減っていく
• INexact-match
  • Exact-match探索は上記のように単純で軽くて速いので、実施する
  • そうすると、Exact-matchの断片の集まりになる
  • 合わないところを「合っていることにして」やりなおし
  • 結果としてうまくはまれば、OK
  • ただし、どれだけ「合っていることにしてやりなおす」かを条件で与える
  • この「合っていることにする」ときに、データの質を考慮することで、データの質を取り込むこともできる
• バックトラッキング
  • やりなおしで行ったり来たりすることは、Exact-matchが「先すぼまりに一致を検出する」という仕組みで「軽い処理」にしていた部分を生殺しにする効果があるので、バックトラッキングをうまくやることは、処理全体の効率に影響する