文字列シーケンス最短マッチング問題

DOI

書誌事項

タイトル別名
  • Shortest Matching of String Sequences Problem

抄録

本論文は，文字列シーケンス最短マッチング問題という，基本的な文字列処理の問題を扱う．この問題では，基準となる文字列シーケンスSと操作対象となる文字列シーケンスTが与えられる．このとき，Tの区切り位置を変更して得られる文字列シーケンスのうち，Sと同じサイズで編集距離が最小のものを求める．この問題の解法として動的計画法による最適解を求めるアルゴリズムと高速に近似解を得るためのGreedyなアルゴリズムを提案する．また，実用性を考慮し，計算範囲のサイズをパラメータとして指定できる改良版のGreedyアルゴリズムを提案する．後半では，文字列シーケンスTに対して部分文字列シーケンスの移動操作を伴う文字列シーケンスの最短マッチング問題はNP完全であることを証明する．そこで，移動操作を1回で，尚かつ性質の良いものに限定した問題を考察し，これを多項式時間で解くアルゴリズムを提案する．

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1390860222070371840
  • DOI
    10.14923/transinfj.2022jdp7043
  • ISSN
    18810225
    18804535
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