易栈网-膘叔

这是yhustc帮烂桔搞定AC自动机的过程。上次在PHPX上看到也有人用PHP实现了一个，但我估计在大并发的时候，效率也不会高到哪里去。PHP纯处理字符串效率毕竟还是不咋地。。如果用perl呢？没试过。。。。还是看一下yhustc怎么实现在的吧。
yhustc的网址是：http://www.yhustc.com ，yhustc在文中还提到了twisted，我没用过这个玩意，后来google了一下，发现还是很迷糊。
原文内容如下：

橘子有个网站，访问量大约每天500万PV，为了怕被屏蔽，需要对一系列敏感词进行过滤（超过1200个词），然后才输出内容给用户。

替 换给定关键词的功能，每种编程语言都有，PHP的最强大。基于正则匹配替换的大家都有，就不提了。基于精确匹配的字符串替换，PHP的 str_replace函数可以根据给定的数组，一次函数调用对多关键词进行匹配。自然橘子用的也是这个咯（如果使用的是for i < 1200 顺序的循环，基本系统效率可以无视了）。可是现在问题出现了：系统负载非常高，而且是持续的高，晚上10点的高峰期CPU一直100%的满负荷运行。

要优化性能，就需要一步步的分析瓶颈在什么地方：

1、 由于橘子说有些关键词以后没准会解封，所以不想把原始内容就保存为带上一堆****这样子。因此原始内容都保存的好好的，那么给用户输出的，是每次过滤过 后的结果。那么这里自然有个问题，就是相同的内容，针对每个用户都被过滤了一次，这不明摆着的CPU浪费嘛。我说你可以考虑空间换时间， 加硬盘后上缓存，一定时间内都只过滤一次，其他用户都读缓存即可，这样计算开销几乎全部省下来了。但是橘子哭穷啊，SSD的硬盘两千多一块。IDE的插上 去就得给机器断点，现在百度正在考验自己的站点，这个电断不得（如果IDC够好的话，夜里换其实没啥问题，偏偏他的IDC技术不照）。那行，看来还是只能每次都过滤了，你爱折腾我也没办法。

2、分析一下PHP的str_replace，他既然支持多关键词的数组输入，说明内部肯定是一个AC自动机。 什么是AC自动机，大家请自行google并学习，我就不长篇大论了。本来多关键字替换的应用，AC自动机是最好的选择，但是为啥他的服务器负责就是居高 不下呢？这与PHP的实现机制有关，PHP的生命周期是一个WEB请求，那么每个用户请求页面时，调用一次str_replace。即使输入的数组是一摸 一样的，也必须重新构建一个AC自动机的搜索树，这个搜索树初始化的计算开销以及内存开销乘以并发数，严重降低了系统性能。（也不全是PHP生命周期引发 的，主要是因为AC自动机是封装在str_replace内部实现的，即使是串行的调用，相同输入仍然会每次都初始化自己的搜索树）

那么我们现在的问题就很明确了：实现一个全局的AC自动机，用他来处理所有的请求即可。这个任务PHP是没法执行了，加之要找AC自动机的相关模块才能自己二次开发，选定了python来干这个事情。https://hkn.eecs.berkeley.edu/~dyoo/python/ahocorasick/  这里是python的AC自动机的模块，非常的简单易用，看看就会。 

读 取关键词列表，添加关键词，构建搜索树，OK！测试一下关键词的搜索效果，windows平台下10000次的循环搜索，python的程序比直接用 PHP的str_replace执行时间缩短了200倍，当时震惊的一塌糊涂！！（不过这跟PHP在windows平台执行效率低也有关系，linux上 面明显要快非常多）

话不多说，把python的程序封装到一个Socket TCP Server里面，这样便于WEB的PHP程序通过套接口请求服务，把原文发过来，过滤后又发回去，这样就实现了一次过滤。 

高高兴兴的把程序发给橘子，结果一上服务器，反而比先前的PHP str_replace效率还差。

