分类 设计模式 下的文章

设计模式笔记:第二个设计模式原则——优先选择组合而非继承

QQ截图20151223224240.jpg

有些OOP程序员认为对象重用、扩展就等同于使用继承。一个类可以有大量属性和方法,通过继承这个类,我们增加新属性和方法,就能轻松的进行扩展,因为无需再重新编写代码。不过最后对于紧密绑定的对象,一味的使用继承方式来扩展会导致这么一个问题,那就是过度继承

- 阅读剩余部分 -

智能聊天机器人小黄鸡及其制作方法

   今天很荣幸担任主讲,与大家一起讨论智能聊天机器人小黄鸡~讲得不好请见谅,提问请轻虐~嘻嘻
       今天的讲座主要分为三个部分,分别是:1. 什么是小黄鸡 2.小黄鸡的基本原理 3.如何自制小黄鸡。
Part 1 什么是小黄鸡
      很多人认识小黄鸡是从人人网开始的,只要@小黄鸡,它就会跑出来跟你聊天。这就是一个典型的人工智能的聊天机器人。
      实际上,人人网小黄鸡是华科一位08级的同学,通过人人网接口,调用韩国聊天机器人SimSimi的API,自动回复提问者。
也就是下图:
1

  SimSimi最早风靡于移动平台。至于它的具体原理以及实现方法我们将在后两部分介绍。也就是说,人人网小黄鸡的原型,就是智能聊天机器人SimSimi。那么什么是聊天机器人呢?
       简单地说,就是基于人工智能原理(Artificial Intelligence,以下简称AI),通过对聊天文本进行分析后给出应答的一类程序。世界上最早的聊天机器人诞生于20世纪80年代,这款机器人名为“阿尔贝特”,用BASIC语言编写而成。而由于中文对“词”划分的模糊及歧义繁多等等原因,中文聊天机器人发展得相对较慢,目前有赢思的小i,爱博的小A,腾讯也有。

Part   2 小黄鸡的基本原理

       AI聊天机器人小黄鸡的工作可以被分成两个部分:训练+匹配。(其实很多AI的东西都可以被这么划分,比如人脸识别,语音识别等等)

2.1 训练

       Simsimi中的“教学”,就是训练的过程,目的在于构建或是丰富词库。
       流程描述如下:
S1:用户通过教学界面向系统提出一个话题与相应应答;
S2:系统对该话题进行分词,判断该话题在系统知识库中应存放的位置;
S3:在系统知识库中添加该话题及相应应答。
      可以看到,这里涉及到两个问题:给出一个话题,系统是如何分词的?词库要如何设计才能又快又准地应答?

2.1.1分词方法

       有人认为我教小黄鸡“埃菲尔铁塔上45度角仰望星空”回答是“呵呵”,那下次它再看到“埃菲尔铁塔上45度角仰望星空”整句话的时候才会有相应回答。但实际上,下次只要它看到“埃菲尔铁塔”就会“呵呵”了好嘛。
       这是因为聊天机器人的存储并不以句子为单位(那样太费时费空间),而是以词。于是,分词,几乎成为聊天机器人的核心。
      英文分词好说,人家用空格什么的就搞定了,但中文不一样,对于一句话,人们可以用自己的认识区分词语,而机器人要怎么做,就是中文分词算法的研究范畴了。
      中文分词技术俨然是一个重要的研究方向,隶属于自然语言处理。现有的分词算法可以分为三大类:基于字符串匹配的分词方法基于统计的分词方法基于理解的分词方法
      用户在聊天时的一个显著特点是所提出的话题一般都是比较短小的,而不是长篇大论,不具有段落篇章结构,绝大多数就是少数几句话。基于统计的分词方法适用于有段落、篇章结构以及上下文关系的文段。基于理解的分词方法目前并不成熟,且时间复杂度高,速度慢。于是,只有基于字符串匹配的分词是比较适合的。
      基于字符串匹配的分词方法,又叫做机械分词方法。按照扫描方向的不同,机械分词法可以分为正向匹配和逆向匹配。(e.g. 字符串“北京华烟云”,正向匹配为《北京,华烟云》,逆向匹配为《北,京华烟云》)逆向匹配的切分正确率要高于正向匹配法,为了便于发现歧义切分,有时候将两者结合起来形成双向匹配法。按照不同长度优先匹配的情况,可以分为最大(最长)匹配和最小(最短)匹配,也就是长词优先和短词优先。按照匹配不成功时重新切取的策略,机械分词法可以分为增字法和减字法。
