zyskm用梦想丈量人生,用奔跑丈量激情

2015年10月26日 #

分布式模式之Broker模式

转发 http://blog.chinaunix.net/uid-23093301-id-90459.html 问题来源: 创建一个游戏系统,其将运行在互联网的环境中。客户端通过WWW服务或特定的客户端软件连接到游戏服务器,随着流量的增加,系统不断的膨胀,最终后台数据、业务逻辑被分布式的部署。然而相比中心化的系统,复杂度被无可避免的增大了,该如何降低各个组件之间的耦合度。 挑战: 需要保证可伸缩性、可维护性、可更新性,需要将服务划分为各个相对独立的组件,组件被分布式的部署,它们之间通过进程间通信方式实现交互。服务的增加、删除、改变都应该被支持。理想情况,以开发者的角度看,集中化的系统和分布式的系统在中心逻辑上没有什么不同。为实现这个目标: l 可以远程的访问服务,而对于访问者,服务的位置应该是透明的。 l 提供服务的组件可以增加、删除、改变,而且这些在运行期同样应该被支持。 l 访问服务的客户端不应该关心服务的实现细节。 解决方案: 引入一个Broker组件,解耦客户端和服务端。服务端注册自己到Broker,通过暴露接口的方式允许客户端接入服务。客户端是通过Broker发送请求的,Broker转发请求道服务端,并将请求的结果或异常回发给客户端。通过使用Broker模式,应用可以通过发送消息访问远程的服务。 这一架构模式允许动态的改变、添加、删除服务端,从客户端的角度,这些都是透明的。 结构: Broker模式定义了6中类:Client,Server,Client_Proxy,Server_Proxy,Broker,Bridge。 Server: l 责任:处理特定领域的问题,实现服务的细节,注册自己到Broker,处理请求并返回结果或异常。 l 协作类:Server_Proxy,Broker Client: Client是需要访问远程服务的应用程序,为此,Client发送请求到Broker,并从Broker上接收响应或异常。Client和Server只是逻辑上相关而已,实际上Client并不知道Server的确切位置。 l 责任:1. 实现用户端功能,2. 发送请求到Broker,3. 接收相应和异常。 l 协作类:Broker,Client_Proxy Broker: Broker可以被看成消息转发器。Broker也负责一些控制和管理操作。它能够定位服务端的位置,若发生异常,能够将异常捕获传给Client。Broker需要提供注册服务的接口给Server。如果请求来自其他的Broker,本地的Broker需要转发请求并最终将结果或异常回应给相应的远程Broker。Broker提供的服务和name service非常相像(如DNS、LDAP)。 l 责任:1. 注册服务。2. 提供服务API。3. 转发消息。4. 容错处理。5. 与其他Broker的交互。6。 定位服务。 l 协作类:Client_Proxy,Server_Proxy,Bridge Client_Proxy: 连系Client和Broker,这一层保证了通讯的透明性,使Client调用远程服务就像调用本地的服务一样。 l 责任:1. 封装特定的系统调用。2. 封装通讯的参数、控制信息等。 l 协作类:Client,Broker。 Server_Proxy: Server_proxy是与Client_Proxy相对应的,它接受请求,解包消息,解析出参数并调用服务的实现接口。 l 责任:1. 封装特定的系统调用。2. 封装通讯的参数、控制信息等。3. 调用server的服务接口。 l 协作类:Server,Broker。 Bridge: Bridge用来连接各个Broker,一般这个组件是可选的。当系统是发杂的网络组成时,有可能需要这一角色。 l 责任:1. 封装特定的网络特性。2. 传递Broker之间的通讯。 l 协作类:Broker。 应用场景一: 直接通讯方式。Client和Server相互理解他们之间的通讯协议。Broker主要完成Client和Server之间的握手。之后所有的消息、异常都是由Client与Server直接交互。(想象DNS)。简单对象交互如图: 应用场景二: l Broker启动,完成自身的初始化,之后进入事件循环,等待消息到来。 l Server启动,首先执行自身的初始化,然后注册自己到Broker。 l Broker接收Server的注册请求,将其加入到可使用服务的列表,并回应Ack给Server。 l Server接收Ack,进入事件监听循环,等待消息到来。 l Client调用远程服务对象的方法,Client_Proxy封装消息请其发送给Broker。 l Broker查询可使用的Server,将请求转发给Server。 l Server_Proxy解析消息,分离出参数和控制信息,并调用特定的Server实现接口。Server处理完的结果通过Server_proxy封装成消息转发到Server。 l Broker将相应消息转发给正确的Client_Proxy,Client受到响应继续其他逻辑。 简单对象交互如图: 应用场景三: l Broker A接收到请求,交由Server处理,但是发现该Server位于其他的网络节点。 l Broker A将请求转发给Bridge A,Bridge A将请求进行必要的格式化,传送给Bridge B。 l Bridge B将请求进行必要的格式化,转化成Broker B可以理解的格式,并转发给Broker B。Broker B执行场景二中的过程,处理的结果按如上逆序返回。 简单对象交互如图: 部署示意图: 总结: u 优点: 1. 服务的位置透明性。 2. 组件的可变性及扩展性。由于Server是注册到Broker上的,所以Server可以动态的增加、删除、改变。 3. Broker之间可交互。 4. 可重用性。 5. 由于组件的耦合度较小,调试和测试的工作也是可控的。 u 缺点: 1. 效率;增加了一层Broker的消息转发,效率有所降低。 2. 容错能力必须要特别考虑。 3. 调试和测试的工作加大。

posted @ 2015-10-26 10:32 zyskm 阅读(125) | 评论 (0)编辑 收藏

2014年10月16日 #

专家思维

