基于SDL的网络搜索引擎系统的形式化研究

刘 业，吴建平

（苏州市职业大学计算机工程学院，苏州 215104）

0 引言

早期的搜索引擎如Yahoo等基于分类模式的开放式目录搜索，是一种类似于黄页的服务，它将搜索的内容事先进行分类，用户通过选定不同的类别进入相应的网站，然后寻找自己想要的信息。严格地说，这不是一个真正意义上的搜索引擎，因为它并没有最终给出用户所需信息的页面，而是提供一种索引方式，来减少用户找到所需信息的时间。随着时间的推移，使用Yahoo的基础用户大为减少。随着Google、百度的相继出现，真正意义上的全文搜索引擎被实现出来作为网络服务放在互联网上，通过这种服务，用户可以定位到包含关键字的网页上，真正实现了从源到目的地的连接。然而互联网上的信息以指数级增长，如何提高搜索的准确度，提高搜索的效率等诸多问题都成为了Google和Baidu等公司的技术问题，全文搜索引擎仍有很大的技术空间需要长时间的发展。

与在软件开发领域应用广泛的UML语言相比，SDL语言主要是电信设备提供商广泛使用的一门形式化语言。SDL由ITU-T（国际电信联盟电信标准分局）制定，在ITU-T Z.100中给出了SDL的完整定义。它利用直观的二维图形将通讯协议高效简洁地描述出来。但SDL不是诸如C、Java这样的编程语言，用SDL形式化系统之后还是需要将它改写成实际可运行的程序才有实际价值。本文借助于集成开发工具（Telelogic TAU）使用SDL对全文搜索引擎系统进行形式化建模和分析。

1 搜索引擎系统的分层结构

一般来说，搜索引擎主要分为三个部分，分别是网络爬虫、高效数据库和前端应用。

1.1 网络爬虫

网络爬虫也叫网络蜘蛛，顾名思义，如同把一只蜘蛛放在一张网上，蜘蛛在网上以某种规则爬行，遍历网上所有的覆盖区域。Web可以抽象成一个图（实际上通过它的名字我们就可以想象出来它是一张网），每一个网页是图上的一个节点，网页之间的链接则是链接各个点之间的边。网络爬虫是一个程序，它访问互联网上的各个网站，抓取网页的内容，通过对网页之间超链接的分析，跳转到另一个相链接的网页，如此遍历整个Internet。同时，每抓取一个网页，把网页全文存到数据库当中，并计算相应需要的网页信息（如网页rank，meta信息，字符区域编码等），也存入到数据库当中。

1.2 高效数据库

由于网页内容的容量十分庞大，而且以字符流的形式储存在数据库中，因此查找信息的时间效率十分的低，对数据库的要求很高。除了需要高效的数据库之外，一些高级数据库技术也用f来支持搜索引擎的使用，例如倒排索引等。因此，严格意义上来说，搜索引擎提供的搜索结果不等于网络爬虫所抓下来的内容，而是建立好倒排索引的文档。倒排索引的效率好坏和实现算法直接影响查找结果的时效性。此外，某些关于page rank等的算法，也需要在数据库的基础上进行计算和分析。这一层也是搜索引擎的核心和决定一个搜索引擎好坏的关键部分。目前Google和Baidu等公司在这些领域都有自己独有的技术，也是它们能够有强大的市场竞争力的保证。

1.3 前端应用

前端应用是针对用户提出的搜索条件进行分析的程序。主要包括分词、语义匹配、高级查询等功能。英文分词因为其语言特性，在国外发展已经比较成熟。而中文分词系统一直是我国的一项重大研究课题。由于汉字的字符数量非常庞大，加上语言规则复杂，拥有几千年的发展历史，因此中文分词还需要很多研究工作来攻克各种技术问题。Baidu在中文市场的优势也在于它的中文分词系统和相对应的倒排索引技术。

语义匹配也是搜索引擎的一个关键技术。它来源于模糊查询，例如一个用户输入“如何购买一辆汽车”，前端应用程序不是简单地去数据库查找字面上出现类似关键字的结果，而是可以对这个搜索条件进行分析，而返回真正的对购买汽车有帮助的页面。

