《模式匹配装置、模式匹配方法和模式匹配系统的制作方法》由会员分享，可在线阅读，更多相关《模式匹配装置、模式匹配方法和模式匹配系统的制作方法（20页珍藏版）》请在金锄头文库上搜索。
1、模式匹配装置、模式匹配方法和模式匹配系统的制作方法专利名称：模式匹配装置、模式匹配方法和模式匹配系统的制作方法技术领域：本发明涉及模式匹配装置、模式匹配方法和模式匹配系统，具体涉及产生匹配树的模式匹配装置、模式匹配方法和模式匹配系统。背景技术：关于模式匹配，已知多种相关技术。作为相关技术的一个示例，专利文献I公开了一种处理事件的方法和系统。专利文献I描述的处理事件的方法和系统包括基于从一个以上事件消费者接收的一个以上订阅的过滤树(filter tree)。并且，专利文献I描述的处理事件的方法和系统使用过滤树来比较事件通知，并基于结果进行处理，将事件通知传送至的事件消费者的范围缩小。 作为相关技
2、术的另一示例，非专利文献I公开了一种发布/订阅(publish/subscribe)系统中的事件匹配算法。非专利文献I中描述的事件匹配算法是在产生事件时判定该事件与哪个订阅匹配的算法。该算法由图50所示树结构的系统900实现。系统900包括节点901和边904，并且表示用于判断事件是否与订阅匹配的条件。节点901中的叶子节点903与订阅(subl_sub3) 907有关。除叶子节点903之外的每个节点901被给予作为事件的构成要素的属性名称905。边904连接父节点901和子节点901，并且给予边904的属性值906与给予父节点901的属性名称(attrl-attr3)905对应。当某个事件输
3、入系统900时，系统900首先查看输入的事件。然后系统900获取与给予根节点902的属性名称905对应的属性值906。在获取的属性值906与给予边904的属性值906中任一属性值906匹配的情况下，系统900使子节点901和孙子节点901分别成为父节点901和子节点901，并执行与上述类似的处理，其中所述边904连接根节点902及其子节点901。在这样重复执行上述处理，并最终达到叶子节点903的情况下，系统90判定与叶子节点903有关的订阅907作为相关事件所匹配的订阅907。此外，在边904被给予*的情况下，无论输入事件的属性值906如何，系统900均前进至对子节点901的处理。作为具体示例
4、，下面描述事件“ATTR1 = Vl ,ATTR2 = V2，ATTR3 = V3 ”输入到系统900的情况，如图50所示。首先，系统900获取事件的与根节点902的属性名称905 “ATTR1”相对应的属性值906 “VI ”。接着，系统900检测到其属性值906 “VI ”与给予边904的属性值906匹配的子节点901 (其属性名称905是“ATTR2”)。接下来，系统900获取事件的与节点901的属性名称905 “ATTR2”相对应的属性值906 “V2”。然后，系统900检测到其属性值906 “V2”与给予边904的属性值906匹配的子节点901 (其属性名称905是“ATTR3”)。
5、接下来，系统900获取事件的与节点901的属性名称905 “ATTR3”相对应的属性值906 “V3, ”。然后，系统900检测到属性值906 “V3, ”与给予边904的任何属性值906均不匹配。系统900结束处理。S卩，在该示例中，无匹配的订阅907,退出。专利文献专利文献I日本专利申请特开No.2003-316610非专利文献非专利文献 1M.K.AGUILERA，R.E.STR0M，D.C.STURMAN，M.ASTLEY，ANDT. D. CHANDRA MATCHING EVENTS IN A CONTENT-BASED SUBSCRIPTION SYSTEM, INPROC. 1
6、8TH ANNUAL ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING,PP. 53-61(1999).发明内容本发明要解决的技术问题然而，在上述公开的技术中，存在这样的问题用于例如事件等的匹配判定的匹配树的结构可能不是最优的。原因在于过滤树或树结构系统的构建没有考虑到事件与节点和边的属性名称和属性值匹配的概率。S卩，在过滤树或树结构系统构建为使得在根节点周围存在属性值匹配的边，而在叶子节点周围不存在属性值匹配的边的情况下，在根节点周围执行的属性值的匹配判定处理因此变得无用。此外，执行事件不与订阅匹配的判定所需的时间变得较长。本发明的目的
7、是解决上述问题，并提供模式匹配装置、模式匹配方法和模式匹配系统，其产生对于高效执行模式匹配判定而言最优的事件模式匹配树。解决问题的手段本发明的模式匹配装置包括事件模式表保持部，保持包括部分事件模式的至少一个事件模式，所述部分事件模式包括第一属性名称和属性值；第一匹配率测量部，基于包括属性的事件和事件模式表保持部中保持的所述事件模式，测量与所述第一属性名称相对应的第一匹配率，其中所述属性包括第二属性名称和属性值；以及事件模式匹配树生成部，基于事件模式表保持部中保持的所述事件模式以及所述第一匹配率，生成事件模式匹配树，所述事件模式匹配树将包括相应匹配率相对较低的所述第一属性名称在内的属性值匹配判定
8、实例排列在相对较高级别。本发明的模式匹配方法包括基于包括属性的事件以及事件模式表保持部中保持的包括部分事件模式的事件模式，测量与所述部分事件模式中包括的第一属性名称相对应的匹配率，其中所述属性包括第二属性名称和属性值，所述部分事件模式包括所述第一属性名称和属性值；以及基于事件模式表保持部中保持的所述事件模式以及所述第一匹配率，生成事件模式匹配树，所述事件模式匹配树将包括相应匹配率相对较低的所述第一属性名称在内的属性值匹配判定实例排列在相对较高级别。本发明的介质中记录的程序，使计算机执行如下处理基于包括属性的事件以及、事件模式表保持部中保持的包括部分事件模式的事件模式，测量与所述部分事件模式中包
9、括的第一属性名称相对应的匹配率，其中所述属性包括第二属性名称和属性值，所述部分事件模式包括所述第一属性名称和属性值；以及基于事件模式表保持部中保持的所述事件模式以及所述第一匹配率，生成事件模式匹配树，所述事件模式匹配树将包括相应匹配率相对较低的所述第一属性名称在内的属性值匹配判定实例排列在相对较高级别。本发明的模式匹配系统包括事件模式表保持部，保持包括部分事件模式的至少一个事件模式，所述部分事件模式包括第一属性名称和属性值；第一匹配率测量部，基于包括属性的事件和事件模式表保持部中保持的所述事件模式，测量与所述第一属性名称相对应的第一匹配率，其中所述属性包括第二属性名称和属性值；以及事件模式匹配
10、树生成部，基于事件模式表保持部中保持的所述事件模式以及所述第一匹配率，生成事件模式匹配树，所述事件模式匹配树将包括相应匹配率相对较低的所述第一属性名称在内的属性值匹配判定实例排列在相对较高级别。本发明的效果 本发明的效果在于能够产生对于高效执行模式匹配判定而言最优的事件模式匹配树。图I是示出了本发明第一示例实施例的结构的框图。图2是示出了本发明第一到第五示例实施例中事件的结构和内容示例的图。图3是示出了本发明第一到第五示例实施例中事件模式的结构和内容示例的图。图4是示出了本发明第一到第四示例实施例中事件模式登记请求的结构和内容示例的图。图5是示出了本发明第一到第四示例实施例中事件模式登记请求的
11、结构和内容示例的图。图6是示出了本发明第一到第四示例实施例中事件模式删除请求的结构和内容示例的图。图7是示出了本发明第一到第四示例实施例中事件模式删除请求的结构和内容示例的图。图8是示出了本发明第一到第五示例实施例中事件模式匹配树的结构的图。图9是示出了本发明第一到第五示例实施例中属性值匹配判定实例的结构的图。图10是示出了本发明第一到第五示例实施例中哈希表的结构的图。图11是示出了本发明第一到第五示例实施例中事件通知实例的结构的图。图12是示出了本发明第一、第三和第五示例实施例中匹配率测量表的结构的图。图13是示出了本发明第一到第五示例实施例中事件模式表的结构和内容示例的图。图14是示出了本
12、发明第一示例实施例中事件匹配操作的流程图。图15是示出了本发明第一示例实施例中事件匹配操作的流程图。图16是示出了本发明第一示例实施例中事件匹配操作的流程图。图17是示出了本发明第一示例实施例中事件匹配操作的流程图。图18是示出了本发明第一示例实施例中事件匹配操作的流程图。图19是示出了本发明第一示例实施例中事件模式匹配树141的组织和重组操作的流程图。图20是示出了本发明第一示例实施例中事件模式匹配树141的组织和重组操作的流程图。图21是示出了本发明第一示例实施例中事件模式匹配树141的组织和重组操作的流程图。图22是示出了本发明第一到第五示例实施例中事件模式匹配树示例的图。 图23是示出
13、了本发明第一示例实施例中匹配率测量表示例的图。图24是示出了本发明第一示例实施例中匹配率测量表示例的图。图25是示出了本发明第一示例实施例中事件模式匹配树示例的图。图26是示出了本发明第一示例实施例中事件模式匹配树示例的图。图27是示出了本发明第一示例实施例中事件模式匹配树示例的图。图28是示出了本发明第一示例实施例中事件模式匹配树示例的图。图29是示出了本发明第二示例实施例的结构的框图。图30是示出了本发明第二和第三示例实施例中匹配率测量表的结构和内容示例的图。图31是示出了本发明第二和第三示例实施例中匹配率测量表示例的图。图32是示出了本发明第二示例实施例中事件模式登记操作的流程图。图33
14、是示出了本发明第二示例实施例中事件模式删除操作的流程图。图34是示出了本发明第二示例实施例中所参考的实例是属性值匹配判定实例的情况下属性匹配判定操作的流程图。图35是示出了本发明第二示例实施例中更新与每个属性名称相对应的匹配率的操作的流程图。图36是示出了第一示例实施例中事件模式匹配树以及与每个属性名称相对应的匹配率的示例的图，用于描述本发明第二示例实施例的效果。图37是示出了第一示例实施例中事件模式匹配树以及与每个属性名称相对应的匹配率的示例的图，用于描述本发明第二示例实施例的效果。图38是示出了本发明第三示例实施例的结构的框图。图39是示出了本发明第三示例实施例中请求事件模式匹配树的重组(
15、reorganization)的操作的流程图。图40是示出了本发明第三示例实施例中匹配率测量部从树重组管理部接收匹配率测量开始请求的情况下操作的流程图。图41是示出了本发明第三示例实施例中匹配率测量部从树重组管理部接收匹配率测量结束请求的情况下操作的流程图。图42是示出了本发明第三示例实施例中事件接收部从匹配率测量部接收事件传输开始请求的情况下操作的流程图。图43是示出了本发明第三示例实施例中事件接收部从匹配率测量部接收事件传输结束请求的情况下操作的流程图。图44是示出了本发明第三示例实施例中事件接收时的操作的流程图。图45是示出了本发明第三示例实施例中匹配率测量表的示例的图。图46是示出了本
16、发明第四示例实施例的结构的框图。图47是示出了本发明第四示例实施例中树重组管理部请求事件模式匹配树的重组的操作的流程图。图48是示出了本发明第四示例实施例中树根属性匹配率测量部更新匹配率测量表131的操作的流程图。图49是示出了本发明第五示例实施例的结构的框图。图50是示出了背景技术中非专利文献I的系统构思的图。图51是示出了使用本发明的计算机设备的示例实施例的结构框图。具体实施例方式下面参照附图详细描述本发明的示例实施例。第一示例实施例图I是示出了本发明第一示例实施例的结构的框图。参照图1，该示例实施例包括事件模式匹配判定系统(也称为模式匹配系统)100、事件输入操作方820、事件接收方830和事件模式管理方840。事件模式匹配判定系统100包括事件模式匹配判定部110、事件模式匹配树生成部120、树相关匹配率测量部(也称为匹配率测量部)130、事件模式匹配树保持部140、事件模式表保持部150以及事件模式接收部160。事件输入操作方820、事件接收方830和事件模式管理方840分别是人(事
