（计算机软件与理论专业论文）中文人名搜索引擎的设计与实现.pdf

摘要 随着时代的发展，w e b 信息量正在以指数级的速度增长，传统搜索引擎的检 索方式，造成搜索的结果集为海量冗余信息，难以找到特定行业用户所需要的精 简而准确的信息。这样，面向主题的搜索引擎便孕育而生，它也被认为是新一代 搜索引擎的发展方向。 本文提出了一种采用了多维数据方体作为中文人名搜索引擎的数据存储方 式，通过对职业、所在地、出生年月的信息提取，然后运用补偿式信息提取的主 题文本分类算法和语句一词条聚类算法，对相似文档归类，最终实现了以检索人 名为主题的中文人名搜索引擎原型系统。通过对原型系统的试验分析，我们可以 将不同的人物按照职业、所在地、出生年月以层次化形式展示，以便用户能够从 不同角度快速的查询目标人物。 关键字：搜索引擎信息提取、文本分类、文本聚类t fi d f 语句一词条矩 阵多维数据方体 l i a b s t r a c t w i t ht h ed e v e l o p m e n to ft h es o c i e t y ，t h ec a p a c i t yo fw e bi n f o r m a t i o n i n c r e a s e se x p o n e n t i a l l y ，s ot h a tt h es p e c i a lu s e r sc a nn o tf i n dt h ew a n t e d s i m p l i f ya n da c c u r a t ei n f o r m a t i o nb e c a u s et h et r a d i t i o n a ls e a r c hm e t h o d s w i l lp r o d u c em u c hr e d u n d a n c yi n f o r m a t i o n i nt h i sc a s et h ev e r t i c a ls e a r c h e n g i n ew a sg i v e nb i r t ht o ，i ti sa l s oc o n s i d e r e dt h ed i r e c t i o no ft h en e w g e n e r a t i o ns e a r c he n g i n e t h i sp a p e rp r o p o s e dak i n do fm u l t i d i m e n s i o n a lt ot a k ed a t as t o r a g e w a y o f c h i n e s ep e r s o n a ln a m es e a r c h e n g i n e ，t h r o u g hc a r r i e d o n i n f o r m a t i o ne x t r a c t i o nt ot h eo c c u p a t i o n ，t h el o c u s ，t h eb i r t hy e a r sa n d t h e nw eu s e dt h es u b j e c tt e x tc l a s s i f i c a t i o n a l g o r i t h m b a s e do n c o m p e n s a t o r yi n f o r m a t i o ne x t r a c t i o na n dt h es e n t e n c e w o r d sd u s t e r a l g o r i t h mt og a t h e r st h es i m i l a rd o c u m e n t s f i n a l l y ，w er e a l i z e dc h i n e s e p e r s o n a ln a m es e a r c he n g i n ep r o t o t y p es y s t e mt h a th a st a k e nr e t r i e v et h e p e r s o n a ln a m ea st om a k et h es u b j e c t t h r o u g hc a r r i e do nt h ee x p e r i m e n t a l a n a l y s i st ot h ep r o t o t y p es y s t e m ，w em i g h tt h ed i f f e r e n t c h a r a c t e r a c c o r d i n gt ot h eo c c u p a ti o n ，t h el o c u s ，t h eb i r t hy e a r sb yt h e1e v e lf o r m d e m o n s t r a t i o n t h u s ，t h eu s e rw a sa b l ef a s tt oi n q u i r eg o a lc h a r a c t e rf r o m t h ed i f f e r e n ta n g l e k e yw o r d ：s e a r c he n g i n e ；d o c u m e n tc l a s s i f i c a t i o n ：d o c u m e n tc l u s t e r i n g ： i n f o r m a t i o ne x t r a c t i o n ；t fi d f ；s e n t e n c e - w o r d sm a t r i x ：m u l t i p l ed a t ac u b e i l l 原创性声明 本人郑重声明；本人所呈交的学位论文，怒在导师的指蹲下独立进行研究所 取得的成果。学位论文中凡引用他人已经发表戏未发表的成果、数据、观点等， 鸷已弱确注羁塞楚。滁文孛已经 妻骥雩| 建静蠹褰努，不包含强隽萁毯个人躐集体 已经发袭或撰写过的科研成果。对本文的研究成果做出重要灏献的个人和集体， 均已在文中以明确方式标明。 本声爨的法律责经由本人承撵。 论文作者签名：勉! 埠 日期：丝! ：三：罗口 关于学位论文使用授权的声明 零人在寻瑟携芬下象完或熬论文及攘关戆敬务终鑫，妇识产权努属兰髑大 学。本人完全了解兰州大学有关保存、使用学能论文的规定，同意学校保存或向 国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和借阕；本人 授投兰髑大学霹班貉零学链论文懿全部凌部分内容编入骞关数器痒进行梭索，胃 以采用任何复制手段保存和汇编本学位论文。本人离校后发袭、使用学位论文或 与该论文直接相关的学术论文或成果时，第一爝名单位仍然为兰州大学。 僚辩论文在解襄器应遵守藏蕊定。 论文作者签名；塞丝 导师签名： 第一章绪论 1 1 问题的提出及研究的意义 搜索引擎作为互联网中用户上网时的必备工具，其作用已被所有的上网用户 广泛认可。但随着网页数目的急剧膨胀，用户想要在普通的搜索引擎中查询到特 定的人物信息有如大海捞针。 为了在浩瀚的网页中搜索人物信息，我们提出并设计了一种中文人名搜索引 擎。这种搜索引擎是一种将信息提取、文本分类、聚类分析与搜索引擎等相关技 术相结合的新的搜索引擎技术。同时通过补偿式信息提取的主题文本分类算法合 语句一词条矩阵的聚簇式动态增长聚类算法进行文档归类，并将数据存放于多维 数据方体中，以便能快速寻找人物的职业、地点和相关内容的信息，将精简准确 的信息呈现给用户。 1 2 国内外研究现状 第一代搜索引擎的出现可以追溯到2 0 世纪9 0 年代初，以人工分类的目录分 类为主，代表厂商是y a h o o ，其特点是用人工的方式把网站放在各种目录下，允许 客户通过各种方式找到想要的网站，现在这种方式依然还在采用。但随着网络应 用技术的发展，客户不再满足于这种对网站分类和摘要的简单查找，更希望对内容 进行查找，于是就出现了关键字查询，即第二代索引掣”。这时最有代表性的就是 g o o g l e ，它使用关键字网页搜索，内容可以覆盖互联网全部网页内容【2 】。 第二代搜索引擎虽然比第一代在搜索速度、针对多种语言信息的扩展等方面 有所改进，在以自然语言为查询语言方面也做了一些探索。然而，随着i n t c m c t 的 强势发展，网上庞大的数字化信息和人们获取所需信息能力之间的矛盾日益突 出。大多数搜索系统的功能还难于满足用户的需求，诸如数据量高速增长的视 频、音频等多媒体信息的检索，现在仍然是无法突破的难题。而且，一般的公共搜 索引擎只能查到h t m l 格式，这就导致了在企业内部的局域网上，任何没有使用 h t m l 格式的信息将无法被外部的搜索引擎查至l j 3 , 4 】。一个好的搜索引擎不再仅 凭借数据库大小、更新频率、检索速度和对多语言的支持这几个基本特性来衡量。 蔺州土掌 中文人名搜索引擎的设计与实现硕士学位论文 随着数据库容量的不断膨胀，如何从庞大的资料库中精确地找到正确的资料，才是 新一代搜索引擎技术的竞争要点，基于此，第三代中文搜索引擎应运而生。第三代 中文搜索引擎最大特点是大量采取人工介入，实现人工和技术的结合，以提高搜索 水平。以慧聪搜索引擎为例，它长于行业性专业商务信息服务，目前是以人工分类 而运作行业搜索，而且它对于中文网页的搜索，是基于对内容相关的分析来做的， 因此它的功能与第二代搜索引擎相比有了很大的提高。其一，慧聪搜索在搜索结 果的相关性方面做得非常好，即更加智能化，能够为查询者提供更多的相关内容； 其二，数据库更新速度快，目前，g o o g l e 的数据库更新速度是2 0d 左右，而慧聪搜 索数据库8d 就更新一次，保证了搜索的准确性和时效性；其三，功能更加全面，内 容更加丰富，图片、m p 3 搜索一应俱全。 未来的终极搜索技术应该是完全个性化和智能化的。目前第三代搜索引擎只 能说是初步实现了个性化和智能化，为了达到前者的目标，搜索引擎的发展方向应 该是不断贴近用户需求，模拟人类智慧，更好地使用技术来完成更具智慧的搜索。 1 3 论文的组织结构 本文以搜索引擎原理为理论依据，以个性化搜索引擎为研究应用对象，展开 了对如何实现中文人名搜索引擎的讨论。 第一章是本文的绪论部分，主要介绍问题的提出，搜索引擎的国内外现状， 以及发展趋势。 第二章是搜索引擎基础理论知识的介绍，具体讨论了通用中文搜索引擎基本 原理、面向主题的搜索引擎的基本原理。最后通过对中文人名搜索引擎的关键技 术，作了详细的阐述。 第三章是中文人名搜索引擎的体系结构，主要介绍该搜索引擎的体系架构和 服务模型，最后阐述了其核心数据分析系统的简述。 第四章是中文人名搜索引擎的实现。这是本文的核心章节，系统阐述了整个 系统的构架，详细介绍了系统实现的工作步骤，并对每个步骤地具体实现细节作 了全面的分析。 田啊文掣 中文人名搜索引擎的设计与实现硕士学位论文 第五章是实验结果和分析。主要介绍了实验原型系统的搭建，并在此基础上 对实验数据进行了测试与分析，系统的说明了多维数据存储方式在中文人名搜索 引擎中的可行性、聚类分析实现层次化展示的准确性以及中文人名搜索引擎搜索 人名的查全率、查准率。 第六章是总结与展望。这是文章结尾部分，是对文章整体工作的总结，以及 对未来工作提出的要求。 萄州土亨 中文人名搜索引擎的设计与实现硕士学位论文 第二章搜索引擎理论概述 2 1 通用中文搜索引擎 搜索引擎，即s e a r c he n g i n e ，这一词在国内外因特网领域中被广泛的使用，然而， 它的含义却不尽相同。在美国，搜索引擎通常指的是基于因特网的搜索引擎，它们 收集因特网上几千万到几亿个网页，并且每一个网页上的每一个词都被搜索引擎 所收录，也就是我们所说的全文检索，典型的如g o o g l c ，i n f o s e e k ，h o t b o t 。在中国， 搜索引擎通常指的是基于网站目录的搜索服务或者是特定网站的搜索服务，前者 如搜狐、新浪等公司开发的网站搜索服务，后者如c h i n a r e n 网站提供的全文检索 服务5 1 。 2 1 1 通用中文搜索引擎概述 一般而言，通用搜索引擎是指以网络的各种信息资源为对象，以信息检索的 方式提供用户所需信息的数据库服务系统。通用搜索引擎起源于传统的信息全文 检索理论，即计算机程序通过扫描每篇文章中的每个词，建立以词为单位的倒排 文件，检索程序根据检索词在每篇文章中出现的频率对包含这些检索词的文章 进行排序，最后输出排序结果。与传统的信息检索理论研究不同，这种搜索引擎 的用户看中的是系统的稳定性、速度、易用性和返回的信息量及相关度【6 】。 通用中文搜索引擎是指以网络上的中文信息为主要对象，提供信息的自动收 集、过滤、索引和检索导航等服务的搜索引擎。根据是否采用词语切分技术，通 用中文搜索引擎可分为基于字的通用搜索引擎和基于词的通用搜索引擎。基于字 的通用搜索引擎将文章中的每一个汉字都录入到索引库中，用户的检索提问根 据单汉字匹配的原则去检索，此法的优点是能够保证很高的查全率，但查准率低 而基于词的通用搜索引擎则是按词建库，当然这种词语是按一定的规则与方法 对文章切词得来的，这种搜索引擎的优点是拥有较高的查准率，用户检索时往往 能一次命中，缺点是对切词技术要求高。 2 1 2 通用搜索引擎的实现策略 按照信息搜集方法和服务提供方式的不同，通用搜索引擎大致可分为： 篙州文拿 中文人名搜索引擎的设计与实现硕士学位论文 基于r o b o t 的搜索引擎：搜索引擎通过一个称为r o b o t 即网络蜘蛛的程序自动访 问w e b 站点，搜集站点上的网页，并根据网页中的链接进一步搜集其他网页或 转移到其他站点上。r o b o t 对搜集到的网页经过分析处理后，获得网页的关键字， 并依此建立索引，存入到资源索引数据库中。用户查询时，通过输入的关键字来 检索数据库，获得相应的结果。 基于d i r e c t o r 的搜索引擎：以人工方式或者半自动方式搜集信息，由编辑人 员查看信息后，人工形成信息摘要，并将u r l 置于事先确定的资源索引数据库 中。用户通过输入关键字查询资源索引数据库的内容，获得相应的结果。 通用搜索引擎的系统构架【1 ： 对于通用搜索引擎，无论采用何种搜索策略，大致都是采用如图2 1 所示的 系统结构。 图2 1 ：通用搜索引擎系统结构图 其中，搜索引擎通过存取分析子系统对h t m l 文档进行分析，获得网页的相关 内容，然后通过搜索控制子系统迸一步获得网页的关键字，从而形成资源索引数 据库。用户通过信息检索子系统对资源索引数据库进行查询，获得相应结果，而 管理和监控子系统负责整个搜索引擎系统的正常运行。 前埘文粤 中文人名搜索引擎的设计与实现硕士学位论文 2 2 面向主题的搜索引擎 由通用搜索引擎的实现策略可以知道，基于r o b i n 的搜索引擎尽管具有更新 及时、无需人工干预的特点，但由于返回的信息过多，甚至返回无用的信息，因 此并不能真正反映出网页的质量。而基于d i r e c t o r 的搜索引擎尽管能保证信息准 确，导航质量高，但需要人工介入维护量大、信息更新不及时的缺点使得它很难 适应当前日新月异的形势。 因此，我们希望开发一种新型的搜索引擎即具有r o b o t 更新及时、无须人工 干预的特点，又具有d i r e c t o r 信息准确的特点，这就是面向主题的搜索引擎。 2 2 1 面向主题搜索引擎概述 所谓主题，是指用户所要搜集的信息的特征。主题通常由用户指定若干相关 网页( 称为样本网页) 来确定。通过用户选定的样本网页来确定所搜集的主题， 在此基础上进行特征提取，分析样本网页，提取特征信息，然后根据所获取的特 征信息进行搜集，对每一个搜集的网页，都赋予一定的相关性，相关性越高，就 说明与主题越相似。 近几年，人们越来越注重对确定主题搜索的研究，提出不少新的算法【8 ，9 1 ， 开发了不少面向主题的搜索引擎文献t s 描述了一种“s h a r k ”搜索算法，该算 法主要是面向主题的搜索；文献【1 们中采用了一种新的算法，并开发出一个实用 系统( f o e us e d c m wl e 0 ，该系统中所谓的主题搜索不再采用关键词而是以网页 作为样本wt ms t l l l 是一个基于启发式搜索算法的主题搜索引擎，在一定程度 上加快了c r a wl e r 的搜索速度g r o u p e r 则是根据网页的主题对网页进行归类， 有助于加快用户从数以千计的搜索结果中筛选目标网页 2 2 2 面向主题搜索引擎的系统结构 根据面向主题的特点，面向主题搜索引擎可以采用如图2 2 所示的系统结构： 雨州文掌 中文人名搜索引摹的设计与实现硕士学位论文 图2 2 面向主题搜索引擎系统构架 从系统结构图可以看出，系统实现面向主题的功能主要有3 个部分组成 1 ) 特征提取子系统：通过读取给定的样本网页，运用文本提取的方法得到 主题的特征向量，存入特征库： 2 ) 存取分析子系统：根据特征库提供的特征向量，搜集网页，对网页进行 初步分析，获得网页的主题信息。 3 ) 搜索控制子系统：根据存取分析获得的主题信息，并参照特征库的主题 描述，对搜索到的网页进行筛选分类，获得资源索引数据库。 2 3 中文人名搜索引擎系统 2 3 1 中文人名搜索引擎系统概述 中文人名搜索引擎是面向搜索人物信息为主题的，因此，它是一种面向主题 的搜索引擎。整体来说，本文所提出的中文人名搜索引擎，结合了多维数据存储、 信息提取、文本分类、文本聚类等技术，是一种新型搜索引擎的研究。 在我们的整个工作过程中，首先，对我们所抓取的姓氏网页，通过对其中与 主题无关的“噪音”数据的消除，实现了数据从带有h t m l 标签的混合文档到 神一击穿 中文人名搜索引擎的设计与实现硕士学位论文 只有中文内容的汉语文档的转换，然后，对已消噪的数据从中提取职业、所在地、 出生年月相关属性，实现了对不同人物的基本划分，进而对所得划分通过补偿式 信息提取的主题文本分类算法和语句一词条矩阵聚类算法进行文档归类，实现了 多维数据方体的构建，最终，将人物信息以层次化结构展示给用户。 2 3 2 中文人名搜索引擎的关键应用技术 1 ) 多维数据在中文人名搜索引擎的应用优势 本文选用多维数据方体作为中文人名搜索引擎的数据存储方案，除了因为其 具有存储数据的能力，关键在于多维数据方体可以提供多级的趋势分析，能整合 和清理数据，提供全面的技术架构、可行的数据管理产品和丰富的内容。同时相 对于操纵型数据库来说其突出的特点是对海量数据的支持和快速的检索技术。把 数据从各种各样的存储方式中拿出来，进行必要的转化、整理，再存放到多维数 据方体内。 另外，多维数据中的数据抽取工具对各种不同存储方式的数据都具有访问能 力。它能生成c o b o l 程序、m v s 作业控制语言( j c l ) 、u n i x 脚本、和s q l 语句等，以访问不同的数据：能通过数据转换删除对决策应用没有意义的数据段； 能转换到统一的数据名称和定义；能计算统计和衍生的数据；能给缺值数据赋给 缺省值；能把不同的数据定义为统一方式。 再者，中文人名搜索引擎的最终目标就是要搜索中文人名，主题明确，所涉 及到的数据，仅仅为与人物相关的网页而已，而在万维网上的数据量庞大，如果 使用传统的数据库很难达到抽取相关数据的目的，那么层次化的展现查询结果那 就更是难上加难了。但是多维数据方体能给我们提供一系列使用方便的数据抽取 和数据转换工具，使得本来困难的工作简单化了，可行性也增强了。 2 ) 信息提取在中文人名搜索引擎中的应用 信息提取( i n f o r m a t i o ne x t r a c t i o n ) 是指从一段文本中提取指定的一类信息 ( 例如事件、事实) 、并将其( 形成结构化的数据) 填入一个数据库中供用户查 询使用的过程【1 2 】。本文需要提取出人的职业、所在地名和出生年份，以树状结构 按职业、所在地和出生年份分层显示。所以我们的信息提取目的是过滤掉与提取 臂一矢喜 中文人名搜索引擎的设计与实现硕士学位论文 目标不相关的文本；然后通过分词标注和知识库，识别所有与提取目标相关的词 汇；句法和语义分析只应用于所有包含了需要提取得关键词的句子的集合，对每 个句子的分析结果近似于该句子的语义框架表示( 此框架的定义与提取目标密切 相关) ，这里以关键词为中心进行句法分析；使用模式匹配方法提取相关信息； 最后对这些信息进行综合，便可得到所需信息的各种数据项( 关系数据模式的各 个字段) 。 3 ) 文本分类在中文人名搜索引擎中的应用 文本分类是指在给定分类体系下，根据文本内容自动确定文本类别的过程。本 文应用了种新的补偿式信息抽取的主题文本分类( c o m p e n s a t e di n f o r m a t i o n e x t r a c t i o nt e x tc l a s s i f i c a t i o n ，c i e t c ) 算法【”1 。这种算法不同于一般的文 本分类算法，它是一种有指导的、不需要建立训练集的、通过信息抽取和文本聚 类循环增加类的数目和类内项的一种线性的文本分类算法。 4 1 文本聚类在中文人名搜索引擎中的应用 文本聚类是一个将文本集分组的全自动处理过程，是一种典型的无教师的机 器学习问题。类是通过相关数据发现的一些组，类内的文本和其他组相比更为相 近。因此，文本聚类的目标是找到这样一些类的集合，类之间的相似度最小，而 类内部的相似性最大。 通常文档聚类是用空间向量模型1 4 ，坫1 ( v s m ) 来表示文本特征。在该模型中， 文档空间被看作是由一组正交词条向量所组成的向量空间，每个文档表示为其中 的一个范化特征量v ( d ) = “，以d ) ；一，w a d ) ；一厶( d ) ) ，其中为词条项，可以为 单词，也可以为词组；w f ( d ) 为在文档中的权值，一般定义为在d 中出现频率 或频率的函数这样，文档集可以用文档集矩阵m ( n ，w ) 表示，n 代表文档数，w 代表词数，行代表文档，列代表文档中出现的词【1 6 】但是，向量空间模型不能 够保持词与词之间的语义联系，因此，不能确保聚类的准确性，所以为了保持词 与词之间的语义联系，我们将会形成一个语句一词条矩阵来表示一个文档，并应 用一种新的语句一词条矩阵聚簇式动态增长聚类算法【1 7 1 对文档聚类。 前科土尊 中文人名搜索引擎的设计与实现硕士学位论文 2 3 3 中文人名搜索引擎系统的特点 本文的搜索引擎是面向搜索人名为主题的，是智能化的、个性化的、面向服 务的一种搜索引擎。但本文的搜索引擎除了具备上节所述面向主题的特点外，还 有以下几个特点： 1 ) 我们的搜索引擎主题鲜明，目的单一，搜寻关键字就是中文人名。 2 ) 我们的搜索引擎中所涉及的分析数据存储于多维数据方体中，而将数据存放 于多维数据方体中的最大优点在于可以分析、重组数据，这是一般数据库和 文件系统所不具备的。 3 ) 我们的搜索引擎查询分析采用了m d x 查询语言。 4 ) 我们的搜索引擎采用了文本挖掘技术中的文本分类算法和聚类分析【1 8 l 方法。 5 ) 我们的搜索引擎根据分析型数据的特点将采用层次化的树形结构显示结果。 小结：本章讨论了通用中文搜索引擎基本原理、面向主题的搜索引擎原理及 中文人名搜索引擎的功能等理论知识，这为后续的章节作了坚实的理论铺垫。在 这些概念当中，其中关于面向主题搜索引擎的概念、多维数据方体的存储方案、 信息提取、分类和聚类分析的概念将是本文中主要涉及的。最后，本章还就中文 人名搜索引擎选取多维数据方体作为数据存储方案，作了详细的阐述。从下章开 始我们将讨论如何把上述知识运用到中文人名搜索引擎当中去。 盈_ 叶文掌 中文人名搜索引擎的设计与实现硕士学位论文 第三章中文人名搜索引擎体系结构设计 体系结构也称为体系构架，为整个系统提供了一个结构、行为和属性的高级 抽象，由对构成系统的元素的描述、元素问的相互作用、元素集成的模式以及这 些模式的约束组成。体系结构不仅指定了系统的组织结构和拓扑结构，并且显示 了系统需求和构成系统的元素之间的相互关系，提供了一些设计决策的基本原 理。它是实现系统其它部分功能设计的前提与基础。 3 1 中文人名搜索引擎的体系结构 由于中文人名搜索引擎的最终目标是搜索人名，换言之它是面向服务的。所 以我们应采用面向服务的体系结构( s e r v i c e o r i e n t e da r c h i t e c t u r e ，s o a ) ，这种结 构在应用程序的不同功能单元( 称为服务) 之间定义良好的接口和契约并将其联 系起来。接口是采用中立的方式进行定义的，它是独立于实现服务的硬件平台、 操作系统和编程语言。这使得构建在各种这样的系统中的服务可以以一种统一和 通用的方式进行交互。 整个体系结构分为数据层、分析层、和应用层。如图3 1 所示： 一盘撼l k 一一 一- 自峨i 扣一一 囤匝习圆圈 一- | 蛾肛 i 慧嫠| 嚣篓鬃篓l | 鲫驸ii 据抓取il 撼洧曝ii 糖券糖l | j 鼍掰“”i 图3 1 ：中文人名搜索引擎的体系结构 数据层是整个中文人名搜索引擎的数据基础，其中包括姓氏w e b 数据抓取、 姓氏w e b 数据消噪、原始网页数据的存储、词频统计等。姓氏网页数据在中文 人名搜索引擎中有着非常重要的作用，它是实现在海量的网页数据中提取个性化 - 1 1 - 盈州文聋 中文人名搜索引举的设计与实现硕士学位论文 姓氏数据的方法，是降低数据存储开销，去除与姓氏无关网页的关键技术。同时 也是为用户提供准确查询的基础和前提。 分析层是将半结构化的网页数据结构化和量化的过程，是整个中文人名搜索 引擎的核心。它主要包括姓氏文档切分词处理、信息提取、相似文档的聚类和姓 氏w e b 多维数据方体的构建。在这个过程中通过对文档的向量化、数值化处理， 实现了以多维数据模型为基础的多维数据方体，将所有姓氏的网页数据有结构的 存贮在其中，这样可以通过m d x 查询语言容易的实现中文人名层次化查询。 应用层是直接与用户交互的平台，是为用户提交查询人名的前台界面。包括 用户查询客户端和查询词分析器。主要功能是提交用户查询、查询结果层次化显 示。 中文人名搜索引擎是建立在s o a 基础之上的。与用户交互的前台是简单明 了的，只是输入查询的人名，便可得到想要搜索的人物信息。后台所有的分析服 务，对于用户都是透明的不可见的。 3 2 中文人名搜索引擎的服务模型 体系结构可有多种设计的方式。下面，我们从服务的角度来分析整个搜索引 擎。归根结底，我们的搜索引擎是个面向服务的体系，在整个网络环境，上节中 所有的模块，都可以看作是一种服务。不管是单一任务的原子服务，还是多任务 的复合服务，它们最终都会提供某种数据服务。概括起来，在本搜索引擎中的服 务主要有以下一些：数据抓取、数据消噪、信息提取、切词分词、文档分类、文 档聚类、数据存储、数据转换、数据检索、结果展示等，结构如图所示： 萄埘土尊- 中文人名搜索引擎的设计与实现硕士学位论文 图3 2 ：中文人名搜索引擎的服务模型 3 3 中文人名搜索引擎的核心：数据分析系统简述 无论从体系结构图，还是服务模型图，数据分析都是整个搜索引擎的核心环 节，是整个系统的心脏。它包括信息提取、姓氏文档切分词处理、补偿式信息提 取的主题文本分类、相似文档的聚类和姓氏w e b 多维数据方体的构建。具体来 说，需要达到以下目标： 1 ) 有效的对消噪后的文档内容切词分词，消除停用词，尤其是歧义词。 2 ) 彻底将半结构化的数据转化为可以由计算机处理的结构化数据。 3 ) 构建合理的语句一词条矩阵模型。 4 ) 文档聚类时将多语句文档和少语句文档分别处理；将长语句和短语句分 别处理。 5 ) 管理多个工作站协同工作，把姓氏网页数据分布式的存储在不同的机器 上。 d 管理多维数据更新和维护。 蔺一文乎 中文人名搜索引擎的设计与实现硕士学位论文 7 ) 合理分配数据计算所需的内存资源，采用多线程机制。 小结：本章中我们通过不同的视角，对中文人名搜索引擎的系统结构和服务 模型做了详细介绍。这使得我们从逻辑的抽象地角度看待整个系统，从宏观上把 握系统地整体构架，为系统地实现做了良好的抽象描述。在以下的章节中我们将 对上述的各个功能模块的实现分别进行详细的阐述。 萄州文学 中文人名搜索引擎的设计与实现硕士学位论文 第四章中文人名搜索引擎系统的实现 4 1 中文人名搜索引擎系统构架设计 众所周知，网页的数据量之大，分布之广，内容形式之多样。已经被业界人 士达成广泛共识。然而，在这样的海量数据中，搜索人名更是有如大海捞针。 其搜索效率和准确率也就不言自明。为此，我们特别设计了姓氏网页爬虫，在抓 取网页后，对所有姓氏网页进行文档分类、聚类，将网页结构化，存入多维数据 方体，再利用多维数据方体特有的检索语言m d x ，搜索查询结果。 本文中我们介绍了一个基于多维数据的中文人名搜索引擎，它是一个集姓氏 网页抓取、网页噪声数据的去除，然后将网页中的职业、所在地、出生年月三个 人物属性提取出来，再对网页主题内容进行分词处理，统计除停用词、歧义词之 外的词频，构建语句一词条矩阵，通过补偿式信息提取的主题文本分类算法和语 句一词条矩阵聚类算法把文档归类，得到不同人物的聚集，从而构建多维数据立 体。最后，利用m d x 查询语言下钻获得搜索关键字的层次化结果。它的工作流 程如图4 1 所示： 图4 1 ：系统流程图 蹰州文拿 中文人名搜索引擎的设计与实现硕士学位论文 4 2 工作流程详细分析 我们的工作，有三个步骤：分别为姓氏w e b 数据集的构建、姓氏数据集的分 析和姓氏多维数据的索引构建。下面我们将对以上三个步骤进行详细介绍。 4 2 1 姓氏w e b 数据集的构建 姓氏w e b 数据集的构建包括姓氏w e b 数据抓取、姓氏w e b 数据消噪。首先， 姓氏w e b 数据抓取是通过网络爬虫器得到中国百家姓中所有相关姓氏的网页内 容。其次，进行w e b 预处理，清除w e b 中的脏数据。 4 2 1 1 姓氏w e b 数据抓取 由于本搜索引擎目的在于为搜索中文人名提供快捷的方式，然而网络的迅速 发展，万维网承载着巨大的海量信息，如何在如此大量复杂的非结构化数据中有 效地提取与姓氏相关的网页信息成为姓氏w e b 数据抓取的主要任务。 本搜索引擎中为了抓取关于姓氏的网页，我们使用了中文百家姓。百家姓 是北宋初年钱塘( 杭州) 的一个书生所编撰的蒙学读物，将常见的姓氏篇成四字 一句的韵文，像一首四言诗，便与诵读和记忆，因此，流传至今，影响极深。百 家姓本来收集四百一十一个经增补到五百零四个姓，其中单姓四百四十四个， 复姓六十个。我们把姓氏，编辑入库。构成百家姓数据库，这样我们可以使用姓 氏网络蜘蛛【1 9 懈不同的姓氏，在百度搜索引擎中，将所有的姓氏的相关网页搜 集并抓取下来，为组建多维数据方体奠定了内容基础。下面我们对姓氏网络蜘蛛 的设计作一详细说明： 姓氏网络蜘蛛，是一个很形象的名字。如果把互联网比喻成一个蜘蛛网，那 么姓氏网络蜘蛛就是在网上爬来爬去找寻中文姓氏的蜘蛛。姓氏网络蜘蛛是通过 百度搜索引擎所搜集的结果，从结果集合中找到相关姓氏的链接地址，然后通过 这些链接地址得到相关网页的内容，直到把搜索结果集合中所有的网页都抓取完 为止，这样就完成了一个姓氏的网页抓取，以此类推将百家姓数据库中的所有姓 氏完全抓取完毕，就完成了姓氏w e b 数据的抓取。 蔺哪更掌 中文人名搜索引擎的设计与实现硕士学位论文 4 2 1 2 姓氏w e b 数据消噪 我们通过上一步骤抓取到的姓氏网页数据，会发现它们通常包含两部分内 容，一部分内容体现的是网页的主题信息，比如一张新闻网页中的新闻部分，我 们称之为“主题”内容；另一部分则是与主题内容无关的导航条、广告信息、版 权信息以及调查问卷等内容，我们称之为“噪音”内容。噪音内容通常分布在主 题内容周围，有时也夹杂在主题内容中间，但它们并无内容相关性。 为了有效的去除网页中的噪音数据，我们可以把一张网页的页面划分为若干 个区域，并把每个区域称为一个内容块。这些内容块中，有的包含着主题内容， 而有的则包含着噪音内容。通常，一个内容块中的内容是紧密相关的，这就意味 着我们可以以内容块为单位对网页中的内容进行取舍。基于这样的分析，网页净 化过程就是保留网页中包含主题内容的内容块而去掉包含噪音内容的内容块。因 此，网页净化过程可以分为两个步骤：网页内容标签树的构造和网页内容块提取 算法。 1 ) 网页内容标签树的构造 针对本搜索所引擎搜集到的网页净化的特殊需求，我们首先对h t m l 规范中 的标签按照功能进行分类，进而提出更加适合网页净化的标签树的构造方法。 依据标签的作用可以将h t m l 的标签可以分为两类： 规划网页布局的标签：如上所述，在视觉上，网页是由若干内容块组成的， 而内容块是由特定的标签规划出的( 称之为容器标签) ，常用的容器标签有 、 、 、 、 pt h e n p 为相似度阈值 7 ：保留c b i 8 ：e l s e 不保留c b i 4 2 2 姓氏w e b 数据集的分析 w e b 数据集的分析包括信息提取、姓氏文档切分词处理、补偿式信息提取的 主题文本分类、向量矩阵模型的生成、相似文档的聚类和姓氏w e b 多维数据集 市的构建。第一，信息提取【2 1 ，2 2 0 引，提取出人的职业、所在地和出生年月三个人 物属性，为分类、聚类做出保障。第二，姓氏文档切分词处理，对摘取的每个文 档按照句号、分号、感叹号或问号断句，然后对每一句话，切词处理，去掉停用 词。第三，补偿式信息提取的主题文本分类，该算法可以根据信息提取的三个属 性，对文档进行分类，且将属性不足三个的文档进行属性补偿。第四，通过t f * i d f 计算，得到每个文档的语句一词条矩阵，形成若干文档的矩阵集合，用聚簇式动 态增长聚类算法对内容相似的w 曲文档归类，再次将属性不足的文档属性补全。 第五，姓氏w e b 多维数据方体的构建，以便实现用户搜寻人名的层次化显示。 煎耐文掌 中文人名搜索引擎的设计与实现硕士学位论文 4 2 2 1 信息提取 由于我们所设计的中文人名搜索引擎的最终目标是实现人物职业、所在地、 出生年月的层次树状结果的显示。因此，在对文档进行了预处理也就是消除文档 噪音之后，首要任务就是在所处理的网页文档中将人物的职业、所在地、出生年 月三个属性从文档中分离出来，为后续的工作铺垫基础。当然，对于所有文档不 是每一篇当中都具备了三个属性，对于属性不全的文档，我们要在这一步骤中加 以标示，为后续工作提供划分依据。 在上一步工作中，尽管我们已经对文档进行了消噪处理，但文档仍然是自 由格式1 2 l ，相对于结构化和半结构化的文本，自由格式文本的信息提取难度相 当大。在这里，我们为了提取出人的职业、所在地和相关机构名，并以树状结 构按职业、地名、机构名分层显示。出于效率的考虑，信息提取模块需要进行 预处理过程，目的在于过滤掉与提取目标不相关的文本；然后通过分词标注和 知识库，识别所有与提取目标相关的词汇；句法和语义分析只应用于所有包含 了关键词的句子的集合，对每个句子的分析结果近似于该句子的语义框架表示 ( 此框架的定义与提取目标密切相关) 。这里以关键词为中心进行句法分析， 使用模式匹配【2 4 1 方法提取相关信息；最后对这些信息进行综合，便可得到所需 信息的各种数据项( 关系数据模式的各个字段) 。其中最关键的是模式库的建 立，我们针对不同类型的网页使用了不同的方法建立模式库。相关工作分析如 下： 1 ) 相关定义 定义l ：知识库d ：由各个知识表构成。知识表是信息提取所需要的涉及到特 定领域的词典以及提取模式库。 定义2 ：姓氏网页数据集m ：姓氏网页数据集合是由网络蜘蛛从i n t e r n e t 上抓 取包含姓氏的网页构建而来。 2 ) 信息提取工作过程 根据m u c 和h o b b s 提出的信息提取体系结构口5 【2 6 1 ，针对本搜索引擎的特点， 我们的信息提取模块的工作过程如下： 鞠埘文亭 中文人名搜索引擎的设计与实现硕士学位论文 1 建立知识库d ： 2 根据搜索的中文人名，在上步姓氏w e b 数据抓取所得姓氏数据集合m 中搜 索，得到所有相关网页内容，定义网页内容集合为w = w l ，w 2 ，w 3 ，w n ) ； 3 对每一个w i 进行网页去噪处理，得到净化后的文本集合t = f t l ，t 2 ， t 3 ，t n ； 4 对每一个t i 再进行分句，得到句子集合s = s i l ，s i 2 ，s i 3 ，s i n ) ； 5 根据文本分类标识库，将文本集合t 分为两类：个人介绍类c 1 和个人活动 类c 2 。对句子集合s 进行文本分类判定，确定s 属于c x 类： 6 对句子s i i 进行分词标注，根据标注词性和相关知识库从句子集合s 中过 滤掉不相关的句子，提取相关的句子集合为c s = c s i l ，c s i 2 ，c s i 3 ，c s i m ) ， 其中m n 或者m u 。) 。其计算方法为 c c = 眈忙+ 1 ) 】 式中：k 表示类c 中文档的个数，表示文档的特征失量，c 岛表示类c 的特征失量。文本特征失量采用t f i t f 计算 - 1 l 陋，如】= i 圪j s z m j l m s z ，” $ l m l 2 s i r e l m j j 肌2 2 s i r e 2 m s l m n 2 s i r e m 的运算法则为s 砌n2 嵩青尚，( 1 f 兰蚶s 七m ) ，在矩阵中求出每行的 最小值m i n 曲一= 珏曲( j 砌。) ，记取最小值的下标为j ，也就是就文本t i 与c j 最 相似。设定阈值a 1 ，若r a i n s i m ， a i ，则将其归于c j 文档类中。并更改其t i 的 属性标识为c j 的属性标识，补偿一部分分类。 通过最邻近相似文本分类处理后，提升了部分u 。文档，还有一部分剩 蕊耐土窖 中文人名搜索引擎的设计与实现硕士学位论文 余u d 未被处理，需要对其中可以提高信息度的文本补偿分类结果。也就是说 对于r e r p j ，有子划分只= 职业，所在地点 ；只= 所在地点，工作单位) b = 职业，工作单位) ；只= 职业) ：b = ( 所在地点 ：只= 工作单位) ；lc 表示鼻所含的属性的个数。u n i , 只= 只，另，) ，u n o 只= 只，易，) ， u 。b = b ，岛，) ，。其中b 代表划分类的中心矢量。那么我们可以 根据类似上述计算再次补偿一部分分类。这样，对于这类文档可以将其文档属 性提升。然后对于剩下的无法分类的姓氏网页文档进行下一步的内容聚类，将 其归类。 4 2 2 4 语句一词条矩阵聚簇式动态增长聚类算法 通过补偿式信息提取的主题文本分类算法我们得到了按照职业、所在地、出 生年月三个人物属性的不同分类，然而还会存在部分人物属性不完全的网页无法 被归类到相应的划分当中去。这样我们就需要应用语句词条矩阵聚类算法，按 照内容聚类，将剩余的网页聚集到相应的分类当中。下面，我们对这一算法做一 分析说明。 i ) 相关定义： 定义1 ：假定d 篇文档，由i n 。单词构成，是矩阵的元素点，0 是第j 个 单词在文档i 中出现的次数，b j t f ( t e r mf r e q u e n c y