原创《一种基于语义的搜索引擎算法与实现》
该文是关于搜索引擎相关本科论文范文和搜索引擎算法和语义和实现有关论文范本。
摘 要：介绍了基于语义搜索引擎的工作原理、模型结构和特点,从空间向量和语义词典相似度两方面分析了基于语义搜索引擎的文本相似度算法和词语相似度的计算方法.建立了空间向量模型,并使用C++语言计算了文本相似度.结果表明,算法能够有效的计算文本相似度,更好地实现与用户之间的交互,达到查全查准的目的,为各领域信息的快速、准确检索提供了参考.
关键词：语义；搜索引擎；文本相似度；词频
中图分类号：TP391.3
文献标识码：Ａ
文章编号：1674-0033（2018）06-0001-05
搜索引擎[1]是在互联网上搜集、提取、处理信息的有效方式,随着互联网上信息量的迅速增加、信息组织方式的散列多样,都对高效准确的搜索引擎算法提出了更高的要求,从而更好地服务用户主动、快捷地查询到所需信息.常见的传统搜索引擎有网络目录和全文搜索引擎.为了保证查全率,往往尽可能地索引更多的页面并根据一定的规则计算反馈结果与所查信息的相关度,进而排序向用户推送结果,由于相关度计算规则的差异性和简单匹配性,导致查询结果的反馈不一定精准.数据量的急剧增加也使得搜索过程不能迅速完成.基于语义的搜索引擎[2-4]相对传统搜索引擎大大提高了召回率和精确度,文本相似度的计算[5]不满足于简单匹配,而更侧重于语义相似性,通过同义词词林[6-7]以及相关平台的词汇相似度[8]统计等计算语义的相似性.使得文本相似度计算方法更加合理精准,更适合于知识密集型领域的应用.
1 基于语义的搜索引擎
基于语义的搜索引擎[3]以自然理解技术为基础,将信息索引关键词的层面提升到概念,增强了对知识的理解能力.对自身索引数据库里的数据进行语义上的标注[4],对用户查询的关键词进行语义分析,在数据库中搜索相关联的项目,反馈给用户.模型结构如图1所示.
索引数据库模块中信息搜索器收集来自互联网的信息,并对其进行整理、去重,生成关键词.将信息输送给语义索引器.语义索引器对信息中的关键词进行提取并作语义标记,再将标记好的关键词进行分类,按照一定类别顺序存入索引数据库中.
搜索模块中,当用户输入查询内容时,检索器负责对用户搜索内容进行关键词的提取,并传送给转换器.转换器将关键词转换成语义推理机能够识别的代码,由语义推理机进行推理、分析,得出用户查询内容的准确含义,形成关键词集,语义索引器在索引数据库中进行查找,结果编辑器对结果进行编辑整理,最终将查询结果输送给用户.同时,结果记忆器记录用户的访问记录,并将访问结果返回给索引数据库,通过对比语义索引器所给关键词,判断查询结果是否准确,以此作为依据,对语义推理机进行优化.
2 基于语义搜索引擎的主要算法
2.1 链接分析算法
2.1.1 PageRank算法
根据网页被链接的次数来判断其重要性,以重要性为依据对网页进行排序.PageRank算法[9]在排序之前,会预先给每个网页一个PageRank值一般为PR等于1/N,N为网页总数.通过查看某网页被直接或者间接链接的次数,来计算PR值,计算方法如式(1)所示,根据PR值对网页进行排序.
其中,Mp是链接网页Pi的所有网页的集合,L(p)是链接网页Pj的网页数目,N是网页总数,α一般取值0.85.
2.1.2 HITS算法
HITS算法[10]通过中心权威网页对外进行链接,并将链接到的符合题意的页面结果进行返回,集中在一个集合中,返回给用户.HITS算法根据一个网页被链接的次数（入度）以及从此网页链接向其他网页的次数（出度）来评价这个网页的重要性.同时,重要网页指向的网页重要性较高.计算重要性,需要先计算各个页面的权威值和目录值.设初始子集的集合P等于{P1,P2,P3,…,Pn},根据页面之间的链接关系建立一个矩阵,如式(2)所示.如果页面i有链接到页面j,则aij的值即为1,反之为0.
2.2 去重算法
去重算法对需要测重的网页进行HTML项分析,并将网页链接抽取出来,上传给互联网.互联网根据这个链接调取索引列表中的其他全部页面进行重复性检测,将重复页面舍弃.检测流程如图2所示.
根据文档中提取出来的关键信息,将特征点一一罗列出来,汇集成文档指纹.并将进行过相似性计算的其它文档与这个指纹进行比较,找出相似的文档.其中,文本相似度算法是去重算法中一个重要的中间算法,相似度算法越有效,查准率、查全率就越高.
3 基于语义搜索引擎的文本相似度计算方法
文本相似度是指两个或者多个文本之间相似程度,介于（0,1）.数值越小,则文本的相似度越低.文本相似度算法[11]是为了计算文本相似度以及文章中主要的关键词.目前,主要有基于向量空间模型的余弦相似度算法和基于语义词典的语义相似度算法.
3.1 向量空间模型（V）的余弦相似度算法
向量空间模型[12]V对文本进行分词处理,在处理好的分词中找到关键词并进行词频统计.将统计好的关键词放置到V的各个维度上,再以余弦相似度为依据,计算出文本相似度.主要分为预处理、关键词选择、加权计算、对生成的空间模型进行余弦计算几个阶段.
预处理阶段对文本进行分词并去除停用词.去掉停用词以及频率较高的副词等一些无实意的词后,根据词语频度找出关键词.关键词频为ＴＦ＝Ｓ/Ｔ,其中S为词语数,T为关键词数,使用TF-IDF权值计算方法进行加权计算,计算方法如式(3)所示.
其中,ct /ct是对关键词的词频信息进行归一化处理, M是文章总数,St是有关键词出现的文章数量.
最后,使用空间模型的余弦算法,将文本之间的运算转化成向量之间的运算,将抽象问题具体化.两个文档W1和W2在空间模型中的向量可以表示为W1等于W1[a11,a12,…,a1n]和W2等于W2[a21,a22,…,a2n],计算两个文档之间的相似度Sim(W1,W2)主要方法：
1）余弦法计算方法
3.2 基于语义词典的语义相似度计算方法
基于语义词典的语义相似度算法[8]也是从中文分词和去除停用词开始,进而进行权值运算.同时要去除小权值的关键词,然后再根据词条建立空间向量,通过语义相似度的计算,得出相似度矩阵,进而得到LCS（松散耦合系统）,最后通过系统来计算两个文本的相似度.基本流程如图3所示.
计算结果受到语义关系、语义距离、节点深度、节点密度四个因素的影响,语义关系包括继承关系、整体与部分关系和同义词关系.语义距离是影响文本相似度之间最重要的因素,是两个义项节点之间路径的长度.路径越大,相似度越低；节点深度是义项与树根路径之间所经过的边数.深度越深,两个义项的相似度越大.节点密度是两个义项拥有的共同祖先的子节点的个数,节点的子节点密度越小,相似度越大.
文本相似度可以从词语相似度、句子相似度以及段落相似度等方面进行判断.通过文本中关键词的编码方式对词语进行相似度处理,提取语义上的关联性进而扩充到文本相似度的计算上.并将其具体应用到语义搜索引擎的检索上,使其能够通过用户访问信息的关键词的关联性在索引库中搜索相关的结果,并推送给用户.
4 基于语义搜索引擎的词语相似度计算方法
词语相似度[8]是文本相似度的基础.词语相关度和词语相关性是影响词语相关度的两个重要指标.一般通过词语之间的距离来判断词语相关性.
每个词语都有一个或者多个义项.而在计算词语之间相似度时,需要用到所有的义项.基于语义搜索引擎根据同义词词林中词语义项的编码以及两个义项的语义距离,计算义项相似度.同义词词林遵循树状层次结构将所有的词条组织收录在一起,层层结构逐级递增,对词义的刻画也越来越细致,要对义项进行相似度计算,首先需要根据两个义项编码在哪层开始不同来判断两个义项在哪层分支上.例如：Ea02A03与Ea02B03,因为在第4层编码开始不同,则从第4层开始分支.从第1层开始,相同则系数乘以1,不同则乘以所在分支层对应的系数,再乘以调节参数,如果义项A和B不在词林中的同一棵树上,则相似度,如果在词林中的同一棵树上并且在第2层分支上,系数为2,则相似度如式(7)所示：
词语相似度的计算主要是通过语义词典对义项[8]的计算来实现的,在对文本进行相似度比较之前,可以对文本进行分词、去除停用词等处理,这样就可以将文本划分成单个的词语.通过语义词典比较词语之间的相似度,判断两个文本中最相似的关键词进行相似度计算[12].
5 实验结果与分析
通过实验,使用C++语言实现了空间向量模型的文本相似度算法,结构如图4所示.
在本模型中,先对输入的文本进行分词、去除停用词等一系列处理,根据词频计算公式统计词语频度,找出关键词,并以数组的形式返回.建立关键词的空间模型,根据公式计算出文本之间的内积和余弦值,最后根据计算出来的阈值来判断文本之间的相似度.在实验中,主要针对空间向量模型建立空间模型,运用向量内积来计算余弦值,求出文本的相似度.
实现算法过程中,先通过判断两个文本的长度,如果文本的长度<1,则直接返回,不进行结果集的运算,如果文本的长度>1,则继续进行相似度运算.
if ((dictionary1.Count < 1) || (dictionary2.Count < 1))
{ return 0.0; }
在进行相似度运算之前,先对文本1进行判断,将文本1的关键词取出,以数组的形式返回,然后对数组进行遍历,根据关键词对文本1,2的值进行匹配,如果值存在则进行计算累计求和,如果值为空则移除.
Dictionary<string,int>.KeyCollection keys1等于 dictionary1.Keys; foreach (string key in keys1) {
dictionary1.TryGetValue(key, out temp1);
if (！dictionary2.TryGetValue(key, out temp2))
{ temp2 等于 0; }
dictionary2.Remove(key);
numerator +等于 temp1 * temp2;
denominator1 +等于 temp1 * temp1;
}
使用相同的方法对文本2进行判断,最后将文本1,2求出的数据进行开平方根计算,得到相似度的结果.
程序中阈值是用来衡量相似度大小的度量值.当设置阈值为0.5时,收录的结果为相似度大于0.5的所有结果.实验中选择了25个文档进行测试,当阈值为0.5时运行结果,如表1所示.
通过程序实现了文本相似度算法的计算,结果显示,文本相似度介于（0,1）,值越接近1,说明相似度越高；值越接近0,则相似度越低.在本次验证中,设置阈值为0.5,对于计算出的相似度低于0.5的,则结果会自动去除,不显示在文档中.所以,显示出来的相似度值均为0.5以上.如0017&0025,表示的是文档17与文档25之间的相似度为0.56.
设置不同的阈值,搜索出的相似文本数量也会有所变化,根据统计,不同阈值所检索出的相似文档数量,如表2所示,通过对比,可以看得出来,阈值越高,查出的相似文档的对数越少,对文档相似的要求越严格,阈值越低,越容易被认定为相似文档.从实验结果可以看出,传统的搜索引擎在搜索过程中,只能找出完全匹配的相似文档,不能找出同义词或者知识性相同表达不同的相似文档,影响文本搜索的准确性和完整性.在基于语义的搜索引擎算法中,根据反馈结果可以选择合适的阈值,获取到准确完整的数据信息.
6 结论
本文深入分析了基于语义的搜索引擎算法和基于空间向量模型的文本相似度算法,总结了基于语义词典的语义相似度算法在计算文本相似度的算法流程,使用C++语言,实现了文本相似度的计算,并对实验结果进行了分析.实验结果表明基于语义词典的语义相似度能够实现文本相似度的有效计算,从而实现更快速、准确地检索.为了保证语义相似度计算的全面性,需要经常更新词典信息库,并通过词语之间的差异,找出新的计算方法.
参考文献：
[1] 韩倩倩.传统搜索引擎与语义搜索引擎检索服务比较研究——以雅虎和Kngine为例[J].信息通信,2015(4):
115-116.
[2] 赵夷平.传统搜索引擎与语义搜索引擎服务比较研究[J].情报科学,2010,28(2):265-270.
（下转第29页）
[3] 徐静.基于语义的搜素引擎研究[J].情报探索,2012,8(8):108-109.
[4] 赵宏亮,杨鹤标.面向领域的语义搜索引擎的应用研究[J].计算机工程与设计,2012,33(5):1801-1805.
[5] 廖志芳,周国恩,李俊锋,等.中文短文本语法语义相似度算法[J].湖南大学学报(自然科学版),2016,43(2):135-140.
[6] 陈海燕.基于搜索引擎的词汇语义相似度计算方法[J].计算机科学,2015,42(1):261-267.
[7] 张硕望,欧阳纯萍,阳小华,等.融合《知网》和搜索引擎的词汇语义相似度计算[J].计算机应用,2017,37(4):1056－1060.
[8] 吴秦,白玉昭,梁久祯.一种基于语义词典的局部查询扩展方法[J].南京大学学报(自然科学),2014,33(7):526
-532.
[9] 李稚楹,杨武,谢治军.PageRank 算法研究综述[J].计算机科学,2011,38(10):185-187.
[10] 张家健,赵冰.基于网页排名的其他链接方法的研究[J].电子设计工程,2016,24(2):128-131.
[11] 夏志明,刘新.一种基于语义的中文文本相似度算法[J].计算机与现代化,2015,6(10):243-256.
[12] 叶施仁,严水歌,杨长春.基于V和LSA的微博搜索排序方法研究[J].情报科学,2015,28(2):98-112.
搜索引擎论文参考资料：
该文总结，上述文章是一篇关于搜索引擎算法和语义和实现方面的相关大学硕士和搜索引擎本科毕业论文以及相关搜索引擎论文开题报告范文和职称论文写作参考文献资料。
