{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00216131","sets":["1164:2592:10824:10825"]},"path":["10825"],"owner":"44499","recid":"216131","title":["デカルト木部分列照合問題の高速なアルゴリズム"],"pubdate":{"attribute_name":"公開日","attribute_value":"2022-01-20"},"_buckets":{"deposit":"743102df-076c-48d4-825e-644122abb3c3"},"_deposit":{"id":"216131","pid":{"type":"depid","value":"216131","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"デカルト木部分列照合問題の高速なアルゴリズム","author_link":["557585","557587","557584","557586"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"デカルト木部分列照合問題の高速なアルゴリズム"},{"subitem_title":"Efficient Algorithms for Cartesian Tree Subsequence Matching","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2022-01-20","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"北海道大学大学院情報科学院"},{"subitem_text_value":"北海道大学大学院情報科学研究院"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Information Science and Technology, Hokkaido University","subitem_text_language":"en"},{"subitem_text_value":"Faculty of Information Science and Technology, Hokkaido University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/216131/files/IPSJ-AL22186003.pdf","label":"IPSJ-AL22186003.pdf"},"date":[{"dateType":"Available","dateValue":"2024-01-20"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL22186003.pdf","filesize":[{"value":"1.2 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"2a66335d-3a64-412f-b48d-64aea4973ede","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2022 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"大泉, 翼"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"有村, 博紀"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Tsubasa, Oizumi","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hiroki, Arimura","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8566","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"デカルト木照合（Cartesian tree matching）は，値の大小関係に基づいてテキストの連続な部分文字列とパターンの照合を行う近似照合問題の一種であり，2019 年に Park と, Amir, Landau, Park らによって提案された．本研究では，デカルト木照合問題をテキストの非連続な部分系列に拡張して，デカルト木部分列照合問題を提案する．さらに，この問題を O(mn log n) 時間と O(mn) 領域で解く効率の良いアルゴリズムを与える．このアルゴリズムは，動的計画法と区間最小値クエリを組み合わせることで，先行研究の加井らによるアルゴリズムの時間計算量 O(mn3) を大幅に改善している．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2022-01-20","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicVolumeNumber":"2022-AL-186"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":216131,"updated":"2025-01-19T15:54:50.627993+00:00","links":{},"created":"2025-01-19T01:16:51.268167+00:00"}