其他的诸如分类查询、垂直查询、手机查询等，是搜索引擎所提供的一些扩展功能，这些功能主要也是由前端应用来完成。针对不同的需求，前端可以分成若干子层，这里不做过多讨论。

2 搜索引擎系统的形式化描述

一个SDL系统一般由系统system、功能块block、进程process、过程procedure四个层级构成。系统以外的部分被视为当前SDL系统的外部环境，外部环境也可以用另一个SDL系统来描述。SDL系统通过信道channel与外部环境env进行通信。SDL描述系统行为的本质是带消息收发的有限状态机。

Telelogic TAU是瑞典Telelogic公司推出的一款SDL语言的集成开发环境，目前由IBM公司收购并维护后续软件版本，用于实现SDL系统形式化过程中的画图、仿真、测试、执行、自动代码生成、早期错误检测等功能，其最大特点在于SDL和MSC的图形化，为各种设计和开发任务提供自顶向下的工程设计辅助方法。其中，当前自动代码生成的是C++代码，代码中变量函数名全部都是自动生成，代码可读性及可维护性非常差，目前这个模块并没有得到实际的使用。本文所有的形式化SDL图都是通过Telelogic TAU给出。

2.1 搜索引擎系统的系统结构

搜索引擎系统的系统结构细分为三大模块，如图1所示，分别为网络爬虫Spider，数据库模块Database和前端模块FrontEnd。与外界通信的模块是Spider和FrontEnd。几个模块之间通过三个信道进行通信，分别针对Spider对Database的查询和写入操作，以及前端对Database的查询操作。

图1 搜索引擎系统的系统结构图

2.2 网络爬虫模块

网络爬虫模块主要有两个进程，如图2所示，WebGetter，是用来抓取Internet网页上的内容；WebParser，则用来解析抓取下的内容。WebGetter进程所抓取的网页内容作为输入发送给WebParser。WebParser所解析出来的URL地址会添加到地址队列中，作为WebGetter的查找目的地。同时，WebParser也会通过与Database的通信来判断是否待解析的URL已经被访问过。

图2 网络爬虫Spider模块图

WebGetter进程是用来抓取网页内容的进程。它通过一个UrlQueue来存放即将访问的网页地址。由于Web网的结构是一个图结构，因此通过对图的生成树进行一种类似层序遍历的访问方式，就可以访问到该图中的各个节点。实际应用中，由于Internet上的网页可以有数十亿个，而且有很多网页每天都在更新，因此理论上WebGetter是一个永不终止的进程。在一个运算能力不是很高的服务器上，WebGetter的网页抓取速度并不能超越Internet上的网页更新速度。因此从图3可以看到，此进程没有终止状态，它不停地等待即将抓取的网页URL，除非人为终止它，即发送一个stop_signal。由于即将访问的URL并不总是有效的，因此它会自行判断此URL是否可以连接，如图中的判断语符号所示，如果不可以连接，则放弃抓取此URL，跳入下一个网页继续抓取。WebGetter把抓取的网页内容，以及一些相关信息送入Database存储起来，通过消息content送至Database。

图3 WebGetter进程图

WebParser进程的主要作用是控制UrlQueue，进程状态图如图4所示，它通过对每个抓取网页的分析，提取出其中的超链接地址，并加入到UrlQueue中去。由于其中的某些Url可能已经访问过，因此不必将此Url再加入到队列中去。这里访问过的意思是通过某种算法标准，在一个时间界定范围内被访问过，例如一个新闻网站，虽然可能在数据库中存在着此Url，但是经过12或24小时之后，其中很多新闻已被更新，有必要重新抓取新的网页内容，因此将其定义为“未访问过”，即isVisited信号为0。WebParser通过到数据库中查询Url和访问时间来确定此条地址是否被访问过。

图4 WebParser进程图

2.3 数据库模块

