Design of fast tree pattern matching algorithms using bit-parallelism on strings

利用字符串位并行性的快速树模式匹配算法的设计

• 批准号: 21500010
• 负责人: YAMAMOTO Hiroaki
• 金额: $ 2.83万
• 依托单位: Shinshu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500010/
• 关键词: アルゴリズム; パターン照合; 木パターン; ビット並列; 検索; 木パターン照合; 文字列パターン照合; ビット並列アルゴリズム; XML; 拡張疑似木パターン照合問題; XML検索; XPath; 木パターン照合問題; 情報検索

In this research, the following tree pattern matching problem is considered : Given two unordered labeled trees P and T, the problem is to find out all occurrences of P in T. Here P and T are called a pattern tree and a data tree, respectively. We developed efficient algorithms for the tree pattern matching problem by taking advantage of bit-parallelism on a string matching problem.

在本研究中，我们考虑以下的树模式匹配问题：给定两棵无序的标记树P和T，问题是找出P在T中的所有出现。这里P和T分别被称为模式树和数据树。我们开发了有效的算法，树模式匹配问题，利用位并行的字符串匹配问题。

项目成果

記号列のラベルをもつ拡張擬似木パターンマッチング

与字符串标签匹配的扩展伪树模式

• 发表时间: 2011
• 作者: Y.Tanaka;Y.Shibata;Koichi Kobayashi and Kunihiko Hiraishi;山本博章,宮嵜敬
• 通讯作者: 山本博章,宮嵜敬

双対型positionオートマトンを用いたコンパクトなDFA表現

使用双位置自动机的紧凑 DFA 表示

• 发表时间: 2011
• 作者: T. Arai;Y. Inoue;C. Sugimoto;A. Matsumuro;Y. Iwaki;M. Hirose;M. Kitaichi;M. Akira;S. Hayashi;K. Nakata;M. Sakatani;山本博章,中村彰吾
• 通讯作者: 山本博章,中村彰吾

双対型positionオートマトンを利用したコンパクトなDFA表現

使用双位置自动机的紧凑 DFA 表示

• 发表时间: 2011
• 作者: Y.Tanaka;Y.Kikuchi;T.Araki;Y.Shibata;山本博章
• 通讯作者: 山本博章

無順序木パターン照合に対するビット並列アルゴリズム

无序树模式匹配的位并行算法

• 发表时间: 2010
• 作者: Y. Inoue;T. Arai;M. Kitaichi;M. Akira;K. Nakata;R. Tazawa;J. Otsuka;M. Hirose;A. Matsumuro;M. Sakatani;山本博章
• 通讯作者: 山本博章

Bit-parallel Tree Prttern Matching Algorithms for Unordered Labeled Trees

无序标记树的位并行树模型匹配算法

• 发表时间: 2009
• 期刊: Proc.of WADS 2009, Lecture Notes in Computer Science 5664
• 作者: H.Yamamoto;D.Takenouchi
• 通讯作者: D.Takenouchi