基于词典的“双向最大匹配”法是目前中文信息处理中最简单有效的方法,有这样的统计:汉语文本中90%左右的句子,其与双向最大匹配的结果相吻合,而且是正确的分词结果。
       当正、反向最大匹配算法得出来的切分结果不一样时,就必须对其进行歧义处理,在此不再赘述。

2.1.2词库设计

       由于中文词的特点:1.中文词是一个开放集,词数在增长;2.以不同字开头的词的数目变化很大,多的达到数百个,少的也有可能只有一个或者没有;3.词的长度变化也很大,有单字词,也有由六、七个字成词的。
这就要求在设计词典时,除了考虑访问效率外,还得充分考虑存储利用率。

请看这种数据结构,就能很好地平衡时间与空间。

2

      首字Hash表通过一次哈希运算就可以直接定位汉字在表中的位置。一个单元包括三项内容:C:存储首字;F标志位:存储以C为首字的最长词条的长度;P:指向词表索引表。
        解释一下哈希:散列表 Hash table,也叫哈希表,顾名思义就是把数据都打散了,再按一定规律存起来,加快访问速度。是根据关键码值Key而直接进行访问的数据结构。
       举个栗子:我想将[0,100)做成一个哈希表,选取“模10”作为散列函数,以数组作为存储单元,则得到A[10][10]的数组,A[0]里依次存着0,10,20…90;A[1]里存着1,11,21…91。依次类推。
现在举一个训练小黄鸡的例子:我教小黄鸡说“大白天的做什么美梦啊?”回答是“哦哈哈哈不用你管”。
S1:应用双向最大匹配算法分词:双向分词结果,正向《大白天,的,做什么,美梦,啊》;反向《大白天,的,做什么,美梦,啊》。正向反向都是一样的,所以不需要处理歧义问题。长词优先选择,“大白天”和“做什么”。
S2:以“大白天”举例,假设hash函数为f(),并设f(大白天)指向首字hash表项[大,11,P]。于是由该表项指向“3字索引”,再指向对应“词表”。
S3:将结构体<大白天,…>插入队尾。体中有一个Ans域,域中某一指针指向“哦哈哈哈不用你管”。
S4:完成训练。

2.2 匹配

       可以被描述成如下流程:S1:用户通过聊天界面向系统提出一个话题;S2:系统对该话题进行分词处理;S3:在系统知识库中寻找与该话题匹配的话语回复用户。

       基于词典的分词算法分为词典加载预处理最大匹配歧义消解几个阶段。

其具体流程如下:

S1:预处理阶段,按照特殊字符(英文字母、数字、标点符号等)将待分析文本进行断句,将待切分的文本切分为只有中文的短句子,这些句子是下一步分词处理的基本单位;
(举个栗子:输入“asdfadf东北师范大学哈哈哈dfadflakfl(*^__^*) 嘻嘻……”,simi只会对其中的中文“东北师范大学哈哈哈嘻嘻”做出响应;输入“(*^__^*)”时,输出“I have no response.”)
S2:对断句出来的句子进行双向最大匹配(双向匹配,长词优先)分词,分词后的结果作为S3的输入;
(举个栗子:输入“东京古巴比伦”,正向与反向切词结果均为《东京,古巴比伦》,长词优先,所以simi只对“古巴比伦”做出响应;输入“古巴比伦埃菲尔铁塔”,正向与反向切词结果均为《古巴比伦,埃菲尔铁塔》,此时Simi对“埃菲尔铁塔”做出响应)
S3:对上一步分词得到的结果进行比较,判断是否存在歧义,如果存在歧义,就进行一定的歧义消解
S4:重复S2、S3,直到处理完步骤一中断句所切分出的所有句子单元。
算法流程如图所示:
3
这里给出与小黄鸡对话的例子:我问小黄鸡:“埃菲尔铁塔上45度角仰望星空”。
S1:双向最大匹配分词:正向反向均为《埃菲尔铁塔上,45度角,仰望星空》,没有歧义。长词优先,系统选择了“埃菲尔铁塔上”作为关键词;
S2:系统在知识库中用刚才说的哈希函数f(埃菲尔铁塔上),找到比如[埃,11,P] 的表项,顺着指针找到6字词的索引,顺着索引找到6字词表,遍历词表,找到<埃菲尔铁塔上,…>结构体;
S3:系统随机选择该结构体Ans域中的一个回答(也有可能是根据频率高低来选择)。比如“两年之后等着你”。
S4:输出回答,匹配结束。

