| 講演名 | 2021-05-08 デカルト木照合の部分系列への拡張 加井 丈志(北大), 光吉 健汰(北大), 古谷 勇(北大), 有村 博紀(北大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | デカルト木照合（Cartesian tree matching）は，値の大小関係に基づいて数値系列の照合を行う数値列に対する近似照合問題の一種であり，2019年にParkらによって提案された．本研究では，テキストのとびとびの部分系列にパターンが照合することを許すようにデカルト木照合を拡張した問題を考察し，動的計画法に基づいた効率良いアルゴリズムを与える．さらに，系列の埋め込み（trace）の計算と，滑り窓（sliding window）を用いた拡張についても議論する． |
| 抄録(英) | 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. |
| キーワード(和) | 文字列照合 / 部分系列照合 / 動的計画法 / 滑り窓 |
| キーワード(英) | String alogorithm / subsequence matching / dynamic programming / slinding window |
| 資料番号 | COMP2021-6 |
| 発行日 | 2021-04-30 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2021/5/7(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 増澤 利光(阪大) |
| 委員長氏名（英） | Toshimitsu Masuzawa(Osaka Univ.) |
| 副委員長氏名（和） | 小野 廣隆(名大) |
| 副委員長氏名（英） | Hirotaka Ono(Nagoya Univ) |
| 幹事氏名（和） | 大下 福仁(奈良先端大) / 安藤 映(専修大) |
| 幹事氏名（英） | Fukuhito Ooshita(NAIST) / Ei Ando(Senshu Univ.) |
| 幹事補佐氏名（和） | 大舘 陽太(名大) |
| 幹事補佐氏名（英） | Yota Otachi(Nagoya Univ) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | デカルト木照合の部分系列への拡張 |
| サブタイトル（和） | |
| タイトル（英） | An Extension of Cartesian Tree Matching Based-on Subsequences |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 文字列照合 / String alogorithm |
| キーワード(2)（和/英） | 部分系列照合 / subsequence matching |
| キーワード(3)（和/英） | 動的計画法 / dynamic programming |
| キーワード(4)（和/英） | 滑り窓 / slinding window |
| 第 1 著者 氏名（和/英） | 加井 丈志 / Takeshi Kai |
| 第 1 著者 所属（和/英） | 北海道大学(略称：北大) Hokkaido University(略称：Hokkaido Univ.) |
| 第 2 著者 氏名（和/英） | 光吉 健汰 / Kenta Mitsuyoshi |
| 第 2 著者 所属（和/英） | 北海道大学(略称：北大) Hokkaido University(略称：Hokkaido Univ.) |
| 第 3 著者 氏名（和/英） | 古谷 勇 / Isamu Furuya |
| 第 3 著者 所属（和/英） | 北海道大学(略称：北大) Hokkaido University(略称：Hokkaido Univ.) |
| 第 4 著者 氏名（和/英） | 有村 博紀 / Hiroki Arimura |
| 第 4 著者 所属（和/英） | 北海道大学(略称：北大) Hokkaido University(略称：Hokkaido Univ.) |
| 発表年月日 | 2021-05-08 |
| 資料番号 | COMP2021-6 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | COMP-11 |
| ページ範囲 | pp.39-45(COMP), |
| ページ数 | 7 |
| 発行日 | 2021-04-30 (COMP) |