| 一种适于XPath查询的自动机最小化算法 |
| |
| 引用本文： | 尹燕,陶世群.一种适于XPath查询的自动机最小化算法[J].电脑开发与应用,2009,22(11):3-5. |
| |
| 作者姓名： | 尹燕 陶世群 |
| |
| 作者单位： | 山西大学计算机与信息技术学院,太原,030006 |
| |
| 摘 要： | 近年来,XM L数据流的查询处理引起了国内外学者的广泛兴趣。如何在XM L流中有效地查询大量XPath表达式是当今研究的一个热点问题。先将多个XPath式通过共享前缀处理,构造一个非确定的有穷自动机（NFA）模型,再将其转化为确定的有穷自动机（DFA）,以实现状态转移的确定性,然后对DFA进行最小化,提出了一种普遍适用的改进的最小化算法,在执行效率和空间代价方面它都优于一般性算法。
|
| 关 键 词： | XPath表达式 共享前缀 NFA DFA 最小化 |
An Algorithm of Automata Minimization for XPath Query |
| |
| Yin Yan et al.An Algorithm of Automata Minimization for XPath Query[J].Computer Development & Applications,2009,22(11):3-5. |
| |
| Authors: | Yin Yan |
| |
| Abstract: | In recent years,the query evaluation of XML data stream has attracted scholars' widespread interest at home and abroad.How to effectively implement a large number of XPath expressions over an XML stream is a hot spot in today's research.Firstly,multiple XPaths are constructed a NFA model by sharing the prefix.Secondly the NFA is converted into a DFA,so as to carry on the deterministic of state transform.Then the DFA is minimized and a kind of universal applicable improved minimum algorithm is proposed.Compa... |
| |
| Keywords: | NFA DFA |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