Part 3 如何自制小黄鸡

       根据第二部分所介绍的原理,个人想要真正完成整个小黄鸡的制作是有难度的。如果能做出一个智能较高的聊天机器人,那直接可以去申请专利开公司了~
       所以在这里我们介绍两种比较简单易行的方法,跳过对智能算法的研究,直接调用SimSimi的库。

3.1 通过获取Cookies方法

       首先我们来看人人网小黄鸡是怎么做的。
       原作者团队在github上给出了源代码,网址https://github.com/wong2/xiaohuangji,他们使用Python语言,获取Cookies,通过人人网的接口,将Simi的库连接到人人上。
       也就是说,人人网小黄鸡并没有真正研究第二部分讲到的 AI聊天机器人的算法,而是通过调用人家Simi的库!这就是人人网小黄鸡跟Simi的关系。
Cookies:指某些网站为了辨别用户身份、进行session跟踪而储存在用户本地终端上的数据(通常经过加密)。利用网页代码中的HTTP头信息进行传递。
(举个栗子,我们第一次登录保研论坛时输入用户名与密码,然后选择保存密码,就相当于保存Cookies,下次再打开eeban就不用再登录了~
       Cookies作为一个大有用处的存在,同时也极大地危害着网络信息安全。因为是可以通过例如JS脚本等方法窃取Cookies的。想想看,别人获取了你的Cookies,都不用知道你的用户名密码就能以你的身份查看邮件,浏览网页等等……当然这是题外话,有兴趣的我们以后讨论~所以希望大家能经常清理自己的Cookies,不给坏人可乘之机~~)
       回到我们的小黄鸡,下图是人人网小黄鸡源代码中关于获取Cookies的一段:
4
       我们要自制呢,就不用他们那么麻烦~咱们只要几行小代码就可以了~
        简单介绍一下核心算法:
S1:利用session对象获取本机在http://www.simsimi.com/talk.htm 上的Cookies
(session,在网络应用中被称为“会话”。简单地说,它就像在网站顶层的一个盒子,无论网页怎么跳转,都能够保存用户的信息。这里注意!Talk页是Simi免费的聊天页面,这一点很重要!)
S2:构造头信息,准备将Cookies添加在HTTP头部信息中
S3:从SimSimi API接口中获取本机的响应
(刚才说过,Cookies利用HTTP头信息进行传递,所以我们将刚才talk页上的Cookies添加在 API页上,相当于是talk页在调用API!!!这一点很重要。
举个栗子,我们拿着一把锁,去找talk页,talk给了我们一把钥匙,但是我们开锁手法我们不知道,于是我们将锁+钥匙一起送给API,然后它帮我们打开了盒子~~~bling~~bling~~)
来,我们看看原理图:
5
下面是我用这个方法做的小黄鸡1号:
6
确切的说是这是一只小黄鸡与一只小黄鸭的互掐。哈哈!
       想要做小黄鸡,这是一个省时省力的方法,但是。。。不得不说这是在盗用SimSimi的劳动成果。。。人家指望它的API库卖钱的呢。。。。额额额
       所以接下来我们来看正版的制作方法~~

3.2 通过key调用API接口

      下面这个网址给出了SimSimi的官方API文档:http://developer.simsimi.com/api
