デカルト木部分列照合問題の高速なアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2022-01-20
• タイトル: デカルト木部分列照合問題の高速なアルゴリズム
• タイトル / 言語: en
• タイトル: Efficient Algorithms for Cartesian Tree Subsequence Matching
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道大学大学院情報科学院
• 著者所属: 北海道大学大学院情報科学研究院
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Faculty of Information Science and Technology, Hokkaido University
• 著者名: 大泉, 翼; 有村, 博紀
• 著者名(英): Tsubasa, Oizumi; Hiroki, Arimura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: デカルト木照合（Cartesian tree matching）は，値の大小関係に基づいてテキストの連続な部分文字列とパターンの照合を行う近似照合問題の一種であり，2019 年に Park と, Amir, Landau, Park らによって提案された．本研究では，デカルト木照合問題をテキストの非連続な部分系列に拡張して，デカルト木部分列照合問題を提案する．さらに，この問題を O(mn log n) 時間と O(mn) 領域で解く効率の良いアルゴリズムを与える．このアルゴリズムは，動的計画法と区間最小値クエリを組み合わせることで，先行研究の加井らによるアルゴリズムの時間計算量 O(mn3) を大幅に改善している．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Park, Amir, Landau, and Park proposed in 2019 an approximate matching problem for numerical sequences, called the Cartesian tree matching problem, that asks to find a consecutive substring of a text string that matches a pattern string based on their Cartesian trees. In this paper, we study an extension of the Cartesian tree matching problem from consecutive substrings to non-consecutive subsequences, called the Cartesian tree subsequence matching problem. Then, we present an efficient dynamic programming algorithm that runs in O(mn log n) time and O(mn) space, which improves on the previous O(mn3) time and space algorithm by Kai et al.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-186, 号 3, p. 1-8, 発行日 2022-01-20
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会