Django的HTTPHandler模型图

很早之前的一篇读书笔记,今天有朋友问我这方面的问题,正好就重新贴出来吧.
时间过得好快啊(:

也谈网页正文提取[下]

上回书到使用行文本密度(Text Density)来解决网页正文提取问题.给出了一个学术界定量的文本行密度阀值.一般来说武功秘籍的下半部总是看起来牛逼些的,就像当年梅超风练的<九阴真经>一样,练了半本书的一路掌法,已经是妇孺闻之变色的"女魔头"了.所以本博的这下半篇也来不得丝毫差池,怎么也得看起来十分有料才行.

前文所述之阈值估计过程本质上是一个全局统计各个密度的过程，并没有像学习算法一样考虑文本行的分布情况，如在页面的中间发生以及文本行可能在一起出现的可能性高等。但阈值估计有助于快速地选择行，而且可以在没有学习样本的情况下获得较好的表现。

但是不同的场景需求对结果的精度要求是不一样的,作为一直致力于追求更快,更准,更优的本博来说,自然是希望抽取的结果最优.这里的"最优"有两个方面的含义：

• 抽取的结果尽可能包含正确的行
• 抽取的结果尽量少地包含错误的结果

为了达到这样的效果,这里介绍两个主要的手段,神经网络(ANN)和错误控制(FDR).

首先来看看神经网络，对这个名字觉得耳熟的朋友肯定至少被忽悠过一次数据挖掘或者人工智能.至少本博第一次听说的时候,是被唬的不行,觉着以自己愚钝的天资还是做不明真相的围观群众好了.但是在我们这里,没有必要那么夸张,下面就由有着生物学背景的本博带领去一亲人工神经网络的芳泽.

既然是人工神经网络,从名字就知道这肯定是模仿其他某些神经组织结构机理而形成的模型.实际上,它所模仿的对象您现在也用着呢,那就是我们人类的"神经细胞"，专业的说法叫做神经元.

神经元结构上大致都可分成胞体和突起两部分,突起又分树突和轴突两种。轴突开始一段称为始段，离开细胞体若干距离后始获得髓鞘，成为神经纤维。我们日常感受的刺激在神经结构上就由树突将冲动转向细胞体.典型的神经突触是在两个神经元之间形成的单向通信机制。神经信息的流向是从突触前细胞到突触后细胞。突触通常形成在突触前细胞的轴突和突触后细胞的细胞体或树突之间.如下图所示

人工神经网络就是模仿上述神经突触联接的结构进行信息处理的数学模型.由大量的节点（或称“神经元”）和之间相互联接构成。每个节点代表一种特定的输出函数.每两个节点间的连接都代表一个对于通过该连接路径的加权值,也叫权重,这相当于人工神经网络的记忆. 输出则依赖节点间的链接方式，权重值和节点输出函数.神经网络的构建一般用来模拟自然界某种算法或者函数的逼近,或者某种逻辑的推演(例如本文的问题).


一个典型的单层神经元网络由有限个神经元构成,上图.

从左到右分别是:

• 输入层,众多神经元接受大量非线形输入信息。
• 隐藏层,简称“隐层”，是输入层和输出层之间众多神经元和链接组成的各个层面，也是实现监督学习算法的主要层面.
  
• 输出层,信息在神经元链接中传输、分析、权衡,形成输出结果。

在我们解决网页正文提取这个特定的场景下,我们采用的神经元学习算法可以归类为监督式学习网络,即从问题领域中提供训练范例，包含输入资料与输出资料。 网络从中学习输入资料与输出资料的内在对映规则.很像老师教学生几个例题,告诉答案,然后训练学生做新的题目.

"ANN是不是一种很复杂的东西?"
    "也许以前是,但现在已经不是了"
"为什么"
    "因为名气大的招数,往往也是高手努力去研究的东西,像ANN这样的利器,江湖甚至出了一个FANN"

首先建立一个fann的训练工程，然后丢给他我们预先标记好的训练文本,过程就是这么简单吖.
关于生成训练文本这里,如果完全手工的话,估计也是一件吐血的事情.但是这活儿又不能没有人工干预,所以折中的办法是预先制定一个训练数据生成算法,然后人工标记检查一下.

训练数据文本格式如下:

3 2 1 //训练对总数 每训练对输入数 每训练对输出数

1 1   //训练对 输入

1     //训练对 输出

1 0

1

-1 1

1

生成算法大致如下:

• 分别计算当前行与前行以及后行的文本密度、文本字节数、总字节数
• 若当前行文本密度在0.3以上,则标记输出结果为1，反之为0

out = map(lambda x,y,z:[x,y,z],[Para()]+d[0:-1],d,d[1:]+[Para()])
f.write("%s %s %s\n"%(len(d),3,1))
line = 3*"%s "+"\n"
for x,y,z in out:
    f.write(line%(y.density,y.bytes,len(y.text)))
    if (y.density > 0.3):        f.write("1\n")
    else:        f.write("0\n")

使用FANN进行训练的主要过程，在前文的LineWirter中加入一个方法:

def get_density_with_ann(self):
        obj = libfann.fann_create_standard_array(2, (3, 1))
        ann = fann.fann_class(obj)
        patterns = fann.read_train_from_file('train_data.txt')
        ann.train_on_data(patterns, 1000, 1, 0.0)
        return [line[3] for line in map(lambda x:[x.density,x.bytes,len(x.text),x.text] , self.lines) if ann.run(line[0:2])[0] > 0]    

使用ANN处理文本提取,可以根据输入的上下文进行启发式学习，从而使得输出更加适合于实际情况.利用机器学习来处理每一文本行的信息，可以找出有用的模式.从人工的决策过程分析，我们采用了九个因素用于决定如何过滤文本行。这些因素分别是当前行的密度、当前行的HTML字节数、当前行的输出文本长度、前一行的这三个值、后一行的这三个值。

当然神经网络也不是完美的,它需要一定量的网页学习.而且如果网页的结构变化较大，那么感知器反而会带来一些弊病.造成精度缺失的情况.本博的实际实验情况中,由于对多种类型的网页都进行了训练,结果在我们给出的示例网页中,结果稍微逊于另外一个测试用例.

如果对抽取的结果准确要求相对教高,并且又没有那么多的训练数据可供使用,那又该怎么办呢?本博这里隆重推出终极杀器----FDR 也有人称之为检出率算法,因为其只考虑期望部分的错误率.这里简要阐述FDR的意义以及应用过程。

假设问题有N个可能的候选输出，每个输出可以采用一个概率或可能性值表示输出结果的正确性概率，根据输出的概率从N个选择中选择一定数量的结果作为最后的输出。假设挑选了 个输出作为结果，其中有s个是真正正确的，另外有 个是错误的，实践中希望错误比例Q=V/R平均而言不能超过某个预先设定的值(如0．05)，在统计学上，这也就等价于控制FDR不能超过5%.

"看起来很复杂的东西,背后往往相当简单"

这个问题可以转化成：设总共有n个候选输出，每个输出对应的P值从小到大排列分别是P(1)..P(m)，若想控制FDR不能超过q，则只需找到最大的正整数i，使得P(i)<=(i*q)/m；然后，挑选对应P(1)，p(2)，⋯ ，P(i)作为输出结果,这样就能从统计学上保证FDR不超过q.

在前文的LineWriter里加入如下代码即可:

def output_fdr(self):

        self.compute_density()

        pvalue = map(lambda x:1.0/x.density ,self.lines)

        pvalue.sort(reverse=True)

        i = len(self.lines)

        m = [j for j in range(i) if pvalue[j] <= (j*5)/i][0]

        density = 1.0/pvalue[m]

        output = StringIO.StringIO()

        output.writelines(''.join([l.text for l in self.lines if l.density > density]))

        return output.getvalue()

   

采用FDR方法统计意义上的学习之后,得到的新的文本密度p为0.59.

最后简单对比下本文设计和实现的三种算法:ANN算法和估值算法总体性能较好，但是FDR在控制错误上具有很好的表现；如果应用需求很高的错误率，那么FDR是一个较好的选择；NN算法的最大问题是需要有学习的样本；估值算法对于简单的网页具有简单高效的特点.

光風(gfn)

基于Subversion的版本管理流程

摘要:本文围绕开源版本控制软件Subverison,结合开发涉及角色描述版本控制管理流程

涉及角色:

• 程序员
• 小组责任人
• 项目经理

代码仓库:

• 开发目录(以下称trunk),包含各个小组的开发目录
• 里程碑目录(以下称tags),包含面向集成测试的里程碑版本
• 生产目录(以下称release),包含用于生产环境的代码

协同流程:

• 程序员

1. 根据项目经理、小组责任人的分配的任务从trunk检出对应模块目录,进行功能开发;
2. 在分配给小组的开发服务器上经行单元测试;
3. 修正集成测试反馈的代码缺陷,重复步骤2)后交付责任人。

