- 浏览: 898441 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (537)
- Java SE (114)
- Struts (18)
- Hibernate (25)
- Spring (3)
- Page_Tech (41)
- Others (87)
- Database (29)
- Server (24)
- OpenSource_Tools (15)
- IDE_Tool (22)
- Algorithm (28)
- Interview (22)
- Test (28)
- Hardware (1)
- Mainframe (25)
- Web application (4)
- Linux (3)
- PHP (17)
- Android (1)
- Perl (6)
- ubuntu (1)
- Java EE (9)
- Web Analysis (5)
- Node.js (2)
- javascript (2)
最新评论
-
一键注册:
request.getRequestURL()和request.getRequestURI() -
SuperCustomer:
...
SED的暂存空间和模式空间 -
juyo_ch:
讲得挺好理解的,学习了
java 死锁及解决 -
chinaalex:
最后一题答案正确,但是分析有误.按照如下过程,上一行为瓶,下一 ...
zz智力题 -
liaowuxukong:
多谢博主啦,弱弱的了解了一点。
C++/Java 实现多态的方法(C++)
4.6 连接节点(Join node)
当一个连接节点的alpha内存中加入一个事实时,将引发此连接节点的right activation,当一个连接结点的beta内存中加入一个token时,将引发此连接节点的left activation。
连接节点的数据结构包括:指向其alpha内存和beta内存的指针,变量连接检测的说明,指向子节点的指针。
当一个连接节点的alpha内存中加入某个事实时,引发right activation。此处,因为right activation 的顺序不同,有可能产生冗余tokens(即在同一个beta内存里存储有两个或以上的相同的token)。结果这个问题的方法有:每次在beta内存中加入一个新的token时,都检测是否已存在相同的token。这个方法的缺点就是使系统的处理速度变慢。另外一个较好的方法是把right activation的顺序确定下来。
4.7 去除事实(Removals of facts)
Tambe, M., Kalp, D., and Rosenbloom,P. (1991). Uni-Rete: Specializing the Rete match algorithm for the unique-attribute representation. Technical Report CMU-CS-91-180,School of Computer Science, Carnegie Mellon University. Tambe, M., Kalp, D., and Rosenbloom,P. S. (1992). An effcient algorithm for production systems with linear-time match. In Proceedings of the Fourth IEEE International Conference on Tools with Artiial Intelligence, pages 36-43.) Uni-Rete:一种特有属性表示法(unique-value)的特殊Rete匹配算法 使用上面的右图来说明Uni-Rete的添加和删除某个事实的操作。假设图中的事实w6和w8尚未添加,下面加入事实w6:
当某个事实从工作内存总删除时,需要更新含有此事实的alpha内存和beta内存,有以下几种方法。
在原始的rete算法中,删除操作和添加操作采用同一种方式。称此方式为rematch-based removal。主要思想是给每个添加或删除操作一个tag,用来表明此操作是添加事实或删除事实。删除操作的具体执行过程同上面讨论的添加一个事实的过程类似。此方法与其他方法相比,速度较慢。因为删除操作与添加操作的工作量几乎相同。在添加事实过程中所获得的信息并没有在执行删除操作时加以利用。下面有三种改进的算法。
在scan-based removal中,当一个连接节点的alpha内存中的某个事实w被去除时,把w传给此连接节点的输出内存,在此内存中寻找最后一个元素为w的tokens,将这些tokens删除,并且把这些tokens传给此连接节点的子节点。在在子节点中做类似删除操作。(Scales,1986)通过使用此方法代替原有方法,获得28%的加速。(Barachini,1991)获得了10%的加速。
在list-base removal和tree-based removal中使用了这样一个原理,即给事实集合以及tokens的数据结构上增添额外的指针,当某个事实被删除时,可以沿着这些指针删除需要删除的元素。
在list-based removal(Scales ,1986)中,把每个事实w上添加一个包含此事实的tokens的链表。当w被删除时,只要沿着此链表删除这些tokens。缺点就是需要大量的空间来存储链表,同时在创建一个新token时也可能花费大量的额外时间。
在tree-base removal中,在每个事实w上添加一个链表,这些链表指向把w作为最后一个元素的tokens。同时,在每个tokens上,添加一个指向此tokens的子节点的链表。当w被删除时,遍历以tokens为根的子树,删除子树上的所有元素。当然,这些额外指针将占用更多内存,同时,建立这些指针也耗费时间。经验表明,采用此方法比原始方法要节省时间。
一、 Uni-Rete简介
产生式系统(基于规则的系统)中的组合匹配(the combinatorial match)在许多应用领域中带来了问题:如在实时系统中,人类认知建模,并行系统等。特有属性表示法(unique-attribute representation)可以有效的解决组合匹配问题。Uni-Rete是对Rete匹配算法进行约束,使用了特有属性表示法,实验结果显示其匹配过程的速度比Rete算法快10倍。
[Tambe and Rosenbloom 1989]通过引入特有属性表示法(unique-attribute representation)消除了产生式匹配中的组合问题。使用特有属性,匹配的时间与规则数目成线性关系。Uni-Rete是Rete算法的特例化,在Soar系统中,Uni-Rete比Rete快10倍。
二、 Rete算法
上图是一个通过使用Rete算法进行匹配的例子。
但是,在一个实际的产生式系统中,规则的数目非常多,从而整Rete网络很复杂,如下图所示。从图中可见,网络中的beta内存中可能存在大量的tokens。产生式匹配中的组合问题指beta内存中tokens的组合个数。在最糟糕的情况下,一条产生式可能产生O(WC)个tokens,其中W是事实个数,C是条件个数。Beta内存中有可能存放如此多的tokens,而tokens的数目在编译时无法确定,Rete使用如链表这样的动态结构来存储tokens。通过使用hash表可以对Rete算法进行优化。尽管如此,匹配过程中的主要花费的时间集中在对beta内存的处理中。
三、 特有属性表示法(The Unique-attribute Representation)
产生式匹配过程中的组合问题的是因为不知道到底哪一个事实最终可以匹配某个条件。在一个有很多条件的产生式中,这样的不确定性带来的级联效应(cascading effect)有可能带来与条件个数成指数关系的匹配时间。这种不确定性表现在当对某个条件进行匹配时有可能出现很多对此条件的部分匹配,每个部分匹配都是一个token。采用特有属性表示法可以消除在匹配过程中的不确定性。使用特有属性表示法,每个条件最多只对应着一个token,从而可以消除产生式匹配过程中的组合匹配问题。
这里我们采用(class object attribute value)这样的四元组来表示一个条件,下图所示即为这样的一个产生式。
所谓的特有属性表示法指:给定某个class, object和atrribute,只允许对应某个特定的value。下面a图所示的三个事实不是特有属性表示法,因为三个条件的class,object,attribute均相同,而B1, B2, B3却是三个不同的value。正是因为给定前三个部分相同的字段(field),而却有不同value导致了匹配过程中的不确定性。b图中显示的是特有属性表示法。
另外,特有属性表示法,对产生式中的条件也有约束,即,在object出现的变量必须预先绑定(pre-bound),即,必须在此更前面的条件中出现。
特有属性表示法通过对事实和条件的约束,保证了匹配代价与条件个数成线性关系。即beta内存中最多含有一个token。
特有属性表示法已经成功地运用到Soar中的各种任务中,包括了一些含有500或更多产生式的任务。在这些任务中,特有属性表示法改善了问题解决的性能,去除了代价很高的学习型规则,因此,使研究人员摆脱了产生式系统的效率问题。当然,对Uni-Rete的进一步加速仍然是必要的。
一般来说,特有属性表示法通过牺牲一些表达能力来获得匹配中的效率。这主要表现在两方面,一方面,使用特有属性表示法很难对工作内存中的非结构化数据进行编码,另一方面,特有属性表示法可能削弱学习型产生式(learned production)的归纳能力。
四、 Uni-Rete算法
下面的左图示意了使用Rete算法对使用的特有属性表示法的规则系统处理的过程。图中,每一个beta内存仅包括一个token。尽管如此,Rete算法仍然像以前一样的创建存储tokens,并且同样进行了大量的内存管理。
Uni-Rete充分利用了每一个bete内存中最多有一个token的性质,减少了对token的内存管理。仅有小部分的token存储在给定内存中,大部分的都存储在其前面的beta内存中。如下面的右图所示。左图中存储(w1, w4)的beta内存,在右图中仅仅存储了(w4),因为此beta内存的前面的alpha仅仅包括单独一个事实(w1)。相似的,在左图中存储(w1, w4, w6)的token,在右图中,仅需要存储(w6),剩下的部分隐含在其前面的beta内存之中。因此,通过仅仅存储一个单独的事实,来存储整个token。另外,存储所需的空间可以事先分配好,因为仅含有一个事实,从而可以避免rete算法中的动态内存管理。
Uni-Rete算法仅仅适用于使用特有属性表示法的系统中,因为,如果beta内存中有多个tokens,那么就无法确定哪些事实构成某个token。因此,Uni-Rete的这种隐含存储(implicit storage)不能用在非限制的产生式系统中。
第一步,对w6进行常量测试(constant tests),把w6存入右图所示的alpha内存中。
第二步,检查前一个条件的事实指针是否为空。如果是空则添加事实操作结束,不空则进入第三步,如检查w6对应条件的前一个条件的事实指针,此处指向w4,非空,进入第三步。
第三步,与前面的条件对应的事实进行一致性测试。如,检查w4和w6是否含有一致绑定。
第四步,存储指向新事实的指针。如果第三步检测成功,在相应位置存储指向新事实的指针。如,w4, w6是一致绑定,则存储指向w6的指针。如果测试失败,不进行任何下一步操作。
第五步,匹配下一个条件。检查下一个条件对应的alpha内存,是否匹配。若成功,则存储指向那个事实的指针。如,例子中,检查w6和条件4对应的事实是否一致绑定。如果成功,则存储指向条件4对应的那个事实的指针。重复第五步直道下一个条件不匹配。
如果出现指向最后一个条件的指针,则匹配成功。
当删除某个事实时:
第一步,从alpha内存中删除此事实。例如,删除w6时,通过常量检测发现w6,并从alpha内存中删除。
第二步,检测时候有指针指向被删除的事实。如,检测是否有指针指向w6,如果有,进入下一步,没有,则删除操作结束。
第三步,置被删除事实的对应的指针为空。如,置指w6的指针为空指针。
第四步,置所有后继的指针为空。
对token内存的优化,是Uni-Rete算法对Rete算法对主要的优化。通过此优化,有三方面优点,第一,beta内存节点的空间可以事先分配,避免了Rete算法中的内存分配回收操作。第二,beta内存节点仅仅存储指向事实的指针,从而避免了复制大量事实到当前beta内存中。第三,避免了对tokens的hashing操作。
五、 Uni-Rete网络的双线性(bilinear)组织
以上所讨论的Uni-Rete算法都是基于线性的网络。即,每一个条件加入网络时都是加入到一条产生式的所有前面的条件之后。但是,可以把这个网络组织成双线性(bilinear)的形式。即可以把某个条件加入到其部分前驱条件之前,而不必是所有的前驱条件前。下图说示即为线性Uni-Rete与双线性Uni-Rete的对比图。双线性Uni-Rete中,包括两部分条件链,(CE1,CE2,CE3,CE4)和(CE1,CE2,CE3,CE4)。这两部分被一个super-p-node连接起来。Super-p-node进行在biliner中未能进行的一致性检查。
使用biliner结构的好处实现是更大程度的共享。缺点是增加了在super-p-node 中的一致性检测的操作。
在一般情况下,采用biliner一般会降低Rete算法的性能,这是因为,1、增加了匹配活动;2、实现复杂;3、共用程度可能没有在使用特有属性表示法的系统高。
Uni-Rete是Rete的一个特殊情况,可以很容易的与Rete结合使用。Uni-Rete可以用在部分含有特有属性表示法的系统中。可以有两种方法把Uni-Rete和Rete结合起来使用,一种是把Uni-Rete用于特有属性的产生式,把Rete用于其它产生式;另一种是在一条产生式中,把Uni-Rete用于特有属性表示的条件中,而把Rete用于其它条件中。
Uni-Rete的一个贡献是通过减少对tokens的动态内存管理而提高性能。像Rete这样的匹配算法都假定tokens的数目在匹配时无法确定,因此需要动态分配内存。而在很多情况下,token内存的大小可以预测,Uni-Rete便利用这一特点使用静态数据结构来提高性能。
发表评论
-
不使用/,%,+和*,如何判断一个数能否被3整除
2012-05-30 14:28 1752如果n的二进制末位为0,那么n和n>>1同时被 ... -
一些数学知识
2012-03-31 20:12 820zz:http://hi.baidu.com/imak ... -
高阶幂的求余的方法
2012-03-31 16:41 2730通常会有如下问法: 有两个数,A和B,A的范围 ... -
从N个变量中找出一个错误变量的方法
2012-03-31 12:17 834假设有N包咖啡,里面有一包咖啡是掺和了沙子的,可以将咖啡放到水 ... -
【转】大数据量算法
2012-03-06 16:11 1224第一部分、十五道海量数据处理面试题 1. 给定a、b两个 ... -
链表的一些常见笔试面试问题总结及代码
2010-10-27 13:39 1068先什么也不说,假设链 ... -
Trie Tree
2010-10-26 11:34 1453给你100000个长 ... -
字典树(trie tree)
2010-10-26 11:19 1366今天AC了两题tri ... -
高度为n的平衡二叉树最少需要多少个节点
2010-10-24 13:42 9375递推关系 A(1)=1 A(2)=2 A ... -
如何判断两个单向链表是否有相交,并找出交点
2010-10-24 13:37 1682题比较简单,单向链表有交点意思就是交点后的节点都是 ... -
大数据排序或取重或去重相关问题解决方案
2010-10-21 16:13 2754Q:TC群里有人发消息说在10亿个数据中找出所有的重复数,内存 ... -
分配排序(桶排序..)
2010-10-21 13:39 1852分配排序的基本思想:排序过程无须比较关键字,而是通过&qu ... -
Rete(2)
2010-10-21 09:57 1136使用RETE算法的模块系统 ... -
Rete(1)
2010-10-21 09:53 1033一、 rete概述Rete算法是一种前向规则快速匹配算法,其匹 ... -
[转]海量数据处理面试题
2010-10-20 15:15 10051. 给定a、b两个文件,各存放50亿个url,每个url各占 ... -
用JDBC实现数据的分页
2010-10-20 11:23 1202数据分页主要用到了resultSet的absolute()方法 ... -
如何求N的阶乘所得的数字末尾含有多少个0
2010-10-19 13:13 2147原题是这样: 给定 ... -
数据库笔试题(经典SELECT语句用法)
2010-10-18 22:49 2090问题描述: 为管理岗位业务培训信息,建立3个表: S ... -
Java分页实现
2010-10-18 22:11 1480Java代码 public interf ... -
Linux下大文件的排序和去重复
2010-10-15 10:02 2096Linux下我们用 sort 与 uniq 的命令来实现去重复 ...
相关推荐
起点小说解锁.js
299-煤炭大数据智能分析解决方案.pptx
299-教育行业信息化与数据平台建设分享.pptx
网络技术和计算机技术发展至今,已经拥有了深厚的理论基础,并在现实中进行了充分运用,尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代,所以对于信息的宣传和管理就很关键。系统化是必要的,设计网上系统不仅会节约人力和管理成本,还会安全保存庞大的数据量,对于信息的维护和检索也不需要花费很多时间,非常的便利。 网上系统是在MySQL中建立数据表保存信息,运用SpringBoot框架和Java语言编写。并按照软件设计开发流程进行设计实现。系统具备友好性且功能完善。 网上系统在让售信息规范化的同时,也能及时通过数据输入的有效性规则检测出错误数据,让数据的录入达到准确性的目的,进而提升数据的可靠性,让系统数据的错误率降至最低。 关键词:vue;MySQL;SpringBoot框架 【引流】 Java、Python、Node.js、Spring Boot、Django、Express、MySQL、PostgreSQL、MongoDB、React、Angular、Vue、Bootstrap、Material-UI、Redis、Docker、Kubernetes
时间复杂度是计算机科学中用来评估算法效率的一个重要指标。它表示了算法执行时间随输入数据规模增长而变化的趋势。当我们比较不同算法的时间复杂度时,实际上是在比较它们在不同输入规模下的执行效率。 时间复杂度通常用大O符号来表示,它描述了算法执行时间上限的增长率。例如,O(n)表示算法执行时间与输入数据规模n呈线性关系,而O(n^2)则表示算法执行时间与n的平方成正比。当n增大时,O(n^2)算法的执行时间会比O(n)算法增长得更快。 在比较时间复杂度时,我们主要关注复杂度的增长趋势,而不是具体的执行时间。这是因为不同计算机硬件、操作系统和编译器等因素都会影响算法的实际执行时间,而时间复杂度则提供了一个与具体实现无关的评估标准。 一般来说,时间复杂度越低,算法的执行效率就越高。因此,在设计和选择算法时,我们通常希望找到时间复杂度尽可能低的方案。例如,在排序算法中,冒泡排序的时间复杂度为O(n^2),而快速排序的时间复杂度在平均情况下为O(nlogn),因此在处理大规模数据时,快速排序通常比冒泡排序更高效。 总之,时间复杂度是评估算法效率的重要工具,它帮助我们了解算法在不同输入规模下的性
5G通信行业、网络优化、通信工程建设资料
网络技术和计算机技术发展至今,已经拥有了深厚的理论基础,并在现实中进行了充分运用,尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代,所以对于信息的宣传和管理就很关键。系统化是必要的,设计网上系统不仅会节约人力和管理成本,还会安全保存庞大的数据量,对于信息的维护和检索也不需要花费很多时间,非常的便利。 网上系统是在MySQL中建立数据表保存信息,运用SpringBoot框架和Java语言编写。并按照软件设计开发流程进行设计实现。系统具备友好性且功能完善。 网上系统在让售信息规范化的同时,也能及时通过数据输入的有效性规则检测出错误数据,让数据的录入达到准确性的目的,进而提升数据的可靠性,让系统数据的错误率降至最低。 关键词:vue;MySQL;SpringBoot框架 【引流】 Java、Python、Node.js、Spring Boot、Django、Express、MySQL、PostgreSQL、MongoDB、React、Angular、Vue、Bootstrap、Material-UI、Redis、Docker、Kubernetes
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
5G通信行业、网络优化、通信工程建设资料
《基于小程序的交友系统的设计与实现》是一个融合了小程序技术和社交功能的毕业设计项目。该项目旨在通过开发一款小程序,为用户提供一个便捷、有趣的交友平台,满足用户寻找新朋友、拓展社交圈的需求。 一、项目背景与目标 随着移动互联网的普及,小程序以其轻便、易用的特性受到了广大用户的喜爱。本项目旨在利用小程序技术开发一款交友系统,通过简洁明了的界面设计和丰富多样的社交功能,吸引用户参与并提升用户体验。通过实现这一系统,旨在帮助用户拓展社交圈,增进人际关系,并推动社交领域的创新与发展。 二、系统设计与功能实现 用户注册与登录:系统提供用户注册与登录功能,确保用户信息的真实性和安全性。用户可以通过手机号或第三方社交账号进行注册和登录。 个人资料展示:用户可以在个人资料页面展示自己的基本信息、兴趣爱好、照片等,以便其他用户了解并产生互动。 附近的人:系统通过定位功能展示附近的其他用户,用户可以浏览附近的人的信息,并主动发起聊天或交友请求。 聊天功能:系统提供一对一的聊天功能,用户可以与感兴趣的人进行实时交流,增进彼此的了解。 活动组织:用户可以发起或参与各类线下活动,如聚会、运动、旅行
5G通信行业、网络优化、通信工程建设资料
shampoo-sales.csv
59-《煤矿测量规程(1989版)》150.pdf
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
5G通信行业、网络优化、通信工程建设资料。
AXIS T864 系列多通道 AXIS T8646 PoE+ 同轴电缆刀片套件 AXIS T8648 PoE+ 同轴电缆刀片紧凑型套件安装指南
MATLAB学习个人笔记总结.7z
【资源说明】【毕业设计】 1、该资源内项目代码都是经过测试运行成功,功能正常的情况下才上传的,请放心下载使用。 2、适用人群:主要针对计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、数学、电子信息等)的同学或企业员工下载使用,具有较高的学习借鉴价值。 3、不仅适合小白学习实战练习,也可作为大作业、课程设计、毕设项目、初期项目立项演示等,欢迎下载,互相学习,共同进步!
5G通信、网络优化与通信建设