高速に類似文字列ペアを発見するビット並列フィルター

• 山田, 太樹

• 清水, 佳奈

抄録

類似する文字列ペアの発見は様々な分野において重要な課題である.本稿では,長さがそれぞれn, m(ただし,n ≥ mとする)の文字列が与えられた場合に,編集距離が閾値θ以内であるか否かを判定する手法を提案する.編集距離そのものを高速に計算する従来研究では,Myersによるワード長wのときO(nm/w)を達成するビット並列アルゴリズムが知られている.これに対して我々は,鳩ノ巣原理に基づく効果的なフィルターFを構成し,Fが受理したペアに対してのみ編集距離を計算する手法を提案する.Fはビット並列によりO(θn/w)で計算可能なため,類似性の低いペアが多く含まれるデータセットに対して非常に高速に動作する.10,000本のゲノム配列から類似ペアを全列挙したところ,Myersの手法と比較して17倍程度,ビット並列を用いずに編集距離を計算した場合と比較して100倍程度高速であった.

収録刊行物

• 第80回全国大会講演論文集

  第80回全国大会講演論文集 2018 (1), 355-356, 2018-03-13

キーワード

• ソフトウェア科学・工学

詳細情報

• CRID: 1050011097170028800
• NII論文ID: 170000176716
• NII書誌ID: AN00349328
• Web Site: http://id.nii.ac.jp/1001/00187617/
• 本文言語コード: ja
• 資料種別: conference paper
• データソース種別:
  • IRDB
  • CiNii Articles