RETE算法并行化改进及在大规模规则匹配场景中的应用

摘要：RETE算法是一个用来实现产生式规则系统的高效模式匹配算法。该算法是由卡内基梅隆大学的Charles L.Forgy在1974年发表的论文中所阐述的算法。RETE算法提供了专家系统的高效实现。RETE作为一种高效的模式匹配算法，在规则引擎方面起着至关重要的作用，同时因为其效率与数据量和规则成线性关系，从而在处理海量数据中可以良好的性能。本课题设计并实现并行化Rete算法，验证改进的算法在大数据处理场景中实时规则匹配的效率。21449
关键词 RETE算法模式匹配并行化
毕业论文设计说明书（论文）外文摘要
Title   Rete algorithm parallelization improvement and application in large-scale rules matching scenarios
Abstract
Rete algorithm is an efficient pattern matching algorithm，which is used to implement the production rule system. The algorithm is created by Charles L.F orgy from Carnegie Mellon university. The algorithm was firstly published in a paper in 1974. Rete algorithm provides an efficient implementation of expert system. Rete, as a kind of efficient pattern matching algorithm, plays a vital role in the rules engine. Because of its efficiency is in a linear relationship with rules and the amount of data, it has a good performance in dealing with huge amounts of data. The goal of this subject is designing and implementing the parallel algorithm of Rete, and verifying the rule matching efficiency of the improved algorithm in real-time data processing.
Keywords: Rete algorithm   pattern matching parallelization
目录
1 绪论   1
1.1 研究背景   1
1.2 研究意义   1
1.3 本文结构   1
2 相关发展及其研究现状   3
2.1 RETE算法简介   3
2.2 RETE算法相关发展   5
2.3 并行化研究   8
2.4 大规模数据处理   9
3 并行化RETE算法设计   10
3.1 鉴别网络   10
3.2 规则匹配   11
3.3 RETE算法并行化   12
4 并行化RETE算法实现   13
4.1 鉴别网络设计   13
4.2 规则匹配   22
4.3 并行化实现   24
5 性能测试   25
5.1 开发环境   25
5.2 程序总体架构   25
5.3 鉴别网络构建   26
5.4 并行化具体实现   27
5.5 实验结果及性能分析   27
6 结论与展望   31
6.1 所得结论   31
6.2 后续工作的设想   31
致谢   33
参考文献   34

1 绪论
1.1 研究背景
    基于规则的系统（Rule-Based System,简记为RBS）用于规则的模式匹配上的时间超过了运行总时间的90%以上。由此可以看出，对于RBS效率至关重要的就是其中的模式匹配的效率。目前基于正向链推理最有效的算法，就是由Charles L. Forgy在1974年首次提出的RETE算法。而后在1979年的博士论文和1982年的论文中进行了详细的介绍。RETE是拉丁文，对应在英文中是网络的意思，即为net。RETE算法被应用于很多商业规则引擎中，如JESS, Drools和soar等。该算法是专家系统有效实施的基础，并被广泛应用在基于规则的专家系统中。目前绝大部分的RBS在模式匹配方面都采用了RETE算法。随着日益普及的物联网和云计算技术的到来，将会实时地产生大量富含语义信息的数据，这其中的难点就是如何快速处理这些海量数据。RETE算法是一种高效匹配的模式匹配算法，因为它的效率与数据量和规则成线性关系，因此当它在处理海量数据中有着良好的性能。 RETE算法并行化改进及在大规模规则匹配场景中的应用:http://www.youerw.com/jisuanji/lunwen_13657.html