基于RETE网的句法分析算法研究

RETE-based parsing algorithm

结构消歧是句法分析的一项重要任务。研究表明,增加复杂特征有利于提高句法分析系统的消歧能力。但相对于不包含复杂特征的句法分析系统,包含复杂特征规则的系统,通常规则数量较大,规则的匹配和存贮成为句法分析算法面临的一个问题。提出一种基于RETE网的高效可并行的句法分析算法。该算法将复杂特征规则转换为RETE匹配网,从而实现规则的高效存贮和快速匹配。实验表明,该算法可以有效组织大量多特征规则,并进行高速句法分析。

Structure ambiguity is key issues in parsing. In order to solve this problem, most parsing systems adopt multi-features rules. Comparing with the simple context-free rules, the multi-features rules include more linguistic information to solve ambiguities which can not be solved by context-free rules. But the form of the multi-fea- tures rules is more complex than context-free rules. And the amount is far more than the amount of context-free rules. Saving and matching them is difficult. In this paper, we propose a RETE-based parsing algorithm to solve above problems. The rules can be stored and searched in RETE net effectively. The experiments show our algorithm can speed up the rule matching and finally improve the performance of whole parsing algorithm.