デカルト木照合の部分系列への拡張

• Item type: SIG Technical Reports(1)
• 公開日: 2021-04-30
• タイトル: デカルト木照合の部分系列への拡張
• タイトル / 言語: en
• タイトル: An Extension of Cartesian Tree Matching Based-on Subsequences
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道大学大学院情報科学院情報科学専攻
• 著者所属: 北海道大学大学院情報科学院情報科学専攻
• 著者所属: 北海道大学大学院情報科学院情報科学専攻
• 著者所属: 北海道大学大学院情報科学研究院
• 著者所属(英): en
• 著者所属(英): Graduate School of IST, Hokkaido University, Japan
• 著者所属(英): en
• 著者所属(英): Graduate School of IST, Hokkaido University, Japan
• 著者所属(英): en
• 著者所属(英): Graduate School of IST, Hokkaido University, Japan
• 著者所属(英): en
• 著者所属(英): Faculty of IST, Hokkaido University, Japan
• 著者名: 加井, 丈志; 光吉, 健汰; 古谷, 勇; 有村, 博紀
• 著者名(英): Takeshi, Kai; Kenta, Mitsuyoshi; Isamu, Furuya; Hiroki, Arimura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: デカルト木照合（Cartesian tree matching）は，値の大小関係に基づいて数値系列の照合を行う数値列に対する近似照合問題の一種であり，2019 年に Park らによって提案された．本研究では，テキストのとびとびの部分系列にパターンが照合することを許すようにデカルト木照合を拡張した問題を考察し，動的計画法に基づいた効率良いアルゴリズムを与える．さらに，系列の埋め込み（trace）の計算と，滑り窓（sliding window）を用いた拡張についても議論する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we consider the Cartesian tree matching problem, originally introduced by Park et al. in 2019. Despite of its usefulness in finance data analysis, the requirement for consecutive substrings seems too rigid to handle real world sequences with potential errors. By relaxing this requirement, we propose its extension, called Cartesian tree subsequence matching problem, where we allow patterns to match non-consecutive subsequences of a text sequence rather than consecutive substrings. For this new problem, we propose an efficient algorithm based on dynamic programming for the problem. Furthermore, we also presented algorithms for computing traces of matching, and for the sliding window version of the matching problem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2021-AL-183, 号 12, p. 1-7, 発行日 2021-04-30
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会