基于有限状态机的URL解析

No.5Oct.,2010

微 处 理 机

MICROPROCESSORS

第5期

2010年10月

基于有限状态机的URL解析

韩培培,付 博

(燕山大学信息科学与工程学院,秦皇岛066004)

摘 要:在网页分类的过程中,鉴于存储查询过程中的URL规范化需求,提出一种基于有限状态机的URL解析方法,并进行了详细的分析设计,解决了现存URL解析方法效率低、资源消耗大的缺点,提高了解析的效率和容错性能。

关键词:URL解析;有限状态机;网页分类

DOI编码:10.3969/.jissn.1002-2279.2010.05.020

中图分类号:TP393 文献标识码:A 文章编号:1002-2279(2010)05-0068-03

URLParsingMethodBasedonFiniteStateMachine

HANPei-peiFUBo

(CollegeofInformationscienceandEngineering,YanshanUniversity,Qinhuangdao066004,China)

Abstract:Duringthewebpageclassificationprocess,InviewoftheURLstandardizationoftheprocessofstoreandquery,itappliesanewURLparsingmethodwhichisbasedonFiniteStateMachine,

it.sprovideamethodtosolvetheproblemthatinefficientandresourcedegradationofexistingURLparsingmethod,improvingtheparsingefficiencyandfault-toleranceperformance.

Keywords:URLparsing;FiniteStateMachine;Webpagecategorization

域;º对特殊字符进行百分号编码或解码;»对path域进行特殊处理。

1 引 言

随着互联网的飞速发展,Web上的网页数量呈指数增长,连Google也不得不承认互联网真的是很大很大的东西,截止到2008年,Google收录的全球网页达到1M,并且网页的内容也是不定和日益变化的,所以,组织和利用海量Web信息的有效途径)))网页分类是一个长期的过程,不可能一劳永逸。考虑到在网页文本分类过程中,URL分类结果存储和查询时需要URL规范化,提出一种基于有限状态机的URL解析方法。

3 现存的URL解析方法

目前存在的URL解析方法有:PHP源码提供的

[2]

URL解析方法、Java源码提供的URL解析方法

[3]

、URIRFC3986中提到的利用正则表达式

[4]

解

析URL等。其中,PHP解析URL需要对URL进行多次扫描,调用了大量库函数,资源消耗大;Java也存在这样的问题,并且程序效率和识别率都相对比较低;正则表达式解析URL则组成复杂,理解性和实用性都很差。基于有限状态机的URL解析能解决了现存URL解析方法效率低、资源消耗大的缺点,提高了解析的效率和容错性能。

2 URL解析概述

URL由三部分组成:资源类型、存放资源的主机域名、资源文件名。

URL的一般语法格式为(带方括号[]的为可选

[1]

项):

protoco:l//[user:password]@host[:port]/path/[?query]#fragment

URL解析过程包括三个步骤:¹分解URL各个

4 方法设计与实现

4.1 URL结构分析

URL解析是一个扫描URL字符串的过程。扫描字符串的过程中,根据URL语法规定的各个域之

[1]

间的分隔符来逐步分解。因此了解URL各个域,

作者简介:韩培培(1984-),女,河北保定人,硕士研究生,主研方向:信息安全。收稿日期:2010-03-12

5期

韩培培等:基于有限状态机的URL解析

#69#

以及各个域允许的字符集,是解析URL的必要步骤,其中重点是搞清楚各个域之间的分隔符和允许以非分隔符形式存在的保留字符。为了描述URL的组成结构,定义了如下的字符集:

gen-delims=\":\"/\"/\"/\"?\"/\"#\"/\"[\"/\"]\"/\"@\"分割字符集

[1]

中的任何一个;当字符串扫描结束,状态为接受状态集合S中一个时,表示输入的URL被FSM接受,解析完成;E为有限输入字符集,包括所有字母和数字;转移函数D定义为如下的状态转移表,如表1所

示。

表1 父FSM的状态转移表

输入状态

S0

S1S2S3S4S5S6S7

AS0S2S2S3--S5S6S7

N1S0S1S2S3S4S5S6S7

N2S0S2S2S3--S5S6S7

:S1S2S2

@S3S3S3

/S5S5--S5S5S5S6S7

?S6

#S7

sub-delims=\"!\"/\"$\"/\"&\"/\".\"/\"(\"/\")\"/\"*\"/\"+\"/\",\"/\";\"/\"=\"

reserved=gen-delims/sub-delims保留字符集unreserved=ALPHA/DIGIT/\"-\"/\".\"/\"_\"/\"~\"非保留字符4.2 有限状态机(FSM)

有限状态机,即FSM

[5]

S6S7

----S6S6S6S6S7

S7S7S7S7S7

S4S3----S5S6S7

S5S6S7

(FiniteStateMachine的

缩写),表示有限状态以及在这些状态之间的转移和动作等行为的数学模型。简单而言,有限状态机由一组状态、一个初始状态、输入和根据输入及现有状态转换为下一个状态的转换函数组成。