7
      文档已经写得非常清晰了,http://api.simsimi.com/request.p?key=your key&lc=en&ft=1.0&text=hi这一行代码就是在调用官方API接口!也就是说,只要你申请到了key,就能调用simi的API,是不是想想就很爽?~最开始我给大家的小黄鸡2号就是正版鸡有木有~现在来讲解一下怎么做。我选择J2EE平台,MVC模式,JSP+JAVA语言。
       最核心的思想是这样的:我们将从表单中获取的字符串,送去调用官方API接口,用request对象返回结果,再打到屏幕上~~是不是很简单?
下面介绍详细算法流程:
S1:talk.jsp——用户填写表单内容,将参数String text传递给chuil.jsp;
S2:chuli.jsp——request对象获取传递来的参数,调用API,用Content类中的getContent(urls)方法获取网页的内容,返回结果String ans,将ans传递给talk.jsp;
S3:talk.jsp——request对象获取传递来的参数ans,将ans打印到屏幕上。结束。
*其中Content类用于获取网页内容,直接上网找的,都不用自己写~hiahia
这是小黄鸡2号的效果图:
8
     正版的方法就是简单~但是因为是正版的,就得付出代价,key是要钱的。我现在用的是试用版,key的有效期限是90天,并且每天只有100次响应,也就是说你一天只能调戏它100次。。。是不是很桑感。

总结

       经过这么多的介绍,大家是不是对类似小黄鸡(SimSimi)的人工智能聊天机器人有了初步的认识。其实你可以做很多只“小黄鸡”,但它的核心都是Simsimi的库,是人家的东西。所以说偶们新时代的年轻人应该要有自己创新意识~让我们来开发自己的智能算法~做自己的小黄鸡、小黄鸭、小黄狗、小黄瓜吧!~~
reference:

  • [1]李鹏.中文分词在聊天机器人中的应用研究[D].中南大学.2009(05)
  • [2] 易顺明,胡振宇. 中文聊天机器人原型系统的设计[J]. 沙洲职业工学院学报. 2007(02)
  • [3]查询处理及分词技术.百度
  • [4]设计和构造一个自动应答聊天机器人都涉及到哪些技术.知乎

问答环节

训练的话玩家调戏它的数据会被录入作为以后回答别人的参考么?还是需要相应权限才能存入库里?
这个就是教学界面。会的。玩家教给它的话题,会在切词之后,打包它的回答,一起存入词库。别人触发相似的关键词,也有可能回答刚刚你教过的答案。
那一个问题有不同答案,如何选择呢?
一个关键词下链接了好几种不同的回答,系统会随机选择一个,比如输入“哈哈”,回答有可能是“呵呵”“笑什么笑”……
以前的这个词表里面对于每个可能出现的词已经有了确定的答案的意思吗?
对,构建词库的时候,还有训练的时候都已经写进去了
但是训练的时候不能随便的吧?万一教他的是错误的知识呢?
谁都可以~~但是一般会有过滤系统,要审核的,像simi就有做任务这个玩法,任务就是,给你别人的回答,让你判断是否可以给不满16岁的孩子看,也有存进去的时候设置敏感词什么的。
原文地址:http://www.cnblogs.com/huj690/archive/2013/01/24/2875114.html

了解PHP设计模式之观察者模式

观察者模式是一种事件系统,意味着这一模式允许某个类观察另一个类的状态,当被观察的类状态发生改变的时候,观察类可以收到通知并且做出相应的动作,观察者模式提供了避免组件之间紧密耦合的另一种方式。

在观察者模式中,被观察者称为subject,观察者称为observer,为了表达这些内容,SPL(Standard PHP Libaray)提供了SplSubject(被观察者)和SplObserver(观察者)两个接口。在编写观察者模式时,只要实现这两个接口即可。接口如下:

 //被观察者接口
interface SplSubject{
   public function attach(SplObserver $observer);//注册观察者(注册的观察者:当我(被观察者)的某个状态改变时,需要通知的对象)
   public function detach(SplObserver $observer);//释放观察者
   public function notify();//通知所有注册的观察者的方法
}
  //观察者接口
  interface SplObserver{
   public function update(SplSubject $subject);//观察者进行更新状态
  }

这一模式的概念是SplSubject类维护了一个特定状态,当这个状态发生变化时,它就会调用notify()方法。调用notify()方法时,所有之前使用attach()方法注册的SplObserver实例的update方法都会被调用。