大师的非凡能力来源于何处?思维方式是关键。科学证据告诉人们,没有天生的大师,只有炼就的专家。只要拥有专家的思维,你就能成为大师! 1909年的一天。多张象棋桌围成了一个圈,一个男子在圈内慢慢踱步。他的双眼不断扫描周围的棋局,每隔两三秒钟就会下一步棋。而在圈外,数十位象棋迷不停地搔头、苦想对策。这个人是谁?为什么他能以一人之力抗衡数十人的智慧?他就是国际象棋界的传奇人物,古巴象棋大师卡帕布兰卡(José Raúl Capablanca)。比赛结果毫无悬念,卡帕布兰卡28局全胜。这只是他巡回表演赛中的一站,在整个巡回表演赛中,卡帕布兰卡赢了168局。 为什么眨眼间他就能作出最正确的决定?面临巨大的压力,他能提前计算几步?卡帕布兰卡轻描淡写地说:“我只提前看一步,但总是最正确的一步。” 这句话再简单不过,却开创了心理学研究的新纪元:象棋大师优于新手的地方就在于那电光火石间的思考。这种快速的、由知识引导的知觉,有时叫做“领悟”。在其他领域,专家们同样具有“领悟”的本领。一次比赛完毕,象棋大师能记住自己走过的每一步棋;对于一段音乐,哪怕只听过一遍,资深音乐家也能写出乐章的曲谱。无论多么困难,象棋大师也能在瞬间想到最妙的棋着;不管多么复杂,经验丰富的专业内科医生有时只须瞥上病人几眼,就能作出准确的诊断。 专家们的非凡技艺从何而来?源于天赋,还是得益于强化训练?通过对象棋大师的研究,心理学家找到了答案。一个世纪的探索积累了大量研究成果,新的理论应运而生,人脑处理信息(信息的组织与提取)之谜也由此破解。这项研究的意义还不仅在于此,人类的教育事业也将从中受益:象棋棋手提高棋艺的技巧,可否用于提高学生们的阅读、写作和计算能力呢? 象棋是最好的研究对象 人类何时开始拥有专业技术?这也许要从祖先们的狩猎说起。对于他们而言,狩猎技术是维系生命的重要工具,不掌握它就难以生存。经验丰富的猎人不仅知道狮子在哪里出没,而且还能推断出狮子的行踪。从孩提时代开始,他们就得跟随长辈练习追踪技术。随着年龄的增长,追踪技术也日益娴熟。“技术的熟练程度随着年龄的增长而增长,35岁左右达到技术的巅峰,”美国加利福尼亚大学富勒顿分校的人类学家约翰?博克(John Bock)说道。练习追踪技术要花费很多时间,可能比培养优秀的脑外科医生还要费事。 相对于新手,如果在技术上没有绝对优势,那就难称专家,只不过是多了一张唬人的文凭。这种披着专家外衣的人比比皆是。过去20年的研究结果表明,所谓的专业炒股者并不比业余者赚的钱多;知名品酒家对酒类的鉴别能力并不比馋酒的老农强;高学历的精神病医生并不比低文凭的同行出色……即使真的存在专业技术,如教学、工商管理,都很难去衡量,更别提如何去阐释。 不过,棋艺却可以度量、可以分解、可以接受试验研究,并且十分直观,尤其在比赛时,任何人都能随时观看。正是基于以上原因,认知科学家如获至宝,将象棋作为研究思维理论的最佳试验对象。于是象棋被称作“认知科学的果蝇”。 对象棋手棋艺的度量,已经走在了其他任何比赛、运动或竞技活动的前面。运用统计学公式,对棋手曾获得的所有成绩进行分析,就可以得到棋手的实力等级。然后根据棋手的等级与对手的实力,即可准确地推算出棋手的获胜几率。如果A棋手的等级分高于B棋手200点,那么在比赛中,A战胜B的平均几率为75%。不管棋手是顶级的还是普通的,这种预测都很准确。例如,俄罗斯特级象棋大师加里?卡斯帕罗夫(Garry Kasparov),他的等级分是2812点,而荷兰象棋大师扬?蒂曼(Jan Timman)的等级分是2616点。如果二者对弈,那么卡斯帕罗夫就有75%的胜算。同样,中等水平的棋手(1200点)与另一个1000点的棋手对弈,前者亦有75%的胜算。选手的等级分代表着他们的真正实力,以选手的等级为标准,心理学家就可以客观地评估他们的专业技术,动态追踪他们整个象棋生涯,而不会受到选手名气的影响。 为什么认知科学家没有选择台球或桥牌作为研究模型,而偏偏选择象棋呢?可能是因为象棋比赛最考验人的智慧。正如德国诗人歌德所言,象棋是“智慧的试金石”。象棋大师的技艺出神入化,令人叹为观止,人们将他们的能力归因于他们“拥有魔力”的大脑。这种魔力在下盲棋时体现得淋漓尽致。法国心理学家阿尔弗雷德?比奈(Alfred Binet)是首个智力测验的发明人之一。1894年,他曾请象棋大师描述他们下棋的过程。起初,他认为棋盘就像照片一样存在于象棋大师的大脑中,但是他很快断定,大师们大脑中的图像还要抽象得多。他们整体把握棋子的位置关系而不注重具体细节,就像只关心马而不关心马的鬃毛一样。 通过把握比赛的即时细节以及回想走过的棋步,盲棋大师能将脑海中的棋局补充完整。假设大师忘记了卒的准确位置,该怎么办呢?他立即开始回想开局时的套路,因为在开局时,套路相对固定,而且已经烂熟于胸,因此很容易找到卒曾经所在的位置。他也可以回忆走过的棋步,通过推理来找到卒的位置――“前两步我没能抓住他的相,所以当时一定有卒在挡路……”他不必纠缠细节不放,利用组织完善的连接系统,可以重获任何想要的细节。 如果大师们的魔力――超凡的计算、计划能力都是以复杂的知识结构为基础,那么就可以肯定,专业技术多半来源于刻苦训练,而非上天的恩赐。荷兰心理学家阿德里安?德赫罗特(Adriaan de Groot)是一位象棋大师。1938年,荷兰举行了一场国际象棋锦标赛,他利用主场之便,对普通棋手、专业棋手与世界顶级大师进行比较后,进一步巩固了上述观点。他曾使用的一种方法就是请棋手观看节选自比赛的棋局,然后说出自己的想法。他发现,尽管专业棋手的分析能力要比普通棋手强,但是当他们的实力提升至大师级时,反而不会去思索更多的下法。因为在高手的心中,只会留下最妙的棋着――正如卡帕布兰卡声称的那样。 近来研究表明,德赫罗特的发现只展示了象棋大师的部分实力。在一场对弈中,如果大量而精确的计算无法避免时,大师们就会拿出真功夫,深入研究各种可能的棋步走法。这种能力,会让普通棋手望尘莫及。同样,知识渊博的物理学家遭遇难题时,也会比他的学生想出更多的解决办法。然而在上述两种情况下,专家依靠的不是与生俱来的强大的分析能力,而是多年来逐渐建立起来的知识结构。面对困难的棋局,一个实力平平的棋手可能会耗费大半个小时去计算、提前看许多步,然而总是错过最正确的一步。相反,一个大师级的棋手根本不用有意识地去分析,立即就能看到精妙入微的一步。 德赫罗特还让参加试验的棋手在短时间内审视棋局,然后凭记忆重建棋局。在这样的试验条件下,任何棋手的实力都会暴露无遗。就算用长达30秒钟的时间去回忆棋局,新手能记起的细节也是支离破碎的。而象棋大师,即使只瞟上几眼,也能轻松重建棋局。这种差别源于一种特殊记忆,也就是对棋局的特异性记忆。特殊记忆是训练的结果,因为在一般性的记忆测试中,大师的表现并不比其他人好。 同样的现象还能从桥牌牌手(多场牌局后,仍记得出过的牌)、计算机程序设计师(能重组大量的计算机编码)和音乐家(能记住大段大段的乐章)身上看到。在特殊领域,对主题事务的记忆能力,是衡量专业技术水平的重要标准。 一个不常见的案例也能证明,知识结构才是专家们战无不胜的法宝。一个叫D.H(姓名不全)的业余棋手,经过9年的训练,终于在1987年成为了加拿大一流的象棋大师。美国佛罗里达州立大学的心理学教授尼尔?蔡内斯(Neil Charness)指出,尽管这个棋手的实力已经今非昔比,但是他对棋局的分析范围并不比从前广泛,反而是日益精深的棋局知识和相关策略帮助他连连告捷。 非凡能力来自何方 在上世纪60年代,美国卡耐基-梅隆大学的心理学家赫伯特?西蒙(Herbert Simon,1978年诺贝尔奖得主)和威廉?蔡斯(William Chase),试图通过研究专家的记忆局限性来更好地洞察专家的记忆能力。按照德赫罗特的研究思路,他们请各个级别的棋手重建曾被人动过的棋局。不过这盘棋局不是大师对弈后的残局,而是一盘乱摆的棋局。在重建这盘随机棋局时,棋手间的差距并不明显。 因此,象棋运动中的特异性记忆不只取决于象棋这项运动,还取决于棋局的类型。这些实验验证了早期的研究结果,有力地证明了能力的非通用性,不同的领域需要不同的能力。早在一个世纪前,美国心理学家爱德华?桑代克(Edward Thorndike)就首先提出了上述理论。当时他指出,拉丁语说得好不等于英语水平高,几何证明也不能教会人们在日常生活中运用逻辑思维。 象棋大师要处理的信息,数量极其庞大,似乎已经超越了人类记忆的极限。为了解释他们这种超凡的能力,西蒙引入了模块理论。1956年,美国普林斯顿大学的心理学家乔治?米勒(George Miller)曾发表过一篇著名的论文――《非凡的数字7±2》。米勒在论文中指出,人的记忆有一定的限度,每次只能处理5~9条信息。西蒙强调说,通过把不同层次的信息构建成一个一个模块,大师就能突破记忆的极限。通过这种方法,他们会去捕捉5~9个模块,而不是5~9个具体细节。 以“Mary had a little lamb”(玛丽有一只小羊羔)这句诗为例。诗里的信息模块数取决于读者对诗歌与英语的熟悉程度。对于以英语为母语的人,这句诗是一个非常大的模块――著名诗歌的一部分;对于懂英语却不懂诗歌的人,这就是一句话――一个完整的模块;对于记得单词却不明白含义的人,这句话是5个模块(单词);而对于认得字母,却不认识单词的人,这句诗就是18个模块(字母)! 在象棋新手和象棋大师之间就能清楚地看到这种差别。假如有一个摆着20个棋子的棋局放在面前,新手和大师会怎么处理其中的信息呢?新手满眼都是棋格,而棋子又有多种摆法,因此他获取的信息模块远多于20个。那么大师呢?他会将棋局整体化,然后把整个棋局分割成5~6个模块,这样记起来不就轻松多了!根据获取一个新的记忆模块所花掉的时间,以及普通棋手成长为大师级选手所需要的时间,西蒙估算出了象棋大师的大脑中存储的信息模块数:5万~10万个!就像我们听几个字就能背出一首古诗一样,象棋大师只要看一眼棋局,就能从记忆中提取出相应的信息模块。 但是模块理论还有缺陷。对一些记忆现象,例如当大师们精力分散时,他们的表现并没有受到明显影响,模块理论就无法给出合理的解释。佛罗里达州立大学的K?安德斯?埃里克森(K. Anders Ericsson)与蔡内斯认为,可能还存在另外一种机制,使得专家可以把长时记忆当作暂存区使用。埃里克森说:“训练有素的棋手在不看棋盘的情况下,能以几乎正常的水平下棋,要用模块理论来解释这样的事例,几乎不可能。因为你必须先了解棋局,然后才能在记忆中把它翻出来。”这一处理过程需要改变已有的信息模块,就像倒背 “Mary had a little lamb”,虽然可以做到,但是很难,而且还会错误不断。然而在下盲棋的时候,象棋大师仍然可以精准快速地下棋,让对手无所适从。 埃里克森还引证了内科医生的学习过程。医生们先把信息变为长时记忆,当需要使用这些信息来诊断疾病时,再把它从记忆中提取出来。埃里克森还列举了一个最普通、最常见的例子――阅读。1995年,他在研究中发现,越是熟练的读者越不容易受到干扰。就算阅读被打断,熟练的读者也能在几秒钟的时间内恢复原有的阅读速度。研究人员用长时工作记忆来解释这一现象。这一说法似乎自相矛盾,因为长时记忆与工作记忆是两个相互对立的概念。不过在2001年,德国康斯坦茨大学进行的大脑成像研究却为这一说法提供了依据。研究结果表明,较之新手,专业棋手的长时记忆显然更容易激活。 上世纪90年代末期,西蒙曾提出过一种竞争理论。英国伦敦布鲁内尔大学的费尔南德?戈贝特(Fernand Gobet)对它推崇备至。竞争理论实际上是模块理论的延伸,它引入了“模板”的概念,也就是一种极其典型并包含了大约12只棋子的大型布局。模板拥有许多插口,大师可以插入卒或者相这样的变量。再以诗句“Mary had a little lamb”为例,如果某个词的韵律与诗句中的词等同,那么就可以用这个词来替换诗中的词。例如,用“Larry”替代“Mary”,用“pool”来替代“school”等等。任何知道原始模块的人,都能在瞬间插入另一个词。 天才是怎样“炼”成的 要想在大脑中建立复杂的知识结构,就得不断努力。西蒙提出了“十年规则”,他认为要掌握任何技艺,十年的艰辛历程是无法避免的。即便是数学天才高斯,音乐奇才莫扎特,象棋神童菲舍尔,也得去拼搏、去奋斗,也许他们所付出的努力是常人难以想象的。 近年来,象棋天才似乎不断涌现,但这都归因于计算机的强大功能。计算机能让孩子们研究海量的大师级比赛,频繁地与大师级程序对抗,于是在较短的时间内,他们就能积累丰富的实战经验。1958年,15岁的菲舍尔获得了象棋大师的称号,当时这一消息震惊了全世界。而目前的记录保持者、乌克兰的谢尔盖?卡尔亚金(Sergey Karjakin)获得大师称号时,仅有12岁零7个月! 埃里克森认为,光是练习远远不够,还需要全身心投入,不断挑战极限、超越自我。就像业余爱好者,他们可能会用大量的时间来练习下棋、打高尔夫球、演奏乐器,却始终达不到专业水平;然而一个经过正规训练的学生,却能在较短的时间内超过他们。这是一个很有趣的现象,说明练习和比赛对棋手的帮助似乎不如踏踏实实地学习。训练和比赛的主要价值在于,新手可以从中发现自己的缺陷,从而在以后逐渐弥补。 在学习初期,新手往往兴趣浓厚,钻研劲儿十足。他们刚开始学习打高尔夫球或者开车时,技术的进步速度可用“神速”二字来形容。但是技术一旦攀升到一定的阶段,例如跟上了高尔夫球友的节奏,或者考取了驾照,大多数人就松懈了。于是,他们变得懒散,技术也被荒废。相反,训练专家总是让人不停地思考,因此参与学习的人就会自觉自律地去钻研、不断提高技术,从而缩小与高手之间的差距。 人类在进步,衡量专业水平的技术标准也在不断提高。现在的高中生能在4分钟内跑完一英里(约合1.6公里);学音乐的学生敢于演奏曾经只有名家才敢尝试的曲子。如果说上述比较还不能让人信服,那么我们再来看看象棋上的证据。英国人约翰?纳恩(John Nunn)既是数学家,又是象棋大师。他利用计算机,比较了1911年和1993年举行的两届国际象棋锦标赛。结果发现,现代棋手出错的几率要小很多,换言之,他们比前辈们下得更准确。纳恩还研究了1911年的一个棋手下过的所有棋局。在当时,这个棋手算是一个中等级别的选手。按照今天的标准,他的等级分不会多于2100点,离大师级标准还有一大段距离。与普通棋手相比,百年前的大师仍然实力强劲,不过与今天的大师相比,可能就有一定的差距。 在卡帕布兰卡的那个时代,计算机、象棋数据库都还没有出现,他们只能靠自己解决一切问题,正如巴赫、莫扎特和贝多芬。如果说今天的大师在技术上已经超越了曾经名满天下的先辈们,然而在创造力方面他们却难以望其项背。今天,刚毕业的物理学博士掌握的物理知识,恐怕连牛顿也要自叹弗如,但是在这些博士中,有谁能像当年的牛顿一样发现万有引力定律? 说到这里,很多怀疑论者的耐心可能会荡然无存。他们肯定会说,要步入卡耐基殿堂,除了练习、练习、再练习之外,还要付出更多的东西。虽然相信天资的重要性,尤其是专家和他们的学生对此深信不疑,然而奇怪的是,没有任何证据来支持这一观点。2002年,戈贝特曾做过一项研究。研究中,他用图形记忆测验衡量各级别棋手的视觉空间智能。结果发现,棋艺的高低与视觉空间智能的强弱根本没有联系。还有研究人员发现,职业裁判预见赛马结果的能力与他们的数学能力也没有什么关系。 ... ...

