楽譜検索のための幾何点列の近似パタン照合(<特集>文字列アルゴリズム)
スポンサーリンク
概要
- 論文の詳細を見る
線形変換による点列パタン照合問題は,ユークリッド空間上の2つの点集合パタンPとテキストTが与えられた時,PをTの部分集合に写像する線形変換を見つける問題である.本稿ではまず主軸について昇順の1次元の点列に対して,平行移動と点の間の空間の挿入・削除による編集距離とそれに基づく近似点列パタン照合問題を定義する.次にPのサイズn,Tのサイズmについて時間計算量O(nm^2)で動作する近似点列パタン照合問題のアルゴリズムを紹介し,高速化のための改良を加えたアルゴリズムが有限解像度を持つP,Tに対してO(nm)で動作することを証明する.更に4人のロシア人の方法を応用してO((nm)/(log m)+m log^2 m)時間に高速化する技法を示す.そして,多項式時間で解くことができる2次元近似点列パタン照合を提案する.
- 社団法人電子情報通信学会の論文
- 2004-01-22
著者
関連論文
- BONSAI Garden:学習アルゴリズムによるアミノ酸配列からの並列知識獲得システム
- 断片パターンマッチングの計算量的困難性と近似アルゴリズムについて
- 文字列パターン照合のための損失のあるデータ圧縮
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- Complexity of Finding Alphabet Indexing(Fundamental Studies on Computational Complexity)
- 表面実相ロボットの実相シーケンスの決定に対する巡回セールスマン問題のアルゴリズムの適用
- 楽譜検索のための幾何点列の近似パタン照合(文字列アルゴリズム)
- テキストデータからの高速データマイニング : 探索的文書ブラウジングとウェブデータへの応用(発見科学)
- 生物配列の局所マルチプルアラインメントの計算困難性
- 大規模幾何データからの高速な極大部分グラフ発見 (特集 「ウェブマイニング」および一般)
- Efficient Discovery of Maximal Two-Dimensional Patterns with Don't-Cares(extended abstract) (テーマ:特集「ウェブデータの知的処理」および一般)
- K語近接相関パタンの高速発見アルゴリズム
- On Approximation Algorithms for Local Multiple Alignment (合同研究会"AIシンポジウム'99"(第10回))
- 文字列相関パタンの分類精度最大化問題について
- 省スペースな線形時間文法圧縮アルゴリズム
- DS-1-9 二次元点集合近似照合によるグラフの格子状配置アルゴリズム(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- Minimum Multiset Covering 問題の近似アルゴリズムについて
- 平面巡回セールスマン問題の高速な近似アルゴリズム
- 無矛盾最小OBDD問題の近似困難性について