以下是实现代码:

  <?php
//被观察者实现类
class DemoSubject implements SplSubject {

  private $observers;    //存放观察者的类
  private $value;

  public function __construct() {
    $this->observers = array();
  }
//注册观察者
  public function attach(SplObserver $observer) {
    $this->observers[] = $observer;
  }

 //释放观察者
  public function detach(SplObserver $observer) {
    if($idx = array_search($observer,$this->observers,true)) {
      unset($this->observers[$idx]);
    }
  }

 //通知所有观察者,执行观察者类中的update方法
  public function notify() {
    foreach($this->observers as $observer) {
      $observer->update($this);
    }
  }

/*设置状态,当状态发生任何变化时,都会调用notify方法通知所有的观察者,即调用观察者类中的update方法*/
  public function setState($value) {
    $this->value = $value;
    $this->notify();
  }
//
  public function getValue() {
    return $this->value;
  }

}

//观察者简单类
class DemoObserver implements SplObserver {

  //接收被观察者发送的通知
  public function update(SplSubject $subject) {
    echo 'The new value is '. $subject->getValue();
  }

}

$subject = new DemoSubject();//初始化被观察者
$observer = new DemoObserver();//初始化一个观察者
$subject->attach($observer);//添加一个观察者
$subject->setState(5);//被观察者修改状态。
?>;

输出结果为:

The new value is 5

观察者模式的优点在于,挂接到被观察者上的观察者可多可少,并且不需要提前知道哪个观察者会响应被观察者发出的响应事件。

这种设计模式在很多PHP框架中都被使用到,如Yii等。

SNS网站Feed功能设计

在SNS的网站中,最核心的功能就是Feed功能,Feed就是一条twitter或一条好友动态。该功能面临的挑战是:每天产生成千上万条数据,数据推送的需要实时性等,做网站其实最大的难点就是对海量数据和高并发的处理。本人通过对Twitter和新浪微博架构的一些资料的学习,大致了解了如何实现一个Feed功能。一个Feed功能往往有多种实现方式,最常见的是这3种:推模式、拉模式、推拉结合模式。

推模式:

推就是把自己的发的feed推送到每个粉丝那里,就是一条feed在数据库中存储多份,做法就将feed表按userId分库,对应粉丝Id的库中插一条记录。这种做法的缺点就是数据量大,数据冗余太严重,如一个明星用户有1000万粉丝,那么他发一条feed,就要产生1000万条记录。Feed的推送需要异步队列,队列的好处就是降并发,推送是需要时间的,所以一个明星发了一条feed后,当最后那个粉丝看到这条feed可能已经是几分钟后的事情了。这种模式的优点是用户查看Feed就很容易了,根据userId查询就可以了。这种做法是牺牲大量储存空间来换取网站的查看性能。

拉模式:

拉就是用户要查看动态时就去每个关注者那边找,然后聚合并展现。Feed数据只储存一份,省了很多空间。这种模式在用户量较小的网站就很容易实现,展示只要一条SQL语句。但是当用户多了以后就会遇到问题,比如我关注了2000个用户,而这2000个用户都是活跃用户,每天都会产生很多feed。我查看 feed时就要去2000个关注者那里找最新的几条,合并和按时间排序,每次查看一条查询语句就快把数据库搞得累死,而且合并和排序这些feed计算量太大。拉模式在用户关注人数很多的网站不太适合。

推拉结合:

顾名思义就是两种模式的结合,将两者的优点结合。不活跃的用户(偶偶上线,关注人数又少的僵死用户等)推送的时候就不要推送给他们,省点资源,当他们上线查看时就直接拉,因为他们关注的人比较少,拉也不是很耗性能。

最后,不管采用什么方法实现,少不了异步队列,nosql等工具。比如发表feed的时候就往队列里一扔,前端马上返回,异步慢慢处理,而用户一点也察觉不出来。Nosql缓存,比如一些计数(关注数、粉丝数神马的)直接用redis、TT等储存,还有feed列表可以存储在memcached或redis 中,redis的list功能很适合这种情形,但是一些大网站还不敢这么做。

以上借鉴于新浪微博架构PPT。