posted @ 2014-10-16 15:32 zyskm 阅读(183) | 评论 (0)编辑 收藏

2014年6月12日 #

信息熵

     摘要: 熵是信息理论中非常重要的一个概念,用来度量信息,在实践中大量使用。
信息检索最重要的概念TF/IDF(term frequency/inverse document frequency)就是基于信息熵理论。搜索引擎、新闻分类、文本相似度计算都使用这个概念。  阅读全文

posted @ 2014-06-12 14:45 zyskm 阅读(1609) | 评论 (6)编辑 收藏

2013年6月24日 #

Chomsky文法

看Chomsky的书是因为在编译原理课程中多次提到这个人,这是个变态天才,神一般的存在,而且还是活的。
Chomsky的语言学理论观点在语言学、心理学和哲学领域都产生了广泛而深刻的影响。Chomsky的哲学思想是一个贯穿了唯实论、自然主义和心智主义的连贯的、完整的体系。这一体系的核心是内在语言理论。但是这一理论观点与传统观点分歧很大 ,因此遭受到哲学界的强烈攻击。Chomsky正是在这些争论的过程中不断地发现问题并对自己的理论和观点进行修改和补充 ,从而使其哲学系统乃至语言学理论系统更趋完善。哲学问题咱不关心这么无聊的问题留给哲学家们去扯。

