文献

J-GLOBAL ID：202002235993011718   整理番号：20A0425891

高速多重パターン直交木マッチング【JST・京大機械翻訳】

Fast Multiple Pattern Cartesian Tree Matching

著者 (5件)： Gu Geonmo (Seoul National University, Seoul, Korea) ,  Song Siwoo (Seoul National University, Seoul, Korea) ,  Faro Simone (University of Catania, Catania, Italy) ,  Lecroq Thierry (Normandie University, Rouen, France) ,  Park Kunsoo (Seoul National University, Seoul, Korea)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12049  ページ： 107-119  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 直交木マッチングは,与えられたパターンのものと同じデカルトツリーを持つ与えられたテキストにおけるすべてのサブストリングを発見する問題である。本論文では,多重パターンの場合に対するデカルト木マッチングを扱った。2つの指紋法,すなわち,親距離符号化と二値符号化を示した。効率的な指紋法と従来の多重ストリングマッチングアルゴリズムを組み合わせることにより,多重パターンデカルトツリーマッチングを効率的に解くことができる。著者らは,Wu-Manberアルゴリズム,Rabin-Karpアルゴリズム,およびAlpha Skip探索アルゴリズムに基づく多重パターンデカルトツリーマッチングのための3つの実用的アルゴリズムを提案した。実験では,著者らの解を以前のアルゴリズム[18]に対して比較した。著者らの解はパターン長が増加するにつれて以前のアルゴリズムより速く走る。特に,Wu-Manberに基づく著者らのアルゴリズムは,33倍速く動作した。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *多重化 ,  *直交性 ,  フィンガープリント法
準シソーラス用語： 探索アルゴリズム ,  バイナリコード , 【Automatic Indexing@JST】

著者キーワード (4件)： 多重パターン直交木マッチング ,  親距離符号化 ,  二値符号化 ,  指紋法

分類 (1件)： 分子・遺伝情報処理  (JE15040B)

タイトルに関連する用語 (3件)： 多重 ,  木 ,  マッチング