• 小组责任人

1. 在各个里程碑期间,保证组内程序员开发的代码通过单元测试;
2. 与项目经理沟通后,确定当前小组负责模块的稳定版本,提交至项目经理指定的tags版本目录。
3. 协助项目经理经行集成测试,接受测试反馈,并组织修复,重复步骤2)。

• 项目经理

1. 召集各小组负责人在里程碑点进行集成测试;
2. 测试产生的问题反馈至相应模块责任人;
3. 确认通过集成测试的系统版本,提交至release,并根据实际情况安排部署。

也谈网页正文提取[上]

看到这里,如果有看官不知道啥叫正文提取,那我只能说,大哥我真的没有忽悠您，我既没说"网页去噪",也没说互联网的"自动摘要",更没说海量互联网数据的"文本挖掘"。由此可见本博是个很厚道的人,会手把手教你如何完成这个看起来牛逼实则很简单的一件事情,绝对让你感到物超所值(阅读的时间)。

从字面意思上理解,网页的正文提取嘛,无非就是把网页当中对咱最有价值的那部分文章给取出来撒.有点编程经验的朋友肯定都知道,右键网页源文件,看看html代码,取出来有正则匹配一下也就几分钟而已的事情。更好一点的办法,那自然是用上像DOM或者XPath这样专门对付html的利器,多写几次估计一分钟也不要。如果本博也这么干的话,那还怎么体现您的慧眼如矩呢:)