理论方法
Chomsky语言学的理论方法概况起来讲,是自然科学中形式主义的演绎方法,用Chomsky自己的话讲,叫伽利略研究风格(Galileo Style),像伽利略为宇宙建立抽象的数学模型一样,构建有关语言知识的抽象数学模型,相信类似数学一样的形式主义的演绎推理模型具有自足自明的真理性。Chomsky的语言研究所追求的是从世界各种语言五花八门的句子样式中抽象出几个简单的句法规则。

Chomsky的句法结构一书中把语言学看成跟自然科学中的其他科学一样,可以从假设出发,进行推演并形式化。换句话说,非经验主义是可能的。《句法结构》有一半篇幅用于英语语法的形式化。非经验主义和形式化是转换生成语法的首要标志。
 
把句法关系作为语言结构的中心并以此说明语句的生成是这场革命的又一表现。为了描写和解释语言现象,Chomsky在《句法结构》中论证了语法的生成能力,认为应该把语法看成是能生成无限句子的有限规则系统。
 
它以"核心句"为基础,通过转换规则描写和分析不同句式之间的内在联系。该书分析了以"马尔可夫过程"为基础的通讯理论,认为它只能生成有限状态的语法,而这种"有限状态的语法"不能生成象英语这种语言里含有不连续结构的所有合乎语法的句子。基于此,乔姆斯基提出了转换语法模式,认为它才能生成所有合乎语法的句子而不会生成不合乎语法的句子。转换语法模式由短语结构规则、转换规则、语素音位规则三套规则构成。
 