数据库模块主要分为两大部分，分别为倒排索引部分reverse_index和查询处理部分handler，如图5所示。由于SDL对于非通信的实体关系之间描述能力比较弱，数据库部分虽然是搜索引擎的核心部分，用SDL描述却比较简单，因此涉及到消息传递的通信动作只有少数几个。可以看到，reverse_index和handler部分之间在途中是没有消息传递的，这是因为它们之间是通过数据库内所存储的内容间接交换信息，只有在添加新的网页内容时，系统通过reverse_index将同样的内容传递给handler一份用来将其存入数据库中。这里的SDL并没有描述如何建立倒排索引的算法，实际上关于建立倒排索引的算法一直是计算机领域所需要解决的研究问题之一，如今并没有一个绝对最优的倒排索引算法，而且Google和Baidu等公司的倒排索引算法也不对外公开，但是其基本思想都是一样的。由于SDL本身对算法描述的能力较弱，因此此处不对建立倒排索引的方法过多研究，只关心它们的消息处理流程。

图5 数据库模块图

倒排索引是全文搜索引擎的核心部分，但是它的对外消息收发流程却十分简单，因此主要的工作都是内部的算法实现问题。如图6所示，建立倒排索引主要有两种方式，一种是基于新的索引关键字，在数据内已有的内容中建立索引。另一种是由于不停地有网页加入进数据库中，对网页的内容进行分析处理加入到相应的关键字索引中也是该进程的主要工作。由于搜索引擎是一种web服务，因此该进程也没有结束状态，只要服务正常提供，那么进程将不停地处理下去。

图6 倒排索引reverse_index进程图

数据库的主要工作是处理查询请求。不仅是来自用户的关键子查询，也有来自于系统内部为了实现功能而需要的查询请求。如图7所示，该进程主要处理三种消息。来自前端的keyword查询，通过索引找到匹配的网页内容，然后发送回前端；来自WebParser的isVisited查询，进程先查找出该URL所在的内容，然后通过某种时间标准判断是否被Visit过，返回给Web-Parser一个0或者1作为结果；来自reserve_index的web content，进程将网页内容和其他信息如访问时间、pangeank等一并添加入数据库中。不管哪种输入，进程处理完之后都将回到初始状态，等待下一条输入消息发送过来。

图7 查询处理handler进程图

2.4 用户前端FrontEnd

用户前端一般来说以一种Web方式提供搜索引擎服务。这里主要的技术难点是分词处理系统。如前所述，由于本文的内容集中在讨论SDL描述消息处理流程问题，因此未对详细算法进行分析。这里前端主要接收用户的查询输入，并向数据库提交查询请求，然后将查询结果显示出来。如图8所示，前端模块有一个进程，为user_interface，顾名思义，它的主要功能是提供给用户一个应用接口，让用户来调用自己的服务。一般来说，以Google和Baidu为主的搜索引擎厂商提供的是POST方式的服务调用方式，可以很好地支持HTTP协议，并且接收比较大的查询请求。而显示搜索结果采用的是HTML的网页方式，用户直接选择相应结果对应的超链接即可找到搜索的网页。

图8 前端模块FrontEnd

用户接口进程是一个顺序处理流程，如图9所示。它等待用户的查询输入，并且通过对查询请求的解析，来获得可以让数据接收的查询关键字。这里的parseQuery过程主要包括分词、语义匹配、布尔检索翻译等工作。然后将解析后的关键字送入数据库获得查询结果。最后将查询结果以特定的方式显示在界面上，供用户浏览。同样，由于它是一种web服务，因此没有终止状态，只要服务存在，此进程将一直工作下去，这点和很多电信通信服务类似。

图9 用户接口流程

3 结语

包括搜索引擎在内的很多WEB服务同通信系统设计一样，是一种一旦部署好就一直存在着的服务。当前已有的文献基本都是使用UML对搜索引擎系统进行描述和建模，本文通过对搜索引擎系统的分析，以信号传输为重点，研究了系统的各个模块与进程之间的消息传输关系。从一个宏观的角度来观察搜索引擎服务，自顶向下逐层细化。本文将SDL这种普遍用于描述通信系统的语言应用于WEB服务上，是一种可以研究的新的尝试。