（信息与通信工程专业论文）基于句子相似度的文本比对算法研究.pdf

，、， j 气 “ 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：日期：年月日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：l 弓虹导师签名：二基翌嗲二一 日期：y 年月，日 l t ， ， - i 一 摘要 摘要 随着计算机和网络的日益普及，各类信息资源共享程度越来越高，给工作和 生活带来极大的便利。人们每天都要获取和处理大量的信息，如何从海量数据中 提取有价值的信息，已经成为信息技术领域的热门问题。然而，面对海量数据， 现在我们又面临着另外一个相反问题：由于计算机与网络带来的极大便利，如何 鉴别信息的相似性? 基于句子相似度的文本比对算法研究，就是在分析句子构成以及句子含义的 基础上，通过某种算法，将目标文本和标准文本进行相似度计算，以得出对文本 相似程度的判定，为将来进行文本比对和鉴定提供依据。 首先本文对现有常见的词语、句子以及文本相似度计算的关键问题进行了讨 论，分析了基于向量空间模型的t f i d f 方法、基于汉明距离的文本相似度计算方 法、隐性语义标引、基于属性论的文本相似度算法、基于语义理解的相似度计算 以及基于知网的相似度算法。 其次，本文对部分相似度算法做了一定程度上的改进，希望能获得更好的相 似度比较效果。文中也给出了关于句子相似度的文本比对算法的计算机实现过程， 并利用相关文本进行了测试，对所用的方法进行验证。 关键词：句子相似度，知网，文本比对，算法改进 、 ； 1 ， a b s t r a c t a bs t r a c t w i mm e i n c r e a s i n gp o p u l 撕够o fc o m p u t e r sa n dn 印) i r o r k s ，m o r et y p e so fr e s 0 1 l r c e s 、j l ，i t l lh i g h l ys h 撕n g 蠡溉l i t a t e 也ew o r ka n dl i f e l a r g e 锄o l i n t so fi n f 0 锄a t i o na r e o b t a i n e d 锄dp r o c e s s e db yp e 0 讲ee v e r y d a y ，h o wt 0e x 眦td a t a 自d mam 嬲so fv a l u a b l e 谢f 1 0 r m 撕o nh a sb e c o m eah o ti s s u e h o w e v m e r ei sa n o m e ro p p o s i t ep d 0 b l e mw i m m a u s s i v ed a ：t a ：h o wc 觚w ei d 锄缸匆m es i m i l a r i t i e s ? t h er e s e a r c ho ft e x tc o m p a r i s o na l g or i _ 岫b a s e do ns e n t e n c es i n l i l a r i t ) ，m e a s l l r e s t 1 1 et a 唱e tt e x ta n d 删a r dt e x ts i m i l a r i 锣w i ms o m ek i i l do fa l g o r i m mw h i c hb a s e do n 也ea i l a l y s i so fm es e n t e n c ef o m 趾ds t e n c em e a n i n g t h i sr e s u l tc a nb eu s e dt 0j u d g e m es i m i l a rl e 、，e 1 矗wm et e x tc o n l p 碰s o na n di d e i l t i j f i c 撕o ni 1 1t 1 1 e 缸t u r e f i r s t ，n l i sn l e s i sd i s c u s s e dt h ek e yi s s u e sa b o u tm ec o m m o nw o r d s ，s e n t e n c e sa i l d t e x ts i m a r i 锣c a l c u l 撕o n ，m e n 缸a l y z e dm et f i d fm e t h o db a s e do n 也ev e c t o rs p a c e m o d e l ，m et e x ts i l l l i l a r 埘c a l c u l a t i o nm e t l l o db a s e do nh a m m i l l gd i s t a n c e ，r e c e s s i v e s e m a n t i ci n d e x i n g ，m et e x ts i l i l 撕t ya l g o r i t h mb a s e do np r o p 哦y v i e w ，也es i l i l a r i 够 c a l c i d a t i o nb a s o do ns e m a n t i cu n d e r s t a n d i i l ga n d 也es i m n a r i t ya l g o 商血mb a s e do n h o 、) i ，_ n e t s e c o n d l y ，也i st l l e s i si l p r 0 v e ss 州e r a ls i m i l 撕够a l g o r i t h m s ，h o p i n gt 0g e tb e 位e r r e s u l t so f 也es i n l i l a r i 辑t h ep a p e ra l s o 垂v e s 吐l e 葩1 1 i e v e m e mo ft e x tc o m p a r i s o n a 1 9 0 r i 也mb a s e do ns e n t e n c es i m i l a r i t ) ro n 也ec o m p m 既a 咀t h e nv a l i d a t ei tw i ms o m e 1 e l e v a n tt e x t s k e y w o r d s ：s e n c e n t c es i n l i l a r i 坝h o w n e t t e x tc o m p a r i s o n ，h i l p r o v e da l g o r i l h m l；， 目录 目录 第一章绪论 1 1 研究背景。 1 2 研究现状 1 3研究意义。 1 4 本论文的选题和研究内容 1 5 论文组织结构 第二章相似度计算及关键问题 2 1 相似度的概念。 2 2 相似度计算。 2 3 文本相似度计算算法研究 2 3 1 基于向量空间模型的t f i d f 方法。 2 3 2 基于汉明距离的文本相似度计算方法 2 3 3 隐性语义标引 2 3 4 基于属性论的文本相似度计算方法 2 3 5 基于语义理解的相似度计算方法 2 4 小结 第三章基于知网的相似度计算 3 1 知网相关 3 1 1 知网概述 3 1 2 知网系统指导思想 3 1 3 知网知识词典 3 1 4 知网描述语言 3 2 基于知网的相似度计算 3 2 1 词语相似度计算。 i i i 目录 3 2 2 句子相似度计算3 3 3 2 3 段落相似度计算一3 4 3 3 中文分词技术3 5 3 3 1 基于词典( 词库) 的分词方法3 5 3 3 2 基于统计( 词频) 的分词方法3 6 3 3 3 基于a i 的分词方法3 7 3 4 小结3 8 第四章文本相似度计算算法分析研究3 9 4 1 基于字符串匹配的文本相似度计算算法设计3 9 4 2 针对基于向量空间模型的t f i d f 算法研究一4 2 4 3 基于语义的文本相似度计算算法4 3 4 3 1 词性的划分一4 4 4 3 2 词语相似度计算4 4 4 3 3 义原相似度计算。4 4 4 3 4 实词概念的相似度的计算4 5 4 4 小结4 7 第五章文本对比系统的设计与实现4 8 5 1 文本对比系统简介4 8 5 2 系统目标设计4 8 5 3 开发设计思想4 8 5 4 功能设计4 9 5 5 系统流程4 9 5 6 系统框架5 0 5 7 系统主要模块设计5 2 5 7 1 分词以及词性标注模块5 2 5 7 2 特征词抽取模块5 5 5 7 3 句子权重计算模块5 8 5 7 4 文本对比以及带标记文本生成模块5 8 目录 5 8 系统测试与实验结果5 9 5 9 小结一6 2 第六章总结与展望6 3 致谢6 5 参考文献6 6 攻硕期间取得的研究成果6 9 v 一 第一章绪论 第一章绪论 随着i n t e m e t 的大规模普及和企业信息化程度的提高，h l t e m e t 已经发展为当 今世界上最大的信息库和全球范围内传播信息最主要的渠道，各种资源呈爆炸式 增长，共享程度越来越高，给工作和生活带来极大的便利。人们每天都要获取和 处理大量的信息，而如何有效获取以及管理利用这些海量数据，已经成为信息技 术领域的热门问题。 在中国互联网络信息中心( a 蝌i c ) 2 0 0 7 年1 月最新公布的中国互联网络发展 状况统计报告中显示，7 0 2 的网络信息均以文本形式体现，如何从中获取特定内 容的信息和知识成为摆在人们面前的一道难题。近年来，文本挖掘、信息过滤和 信息检索等方面的研究出现了前所未有的高潮。 研究文本相似度比较，可以从技术层面上实现对现有文本的分析和对比，通 过合理的比对相似度反映文本与给定的文本的相关程度，这在自然语言处理的各 个领域都有着广泛的应用，也决定着这些领域的研究进展，可以实现资源的筛选 及现有的知识产权保护。 1 1 研究背景 互联网的高速发展和社会信息化时代的到来，使得计算机在日常生活中扮演 着非常重要的角色，高度信息共享己经成为现实，网上信息出现爆炸性增长，人 们使用计算机从事科研、学习、通信、娱乐、沟通联系等各种活动，越来越多的 人通过快捷廉价的互联网来获取信息，互联网已经成为人们获取信息的主要方式。 在这些海量的资源中，用户如何获取对自己有用的信息成为急需解决的问题。 人们也希望能用自己民族的语言像人与人沟通一样同计算机进行交流，在人与机 器之间建立起一种简单的关系，通过计算机来处理各类信息，满足自身需要。另 一方面，这些海量的电子数据在提供丰富的信息资源和便利的交流机会的同时， 也因为其获取的容易及简单操作功能，为一些学术不道德行为提供了便利。 在海量数据的选择当中，文本的分类、检索、过滤都需要根据用户需求来处 理，因此处理这些海量信息中的有用信息成为文字信息处理领域的重要课题，而 计算用户需求文本与处理文本之间的相似度成为其中的核心。自然语言是发展的 电子科技大学硕士学位论文 语言，它的结构要素以及含义会在主体相互交流和影响中发生变化。自然语言处 理就是为了进一步解决人类在获取信息、筛选信息的需要产生的一门学科，主要 用于对语言进行转换、传输、存贮、分析等加工雎】。在文字处理和中文研究领域， 它是一门交叉性学科，研究如何利用计算机来解决汉语语言问题的科学，它涉及 到语言学、数理基础、计算机技术等多种学科的相互联系和融合。 自然语言是人类用来获取信息的基本载体，是人类在社会不断发展中产生的 用来进行相互交际的声音及符号的总和，通过历史长期发展，不断约定俗成的产 物。目前现有的自然语言处理的理论和技术大多都是以英语为研究对象发展起来 的，因为英语是形合( m e r p l o t 枷c ) 语言，构造句子时要求词语形态按照规则进 行变化，注重句法平面【2 】。但汉语无论是发音、字形，还是构词方式、用词方式及 其语义等各个层面上都存在较大差异，这些显著的差别让西方目前相对成熟的理 论和技术不能直接用于中文信息处理。从这个方面来说，汉语目前还属于计算模 型比较不发达的语言，这对从事汉语处理相关工作的研究者来说有着巨大的挑战。 相比之下，英语文本处理的研究己经取得很好的成绩。 近年来，我国学术不端行为发生较多，因论文剽窃和抄袭引发的争论越来越 激烈，这种行为对原作者权益和国内学术发展环境都带来了严重的影响，同时也 限制了科技发展和创新能力提高。因此，在学风问题已成为大家关注的焦点时， 如何利用自然语言的处理技术来进行抄袭剽窃等行为认定也成为当前的热门方 向。 除此之外，自然语言处理技术己经广泛的应用于网络超容量文本数据的获取 和分析；网络信息的纯洁和安全处理；机器人语音对话；大型数据库自然语言接 口；专家系统自然语言接口；c a d 、c 灿和o a 的人机交互系统；计算机自动书 写，摘要提取，文档自动分类和文书管理系统；机器翻译和机助翻译；信息过滤、 主题识别、文本分类和文本挖掘；网上交叉语言和自然语言信息检索等多个方面。 人机自然语言接口问题，正受到世界各国的高度重视。 1 2 研究现状 文本相似度比较经常用于文本信息检索。传统意义上的文本信息检索基本上 以文本的信息库和检索用户两方面的数据处理为主，用户通过界面输入查询需求， 然后系统将需求与信息库中的数据通过多种方式输入进索引模块，索引模块再依 据信息库中的文档与查询需求的相似度进行排序，并直接反馈给查询用户。 2 第一章绪论 而在检索系统中，运用何种模型来实现查询需求，同时运用何种算法来计算 文档的相似度是最关键的问题。2 0 世纪6 0 年代中期以来，大量的文本相似度比较 的模型研究出现，从最初的简单的结构化的特殊模型，发展到现在具有较强理论 基础和能处理多种文档格式的模型。从总的情况来看，目前使用比较广泛的模型 有一下三种： 1 、布尔模型( b 0 0 l e a nm o d e l ) ：布尔模型是基于集合论和布尔代数的一种简单 检索模型。由于集合的定义是非常直观的，b 0 0 l e a n 模型提供了一个信息检索系统 用户容易掌握的框架，实现简单，计算复杂度低，支持结构化查询，但它的检索 策略是基于二元判定标准( b i n a r yd e c i s i o nc r i t 舐0 n ) 缺乏文档分级( r 锄k ) 的概念， 限制了检索功能。其查询串通常以语义精确的布尔表达式的方式输入，但常常很 难将用户的信息需求转换为布尔表达式，b o o l e a n 模型定义索引术语只有两种状 态，出现或者不出现在某一篇文档中，这样就导致了索引术语的权重都表现为二 元性。 b 0 0 1 e a n 模型的主要优点在于具有清楚和简单的形式，而主要缺陷在于完全匹 配会导致太多或者太少的结果文档被返回。众所周知，索引术语的权重从根本上 提高了检索系统的功能，从而导致了向量( v e c t o r ) 模型的产生。因此在初期信息 检索系统和文档数据库系统中的应用中较为广泛。例如现在的图书馆信息检索系 统。 2 、统计模型( s t a t i s t i c a lm o d e l ) ：有些过程无法用理论分析方法导出其模型，但 可通过试验或直接由工业过程测定数据，经过数理统计法求得各变量之间的函数 关系，称为统计模型。在文本相似度计算中，统计模型通常是基于文本统计信息 ( 如词语频度统计等) 和统计自然语言处理方法来进行计算。统计模型从布尔模 型的“精确匹配”发展到“最优匹配 ，其中又包括向量空间模型( 、，e c t o rs p a c em o d e l ) 和概率模型( p 玎0 b a b i l i s t i cm o d e l ) 两类。 向量空间模型( 或词组向量模型) 是一个应用于信息过滤，信息撷取，索引以 及评估相关性的代数模型。s m a r t 是首个使用这个模型的信息检索系统。文件( 语 料) 被视为索引词( 关键词) 形成的多次元向量空间，索引词的集合通常为文件中至 少出现过一次的词组。 搜寻时，输入的检索词也被转换成类似于文件的向量，这个模型假设，文件 和搜寻词的相关程度，可以经由比较每个文件( 向量) 和检索词( 向量) 的夹角偏差程 3 电子科技大学硕士学位论文 度而得知。计算夹角向量之间的余弦比直接计算夹角容易：余弦为零表示检索词 向量垂直于文件向量，即没有符合，也就是说该文件不含此检索词。 概率模型基于以下理论：给定一个用户的查询串和集合中的文档概率模型来 估计用户查询串与文档相关的概率。概率模型假设这种概率只决定于查询串和文 档。统计模型是当前应用最广泛的检索模型，在从小规模纯文本信息检索系统到 搜索引擎在内的各种检索系统中广泛应用。 概率模型的优点在于，文档可以按照他们相关概率递减的顺序来计算秩 ( 捌【l k ) 。他的缺点在于：开始时需要猜想把文档分为相关和不相关的两个集合， 实际上这种模型没有考虑索引术语在文档中的频率( 因为所有的权重都是二元 的) ，而索引术语都是相互独立的。 3 、语言与知识模型( l i n g u i s t i ca i l dk n o w l e d g e - b a s e dm o d e l ) 。与其他的模型不 同的是，基于语言和知识的检索模型试图了解查询用户的真正需求，准确理解用 户意图，以获得更好的检索效果。目前较常用的做法是通过考察用户查询和相关 文档之间的语言模型的相似程度，来进行文档相关度的计算。语言和知识模型在 本世纪初以来得到了较为广泛的应用，目前信息检索研究领域应用较为广泛的 l 锄u r 1 1 1 越系统，就是基于此模型进行内容相似度计算的。 以上都是目前最常用的相似度计算模型，而直到今天，信息检索系统的架构 设基本上也没有太大的变化，即使目前在处理海量规模网络文本数据的问题上也 能够满足需要。当前信息检索研究的重点，一方面在于利用自然语言处理方面的 研究成果对检索相似度模型框架进行修正；另一方面则在于对检索系统的应用对 象加以拓展，针对专门检索系统如网络信息检索系统、多媒体检索系统等开展研 究和分析。 针对文本相似度的比对，目前国内外对各类相似度算法已经有了相当的研究， 进行文本比对目前最基础的就是对句子和词语相似度的计算，现阶段的计算方法 基本上可以分为三大类： ( 1 ) 基于词语特征的相似度算法； ( 2 ) 基于词语意义的相似度算法； ( 3 ) 基于句子语法的相似度算法。 但由于没有统一的标准，在不同领域具有不同的量度，所以目前世界上仍然 缺乏公认的优秀相似度算法。 在现有的三大类基本计算方法中，对词语的分析大部分采用基于向量空间模 型的计算方法，对语义的分析大部分都是对句子进行深层的句法分析，找出语义 4 第一章绪论 之间的关系，再来分析相似度。但这两种单纯的方式都存在或多或少的不足，原 因就在于句子结构和语义的复杂性，以及句子之间的关联性。尤其是在中文领域， 由于中文词汇的复杂和词意语境不同造成的意思变化较大，使得在中文文本比对 上，存在更多的困难。 传统的文本处理中相似度的计算，是根据欧式空间中向量之间夹角的余弦值 来表征的，它根据余弦值的大小来反应文本之间的相互关系。例如中科院计算所 在文本自动分类中，复旦大学在t r e c 过滤中，都采用了这种方法。北京邮电大 学则首先建立文本集与码字集之间的一一对应关系，然后借用编码理论中汉明距 离的计算公式，计算文本相似度，中科院计算所以属性论为理论依据，建立了文 本属性重心剖分模型，并在属性坐标系中表示文本向量，计算向量之间的匹配距 离，从而得到文本的相似度。 目前国内外对词语相似度计算的研究基本上分为两类：一是基于按照概念间 结构层次关系组织的语义词典方法，用词语间概念的关系来计算相似度；二是基 于词语统计的概率分布作为相似度的参考，利用大规模的语料库来进行比较，但 计算量大，方法复杂，有时候受到数据稀疏和数据噪声干扰较大，出现明显的错 误。前者是一种基于语言学和人工智能的理性主义方法，利用语义词典，依据概 念之间的关系，通过计算概念在体系中的距离来得到词语间的相似度。后者是把 相似度的研究建立在可观察的事实上，需要两个词语语义相似当且仅当上下文环 境也相似的这一假设。 句子的相似度的计算，是在基于关键词的相似度比较基础上，也就是对词语 相关的概念之间的相似度比较。一般都采用对关键词的空间向量夹角余弦值来作 为句子相似度，或者利用句子中关键词语义，关于语义距离和语义依存的信息来 进行相似度计算。前者是把句子看成词的线性序列，不对语句进行语法结构分析， 只是利用句子的表层信息，即词频和词性等信息；后者是一中深层结构分析，是 对被比较的两个句子进行深层的句法分析，找出语义之间的关系，然后再进行相 似度的计算。 目前国内已经有大学开发出了依存句法分析器，能够获得句子各成分之间的 依存关系。这几种方法反映了句子的几个重要的特征，但每个方法都存在一定的 局限性，在不同的应用领域需要进行不同的选择，以便较为全面地衡量句子的相 似度。在赵巾帼等的汉语句子相似度计算方法对比之研究【3 】一文中提到，计算 句子之间的相似度，等价于计算句子之间关键词的相似度，比较两个词的相似度， 往往是比较词相关的概念之间的相似度。 电子科技大学硕士学位论文 尽管国内外在相似度计算方面进行了多年的研究，在英语的相似度研究方面， 国外已经取得了部分成果，英文是基于句法的语言，但中文基于语义的语言，在 中文领域中，中文词汇的复杂和词意语境不同造成的意思变化复杂，使得在中文 文本比对上；存在更多的困难。由于词汇数目的庞大，句子结构的变化以及语义 的丰富含义，再加上相似度的概念主观性较强，目前为止还没有很高效的方法， 因此寻求一种简单高效的对比算法，提高对文本相似度的识别，是今后研究的一 个重点。这需要总结现有的相似度计算的研究成果，分析其优缺点，不断改进有 效算法或提出新的计算模型，才能促进这方面工作的研究。 在未来的几年力，随着数学模型和理论的发展，以及计算机技术的进步，在 相似度算法方面应该会有进一步的发展，尤其是结合新理论和技术的新算法，以 及对原有经典算法的改进将会提高对相似度比较的效率。 1 3 研究意义 目前对英语为主的相似度计算研究比较深入，因为英语相对较为简单，尤其 是对于汉语使用来说。汉语作为世界上产生时间最长使用最复杂的古老语言之一， 是典型的意合型语言，在使用过程中没有固定语序，变化灵活，缺省指代和相似 相近词较多。目前对于词法分析、句法分析以及语义分析，已经有了大量相关研 究，也取得了丰硕的成果。而相似度计算在自然语言处理中有着广泛的应用，是 一项非常重要的基础工作，例如，在基于实例的机器翻译、信息检索( 自动问答) 、 自然语言接口以及自动文摘等领域，相似度计算都是一个关键技术问题，函待解 决。 1 4 本论文的选题和研究内容 本文将要论述的文本相似度研究，就是通过某种算法，将目标文本和标准文 本进行相似度计算，以得出对文本相似程度的判定，为将来进行文本比对和鉴定 提供依据。 研究文本相似度比较，可以从技术层面上实现对现有文本的分析和对比，通过 合理的比对相似度反映文本与给定的文本的相关程度，这在自然语言处理的各个 领域都有着广泛的应用，也决定着这些领域的研究进展，同时相应的技术也可以 用于现有的知识产权保护。 6 第一章绪论 在本文中，主要针对已有的文本相似度计算算法如基于向量空间模型的 t f - d f 算法、基于汉明距离的文本相似度算法、隐性语义标引、基于属性论的文 本相似度计算、基于语义理解的相似计算以及基于知网的中文分词技术和相似度 计算进行了分析，对基于字符串匹配的相似度计算，基于向量空间的t f i d f 算法 和基于知网的相似度计算进行了进一步的分析探讨，针对其中的不完美之处，提 出了一定的改进。对于基于向量的t f m f 方法，本文增加了位置向量，从而使得 对比更加具有语义意义。对于基于知网和语义的文本相似度计算，本文主要从词 语的角度出发，对文本进行切分，为最终系统分析的实现提供理论支持。 本文通过分析现有常见的分词技术和句子相似度算法，就文本相似度研究的相 关技术做了说明，同时也对现有的相似度研究的不足和发展趋势进行了说明，同 时也对某些算法进行了改进。对实践也有一定的指导作用。 1 5 论文组织结构 本文研究了在文本相似度计算中各类相似度计算的主要方法和关键技术，重 点讨论了如何基于句子相似度来进行中文文本内容比较，研究了现有常用中文文 本句子相似度算法的原理和计算方法，同时利用知网相关技术和现有分词技术， 改进了几种文本相似度计算策略，给出了相应系统的设计和实现，提高了相似度 比较计算的精确度和可信度。全文共分六章。 第一章是绪论。分析了课题研究的背景，内容和意义，确定了课题研究的目 标；介绍论文的组织架构。 第二章是相似度计算及关键问题。首先介绍句子及文本相似度的概念，其次 讨论了相似度计算模型以及相似度计算的关键技术和问题，介绍了常用的文本相 似度计算方法，分别研究了基于大规模语料统计和以及基于某种知识体系的语义 词典的计算方法。 第三章是基于知网语义的相似度计算。首先阐述知网理论，包括知网的概念、 产生背景和目的，知网的指导思想以及知网的知识辞典和描述语言。其次，对基 于知网的相关语义相似度算法进行了分析和研究。同时分析了知网中涉及的中文 分词技术。 第四章是文本相似度计算算法分析研究。在这一章中，根据前面章节对相似 度算法的分析，针对基于字符串匹配的相似度算法，基于向量空间模型的t f i d f 方法相似度算法，以及基于知网和语义的相似度算法进行了改进。 电子科技大学硕士学位论文 第五章是文本对比系统的设计与实现。通过结合实际应用，介绍了文本相似 度算法实现的系统和主要模块设计，同时通过实验对理论进行验证。 第六章是总结与展望。本章中进一步回顾和总结了，对各部分明确了主要工 作内容，以及今后要发展和研究的方向。 第二章相似度计算及关键问题 第二章相似度计算及关键问题 2 1 相似度的概念 相似度是一个比较复杂的概念，在语义学、哲学和信息理论中被广泛的讨论。 因涉及到语言构成、语句意义和其他一些因素，目前对相似度还没有一个标准和 通用的定义。词语作为构成汉语语言体系的基本单位，计算其相似度往往也是计 算句子相似度的基础，而句子相似度计算则是成为文本相似度计算的基础。词语 相似度的主观性较强，词语间的关系很复杂，无法用明确的客观标准来衡量，也 就很难用单纯的数据来度量其差别。 脱离具体的应用背景谈论词语或者句子的相似度，很难得到一个统一的定义， 明确的词语相似度含义只有在具体的应用中才能体现。例如，在自动问答系统中， 文本相似度更多地反映文本中旬子间语义上的匹配程度。 定义2 1 ：句子相似度指两个待比较的句子在语义上的匹配符合程度，值为 【0 ，1 之间的实数，值越大表明两个句子越相似。当取值为l 时，表明两个句子在 语义上完全相同；值越小则表明两个句子相似度越低，当取值为o 时，表明两个 句子在语义上完全不同【4 】。 文本相似度是指两个本文内容中旬子的用词和语义上的匹配符合程度，是一 个介于o 和1 之间的实数，理论上数值越大表示两个本文的内容越相似。相似度 的计算在信息检索以及文档复制检测等领域具有广泛的应用前景。在文本相似度 度量过程中，词语相似度的度量是最基础的度量。词语相似度可以通过转换为词 语距离讨论，它们通过一种简单的对应关系同时反映相同关系特征。对于两个词 语和，记其相似度为m ( ，呒) ，其词语距离为d 西( 彬，吸) ，那么我们可以 定义一个满足以上条件的简单转换关系： 跏( ，暖) 2 丽蒜 ( 2 - 1 ) 其中口是一个可调节的参数。我们把a 含义为当词语相似度为o 5 时的词语之 间的距离值。但这只是其中的某一种可能，不能唯一代表这种转换关系。在很多 情况下，直接计算词语的相似度比较困难，通常可以采取先计算词语之间的距离， 然后再转换成相似度的方法【5 】。 9 l 电子科技大学硕士学位论文 词语之前相互关联的程度是通过在相同语境中词语共同出现的可能性衡量， 它反映了词语之间的相关性。例如，我喜欢喝可乐和可乐是我爱喝的这两个句子 之间就是语义相似，但我喜欢喝可乐和我爱喝饮料则是语义相关。这是两个不同 的概念，没有直接的对应关系。 目前存在两种类型的句子相似度计算方法，基本上是按照对目标语句进行分 析的程度来进行计算： 1 、基于向量空间模型的计算。此类计算只考虑句子中词语存在的形式，不对 词语间的关系和语义进行分析，在对相似度进行衡量时只利用了句子中所有词的 词频、词性等表层信息。不通过任何的句子结构分析，因此此类方法在计算相似 度时不能考虑句子的整体结构相似性。 2 、基于完全语义分析的计算。该方法属于深层结构分析法，通过对语句进行 完全的语法和语义分析，找出被比较句子之间的依存关系，在此基础上进行相似 度的计算。 2 2 相似度计算 由于涉及到语言、语义、句子结构以及其他的因素，相似度被认为是比较复 杂的概念，没有通用统一的标准定义，被广泛运用于语言处理、哲学以及信息学 中。d e k 孤gl i n 和p a t r i c kp a n t e l ( 2 0 0 1 ) 曾从信息论的角度给出了一个统一的、与应 用领域无关的相似度的非形式化定义。他们认为，两个概念a 和b 之间的相似度 取决于他们之间的共性和差异性。当a 和b 关联越大，共性越多，相似度就越高； 关联越小，差别越大，相似度就越低。如果a 和b 完全相同的时候，相似度达到 最大【6 1 。 但在实际生活中，两个概念的相关性和相似性是联系紧密但有区别且容易混 淆的。词语的相关性是对两个词语共同出现的频率的描述，一般通过统计大规模 文本库中词语的共现频率的方法来得到。刘群等人分析了词语相似性中语义的相 关性的作用，提出了概念之间的相似性和相关性分别跟概念的聚合和组合特点相 关，这两者联系紧密，如果两个概念相似性很高，那么他们的相关性也一定较高， 但反之则不一定r 7 1 。例如“鼠标 和“键盘”两个概念，两者相关性很高，但相似 性却很低。所以相似是因为有着相类似的特征，而相关这是因为某种自然规律的 联系起来，前者可以根据不同的特征产生不同的聚合，往往随人的主观因素变化 而变化；后者往往比较固定，并不因为人的主观变化而变化，只会受到认知主体 1 0 第二章相似度计算及关键问题 的认知水平影响。 中文语言主观性较强，语义复杂，文本相似度计算中包含词语之间、词句之 间、词段之间、句段之间和段落之间等关系。如果脱离具体的应用背景来讨论相 似度，很难得到统一的定义，因此要根据实际的需要来确定最准确最合适的定义。 相似度的含义在实际不同的具体应用中也有所不同。例如，在信息检索中，相似 度一般是指用户查询与目标文本能够匹配的程度，如果文本与用户查询的要求越 相近则相似度越大，反之越小；在基于实例的机器翻译或者文本研究中，相似度 的定义主要以文本中词语可替换程度来衡量，词语替换后句义变化越小则表示所 替换词语的相似度越大，反之越小；在自动问答领域中，相似度反映的是用户问 句和领域文档在句子之间语义上的匹配程度；而在多文档文摘系统中，相似度可 以反映出局部主题信息的拟合程度。 虽然目前还没有公认的相似度的准确定义，但在实践中也形成了一些划分方 法。比如： ( 1 ) 规模划分( 级别划分) ：相似度在相似算法中有不同级别，一般按照规 模可以划分为局部相似度和整体相似度。词语和句子级别的相似度基本上是以局 部相似度为基础的，即以义原为基础出发，层层叠加。由义原的相似度可以得到 词语的相似度，由词语的相似度可以得到句子的相似度。针对本文的研究基本上 是考虑整体相似度，也就是句子级以上的相似度，可以由句子相似度来判断段落 与段落，文本之间的总体相似度。 ( 2 ) 知识程度划分：在相似度的定义和评估中知识含量的多少能决定相似度 的大体划分，一般可分为表层的基于句法的相似度和深层的语义相似度。前者属 于属于知识贫乏型相似度，主要根据句子最简单的句法和表层词法等属性来计算 相似度。而后者属于知识密集型相似度，利用大量的知识库例如语义词典等来对 句子进行较深层的语义分析，进而计算出语义相似度。 2 3 文本相似度计算算法研究 在文本相似度计算算法中，目前已经有较多比较常用的算法，下面将分别介绍 一些相对运用广泛且具有一定代表性的文本相似度算法，并分析其相关的算法性 能并比较优缺点。 电子科技大学硕士学位论文 2 3 1 基于向量空间模型的t f ld f 方法 向量空间模型( v s m ：v b c t o rs p a c em o d e l ) 是近年来广泛运用于相似度计算且效 果较为突出的一种信息检索模型。在v s m 中，文本是由相互独立的词条组 ( 互，互，z ) 构成，每一词条z 赋以权值形，其中彬表示该词条在文本中的重要程 度，同时( 五，互，z ) 被当做在玎维坐标系中的坐标轴，形为对应坐标值。 这样由( 互，互，正) 分解而得的正交词条矢量组和对应的权值就组成能反映文本信 息的向量空间，其中的每一个点都是对应的文本映射到空间中的体现。我们用矢 量( 石，形互，。，瓦，蜕) 用来表示所有文本和用户查询信息，其中用户查询为q ， 被检索文档d ，用向量之间的夹角来度量信息匹配的相似程度，夹角越大相似度 越低。这就将相关问题转化为向量空间中的矢量匹配问题。 向量空间模型的常用方法有t f i d f ( t e m lf r e q u e n c y i n v e n e dd o 嘲e n t f r e q u e n c y ) 嘲，是在相似度计算中应用较为广泛的方法之一，该方法综合考虑了词 语在所有文本中的出现频度( t f 值) 和这个词对不同文本的分辨能力( i d f 值) 。假设 形，呢是所有文本中的词语，n 维向量r = ( 互，互，疋) 则用来表示每一个句 子。设n 为特定词语彬在目标文本中出现的次数，m 为其它所有出现或者包含彬的 文本个数，m 为文本总数，互( 1 f ，z ) ，那么霉= 珂l o g ( m m ) 。在这个计算式中， 词语出现次数越多，n 值将越大，但这并不代表这个词语就一定具有较高的丁值。 例如，“的 字在所有汉语语言使用当中出现频率非常高，因此这个词将具有较大 的t f 值( n 值) ，但因为它对理解分辨不同文本的作用不大，反而使得它的仞f 值 ( 1 0 9 ( m m ) ) 很小。用这种方法来计算相似度，综合考虑了词语使用频度和词语分 辨度。 同样【9 】，目标文本中n 维向量z = ( 互。，乏，乏) 的计算也可以利用上述方法。 在分别得到丁和丁后，再计算两个向量之间的夹角余弦，进而得到其对应的两个 文本之间相似度。 常用的相似度计算方案有内积、d i 系数、j a c c a r d 系数和余弦系数等。 设文本丁= 旺，正，乙) ，丁= ( 乐，) ，则丁与z 。之间的相似度用上述方 法分别表示如下： ( 1 ) 内积 l 聊( 丁，丁。) = 互木互。( 2 2 ) f = l ( 2 ) d i c e 系数 1 2 第二章相似度计算及关键问题 ( 3 ) j a c c a r d 系数 ( 4 ) 余弦系数 2 互木z & m ( 丁，丁) = 了上l i 一 互2 + z 2j _ o l ji_ f = lf = 1 溉口，r ) = z 中互 ji：!：】1一 互2 + 互”一互拳l 跏( 丁，r ) = n z 木z f = l ( 2 - 3 ) ( 2 4 ) ( 2 5 ) 虽然基于向量空间模型的t f i d f 比较经典，使用较为广泛，但也存在一些不 足。因为它是基于统计的一种方法，只有当目标文本所包含的单位足够多，相关 的要素重复出现时才有较高的真实度和效果。同时，t f i d f 方法并没有考虑词语 本身具有的相关因素( 如意义、情感、结构等) ，只是考虑了词语出现的统计特性， 存在一定的局限性，这也形成了利用向量余弦来计算相似度没有严格的理论依据 的说法。 2 3 2 基于汉明距离的文本相似度计算方法 基于汉明距离的文本相似度计算方法f l f j l 主要是借助编码理论中汉明距离的概 念，通过求文本与查询式之间的汉明距离，来计算文本的相似度。与其它相似度 计算方法相比较，它具有运算简便等优点。 ( 1 ) 关于汉明距离 在信息论中，汉明距离是一个基本的概念，它是描述两个n 长码字 工= ( 五屯魂矗) 与y = ( 咒耽败只) 之间的距离，计算公式为： d ( 工，y ) = 吒。败 ( 2 6 ) 七= l 其中，o 表示模2 加运算，以 o ，1 ) ，y 。 o ，1 ) 。 d ( x ，y ) 反映了码字之间的不同，表示相比较的两个码字在同样位置上出现不 1 3 电子科技大学硕士学位论文 同符号的次数，为下一步进行码字之间的相似度比较提供支持。 在进行文本比较时，首先根据文本中的关键词、文摘等信息，构建一个有刀位 序列的码字，这些码字就反映了文本的相关信息，与文本之间建立1 1 对应关系。 同样码字也可以用来表示查询式。如文本w 可表示为 w = ( 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 ) ，查询式c = ( 1 1 0 0 1 0 1 0 1 0 l o o o l 1 1 1 1 0 ) 。在这个两 个码字当中，0 表示文本在对应的分量位置上为没有相关信息的状态，1 表示文本 对应分量上存在相关的信息。通过这种方法，可以将原来的文本集合与相关的码 字进行1 1 对应，这样就可以把需要讨论的文本之间的相似关系通过码字之间的汉 明距离来表征。具体地，设m 和m ，分别为文本w 对应码字和查询式对应码字， 可用上面的公式( 2 6 ) 计算膨。和慨的汉明距离，这能较好反映出对应的相关关系。 对于d ( m ，m ，) 来说，这是介于o 与拧之间的数字，表示了它们之间的距离。当文 本与查询式的码字完全不同，则距离和码字位数一样为玎，当他们拥有完全相同的 码字时，则距离为o ，d ( m m ，) 定量地描述了文本之间的差异程度。 ( 2 ) 相似度计算方法 首先需要确定文本集对应的码字集，对于不同的对象之间，设 m = ( 五而) ，m 2 = ( m 咒耽以) ，则m 。和鸠之间的相似度计算公式 为： o 以 跏( m l 鸩) = 1 一丝一 ( 2 7 ) ，2 其中晚、虼分别表示文本对应的码字蝎和查询式w 2 对应的码字鸠中第尼 位的分量，要么为l 要么为o ，o 就是对于计算机来说运算速度极快的模2 加运算。 用公式( 2 7 ) 计算出来的结果在o 1 之间，这是比较合理的，它反映了文本之 间的差异，也与利用求向量夹角余弦的方法类似。当两个文本完全相似时， 跏( m ，m ，) 的值为1 ，完全不相似则为o 。比如，设有码长均为1 0 位的文本w ， 心，其对应的码字分别为m