短语结构规则有三种:合并、递归、推导式,其基本形式是x→y 。→读作"改写",这个公式就是将x改写成y。短语结构规则生成的是"核心语符列",不经过转换直接由这种语符列得出的基本句型叫"核心句"。
 
转换规则包括:移位、删略、添加。最后运用语素音位规则得出实际说出的句子。这三套规则中,最引人注目的是转换规则,因为短语结构规则和语素音位规则实际上继承了描写语言学的"直接成分分析"和语素音位的分析,转换是一种创新,它使语法具有更强的解释力。
 
《句法结构》把语义排除在语法之外,这一时期的理论框架不包括语义部分。乔姆斯基认为,语法理论不应该建立在语义的基础上,而应该用某种严格的、客观的方法去代替对于模糊的语义的依赖。不过这一理论在后来的发展中做了重大的修正。

Chomsky 定义的四种形式语言文法中, 0 型文法又称为 ( A )文法; 1 型文法又称为 ( C ) 文法; 2 型语言可由 ( G ) 识别。
A .短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法
E 图灵机 F 有限自动机 G 下推自动机
文法是用来定义语言的一个模型,常用的文法体系为Chomsky文法体系。
 
文法定义
 
文法G(Grammar)是一个四原组,G=(N,T,P,S),N(Non-terminator)是非终结符集合,T(Terminator)是终结符集合,P(Production)是产生式集合,S(Start)是起始符
 
其中:
 
N 交 T = 空集
 
P 是形式为 α -> β 的产生式
 
   α ∈  (N∪T)*N+(N∪T)*,也就是说α中必须有一个非终结符
 
   β ∈  (N∪T)* ,也就是说β可以是空串
 
S∈N
 
 
 
分类
 
0型文法(短语文法或无限制文法),识别0语言的机器叫做图灵机

  定义:P中产生式a-->b,其中a属于V正闭包且至少含有一个非终结符,b属于V星闭包

  注:任何0型文法都是可递归可枚举的

    对0型文法作某些限制,可以得到其他文法的定义

1型文法 又称上下文有关文法。生成式形式为 α->β, 且 |α| < |β| 并且不存在 A->ε
 
2型文法 又称上下文无关文法。生成式形式为 A->α,即左边必须只有一个非终结符
 
3型文法 又称正则文法。
 
             生成式 A->wB或A->w,称为右线性文法
 
             生成式 A->Bw或A->w,称为左线性文法
 
0型文法 对生成式没有任何限制的文法称为0型文法。从0到3都是包含的关系,但是有特例,包含  A->ε 产生式的2,3型文法不属于1型文法。
 
四种文法产生的语言分别称为 上下文有关语言,上下文无关语言,正则语言,无限制性语言。
 
 
 
2型语言的表示法
 
2型语言是很重要的一种语言,除了用四元组的方法表示,此处再介绍两种表示方法。
 
当人们要解释或者讨论程序设计语言本身时,经常又需要一种语言,被讨论的语言叫做对象语言,即某种程序设计语言,讨论对象语言的语言称为元语言,即元语言是描述语言的语言。BNF范式通常被作为讨论某种程序设计语言语法的元语言,而语法图是与BNF范式的描述能力等价的另一种文法表示形式,因其直观性而经常采用。
 
(1)巴科斯范式(Backus Normal Form,BNF)
 
2型文法生成式左端只有一个非终结符,所以可以把左端相同的生成式合并在一起,右端用|隔开,用::=代替->,所有非终结符用<>括起来,这是Backus为了描述AIGOL语言首次提出并使用的。
 
用BNF描述十进制整数的生成语法:
 
<无符号整数> ::= <数字>|<数字><无符号整数>
 