3、这时候才想到一个问题，我做的测试是串行执行的，只能算运行总时间。如果要上web上面应用，需要考虑并发问题。也就是需要ab测试。ab -c 500 -n 500测试了一把，果不其然，效率忒低。继续分析，我觉得是高并发情况下，python那个简单封装的TCPServer不够用。线程开销和阻塞式的服务 模式拖低了系统效率。为什么会有这种问题，请问自己“你写的http server能跟apache比不？”这里面的性能优化太高深，搞不明白，怎么办呢？我们需要站在巨人的肩膀上才行。于是想到可以用Twisted库来构建自己的TCP Server。什么是Twisted？也请自行google，并且学习一下。

把TCP的服务器用Twisted改写了之后，AB测试了一把，大大的有惊喜：

PHP的str_replace版本

ab -c 500 -n 500 str_version.php
Requests per second:    165.86 [#/sec] (mean)
Time per request:       3014.552 [ms] (mean)
Time per request:       6.029 [ms] (mean, across all concurrent requests)

PHP + python的旧版本的tcp server + AC自动机

ab -c 500 -n 500 old_ac_filter.php
Requests per second:    165.06 [#/sec] (mean)
Time per request:       3029.286 [ms] (mean)
Time per request:       6.059 [ms] (mean, across all concurrent requests)

PHP + python的twisted版本的tcp server + AC自动机

ab -c 500 -n 500 twisted_ac_filter.php
Requests per second:    620.93 [#/sec] (mean)
Time per request:       805.246 [ms] (mean)
Time per request:       1.610 [ms] (mean, across all concurrent requests) 

高并发的情况下，每秒处理的请求数提升了4倍，效果那不是盖的。

晚上十点，又迎来了一个访问量的高峰，情况非常稳定，橘子回报：

“之前这个点都是满负载跑-，-  -v-而且还是关闭了在线统计功能的情况下”

“现在我把在线统计打开了，cpu也就50%左右”

反正是够用了，就优化到此为止吧。

其实这个需求，还有进一步优化的余地，空间换时间+全局的AC自动机，可以把系统性能提高若干数量级。 

大 致思路是：在内容刚刚产生的时候PHP通过UDP消息把需要处理的东西发送给python程序，python实现一个两个线程的生产消费者模式的工作进 程。消费线程每次取出消息槽里面一个需要处理的请求，使用一个全局的AC自动机对内容进行处理，然后存放起来，继续处理下一个请求，当没有请求的时候就阻 塞住。生产线程是一个UDP的server，收到数据后就给消息槽添加一个请求数据，并且给消费线程发送信号激活它工作。如此往复即可。

--EOF--
小知识：
Twisted是一个事件驱动的网络框架，它由Python写成，基于MIT授 权协议。Twisted支持各种各样的底层协议，比如：TCP，UDP,SSL/TLS,多地址传输，Unix socket等，以及HTTP，NNTP,IMAP,SSH,IRC,FTP等其他高级协议。有了这些支持相当于有了一个强有力的基础，你可以用它来开发 诸如web server,Mail server，即时通讯软件 等等。

这里还有一个简单的教程（繁体字）

http://ez2learn.com/index.php/python-tutorials/twisted-tutorials

　　众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以字为单位，句子中所有的字连起来才能描述一个意思。例如，英文句子I am a student，用中文则为：“我是一个学生”。计算机可以很简单通过空格知道student是一个单词，但是不能很容易明白“学”、“生”两个字合起来 才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分词，有些人也称为切词。我是一个学生，分词的结果是：我是 一个 学生。
目前主流的中文分词算法有：

1、 基于字符串匹配的分词方法

这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功 （识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最 短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下：
1）正向最大匹配法（由左到右的方向）；
2）逆向最大匹配法（由右到左的方向）；
3）最少切分（使每一句中切出的词数最小）。
还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向 最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169， 单纯使用逆向最大匹配的错误率为1/245。但这种精度还远远不能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各 种其它的语言信息来进一步提高切分的准确率。
一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识别和切分出一些带有明 显特征的词，以这些词作为断点，可将原字符串分为较小的串再来进机械分词，从而减少匹配的错误率。另一种方法是将分词和词类标注结合起来，利用丰富的词类 信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。
对于机械分词方法，可以建立一个一般的模型，在这方面有专业的学术论文，这里不做详细论述。

2、 基于理解的分词方法

这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义 现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义 进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可 直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。

3、 基于统计的分词方法

从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映 成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字X、Y的相邻共现概率。互现 信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要 切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一”、“之 一”、“有的”、“我的”、“许多的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典（常用词词典）进行 串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识 别生词、自动消除歧义的优点。

值此，放上收藏的三篇文章和程序
1、yhustc的分词词库（采用sqlite，无词频分析，下载地址为：http://www.neatcn.com/dict/dict.tar.gz，在http://www.neatcn.com/dict/有简单的试用，也可以通过http://www.neatcn.com/dict/test.php?type=json&encode=gbk&contents=xxx等调用返回），

2、dede的分词，(织梦的算法:http://www.dedecms.com/html/chanpinxiazai/20061229/3.html#，该页同时有演示，采用CSV文件）

3、一篇比较老的分词程序：http://www.neatcn.com/show-592-1.shtml

jQuery这种轻量级的框架大家使用的都比较多，1.3后效率据说又上升了不少，因此，开发基于jQuery的插件也就显得那么理所当然了。
一般来说，jQuery有两种插件模式，一种是：$.extends({}) ，另一种是：$.fn.extends({})
个人理解：前一种是属于全局性的调用，后一种是针对某个元件的绑定调用。这当然是简单的理解。但事实上，也基本上就是这么做的。

官方的例子也比较简单：

看上去是不是容易？然后就可以直接调用了。 $.min(2,3) 返回2
一般情况下，为了在扩展中使用$，却又担心的页面使用了jQuery.noConflict()而取消了$指向jQuery的引用，则需要这样写

这样写不仅能够将$显式指向jQuery，而且将产生的变量封在function的作用范围内，不会污染window全局。
而基于$.fn.extends({})的扩展又如何开发呢？

在这里我引用Roby的译文：http://www.robysky.com/archives/171
英文原文：http://www.learningjquery.com/2007/10/a-plugin-development-pattern

我认为以下插件开发模式是必须应该掌握的：
1.在JQuery命名空间内声明一个特定的命名；
2.接收参数来控制插件的行为；
3.提供公有方法访问插件的配置项值；
4.提供公有方法来访问插件中其他的方法（如果可能的话）；
5.保证私有方法是私有的；
6.支持元数据插件；

下面，我将逐一讲述上面的内容，并在同时给出相关的简单插件开发代码。
1.在JQuery命名空间内声明一个特定的命名

这意味着开发的是一个单一命名的插件脚本，如果你的脚本包含多个插件或者有补充性质的插件，比如$.fn.doSomething() 和$.fn.undoSomething()，那你得声明多个命名了。但是总体来说，当开发一个插件时，我们应该努力做到用一个单一的命名来搞定整个插件。

在例子中，我们将声明一个名为“hilight”的插件。

我们可以这样调用：
$(’#myDiv’).hilight();
但是假如我们需要打破这种单一的命名和调用方式呢？有很多理由支持我们这么做：设计上的需要；更加简单和可读的配置；而且那样将更加符合OO的要求。

在没有给命名空间来到麻烦的前提下，将插件的部署打破成为多个函数的形式将是十分繁琐的。我们通过认识并利用JavaScript中 functions是最高层的对象，和其他对象一样，functions可以被赋予属性，前面我们已经将hilight命名声明在了JQuery的原型对象上，那么，其实，其他的我们想扩展的属性或对象都能够在hilight上进行声明。稍后将详细讲述此点。
2.接收参数来控制插件的行为；

来为我们的hilight插件添加指定前景和背景色的功能，我们需要在函数中允许一个object类型的选项设置。如下所展示的那样：

现在，我们的插件可以这样来调用：

$(’#myDiv’).hilight({
  foreground: ‘blue’
});
3.提供公有方法访问插件的配置项值；

上面的代码我们可以做一下改进，使得插件的默认值可以在插件之外被设置。这无疑是十分重要的，因为它使得插件用户可以使用最少的代码来修改插件配置，这其实是我们利用函数对象的开始。

 4.提供公有方法来访问插件中其他的方法（如果可能的话）

这里要讲的方法和前面的讲解一脉相承，用此方法来扩展你的插件（而且能够让其他人进行扩展）是件很有意思的事情。例如，在扩展hilight插件时，我们可以定义一个format方法用来格式化高亮显示的文本，原来的hilight插件和扩展了format方法的插件代码如下：

如前面所述，我们已经很容易的通过设置options对象的属性来允许一个回调函数来覆写默认的格式设置。在这里有另外一个非常棒的方法来个性化你的插件，上面展示的方法实际上就是通过暴露format方法，使其可以被重新定义。这种做法使得其他人可以采用他们自己的习惯和方式来重写你的插件，这意味着他们可以为你的插件写额外的扩展插件。
仔细考量一下前面我们用到的插件例子程序，你可能会想“我们究竟应该在什么时候使用这种插件方式来实现需求”的问题。一个来自现实应用中的插件便是“ Cycle Plugin”，它是一个支持多种滑动显示特效的插件，特效包括滚动、滑动和渐变等等。但是，实际上，并没有办法来定义每一个可能会用在滑动变幻上的特效。这就是这种扩展方式的有用之处。“ Cycle Plugin”插件暴露了”transitions”对象，这使得用户只需要按照如下方式便可以添加自己的变幻定义：
$.fn.cycle.transitions = {
…
};
这种技巧使得用户可以定义或者采用自己习惯的方式来扩展“ Cycle Plugin”。
5.保证私有方法是私有的；

上面提到的暴露插件中的公有方法的技巧使得插件能够被覆写，这将使插件变得十分灵活而强大，但至于哪一部分，那些属性和方法应该被暴露出来，你得小心了。一旦使其能够被外界访问到，你就得注意到任何调用参数和语义化的变动都可能使其丧失向前的兼容性。作为一般准则，如果不确定是否应该暴露某个属性或对象的话，那就最好别那样做。
那么我们应该怎样来定义多个方法而不至于使命名空间混乱并且保证不被暴露再外呢？这就是闭包的工作，为了便于演示，我们给插件加入了一个叫做 “debug”的功能，它用来记录firebug控制台所选择的网页元素数目。为了创建一个闭包，我们将整个功能的定义放入在一个function中了（有关这方面的知识，可参见JQuery手册）。

debug方法在这里是无法被在插件以外访问到的，因此，我们称之为它是插件私有的。
6.支持元数据插件；

根据你所写的插件的类型，为你的插件加入元数据插件的支持将使其变得更强大。就我个人来说，喜欢采用元数据插件的重要原因便是它可以让你使用定义之外的标签来覆写你的插件属性设置（这在创建demo和例子时十分有用），而且支持它十分的简单。
更新：这部分内容可以在本文的评论中展开讨论（既然有争议的话）

改动部分的代码会做如下的事情：
*测试metadata插件是否可用
*如果可以，将用metadata扩展options对象
这被加入到jQuery.extend，作为其最后一个参数，所以它可以覆写任何其他参数设置。现在我们可以通过下面的方式控制其行为：

而在调用方面，我们通过一行简单的代码就可以实现预期的效果：
$(’.hilight’).hilight();

将上面所述内容涉及到的代码放在一起，完整的例子程序代码如下：

看完以上的内容，你是不是对jQuery的插件开发加深了一定的了解了呢？
顺便提一下，yhustc在自己的博客上写了一个基于jQuery的软键盘插件，你是不是又可以根据上面的教程来写一个基于$.fn.extends的扩展呢？让yhustc的插件可以绑定在某个元件上？

YY博鼎力之作哦，大家支持一下。
除此之外，他还写了一个yBlog，同样请大家支持
http://www.yhustc.com，就是yBlog的官方网站。

介绍：

ThinkPHP 2008年离线资料包，将ThinkPHP论坛使用版面与帮助资料版面2008年所有帖子全部采集生成HTML文件，并添加了全文检索功能。可以在不联网的情况下方便查找论坛中相关问题的讨论，并且可以方便的搜索，比CHM的搜索更强大的搜索。点击搜索结果可以直接来到帖子页，也可以直接通过首页进入相关版面列表，就跟操作BBS一样。

注意：需要安装.NET框架2.0及以上版本

图片：

下载地址：http://www.yhustc.com/ThinkPHP2008.rar

本站分流：下载