お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2021-05-08 11:00
デカルト木照合の部分系列への拡張
加井丈志光吉健汰古谷 勇有村博紀北大COMP2021-6
抄録 (和) デカルト木照合(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 / / / /  
文献情報 信学技報, vol. 121, no. 11, COMP2021-6, pp. 39-45, 2021年5月.
資料番号 COMP2021-6 
発行日 2021-04-30 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2021-6

研究会情報
研究会 COMP IPSJ-AL  
開催期間 2021-05-07 - 2021-05-08 
開催地(和) オンライン開催 
開催地(英) Online 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2021-05-COMP-AL 
本文の言語 日本語 
タイトル(和) デカルト木照合の部分系列への拡張 
サブタイトル(和)  
タイトル(英) An Extension of Cartesian Tree Matching Based-on Subsequences 
サブタイトル(英)  
キーワード(1)(和/英) 文字列照合 / String alogorithm  
キーワード(2)(和/英) 部分系列照合 / subsequence matching  
キーワード(3)(和/英) 動的計画法 / dynamic programming  
キーワード(4)(和/英) 滑り窓 / slinding window  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第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.)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2021-05-08 11:00:00 
発表時間 30 
申込先研究会 COMP 
資料番号 IEICE-COMP2021-6 
巻番号(vol) IEICE-121 
号番号(no) no.11 
ページ範囲 pp.39-45 
ページ数 IEICE-7 
発行日 IEICE-COMP-2021-04-30 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会