<数字> ::= 0|1|2|3|4|5|6|7|8|9
 
(2)语法图
 
语法图有四种基本形式
 
(3)推导树
 
2型文法还经常用推导树表示

posted @ 2013-06-24 11:25 zyskm 阅读(2317) | 评论 (0)编辑 收藏

2013年6月9日 #

通过antlr语法文件学习java---strictfp

  节选自java.g
modifiers 
    :
    (    annotation
    |   'public'
    |   'protected'
    |   'private'
    |   'static'
    |   'abstract'
    |   'final'
    |   'native'
    |   'synchronized'
    |   'transient'
    |   'volatile'
    |   'strictfp'
    )*
    ;Strictfp —— Java 关键字。
  strictfp, 即 strict float point (精确浮点)。
  strictfp 关键字可应用于类、接口或方法。使用 strictfp 关键字声明一个方法时,该方法中所有的float和double表达式都严格遵守FP-strict的限制,符合IEEE-754规范。当对一个类或接口使用 strictfp 关键字时,该类中的所有代码,包括嵌套类型中的初始设定值和代码,都将严格地进行计算。严格约束意味着所有表达式的结果都必须是 IEEE 754 算法对操作数预期的结果,以单精度和双精度格式表示。
  如果你想让你的浮点运算更加精确,而且不会因为不同的硬件平台所执行的结果不一致的话,可以用关键字strictfp.

posted @ 2013-06-09 10:27 zyskm 阅读(1871) | 评论 (0)编辑 收藏

java静态导入

import语句可以导入一个类或某个包中的所有类

import static语句导入一个类中的某个静态成员(方法或属性)或所有静态成员

语法举例:

import static java.lang.Math.sin;

import static java.lang.Math.*;

例子:


//导入Math类中的所有static方法和属性。 
//这样我们在使用这些方法和属性时就不必写类名。 
import static java.lang.Math.*;//import static java.lang.Math;//这样写报错  
public class StaticImport { 
       public static void main(String[] args) { 
//            System.out.println(Math.max(3, 5));//没有使用静态导入 
//            System.out.println(Math.abs(1-9));//没有使用静态导入 
              System.out.println(max(3, 5)); 
              System.out.println(abs(1-9)); 
       }

注意:1默认包无法用静态导入。

2如果导入的类中有重复的方法和属性则需要写出类名,否则编译时无法通过。

 
}

posted @ 2013-06-09 10:23 zyskm 阅读(1976) | 评论 (0)编辑 收藏

2013年5月14日 #

dbcompare---数据库结构比较工具

概述:
在设计开发过程中经常会出现开发库与测试库不一致,测试库与生产库不一致,每次手工比对是个辛苦的活。
以前用java写过一个数据库结构比较工具,最近腾出功夫来学习了一下python,用python重写了一下,已经提交到了github和sourceforage.
版本控制使用github
https://github.com/zhengys/dbcompare.git
sourceforage上边放了exe文件(用pyinstaller打包的程序发现在部分win7上不能正常工作,又用py2exe打包了一个64位版本的,已经上传sourceforage  , 感谢itshu的反馈)
http://sourceforge.net/projects/databasecompare/files/
通过这个工具可以做到简单明了的看出区别。
对于数据库和设计文档不一致的情况,目前只能是先根据文档生成数据库,再和原来的库做比对。未来考虑增加powerdesinger和数据库的间直接比较。
目前只支持oracle,mysql,sqlserver,要是用的人多了再增加其它类型的数据库。

使用:
功能类似文本比较工具,分别输入数据库连接信息,在结果页面显示比对结果。
操作很简单看图就知道怎么用了。
如图:


打包说明
一开始用py2exe打包,发现在winxp下用不了
改用pyinstaller打包,360会误认为是木马拦截,文件夹形式打包,比较占地方,压缩后也得36MB.
可根据源码自行打包。


posted @ 2013-05-14 23:49 zyskm 阅读(3796) | 评论 (3)编辑 收藏

2013年3月1日 #

SOCKS5协议的原理和应用(转载)

首先解释一下为什么它被称之为SOCKS。其实该协议设计之初是为了让有权限的用户可以穿过过防火墙的限制,使得高权限用户可以访问一般用户不能访问的外部资源。当时设计者考虑到几乎所有使用TCP/IP通信的应用软件都使用socket(套接字,实际上是一组应用程序接口)完成底层的数据通信。为了方便软件开发者使用该协议,协议设计者就刻意对应了几组socket编程最经典的操作,并且将协议定名为SOCKS。


最先被广泛使用的SOCKS协议是其第四版本,就是SOCKS4。IE和一些其他应用程序直接用“Socks”表示SOCKS4协议。该版本支持TCP的connect(作为客户端连接)和listen(打开一个监听端口),不支持UDP协议。SOCKS4A对SOCKS4作了一点增强,即允许客户端将域名发送给SOCKS服务器,让SOCKS服务器进行域名解析。


SOCKS5是第五版,相对第四版作了大幅度的增强。首先,它增加了对UDP协议的支持;其次,它可以支持多种用户身份验证方式和通信加密方式;最后,修改了SOCKS服务器进行域名解析的方法,使其更加优雅。经过这次脱胎换骨的升级,SOCKS5于1996年被IETF确认为标准通信协议,RFC编号为1928。经过10余年的时间,大量的网络应用程序都支持SOCKS5代理。


SOCKS5虽然可以支持多种用户身份验证方式,但是应用程序真正实现的一般也只有两种:不验证和用户名密码验证。所以大多数应用程序SOCKS5代理设置也只有用户名/密码这一种可选验证方法。另外,尽管从SOCKS4开始,就支持打开TCP监听端口,但是直到SOCKS5,也只允许这个端口接收一个客户端连接。因此网络服务提供者(如http服务器)不能使用SOCKS。实际上,很多SOCKS服务器的实现也不支持打开TCP监听端口。