上面说的方法,实际上在垂直搜索引擎的定向抓取中,给一个目标站点利用DOM建立抽取模板是一个很常用也很准确的办法。但是当问题域变得稍微大那么一点点,比方说吧,我觉着谷歌做的不错，我也想搞一个的话,那咋整呢?再利用上面的办法,机械的给每一个页面建立DOM,是会死人的哟XD

那么问题其实就变成了对于任意篇网页,有没有办法"聪明"点的法子,能识别出正文部分呢?
既然我们人是可以做到这一点的,那么就说明存在利用人工智能去解决这个问题的可能性.当然,我们现在不急,先从简单的做起.

网页里面除了可读文本就是链接,图片,视频,以及其他媒体类型.而后面这些东东在HTML里面都是用专有的标签来显示的,而且还是被标签所"夹住"的。那我们来看看一个文本块里,除了标签还剩下来的东西有多少.

通过Python内置的htmllib模块和formatter的配合,我们可以统计出网页中每一行文本中标签和正文的数量.代码如下:

#coding:utf-8

import htmllib,urllib2
import formatter,StringIO

class TrackParser(htmllib.HTMLParser):

    def __init__(self, writer, *args):
        htmllib.HTMLParser.__init__(self,*args)
        self.writer = writer
  
    def parse_starttag(self,i):
        index = htmllib.HTMLParser.parse_starttag(self,i)
        self.writer.index = index
        return index

    def parse_endtag(self,i):
        self.writer.index = i
        return htmllib.HTMLParser.parse_endtag(self,i)


