文字列シーケンス最短マッチング問題
書誌事項
- タイトル別名
-
- Shortest Matching of String Sequences Problem
抄録
本論文は,文字列シーケンス最短マッチング問題という,基本的な文字列処理の問題を扱う.この問題では,基準となる文字列シーケンスSと操作対象となる文字列シーケンスTが与えられる.このとき,Tの区切り位置を変更して得られる文字列シーケンスのうち,Sと同じサイズで編集距離が最小のものを求める.この問題の解法として動的計画法による最適解を求めるアルゴリズムと高速に近似解を得るためのGreedyなアルゴリズムを提案する.また,実用性を考慮し,計算範囲のサイズをパラメータとして指定できる改良版のGreedyアルゴリズムを提案する.後半では,文字列シーケンスTに対して部分文字列シーケンスの移動操作を伴う文字列シーケンスの最短マッチング問題はNP完全であることを証明する.そこで,移動操作を1回で,尚かつ性質の良いものに限定した問題を考察し,これを多項式時間で解くアルゴリズムを提案する.
収録刊行物
-
- 電子情報通信学会論文誌D 情報・システム
-
電子情報通信学会論文誌D 情報・システム J106-D (9), 435-444, 2023-09-01
The Institute of Electronics, Information and Communication Engineers
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390860222070371840
-
- ISSN
- 18810225
- 18804535
-
- 本文言語コード
- ja
-
- データソース種別
-
- JaLC
-
- 抄録ライセンスフラグ
- 使用不可