由于SOCKS5实际上仍然对应了socket的经典操作,所以有人利用这一点编写了一种通用软件,可以让不支持SOCKS5协议的应用软件也能通过SOCKS5服务器进行网络通信,而应用软件则对此一无所知。这类软件最著名的莫过于SocksCap32了,它是Permeo公司(其前身是NEC北美公司的一个部门,而SOCKS最初就是NEC北美公司的工程师开发并维护的)早期推出的一款产品。用户可以免费使用其试用版。试用版和正式版相比,没有功能上的限制,只有使用时间的限制。但是到目前为止,Permeo总是会在老版本到期之前推出一个延后了期限的“新”版本,所以用户实际上可以免费使用。SocksCap32是利用API钩子,截获应用软件对socket函数的调用来实现对SOCKS5客户端的模拟。尽管SocksCap32很有名,但是由于推出的时间较早,对很多现代应用软件时常表现的力不从心,所以Permeo又提供了Permeo
Security
Driver(以下称为PSD)。这款产品使用了驱动技术从底层直接截获应用软件的socket通信,因此几乎可以为所有应用软件提供SOCKS5客户端的支持。PSD不提供试用版,但是可以找到其早期版本的注册码。


虽然说设计SOCKS协议的初衷是在保证网络隔离的情况下,提高部分人员的网络访问权限,但是国内似乎很少有组织机构这样使用。一般情况下,大家都会使用更新的网络安全技术来达到相同的目的。但是由于SocksCap32和PSD这类软件,人们找到了SOCKS协议新的用途——突破网络通信限制,这和该协议的初衷实际上正好相反。比如某些网游的部分服务器设置为只接收部分地区的IP地址的连接。为了突破这种限制,可以找一个该地区的SOCKS5代理服务器,然后用PSD接管网游客户端,通过SOCKS5代理服务器连接游戏服务器。这样游戏服务器就会认为该客户端位于本地区,从而允许进行游戏。还有一种情况是:防火墙仅允许部分端口(如http的80端口)通信,那么可以利用SOCKS5协议和一个打开80端口监听的SOCKS5服务器连接,从而可以连接公网上其他端口的服务器。利用一些额外的技术手段,甚至可以骗过内部的http代理服务器,这时在使用内网http代理上网的环境下也可以不受限制的使用网络服务,这称之为SOCKS
over HTTP。通通通([url]www.tongtongtong.com[/url])是老牌SOCKS over
HTTP代理提供商,实现了所有的SOCKS5的连接功能,且有多组国内外服务器。信天游([url]www.xtyproxy.com[/url]),则是最近刚刚出现的代理服务提供商,功能和通通通相比还有差距,但是目前完全免费。当然,使用代理服务器后,将不可避免的出现通信延迟,所以应该尽量选择同网络(指网通/
电信),距离近的服务器。

sock5代理的工作程序是:

1.需要向代理方服务器发出请求信息。
2.代理方应答
3.需要代理方接到应答后发送向代理方发送目的ip和端口
4.代理方与目的连接
5.代理方将需要代理方发出的信息传到目的方,将目的方发出的信息传到需要代理方。代理完成。
由于网上的信息传输都是运用tcp或udp进行的,所以使用socks5代理可以办到网上所能办到的一切,而且不舆目的方会查到你的ip,既安全又方
便
sock5支持UDP和TCP,但两种代理是有区别的,以下分类说明
如何用代理TCP协议
1.向服务器的1080端口建立tcp连接。
2.向服务器发送
05 01 00 (此为16进制码,以下同)
3.如果接到 05 00 则是可以代理
4.发送 05 01 00 01 + 目的地址(4字节) +
目的端口(2字节),目的地址和端口都是16进制码(不是字符串!!)。 例202.103.190.27 -7201 则发送的信息为:05 01 00 01 CA
67 BE 1B 1C 21 (CA=202 67=103 BE=190 1B=27
1C21=7201)
5.接受服务器返回的自身地址和端口,连接完成
6.以后操作和直接与目的方进行TCP连接相同。
如何用代理UDP连接
1.向服务器的1080端口建立udp连接
2.向服务器发送
05 01 00
3.如果接到 05 00 则是可以代理
4.发送 05 03 00 01 00 00 00 00 +
本地UDP端口(2字节)
5.服务器返回 05 00 00 01 +服务器地址+端口
6.需要申请方发送 00 00 00 01
+目的地址IP(4字节)+目的端口 +所要发送的信息
7.当有数据报返回时 向需要代理方发出00 00 00 01 +来源地址IP(4字节)+来源端口
+接受的信息
注:此为不需要密码的代理协议,只是socks5的一部分,完整协议请RFC1928

posted @ 2013-03-01 14:18 zyskm 阅读(9128) | 评论 (0)编辑 收藏

2012年11月29日 #

linux 怎么完全卸载mysql数据库

在linux下开发,mysql数据库是经常用到的,对于初学者来说,在linux怎么安装卸载mysql数据库,也许可能比较痛苦,这里简单介绍下,怎么卸载msql数据库。

a)查看系统中是否以rpm包安装的mysql

  1. [root@linux ~]# rpm -qa | grep -i mysql 
  2. MySQL-server-5.1.49-1.glibc23 
  3. MySQL-client-5.1.49-1.glibc23 
卸载MySQL-server-5.1.49-1.glibc23和MySQL-client-5.1.49-1.glibc23
  1. [root@linux ~]# rpm -e MySQL-client-5.1.49-1.glibc23 
  2. [root@linux ~]# rpm -e MySQL-server-5.1.49-1.glibc23 
b)查看有没有mysql服务

 

  1. [root@linux ~]# chkconfig --list | grep -i mysql 
  2. mysql           0:off   1:off   2:on    3:on    4:on    5:on    6:off 
删除mysql服务
  1. [root@linux ~]# chkconfig --del mysql 
c)删除分散mysql文件夹
  1. [root@linux ~]# whereis mysql 
  2. mysql: /usr/lib/mysql /usr/share/mysql 
