Posted on 2007-06-09 23:42
sunbaby 阅读(644)
评论(0) 编辑 收藏 所属分类:
JAVA技术点滴
1问题的提出
2002年，中国大约有5000万网页和5万个Web站点[1]，而且网页数量还在以惊人的速度递增。这些海量网页中蕴含着巨大的信息资源，如果能及时而又准确地处理这些网页就相当于拥有了开启Internet资源库的钥匙。网页处理已经成为网络信息资源处理过程中一个极为重要的部分。
网页处理首先需要分解出网页中的有用信息单元和无效（或作用不大）单元，往往采用网页清洗技术。
所谓网页清洗，就是从Web页面中划分出精确的信息单位，并根据Web页面信息加工的后续应用的需求，将页面中不需要的部分去除，将需要的部分提取出来。[2]
网页清洗主要分三步：首先是去除页面中的注释、脚本、样式表等无关信息。然后再将页面划分为若干块，包括文本块、链接块、图像块等。最后按照语义对各块作进一步区分，如从文本块中区分出广告等非关键信息块；从链接块中区分相关链接块、导航链接块、广告链接块等不同内容。经过上述处理后，Web页面在结构和语义上都被划分为细粒度的信息块，从而使后续的信息加工处理工作得以顺利进行[3]。
国内学者周源远等人开发了一个实验系统PageExtract来完成Web页面的相关清洗工作[2]。但是由于网页中包含的信息的形式多样化，有文本、图片、动画、音频、视频等多种信息形式，以及网页中存在严重的冗余与无序的现象，并且信息内容本身也是不断更新的，使得网页清洗算法繁杂、不易实现，其清洗结果也不能完全使人满意。
周源远等人对随机选取的744个Web页面（页面大小总和为7974KB）进行了网页清洗测试。随后，又从清洗的结果中随机选取了100个页面进行人工评分，分为三个等级：好（指页面提取正确）、一般（指有少量一般性错误，但从整体上来看，可以接受）、差（指有严重错误或误差较多，难以接受）。结果，得分为“好”、“一般”、“差”的文本块网页分别为31%、50%、19%。也就是说，高达19%的清洗结果是完全不能接受的[2]。
??? 本文将提出一种专用于新闻网页的正则表达式解析网页的算法。这种算法避开了网页清洗技术的缺陷，简便易行，效率很高，准确性也很高。
2新闻网页的特征以及结构分析
新闻网页是具有很强开发价值的一类网页，它具有时效性强、信息量大、结构稳定、更新快、需求广泛、实用价值高等特点。考虑到这些特点，对新闻网页的处理如果按照传统的网页解析方法，不仅效率低，效果也不会理想。
??? 而有一类新闻网页更为特殊也更具有代表性，它们是各大门户网站或新闻网站用来提供用户检索新闻之用的新闻页面，这类新闻页面包含符合检索条件的若干条新闻记录，这些条新闻记录有标题、文摘、出处以及超链，可以用来指引用户查阅新闻全文。这类新闻网页其实就是各大网站给自己站内的所有新闻网页编的“索引”，能起到很好的说明和指示的作用。因此，只要能处理好这类有关某一主题的新闻网页，实际上就等于处理了绝大部分的与这一主题相关的网页新闻。
?? 由于这些网页在各大网站所起的作用相似，而且功能相近，所以这类网页的结构相当稳定，而且不会受到某一个具体网站的约束，适用于大批量地统一处理。比如新浪网和搜狐网，百度网等新闻网页就基本一样。下面是新浪网站一个新闻网页的实际例子：
<html>……<head>……</head><body>
<ul class=l15><a href="http://tech.sina.com.cn/o/62874.shtml" target=_blank><font class=f15>背景资料：先进的攀岩工具SRT</font></a> <font color=#333333><i>2001/04/13 15:56</i></font><br>...最大问题，这次中外联合科考队将使用目前世界上最先进的攀岩工具SRT。<b> </b>SRT包括上升<b> </b>下降手柄等一系列工具组成，攀岩者通过它借助自身的.
<!---qubo debug 分类=科技:大众科技--->
?</ul>
<ul class=l15><a href="http://auto.sina.com.cn/news/2002-12-11/31590.shtml" target=_blank><font class=f15>峰会--2款超级跑车对比测试</font></a> <font color=#333333><i>2002/12/11 10:22</i></font><br>...大堆“肌肉”发达的美国两座超级跑车中，道奇蝰蛇<b> </b>Dodge<b> </b>Viper<b> </b>SRT<b> </b>10和雪佛兰克尔维特<b> </b>Chevrolet<b> </b>Corvette<b> </b>Z06无疑是最具代表...<b> </b>实际上
<!---qubo debug 分类=汽车--->
?</ul>
………
<ul class=l15><a href="http://tech.sina.com.cn/o/67356.shtml" target=_blank><font class=f15>探险神秘地下世界--天坑科考活动始末</font></a> <font color=#333333><i>2001/05/17 19:22</i></font><br>...，我们架一些绳梯，然后再利用绳索，用垂直降落技术，这种技术叫SRT，单绳垂直降落技术。...然后再结合我们现在比较先进的SRT技术，两个<!---qubo debug 分类=科技:大众科技---> </ul>……</body>… </html>??????
?
??? 可见，这类网页具有非常明显的结构特征，对此结构展开如下：(略)
?
可以看出，这类网页的结构很清晰，而我们所需要的也就是那些一个个新闻信息单元里面的内容。为此，我们完全不需要按照传统的解析网页的方法来一步步地细化网页，而只要把<ul class=115>…</ul>这些信息单元直接匹配出来即可，而且这些信息单元里面同样也是结构化的，下面就是某一个<ul class=115>…</ul>片断：
<ul class=l15><a href="http://tech.sina.com.cn/o/62874.shtml"target=_blank> <font class=f15>背景资料：先进的攀岩工具SRT</font></a><font color=#333333><i>2001/04/13 15:56</i></font><br>…最大问题，这次中外联合科考队将使用目前世界上最先进的攀岩工具SRT。<b> </b>SRT包括上升<b> </b>下降手柄等一系列工具组成，攀岩者通过它借助自身的.
<!---qubo debug 分类=科技:大众科技--->
?</ul>
?
对这些结构化的信息单元进行再匹配就能得到每条新闻的所有重要信息，可以构成一个完整的新闻元数据：
新闻的超链：“http://tech.sina.com.cn/o/62874.shtml”
新闻的标题：“背景资料：先进的攀岩工具SRT”
新闻的时间或出处：“2001/04/13 15:56”
新闻的文摘：“...最大问题，这次中外联合科考队将使用目前世界上最先进的攀岩工具SRT。SRT包括上升，下降手柄等一系列工具组成，攀岩者通过它借助自身的.”
而上面的每条新闻的元数据则是进行进一步信息重组和知识再现的最好素材。所以整个解析思路的核心就是直接匹配。而正则表达式完全具备了解释上述新闻元数据的匹配功能。因此，可用正则表达式来实现相关解析工作。
3正则表达式简介
神经生理学家McCulloch 和 Pitts最早用正则表达式来描述神经网络。1956年，数学家 Stephen Kleene 在此基础上，发表了一篇题名为《神经网事件的表示法》的论文，引入了正则表达式的概念。正则表达式就是用来描述他称之为“正则集的代数”的表达式。随后，人们发现可以将此表达式应用于使用Ken Thompson 的计算搜索算法的一些早期研究。正则表达式的第一个实用应用程序就是 Unix 中的qed 编辑器。
正则表达式提供了一种从字符集合中搜寻特定字符串的机制[4]。它可以让用户通过使用一系列的特殊字符构建匹配模式，然后把匹配模式与数据文件、程序输入等目标对象进行比较，根据目标对象中是否包含匹配模式，执行相应的程序[5]。
正则表达式有以下几个主要功能：数据有效性验证功能，用于测试字符串的某个模式是否有效。例如，可以对一个输入字符串进行测试，看此字符串是否符合email的模式。替换文本功能，用于在文档中使用匹配模式来标识特定文字，然后将其删除或进行替换。提取子串功能，用于根据模式匹配，从字符串中提取一个子字符串。
它主要有四类字符：首先是匹配字符，包含了需要搜索匹配的对象。例如，“.”号匹配任一字符，“[]”号匹配方括弧之间的任一字符，“[^]”号匹配不在方括弧之间的任一字符。其次是重复操作符，描述了查找一个特定字符的次数。例如，“?”号匹配某一部分一次，“*”号匹配某一部分多次，“+”号匹配某一部分一次或多次，还有“{n}”，“{n,N}”等符号。还有锚，它指定了所要匹配的格式，有“^”、“$”、“\>”、“\<”、“\b”等。当然还会有一些保留字符，需要用反斜杠来替换它们，比如“*”号，是个保留字符，如果要在表达式里表示这个特定的字符，就得用“\*”这种形式。
4正则表达式来处理解析匹配工作的算法
SUN公司最新发布的JDK1.4中加入了java.util.regex包，全面提供对正则表达式的支持。而且Java.lang.String类中的replaceAll和split函数也是调用的正则表达式来实现的。正则表达式可以利用模式匹配找到符合条件的字符串以及判断相关字符串。java.util.regex包中有三个类：Pattern类，Matcher类以及异常类patternSyntaxException。Pattern类主要是按照正则表达式的语法，针对要匹配的对象构造正则表达式。所构造的表达式必须是唯一的完全匹配。Matcher类主要是用构造好的Pattern来匹配所要处理的对象，异常类则用来处理表达式可能出现的语法错误等情况[6]。
下面给出在Java语言里运用正则表达式进行匹配的几个比较简单的例子。
1）字符串匹配，这是不符合条件的，匹配不成功。
?p = Pattern.compile("ac*b");
?m = p.matcher("bcaaab");
?b = m.matches();
2）字符串匹配，这是符合的条件的，匹配成功。
p = Pattern.compile("cd*b");
?m = p.matcher("cdaaaab");
?b = m.matches();
3）字符串替换，操作成功。
?p = Pattern.compile("ab");
?m = p.matcher("aaaaab");
?s = m.replaceAll("d");
对于前面所讨论的新闻网页，所构造的正则表达式需要完成两项任务。首先是从整个网页中匹配所有的<ul class=115>…</ul>单元，然后就是把每一个信息单元中代表新闻的字段（新闻的标题、新闻的文摘、新闻的超链以及新闻的出处等）从每个单元中解析出来，并作为一个完整的知识单元存入数据库中。所以每项任务都需要构造一个Pattern。
第一个pattern是：
Pattern p=Pattern.compile("<ul([^>]*)>(.*?)</ul>"，Pattern.MULTILINE | Pattern.DOTALL)
?
就是能把每个<ul class=l15>…</ul>单元从整个网页里面取出，<ul([^>]*)>(.*?)</ul> ，其中，“<ul”表示匹配单元必须以此开头，“([^>]*)”表示匹配的是除字符“>”以外的任意多字符，然后以”>”结束，这样就能找到相关的单元开始，剩下的就是只取一个单元。“(.*?)”表示任意多字符，“</ul>”表示以此标识结束。这样就很简单的匹配到一个个<ul class=l15>…</ul>单元。“Pattern.MULTILINE”表示可以多行匹配，“Pattern.DOTALL”表示对大小写不敏感。
第二个pattern就是解析出每个单元里面我们所需要的元数据的字段。即新闻的超链等字段。
Pattern p1 = Pattern.compile("<a href=\"([^\"]*)\".*<font class=[^>]*>(.*)</font></a>.*<font color=[^>]*><i>(.*)</i></font><br>(.*).*"， Pattern.MULTILINE | Pattern.DOTALL)
?
笔者还对其它门户网站的新闻网页结构进行了分析，发现它们都具备与新浪网站的新闻网页相似的结构。比如，搜狐网站的新闻网页就是由一个个<span class=blank>…</span>单元组成的新闻记录，每条新闻记录里面也同样包括新闻的标题、文摘、出处、超链等。而网易则是由一个个<li>…<p>单元组成的新闻记录，记录里面的结构也相似。因此门户网站和新闻网站的这类网页在结构上基本相同，只是细节上有略微的差别。所以对各个网站的这类网页的解析算法都可采用正则表达式方式，区别只在于正则表达式的构造有所不同。
5算法测评与应用实例
?? 笔者分别从新浪、搜狐以及百度网站各随机抽取了267个、342个、327个（共936个页面，页面大小总和21546 KB）新闻网页，对正则表达式法算法的解析结果进行测评。测评工作主要分为两项：速度和准确度。
对936个页面用正则表达式进行批处理解析，共用时约18秒，平均每秒解析网页52个，平均速度为1197KB/S，而周源远等人研制的网页清洗系统的解析速度为891KB/S[2]。显然正则表达式算法由于是采用直接完全匹配的思路，运行速度上要强于网页清洗解析网页的算法。
从上述936个页面中随机选取了250个页面，对正则表达式算法解析的质量进行人工评分，分为三个等级：好（指页面中所有相关主题的新闻记录都被准确提取，每条新闻记录中的各重要信息也被准确提取）、一般（指有少量一般性错误，新闻记录有少量遗漏，或新闻记录中的重要信息有少量错误，但整体可以接受）、差（指有严重错误或误差较多，难以接受）。结果，得分为“好”、“一般”、“差”的网页比例分别为78%、20%、2%。也就是说，此算法解析网页的准确度在整体上有98％是可接受的，不可接受的仅为2％。之所以有这么高的准确度是因为在掌握网页结构的前提下，算法对所处理的对象有很高的匹配成功率。但是仍然有2%的不可接受的结果，那是因为网页间在结构上还是有差异的，比如像百度网的新闻网页，网页中的新闻记录有时有图片，有时没有图片，这给算法的编写带来了一定的难度，所以算法有进一步改善的可能。
笔者已将上述正则表达式解析新闻网页算法成功应用于自主开发的个性化网络新闻定制系统中。系统工作在Windows 2000 Server操作系统和SQL Server 2000数据库管理系统平台，WEB服务器为Apache 2，前台网站采用JSP(Java ServerPages)来处理，JSP引擎为resin2.1.6，后台模块采用Java语言编写，Java虚拟机为JDK1.4，按照个性化信息服务的工作模式提供新浪、网易、搜狐三大门户网站的新闻定制服务。当成为注册用户后，用户就可以享受个性化新闻的定制服务。用户进入相关页面提交需要定制的新闻主题以及新闻提醒服务的形式，系统会定期按照用户的需求，以网页或邮件的形式把相关新闻信息推送给用户。系统分为信息采集、信息处理、信息代理服务三个模块，其中的信息处理模块的功能就是采用正则表达式算法，对取回新闻检索结果页面进行处理，提取出系统所需新闻元数据，包括新闻标题、新闻来源、新闻时间、新闻文摘等字段。
6 结束语
本文在对新闻类网页的特定结构进行分析后，研究出利用正则表达式来挖掘新闻网页的新算法，它对网页中的一个个新闻记录单元进行解析匹配，获得了很好的效果，解析效率高，速度快，而且程序编写简单。最重要的是它是中文信息处理的一种新思路，值得进一步深入研究。不过这种方法仍然存在很多问题，比如它要求被处理的网页结构比较稳定，而且事先也要人工对网页的结构进行分析，然后才能构造正则表达式，这样算法就显得不够灵活。因此，该方法也存在适用面不广，智能化不高的的局限性。但由于正则表达式的强大的解析、匹配的能力，以及研究尚处于初期，该算法仍然具有广阔的前景