class Para:

    def __init__(self):
        self.text = ''
        self.bytes = 0
        self.density = 0.0

class LineWirter(formatter.AbstractWriter):
    """
    a Formatter instance to get text in lines
    """

    def __init__(self):
        self.last_index = 0
        self.lines = [Para()]
        formatter.AbstractWriter.__init__(self)

    def send_flowing_data(self, data):
        t = len(data)
        self.index += t
        b = self.index - self.last_index
        self.last_index = self.index
        l = self.lines[-1]
        l.text += data
        l.bytes += b

    def send_paragraph(self,blankline):
        if self.lines[-1].text == '':
            return
        self.lines[-1].text += 'n'*(blankline+1)
        self.lines[-1].bytes += 2*(blankline+1)
        self.lines.append(Para())
      
    def send_literal_data(self,data):
        self.send_flowing_data(data)
  
    def send_line_break(self):
        self.send_paragraph(0)



def extract_text(html):

    writer = LineWirter()
    fmt = formatter.AbstractFormatter(writer)
    parser = TrackParser(writer,fmt)
    parser.feed(html)
    parser.close()
    return writer.lines


htmls = urllib2.urlopen("http://ent.hunantv.com/d/x/20091128/503722.html")
print map(lambda x:[x.bytes,len(x.text)],extract_text(htmls.read()))

看着飞速跑过的列表,你是不是恨不得把他给全部写入一个文件来看看结果?在文件尾部加入

q = open("e.csv","w+").writelines('\n'.join(["%s,%s"%(x[0],x[1]) for x in s]))

现在结果变成了一个csv文件鸟,来上个图看看:

上图清晰的表达了该网页的文本分布,根据与页面的比对,我们发现文本所在的区域与相对应的行域保持了某种关系.这似乎说明我们的思路是正确的.

实际上行文本字节数与行总字节数的比值被称为行文本密度.有了这个概念,我们就可以对网页全文扫描计算相应的文本密度,这里我们不妨做一个假设,文本密度在0.5以上的就是我们需要的文本部分，也就是说我们认定某行的文本至少和该行的标签一样多的话,他就可能是我们需要的文本区域.

修改上述代码的两个地方,我们来初试下身手,
在原有的LineWriter里加入:

    def output(self):
        self.compute_density()
        output = StringIO.StringIO()
        for l in self.lines:
            if l.density > 0.5: //这里就是我们设置的行文本密度
                output.write(l.text)
        return output.getvalue()

修改extract_text函数

def extract_text(html):
        writer = LineWirter()
        fmt = formatter.AbstractFormatter(writer)
        parser = TrackParser(writer,fmt)
        parser.feed(html)
        parser.close()
        return writer.output()

文件末尾改成

htmls = urllib2.urlopen("http://ent.hunantv.com/d/x/20091128/503722.html")
s = open('e.html','w+').write(extract_text(htmls.read()))

先透口气,然后平静的点开e.html，喔,你看见了什么！

激动之后,应该会有这么一个疑问,刚才我们设置的文本密度为0.5，这个数字到底是怎么来的?他具有普适性么?

其实这个文本密度是可以计算出来的:
设y为行文本集合,z为行标签集合,则文本密度p为:

设i代表任意行,分别用yi,zi代表任意行文本/标签的长度,设且均符合正态分布.uy,uz分别代表行文本和行标签的平均长度：

计算方差:

如果选择文本行的概率为p,那么标签行就为1-p.相应的各文本项平均长度为

最后得到p的估值:

将我们选用的网页实际情况带入以后,我们得到真实的文本密度p大约为0.53,和估计值很相近.学术界有针对行的做了大量实验,得出新闻资讯类网站的文本密度大约在0.4-0.6左右,sina和sohu的这个值大约都是0.6;博客类网站的文本密度大约在0.7-0.8之间.

作为这个话题上半部分的结束,谈谈这个文本密度的实际应用,除了本文所涉及到的文本抽取以外,文本密度现在被广泛应用于搜索引擎网页价值分析的预处理,同时我们也大体可以看出网站内容的大致分布.

下半部分,本博将引入ANN(神经网络)和FDR(错误控制)的相关方法继续探讨这个话题.敬请围观.


光風(gfn)

数组过滤之bitmap解法

求一个数组中过滤掉重复的元素,并保证原有的元素均存在。

>>> data
['a', 'a', 'z', 'b', 'a', 'b', 'c']
>>> def foo(f,n=0):
    if f%2 != 0:
        l.append(n)
    if f/2 == 1:
        l.append(n+1)
        return l
    n += 1
    foo(f/2,n)

   
>>> l = []
>>> p = foo(reduce(lambda x,y:x|y,map(lambda x:1<<(128-ord(x)),data)))
>>> r = map(lambda x:chr(128-x),l)
>>> r
['z', 'c', 'b', 'a']

March Liu大法

>>def refoo(d, k):
c = d.get(k, 0)
d[k] = c+1
return d

>>> map(lambda p: p[0], filter(lambda p:p[1]==1, reduce(refoo, data, {}).iteritems()))

通过Shell Script解决Subversion分支与主干合并

最近公司内部推行了基于Subversion的开发流程规范.程序员在开发功能模块的时候,基本在各自的trunk活动,当完成单元测试后，方可提交至生产版本库.这样一来就涉及到版本合并的问题.

使用Windows的朋友自然不觉得这是一个多麻烦的事情,毕竟有"小乌龟"嘛.可是,作为拥护Unix&Shell以及崇尚"DRY"原则,还不时热爱捣鼓点新鲜玩意儿的本博来说:岂有不用shell实现的道理;)

#!/bin/bash
export trunk_dir=/root/dp-trunk/
export release_dir=/root/dp-release/dp-0.1.0/

trunk=`svn up $trunk_dir|grep revision|awk -F' ' '{ print $3 }'|awk -F'.' '{print $1}'`
release=`svn info $release_dir | grep "Last Changed Rev"|awk -F: '{print $2}'`

info=`svn merge -r $release:$trunk $trunk_dir $release_dir && svn ci -m '' $release_dir`
echo $info

Perl实现Subversion更新守护进程

和前一篇使用Subverison同步多台服务器代码类似,前者主要解决Subversion向服务器同步完全相同的环境代码,但是当不同的服务器需要的程序并不一样的时候,前者就很捉襟见肘了.于是,这里给出一个Perl的Deamon实现

#!/usr/bin/perl
exit if fork();
while(1) {system("svn up /root/192.168.8.192");sleep(5)};

使用Subverison同步多台服务器代码

在实际生产中,一套分布式的程序可能需要被部署在很多环境相同的服务器上.如何实现程序的自动部署不仅可以降低因版本冲突而导致的服务异常,也可以未将来的持续集成做基础准备.

这里采用的代码版本控制程序为Subversion,由中央版本库向多台服务器同步代码的方法有很多,基本上都是通过使用hook(post-commit)来实现的.

这里记录下我的post-commit：

use Net::SSH::Expect;


#此处添本代码仓库需要同步的服务器组
my @cluster = ('192.168.1.191',
               '192.168.1.190',
               '192.168.1.193'
              );


foreach $svr (@cluster) {
   my $ssh = Net::SSH::Expect->new(
   host =$svr,
   password ='xxx',
   user ='xxx',
   raw_pty =1
   );
   my $logins = $ssh->login();
   my $command = $ssh->exec('svn up /path');
   $ssh->close();
}