分别删除
  1. [root@linux lib]# rm -rf /usr/lib/mysql/ 
  2. [root@linux lib]# rm -rf /usr/share/mysql 

通过以上几步,mysql应该已经完全卸载干净了
原文地址:http://blog.csdn.net/love__coder/article/details/6894566

posted @ 2012-11-29 17:13 zyskm 阅读(21901) | 评论 (0)编辑 收藏

linux 安装应用程序

一、 解析Linux应用软件安装包:

     通常Linux应用软件的安装包有三种:

     1) tar包,如software-1.2.3-1.tar.gz。它是使用UNIX系统的打包工具tar打包的。
     2) rpm包,如software-1.2.3-1.i386.rpm。它是Redhat Linux提供的一种包封装格式。
     3) dpkg包,如software-1.2.3-1.deb。它是Debain Linux提供的一种包封装格式。
      而且,大多数Linux应用软件包的命名也有一定的规律,它遵循:
     名称-版本-修正版-类型
     例如:
     1) software-1.2.3-1.tar.gz 意味着:
     软件名称:software
     版本号:1.2.3
     修正版本:1
      类型:tar.gz,说明是一个tar包。
     2) sfotware-1.2.3-1.i386.rpm
     软件名称:software
     版本号:1.2.3
     修正版本:1
     可用平台:i386,适用于Intel 80x86平台。
     类型:rpm,说明是一个rpm包。
     注:由于rpm格式的通常是已编译的程序,所以需指明平台。在后面会详细说明。
     而software-1.2.3-1.deb就不用再说了吧!大家自己练习一下。
   二、 了解包里的内容:
     一个Linux应用程序的软件包中可以包含两种不同的内容:
     1) 一种就是可执行文件,也就是解开包后就可以直接运行的。在Windows中所 有的软件包都是这种类型。安装完这个程序后,你就可以使用,但你看不到源程序。而且下载时要注意这个软件是否是你所使用的平台,否则将无法正常安装。
     2) 另一种则是源程序,也就解开包后,你还需要使用编译器将其编译成为可执行文件。这在Windows系统中是几乎没有的,因为Windows的思想是不开放源程序的。
     通常,用tar打包的,都是源程序;而用rpm、dpkg打包的则常是可执行程序。一般来说,自己动手编译源程序能够更具灵活性,但也容易遇到各种问题和困难。而相对来说,下载那些可执行程序包,反而是更容易完成软件的安装,当然那样灵活性就差多了。所以一般一个软件总会提供多种打包格式的安装程序的。你可以根据自己的情况来选择。
   三、 搞定使用tar打包的应用软件
     1. 安装:
     整个安装过程可以分为以下几步:
     1) 取得应用软件:通过下载、购买光盘的方法获得;
     2)解压缩文件:一般tar包,都会再做一次压缩,如gzip、bz2等,所以你需要先解压。如果是最常见的gz格式,则可以执行:“tar –xvzf 软件包名”,就可以一步完成解压与解包工作。如果不是,则先用解压软件,再执行“tar –xvf 解压后的tar包”进行解包;
     3) 阅读附带的INSTALL文件、README文件;
     4) 执行“./configure”命令为编译做好准备;
     5) 执行“make”命令进行软件编译;
     6) 执行“make install”完成安装;
     7) 执行“make clean”删除安装时产生的临时文件。
     好了,到此大功告成。我们就可以运行应用程序了。但这时,有的读者就会问,我怎么执行呢?这也是一个Linux特色的问题。其实,一般来说, Linux的应用软件的可执行文件会存放在/usr/local/bin目录下!不过这并不是“放四海皆准”的真理,最可靠的还是看这个软件的 INSTALL和README文件,一般都会有说明。
     2. 卸载:
     通常软件的开发者很少考虑到如何卸载自己的软件,而tar又仅是完成打包的工作,所以并没有提供良好的卸载方法。
     那么是不是说就不能够卸载呢!其实也不是,有两个软件能够解决这个问题,那就是Kinstall和Kife,它们是tar包安装、卸载的黄金搭档。它们的使用方法,笔者会另行文介绍。在此就不加赘述了。
   四、 搞定使用rpm打包的应用软件
     rpm可谓是Redhat公司的一大贡献,它使Linux的软件安装工作变得更加简单容易。
     1. 安装:
     我只需简单的一句话,就可以说完。执行:
   rpm –ivh rpm软件包名
     更高级的,请见下表:
   rpm参数 参数说明
   -i 安装软件
   -t 测试安装,不是真的安装
   -p 显示安装进度
   -f 忽略任何错误
   -U 升级安装
   -v 检测套件是否正确安装
     这些参数可以同时采用。更多的内容可以参考RPM的命令帮助。
     2. 卸载:
     我同样只需简单的一句话,就可以说完。执行:
    rpm –e 软件名
     不过要注意的是,后面使用的是软件名,而不是软件包名。例如,要安装software-1.2.3-1.i386.rpm这个包时,应执行:
    rpm –ivh software-1.2.3-1.i386.rpm
     而当卸载时,则应执行:
    rpm –e software。
     另外,在Linux中还提供了象GnoRPM、kpackage等图形化的RPM工具,使得整个过程会更加简单。这些软件的具体应用,笔者会另行文介绍。

  五、 搞定使用deb打包的应用程序
     这是Debian Linux提供的一个包管理器,它与RPM十分类似。但由于RPM出现得更早,所以在各种版本的Linux都常见到。而debian的包管理器dpkg则只出现在Debina Linux中,其它Linux版本一般都没有。我们在此就简单地说明一下:
     1. 安装
    dpkg –i deb软件包名
      如:dpkg –i software-1.2.3-1.deb
     2. 卸载
    dpkg –e 软件名
     如:dpkg –e software

posted @ 2012-11-29 15:53 zyskm 阅读(294) | 评论 (0)编辑 收藏

仅列出标题  下一页