依据有限状态机的原理机制,可以建立状态转移函数。FSM逐步读取输入符号,依据转移函数/跳转0过一系列状态,直到输入结束FSM停止,依据其停止状态,判断自动机是/接受0,还是/拒绝0这次输入。/接受状态0是机器成功运行了它的程序之后的状态,在状态转移图中表示为双重圆圈;否则就是/拒绝状态0,在状态转移图中用单个圆圈表示。

4.3 基于FSM的URL解析

通过对URL的结构分析,并结合FSM的原理机制,提出了基于有限状态机的URL解析方法。具体方法如下:建立URL解析的FSM,同时建立子FSM完成path域的处理,由此构成一个嵌套的FSM模型,即在FSM的一个内部状态处理中又生成了一个子FSM,即由子FSM来负责父FSM一个状态内部的处理流程。

4.3.1 父FSM的建立

URL各个域有不同的字符集,因此各个域的处理情况不同。所以父FSM的状态完全根据URL的组成来定义,定义父FSM的接受状态为S{S0,S1,S3,S4,S5,S6,S7},根据URL的组成结构,状态S0~S7分别对应的URL域为:{user,host},{pass-word,port},password,hos,tpor,tpath,query,fragment。

根据此状态定义得出URL解析的有限状态自动机的定义:M=(Q,q0,S,E,D)

其中,Q是上面定义的状态集合;初始状态q0

是状态S0{user,host},即处于状态集合{user,host} 其中,A表示英文字母和除gen-delims的特殊字符;N1表示出现的前5个数字,N2表示除N1的其他数字;---.表示没有转移项,即出错。

父FSM的状态转移图,如图1所示。

其中,C1表示表3中的A、N2或分隔符-:.;C2表示分隔符-/.、-?.或-#.;C3表示表3中的A、N2以及分割字符-:.和-@.。4.3.2 子FSM的建立

URL解析的子FSM用来处理URL的path域,在父FSM的状态S5内部执行。子FSM定义Mi为Mi(Q,q0,S,E,D)

其中,子FSM的接受状态为S{S5-0,S5-2,S5-3,S5-4,S5-5};根据当前扫描指针前面连续的字符//0和/.0的情况定义状态集合Q;初始状态是q0{S5-0};接受状态S是{S5-5};状态转移是当前状态和输入的函数,子FSM的状态转移表,如表2所示。

表2 子FSM的状态转移表

输入状态 S5-0S5-1S5-3S5-4S5-5

D1S5-5--S5-5S5-5S5-5

D2S5-0S5-0----S5-0

D3S5-1S5-2S5-4S5-4S5-3

其中,D1表示除特殊字符//0和/.0外的所有字符;D2表示特殊字符//0;D3表示特殊字符/.0;---.,表示没有转移项而出错。

子FSM的状态转移图,如图2所示。

#70#

微 处 理 机2010年

图1 父FSM的状态转移图

程中均对URL进行了多次扫描,调用了大量库函数,资源消耗大,并且程序效率和识别率都比较低,实用性差。而基于有限状态机的URL解析只需对URL进行一次扫描,效率高,减少了资源消耗量,同时,此方法建立的嵌套FSM处理函数提供了比现存方法更完善的错误识别机制,不仅能正确解析组成良好的URL,还能对结构错误的URL识别处理。

参考文献:

[1] 孙建涛,沈抖,陆玉昌,等.网页分类技术[J].清华大

学学报,2003,44(1):65-68.[2] ChoonY.ClassificationofWorldWideWebdocuments

[D].Pittsburgh:Carnegie-MellonUniv,2000.[3] 王晓霞.基于支持向量机的中文网页自动分类技术研究[D].太原:中北大学,2007.[4] ThomasHCormen,CharlesELeiserson.IntroductiontoAlgorithms,SecondEdition[M].TheMassachusettsInst-i

tuteofTechnology,2001.[5] KAas,LEikvi.lTextcategorization:Asurveytechnical

report[M].NorwegianComputingCenter,1999.

图2 子FSM的状态转移图

子FSM的结束不总是到URL的末尾,当扫描到分割字符-?.或-#.时,path部分处理完毕,子FSM退出。如果退出时子FSM的状态是S5-5,则

返回到父FSM,继续解析URL,直至URL解析的任务全部完成。否则,错误返回,父FSM停止。

5 结束语

如上文分析,现存的URL解析方法,在解析过(上接第67页)

的基本要求。

参考文献:

[1] 王静,曲凤娟.基于Socket的多用户并发通信的设计[J].福建电脑,2007(3):164-165.

[2] 陈更力,张青.基于JavaSocket网络编程的一种新实现[J].电脑开发与应用,2006(6):12-13.

[3] ElliotteRustyHarold.JAVA网络编程(第3版)[M].

朱涛江,林剑,译.北京:中国电力出版社,2005:283-390.

5 结束语

介绍了Socket的通信机制,建立了一个基于Ja-vaSocket的聊天室系统。该系统能够实现公共聊天和私人聊天,允许在网络上有多个Server,客户端根据输入Server的IP地址连入相应的服务器参与聊天活动,服务器上显示当前在线的用户信息,并对用户进入或断开的信息加以显示,满足了聊天室系统