講演名 | 2008-10-10 制限されたラベルをもつ木に対するビット並列型木パターン照合アルゴリズム 山本 博章, 竹之内 大地, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 次のような木パターン照合問題を考える:2つのラベル付き無順序木がPとTが与えられたとき、TにおけるPの出現をすべて見つけよ。本論文では、ラベルが非再帰的であるPに対し、効率的な木パターン照合アルゴリズムを設計する。まず、擬似パターン照合という条件を導入し、この条件のもとで効率的なアルゴリズムを設計する。次に、このアルゴリズムを木パターン照合アルゴリズムへと拡張する。 |
抄録(英) | The following tree pattern matching problem is considered: Given two unordered labeled trees P and T, find all occurrences of P in T. Here P and T are called a pattern tree and a target tree, respectively. In general, it is more difficult to design an efficient algorithm for unordered trees than for ordered trees. In this paper, we will consider a pattern tree P with non-recursive labels. Then we first introduce a new problem called the pseudo-tree pattern matching problem, and show an efficient bit-parallel algorithm which finds out all pseud-occurrences of P in T. Our algorithm runs in linear time if a pattern tree P is small. Furthermore, we extend our algorithms to a tree pattern matching algorithm. |
キーワード(和) | 木パターン照合アルゴリズム / 無順序木 / 非再帰的ラベル / ビット並列アルゴリズム |
キーワード(英) | tree pattern matching algorithm / unordered tree / non-recursive label / bit-parallel algorithm |
資料番号 | COMP2008-34 |
発行日 |
研究会情報 | |
研究会 | COMP |
---|---|
開催期間 | 2008/10/3(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Theoretical Foundations of Computing (COMP) |
---|---|
本文の言語 | ENG |
タイトル(和) | 制限されたラベルをもつ木に対するビット並列型木パターン照合アルゴリズム |
サブタイトル(和) | |
タイトル(英) | Bit-Parallel Tree Pattern Matching Algorithms for Trees with Restricted Labels |
サブタイトル(和) | |
キーワード(1)(和/英) | 木パターン照合アルゴリズム / tree pattern matching algorithm |
キーワード(2)(和/英) | 無順序木 / unordered tree |
キーワード(3)(和/英) | 非再帰的ラベル / non-recursive label |
キーワード(4)(和/英) | ビット並列アルゴリズム / bit-parallel algorithm |
第 1 著者 氏名(和/英) | 山本 博章 / Hiroaki YAMAMOTO |
第 1 著者 所属(和/英) | 信州大学工学部 Faculty of Engineering, Shinshu University |
第 2 著者 氏名(和/英) | 竹之内 大地 / Daichi TAKENOUCHI |
第 2 著者 所属(和/英) | NTTアドバンステクノロジ株式会社 NTT Advanced Technology Corporation |
発表年月日 | 2008-10-10 |
資料番号 | COMP2008-34 |
巻番号(vol) | vol.108 |
号番号(no) | 237 |
ページ範囲 | pp.- |
ページ数 | 8 |
発行日 |