线性代数式检索结果相似度排序研究

1、HEBEI UNIVERSITY密 级 分类号 学校代码 学 号1007520151332硕士学位论文线性代数式检索结果相似度排序研究学位申请人：孙梦颖指导教师：田学东教授学位类型：工学硕士学科专业：计算机科学与技术授予单位：河北大学答辩日期：二o八年五月CODE: 10075Classified Index:U.D.C:NO: 20151332A Dissertation for the Degree of M. EngineeringStudy on Similarity Ranking of TheRetrieval Results of Linear AlgebraicExpressi

2、onsCandidate:Supervisor:Academic Degree Applied for:Specialty:University:Date of Oral Examination:Sun MengyingProf. Tian XuedongMaster of EngineeringComputer Science and TechnologyHebei UniversityMay, 2018河北大学学位论文独创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人己经发表或撰写

3、的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢。作者签名：一_日期：2盅年Y月X日学位论文使用授权声明本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。本学位论文属于1、保密口 在年月日解密后适用本授权声明。2、不保密y（请在以上相应方格内打“。”）作者签名：日期：圳年y月讯日导师签名：阔步饥日期：年厂月日保护知识产权

4、声明本人为申请河北大学学位所提交的题目为（的学位论文，是我个人在导师（回折;）指导并与导师合作下取得的研究成果， 研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费 资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定 的各项法律、行政法规以及河北大学的相关规定。本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大 学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内 容。如果违反本声明，本人愿意承担相应法律责任。声明人： 孙皆奴日期：加* 年了月 以日摘要线性代数是现代数学的重要组成部分，它被广泛地应用于自然科学和社会科学中

5、。 随着线性代数研究的不断深入，以线性代数式为线索的数学公式检索需求量不断增加, 现有的检索技术和搜索引擎理论与方法面临挑战。较普通数学公式而言，线性代数式的结构更为复杂，语法、语义更加丰富，实现其 检索并将结果合理排序更加困难。针对此问题，本文对线性代数式检索模型中的检索结 果排序问题展开研究。首先，通过对线性代数式特点的分析，在定义线性代数式查询模式的基础上，归纳 总结了线性代数式的结构、符号、语法、语义等方面特征。其次，利用犹豫模糊集相关知识，从整体和局部两个角度出发，定义线性代数式的 犹豫模糊相似度评价属性及其相应的隶属度函数，建立线性代数式的相似度函数。最后，将线性代数式之间的相似度

6、计算转变成对应犹豫模糊集间的相似度计算，实 现基于相似度的线性代数式检索结果的排序。通过对6352条公式的实验，证明了该方法能够实现线性代数式检索系统结果数据 的有序输出。关键词线性代数式检索匹配模式犹豫模糊集相似度函数排序AbstractAbstractLinear algebra is an important part of modern mathematics. It is widely used in natural science and social science. With the deepening of linear algebra research, the mathe

7、matical formulas retrieve requirements for linear algebraic formulas is increasing, the existing retrieval technology and search engine theory and methods are facing challenges.Compared with the general mathematical fbnnulas, the linear algebra formulas have more complex structures and richer syntax

8、 and semantics, so it is more difficult to retrieve them and sort the results in a reasonable order. And aiming at this problem, we study the ranking of retrieval results in linear algebra formulas retrieval model.Firstly, on the basis of defining linear algebraic query mode, the characteristics of

9、linear algebraic structure, symbol, grammar and semantics are summarized by analyzing the characteristics of linear algebraic methodsSecondly, the fuzzy similarity evaluation attributes and their corresponding membership functions and the similarity functions of linear algebra formulas were defined

10、from global and local aspects by using the knowledge of hesitant fiizzy set.Finally, the similarity computation between linear algebraic equations is converted into similarity computation between corresponding hesitant fiizzy sets, and the ranking of linear algebraic retrieval results based on simil

11、arity is achieved.Through the experiment of the 6352 formulas, it is proved that the method can realize the ordered output of the retrieval results of linear algebra formula retrieval system.Keywords Linear algebraic formulas Retrieval Matching modes Hesitant fuzzy sets Similarity function Sorting目录

12、 TOC o 1-5 h z 第1章引言1研究背景及意义1国内外研究现状11.2.1数学表达式检索结果排序研究现状1 HYPERLINK l bookmark43 o Current Document 1.2.2犹豫模糊集及其应用研究现状4 HYPERLINK l bookmark46 o Current Document 研究内容及主要工作6 HYPERLINK l bookmark52 o Current Document 本文的组织结构6 HYPERLINK l bookmark64 o Current Document 第2章线性代数式解析及特征提取9 HYPERLINK l book

13、mark67 o Current Document 线性代数式检索模式9 HYPERLINK l bookmark73 o Current Document 2.2线性代数式解析13 HYPERLINK l bookmark76 o Current Document 2.3线性代数式相似特征提取14 HYPERLINK l bookmark84 o Current Document 本章小结17 HYPERLINK l bookmark87 o Current Document 第3章线性代数式检索结果相似度排序19 HYPERLINK l bookmark90 o Current Docum

14、ent 3.1犹豫模糊集相关技术19 HYPERLINK l bookmark99 o Current Document 3.2基于犹豫模糊集的线性代数式相似度评价原理20 HYPERLINK l bookmark102 o Current Document 3.3基于犹豫模糊集的线性代数式相似度评价流程22 HYPERLINK l bookmark105 o Current Document 3.4线性代数式相似度评价23 HYPERLINK l bookmark111 o Current Document 3.4.1线性代数式相似度评价局部属性24 HYPERLINK l bookmark

15、132 o Current Document 3.4.2线性代数式相似度评价整体属性313.4.3线性代数式犹豫模糊隶属度函数定义33 HYPERLINK l bookmark142 o Current Document 3.4.4隶属度函数参数设置说明38 HYPERLINK l bookmark145 o Current Document 3.5基于犹豫模糊集的线性代数式相似度计算39 HYPERLINK l bookmark148 o Current Document 3.6线性代数式检索结果相似度排序算法41 HYPERLINK l bookmark160 o Current Docu

16、ment 3.7本章小结42 HYPERLINK l bookmark163 o Current Document 第4章实验结果与分析43 HYPERLINK l bookmark166 o Current Document 4.1线性代数式数据集构建43ill TOC o 1-5 h z HYPERLINK l bookmark169 o Current Document 4.2线性代数式检索相似度排序结果与分析44 HYPERLINK l bookmark172 o Current Document 4.2.1线性代数式检索结果相似度计算实例44 HYPERLINK l bookmark

17、175 o Current Document 4.2.2线性代数式检索结果排序算法对比46 HYPERLINK l bookmark178 o Current Document 4.3本章小结49第5章总结与展望51工作总结51 HYPERLINK l bookmark188 o Current Document 后续工作展望51 HYPERLINK l bookmark194 o Current Document 参考文献53 HYPERLINK l bookmark242 o Current Document 致谢57 HYPERLINK l bookmark245 o Current D

18、ocument 攻读学位期间取得的科研成果58第1章引言1.1研究背景及意义随着科学技术的发展，科技信息的载体与交流方式日益丰富，人们不再仅仅依靠纸 质书籍来获取所需要的信息，而是更多地通过网络和搜索引擎来查询数字化资料，这极 大地方便了人们的工作、学习与生活，当然，也不可避免地存在诸多问题，如：查询结 果多而杂乱，甚至有许多与查询内容不相关的结果。因此，如何将无关结果剔除，返回 给用户真正需要的信息，成为亟待解决的问题。目前的搜索引擎主要针对的是文本，二维分布的数学公式与文本在结构上存在本质 差别，而与普通数学公式相比，线性代数式的结构更加复杂，语法、语义更为丰富，所 以很难通过现有的搜索引

19、擎来查找线性代数式相关内容。针对数学理论及其应用的研究 日新月异，人们希望借助搜索引擎输入数学公式来快速查找到相关内容的要求日益迫切, 因此，许多国内外专家学者对数学公式检索理论和技术进行了研究，并提出多种数学公 式的检索模型。当大量的检索结果呈现在人们眼前时，人们希望将与查找内容完全一致或者更相近 的结果排列到前面，这样可以避免从杂乱无章的结果中挑选有用内容的过程，缩短查询 时间，数学公式检索的情况也是如此。目前，虽然部分数学公式检索方法针对数学检索 结果的排序问题，设计了相似度排序算法，但还是存在许多有待解决的问题，尤其是对 成分、结构更为复杂的线性代数式而言，还需要有针对性的研究与开发。

20、本文利用犹豫模糊集相关知识，提出了一种线性代数式检索结果的相似度排序方法。 从整体和局部两个层面对线性代数式进行考察，提取其特征值，并构造隶属度函数用于 将抽象特征数字化，再根据犹豫模糊集的距离公式，完成线性代数式之间相似度计算， 实现基于相似度的检索结果排序。本论文选题来源于国家自然科学基金项目（项目批准号：61375075）和河北省高等 学校科学技术研究重点项目（项目批准号:ZD2017208； ZD2017209）的部分研究内容。1.2国内外研究现状1.2.1数学表达式检索结果排序研究现状目前，对线性代数式检索的研究还不够成熟，缺乏一些针对性的检索系统的设计， 而普通数学公式检索系统的开

21、发日益增多，为线性代数式检索系统的研究打下了良好的 基础。现有的搜索系统按照实现方法可分为两大类。其一是改进文本检索以适应数学公 式搜索的系统，包括：EgoMath、DLMF Search。】、MathDex、LeActiveMath7_9等。 其二是为数学公式专门建立的检索系统，包括：Wikimirs1011 MathWebSearch12-14o检索结果排序是否合理是评价检索系统优劣的重要指标，而随着网络数学资源日益 丰富，用户进行检索时往往会返回大量的检索结果，正确的排名结果能够有效地减少错 误证明的尝试和回溯数，缩短查询时间提升工作效率。目前，对线性代数式检索结果 的相似度排序研究还处

22、于起步阶段，而一些学者针对普通数学公式的检索结果排序提出 了相关算法。Schellenberg16将数学表达式用五元组(s,n,r, p,b)表示，其中s表示表达式的当前 字符、n表示当前字符的相邻字符、r表示当前字符和相邻字符的位置关系、p表示当 前字符所处层次、b表示表达式中子表达式的层次变化。利用距离公式计算表示待查询 表达式和结果表达式的五元组的距离，得出它们的相似度，完成排序。Kamali和Tompa提出了一种面向Presentation MathML格式的数学表达式的结构 相似度的检索方法，首先把各种形式的数学表达式归一化成该格式，之后利用“树编辑 距离”来计算待查询表达式与结果表

23、达式之间的相似度，实现对检索结果表达式的相似 度排序。Zhang和Youssef】针对MathML格式的数学表达式设计了一种检索结果相似度排 序方法，该方法利用MathML解析树表示数学表达式，建立其索引结构，并定义五个评 价特征：“数据类型层级”、“查询覆盖度”、“公式/表达式”、“匹配深度”、“函数分类距 离”，再根据这些特征值递归进行待查询表达式和结果表达式的相似距离计算，得出它 们之间的相似度，并依据该相似度进行检索结果的相关排序。Nguye等人NO设计并实现了数学公式检索系统MASE和Lattice-based Math Searcho 前者应用空间向量进行数学公式的检索操作，在进行

24、数学公式特征提取后采用被动攻击 的在线学习分类模型对检索结果进行排序。后者把不同形式的数学公式统一成MathML 格式，在此基础上进行特征提取形成数学概念格，并在概念格中实现数学公式的相似度 排序。Hu等人【I。】改进了 TF-ID算法并将其应用于数学公式检索结果排序上，将表达式归 一化成树的形式，并将节点所在层次作为评价指标，计算每个节点出现的频率和倒排公 式的频率，由此得出表达式间的相似度，完成检索结果表达式的相似度排序。LinUM等 人改进了该方法，引入了检索结果式包含待查询式的相同节点个数占待查询式节点总数 的比例这一评价指标，使排序结果更加合理化。徐艳霞21提出了一种基于CAS的面向

25、数学搜索的排序算法，将TF-IDF算法进行 改进，考虑了数学公式间的相关度和子公式的权重因素来计算待查询公式与检索结果式 的相似度，并以此进行检索结果的相似度排序，该算法中将数学公式之间的关系分为四 种：等价、代数相关、完全相同和无关，并为前三种关系设计针对性的相似度计算方法。 这一方法为处理数学公式的语义智能识别与搜索问题提供了新的思路，提高了系统搜索 的全面性和准确性。马惠娟HI设计并实现了 “基于CAS的数学搜索引擎索引方法”，利用抽象倒排树索 引结构建立索引，在建立索引时，采用加权算法Ro】构造数学公式及其所在文档的权值矩 阵。最后利用优化排序和快速排序两种方法对数学表达式进行相似度计

26、算，并将结果表 达式进行排序返回给用户。景珂囚对数学搜索引擎进行研究，提出了 content索引和Presentation索引两种索 引机制，并针对两种索引机制提出了不同的检索结果排序算法。在Content索引机制中， 建立数学公式查询树，并定义节点N-grams长度、节点深度和节点复杂度特征为每个节 点赋予权重，通过权重值实现数学表达式的排序。在Presentation索引机制中，采用 N-grams倒排索引以实现结果表达式的合理排序。高良才、汤帜等人将分层思维应用到数学公式相似度排序上，设计并实现了 WikiMirs系统。以数学公式树原型为提取层次特征的模型基础，提取其层次信息用于相 似度

27、计算，从空间和文本两个维度上考察公式间的相似性，完成相关检索。文献24提出了一种数学表达式检索结果相关排序算法，定义数学表达式评价属性 及其相应的隶属度函数，利用犹豫模糊集构造数学表达式相似度计算公式，将提取数学 表达式特征值带入其中以得出带查询数学表达式与检索结果集中表达式的相似度，实现 了数学公式间的相似度排序。现有的数学检索原型系统也在数学表达式检索的相似度排序上进行了研究，设计或 改进了一些排序算法，以求反馈给用户合理的排序结果。MathWebSearch12-14在数学公式检索结果相似度排序上采用标准的TF-IDF算法来 计算查询内容与结果文档的相似度，以便把结果文档按其与检索内容的

28、相关性大小划分 等级，完成相似度排序。MathDex6依据待查询式与文件语法的相似度进行相关排序。将待查询式与检索结 果式的匹配程度和待查询式在文档中的位置作为评价指标，首先记录检索结果集中的所 有公式及其子公式的出现频率，并采用N-grams方法进行数学公式匹配，再为待查询公 式的位置信息分配权重。DLMF Search5采用针对数学公式特点改进的TF-IDF算法进行检索结果的相似度 排序，按照运算符的重要性大于运算数来分配分配权重，得到较为准确的排序结果，但 它的本质没有改变，其检索原理仍然是针对文本的。以上方法为线性代数式检索结果排序提供了思路。由于线性代数式的结构、语法和 语义的复杂性

29、，选择合理的理论及模型，多视角研究线性代数式的特征，才能完成线性 代数式检索结果的相似度排序。1.2.2犹豫模糊集及其应用研究现状模糊集因决策问题而产生，由ZadehW在1965年首次提出，之后它的几种扩展形 式直觉模糊集I、模糊多重集等也相继被提出，但它们并不能对所有决策问题进行 有效的表述，例如：不确定性决策问题，于是Torra27于2010年提出了犹豫模糊集的概 念，用多个可能值集合的形式来表示某一对象隶属于模糊集的程度，有效地刻画了决策 中的不确定性。由于犹豫模糊集在处理不确定性问题上的优势，国内外专家学者对犹豫模糊集进行 了更加深刻地研究并将其应用到更多的决策性问题上。朱斌等人即提出

30、对偶犹豫模糊集的概念，用可能隶属度和可能非隶属度的形式来表 示对决策问题的犹豫度，使决策结果更加精准。陈树伟等人2刃扩展了犹豫模糊集，考虑到区间值的特性与优势，定义了区间值犹豫 模糊集的概念以及它的运算法则等内容，为后续的区间值犹豫模糊集的聚合算子、相应 的决策方法等研究奠定了基础。李春梅等人3对区间值犹豫模糊集进行了研究，并将其应用于用户聚类领域中，利 用嫡权重公式计算出未知的属性权重值，最后结合相关算法得到最终的分类结果以实现 群推荐。吴婉莹等人DI将区间值与对偶犹豫模糊集进行结合，提出了区间值对偶犹豫模糊集 这一全新的概念，并且定义了其相关系数的计算公式，巧妙地解决了属性权重部分未知 的

31、模糊多属性群决策问题。战秋艳等人3幻改进了区间值犹豫模糊集，重新定义其距离公式和相彳以度计算公式, 并提出犹豫度理论，在该理论中同时考虑了犹豫区间数量和端点值两个方面的不同，通 过实例分析对其合理性进行了证明。赵晓冬等人闵对区间值犹豫模糊集和Heronian平均算子进行研究，提出了一种结 合两者特点的多属性决策方法，定义了四类算子并对其性质进行详细说明，有效的利用 Heronian平均算子处理属性间关系的优势，使决策效果得以优化。刘卫锋和何霞目4将毕达哥拉斯模糊集融入到犹豫模糊集理论中，充分利用了这两种 集合各自的优势，给出了毕达哥拉斯犹豫模糊集的定义与运算规则，为处理多属性的模 糊决策问题提

32、供了一种创新性的方法。彭定洪和聂军的对Tversky相似性模型进行了改进，面向犹豫模糊集，提出了一种 全新的相似度测度函数，解决了传统原始测度不能全面处理原始数据的问题，该函数借 助差异化系数赋值，得到多组结果来进行比较，提高了系统的准确性。Babitha和JohnW将犹豫模糊集和软集相结合，提出了犹豫模糊软集理论，该理论 中给出了交运算、补运算等基本运算的定义，开辟了解决多属性决策问题的新方法。吴良刚和周赛军印在此基础上扩展了犹豫模糊软集理论，对集结算子及相应的运算 法则进行了研究并给出了具体的定义，并通过实例证明了这些集结算子在处理多种的领 域中的多属性决策问题时存在显著优势，丰富了犹豫模

33、糊软集理论。周小强网也对犹豫模糊集和软集进行了研究，提出了广义直觉模糊软集等一系列概 念和相应的运算规则，研究了几种决策算子在群决策中的应用，证明了犹豫模糊软集的 优势。王新鑫等人提出了一种基于专家打分法的犹豫模糊多属性群决策方法，利用犹豫 模糊决策矩阵的扩充和聚合来评价各种决策方案，以便选出最优解决方法。陈秀明等人4对直觉犹豫模糊集进行了研究，为了增加其在群推荐中的适用性，提 出了相关系数概念并给出聚类算法，并借助于电影推荐的实例分析并证明了该方法切实 可行。安景文等人41将犹豫模糊集理论应用到安全事故应急预案的评估上,并从内容的周 详程度、编制的合法程度、应用的科学程度、操作的难易程度，费

34、用的精简程度五个方 面进行测评，再利用犹豫模糊集的相关知识进行相似度求解，选出准确度更高的应急预 案。谢海研究了犹豫模糊集和传统集合之间的关联性和差异性,为了使这两类集合得 以沟通，针对犹豫模糊集和犹豫模糊关系分别提出了截集和截关系两个概念，为后续的 犹豫模糊集理论的研究奠定了更加稳固的基础。上述研究丰富了犹豫模糊集理论，并将犹豫模糊集应用到了多属性决策问题的求解 上，这为将犹豫模糊集理论应用于线性代数式检索结果的相似度排序这一同属于多属性 决策的问题奠定了基础。1.3研究内容及主要工作由于线性代数式由多个子式构成，与普通数学公式相比，它的结构、语法和语义更 加复杂，实现其检索结果的相似度排序

35、的难度更大，因此，本文综合考察了线性代数式 的各个方面的特点，利用犹豫模糊集知识，设计了相关的排序算法，完成针对线性代数 式检索结果的相似度排序。论文主要研究内容包括：设计线性代数式解析算法。针对线性代数式的特点，将文献43设计的FDS (Formula Description Structure)数学公式解析算法进行改进，并利用改进后的算法对线性代数式的特征进行提取。分析线性代数式的属性特征，包括：结构、语法和语义三个方面。设计评价 属性和与之相对应的评价标准，并针对每一个评价标准设计相应的隶属度函数。设计面向线性代数式的检索结果排序算法。梳理线性代数式检索结果相似度 排序流程，将犹豫模糊集

36、理论应用到线性代数式之间的相似度计算上，实现面向线性代 数式的检索结果的相似度排序。1.4本文的组织结构本文基于现有的数学表达式检索系统，研究线性代数式检索结果的排序问题。论文 总共分五章:第1章引言。介绍数学表达式检索的研究背景及意义，国内外对数学表达式检索结 果排序的研究现状，以及犹豫模糊集及其应用的研究现状。第2章线性代数式解析及特征提取。主要介绍了线性代数式的三种匹配模式，针对 线性代数式改进的解析算法，以及利用该算法进行特征提取的相关过程。第3章线性代数式检索结果相似度排序。主要介绍犹豫模糊集相关技术，基于犹豫 模糊集的线性代数式相似度评价原理及流程，线性代数式相似度评价属性和与之相

37、对应 的隶属度函数的设计，利用犹豫模糊集进行线性代数式相似度计算，并依据该结果进行 线性代数式检索结果的相似度排序，以及线性代数式检索结果相似度排序算法的设计。第4章实验结果与分析。介绍线性代数式数据集的构建以及线性代数式检索结果相 似度计算实例分析与结果对比。第5章总结与展望。将本文的主要工作进行总结，分析其中的不足之处，确定后续 研究的目标，提出建议和展望。第2章 线性代数式解析及特征提取线性代数式的解析和特征提取是线性代数式相似度评价的基础，其合理性和全面性 影响着线性代数式相似度评价的优劣程度，所以要应用恰当的解析算法将线性代数式进 行全面的解析，然后把提取到的线性代数式的特征值应用于

38、线性代数式相似度评价之中, 从而实现线性代数式检索结果的有序输出。2.1线性代数式检索模式线性代数式的种类较多，包括矩阵、行列式和方程组等，不同种类的线性代数式的 变形和计算也十分丰富，因此在设计线性代数式的检索系统时，要从用户的实际需求出 发，把它们区分开来，设计不同的线性代数式匹配模式，有针对性的将待查询式归于某 一类检索模式，再与数据库中的线性代数式进行合理的匹配，以得到用户最为需要的检 索结果。定义1线性代数式中按照行列规则排列的、既相互独立又有联系的子表达式称为 线性代数式的子式。各类线性代数式的子式举例如表1所示。表1各类线性代数式的子式线性代数式种类行列式矩阵方程组0、实例11

39、anb.aux + arx =t。篁+ a22x2 =线性代数式的子式“224，i + anx2 = bx,+= b、定义2 Eq为一个m行列的线性代数查询式，Eq(i,j)(i=l, 2, m; j=l, 2, n) 为其子式，耳q (t=l, 2,人)为检索结果集合中的)个/行d列线性代数式,Erq (k,l)(k=l, 2, c; /=1, 2, d)为其子式。本文改进了数学表达式检索系统中的子式匹配模式，针对不同种类的线性代数式设 计了三种检索模式，分别为：矩阵匹配模式、行列式匹配模式、方程组匹配模式。其中，矩阵匹配结果中除包含与待查询矩阵精确一致或部分子式包含待查询矩阵的子式的矩 阵

40、外，还包括逆矩阵变换、增广矩阵变换和转置变换等矩阵形式，在进行检索结果的相 似度测评时，将待查询矩阵的这些变型形式作为评价因子；同理，在行列式匹配中将待 查询行列式的转置变型和值作为相似度的评价因子；方程组匹配仅实现子式匹配的功能。x y不同种类的线性代数式进行不同的模式匹配时，均遵循行优先原则，以= ”、x + 1 yEr=”为例，按行优先原则进行模式匹配的流程图如图1所示。x+ j x步骤一-1步骤二1步骤一步骤二x + l yx yx+ y X7y xtt步骤三步骤四11x + yt步骤三步骤四1_=1，步骤一步骤二+1x + 1 yy x1x + y x步骤一步骤二Vx + 1 y步骤

41、三1_步骤四_1Lx+ y xf t步骤三步骤四图i行优先原则匹配流程图图1中，由左向右最先将待查询线性代数式的第一行的各列子式同数据库中线性代 数式的由左向右、从上至下的每一个子式进行匹配，直至检索结果集中的所有线性代数 式的所有子式全部匹配完成，再按相同原则匹配待查询线性代数式的下一行的各列子式, 直至最后一行的最后一列子式同数据库中所有线性代数式的子式匹配完成，则匹配过程 结束。子式匹配：将用户输入的待查询线性代数式与的子式Eq(i,j)和检索结果集中的线 性代数式凡的子式E/k,l)看做独立的数学公式，按行优先原则递归地将Eq(i,j)同E叫(k,l)进行包含匹配，即要求Eq(i,j)

42、 = q (k,l)或者Eq(i,j)是 (k,l)的一部分，若包 含匹配成功，就把耳q伙,/)所对应的Eg归入到最终的检索结果，子式匹配原理如图2 所示。(3)递归匹配每一个子公式包含匹配相似度计算整合结果Eq的子公式 数据集 子结果集 检索结果递归匹配每_个子公式1图2子式匹配原理图矩阵匹配：在子式匹配的基础上，将检索结果集中加入待查询矩阵的转置矩阵、逆 矩阵、增广矩阵和伴随矩阵，因为逆矩阵和伴随矩阵的所有子式可能不包含原矩阵的任 何子式，这样就会导致子式匹配失败，即检索结果集中不会出现待查询矩阵的逆矩阵和 伴随矩阵，显然这样的结果是不合理的。为了能够达到用户满意的效果，将这些矩阵的 变换

43、形式作为一个评价属性，设置其相应的隶属度函数，完成矩阵匹配。1 2 3 一例如：待查询线性代数式与为“”，它的逆矩阵为“ 2 2 2 ”，3 2 32 32 2 ”子式相同也不是其子式的一部2_22 3分，这样就会导致包含匹配失败，但二者在逻辑上是互为逆矩阵的，这样就会造成检索 结果存在偏差，因此有必要将矩阵的变换形式作为一个评价属性，应用于矩阵间的相似 度评价。行列式匹配：与矩阵匹配类似，考虑到行列式之间的逻辑相似性，将行列式变换形 式和行列式的值分别作为评价属性，并为它们设置相应的隶属度函数，使行列式匹配的 检索结果更加合理，这里的行列式变换主要考虑的是待查询行列式的转置形式。例如：待查询

44、行列式与为4 5 6 ”，检索结果集中的两个行列式分别为7 8 91 2 31 4 7% =”4 5 6”和 =”2 5 87 8 03 6 9!1虽然氏和，有8个子式相同且相同子式位置完 q icii1 2 31 4 7全一致，而与和耳中仅有3个相同子式的位置一致，但“4 5 6和“2 5 87 8 93 6 9在逻辑上互为转置，所以在行列式变换评价标准上，我们认为与和耳q更相似。相反，如 果不考虑该属性就会造成检索结果的查准率下降，因此将行列式的变换形式作为行列式 间相似度评价时的一个评价属性是十分合理的。方程组匹配：方程组匹配等同于子式匹配，其原理与子式匹配的原理完全相同，就 是将包含待

45、查询方程组的一个或多个子式的数据库中的方程组返回给用户，完成方程组 匹配。例如：待查询方程组为数据库中某一方程组为 q 3x+），= 7x +），= 3% =匕3x + y = 7,因为|中包含与与相同的子式，所以将Erqi纳入到检索结果集中。 、z = 52.2线性代数式解析本文主要针对LaTeX形式的线性代数式进行研究，在文献43提出的数学表达式解 析算法基础上做了改进，将其解析成改进的FDS （Fonnula Description Structure）结构， 存储组成线性代数式的每个子式包含的所有符号nodeexp,长度length,层次level,是 否为运算符/数operate,标

46、志位flag,起始位starloc,位置信息/M（包含行号s_line和 列号s_colu两部分信息），并且存储线性代数式的整体属性特征，包括：矩阵变换信息 mx_vart,行列式变换信息行列式等值信息djkey,规模信息size （包含行数line 和列数co/”两部分信息），相同子式数量信息same_s,便于对线性代数式进行特征提 取。文献43中FDS结构将标志位分为8种，分别为：右邻水平、上部、右上标、右下 标、下部、内部、左上标、左下标，分别用“0, 1, 2, 4, 5, 6, 7, 8”这8个数字进 行表示。针对线性代数式，规定每行的第一个子式的主基线的标志位为6,其中1=1,2,

47、., 表示其所在行号，每行的非第一个子式的主基线的标志位为0。以矩阵“ 2”为例，对改进后的标志位信息的标注规则进行说明。ya + aL 2 J“白”位于第一行第一列,则分数线“的必宓值为61,而“ b2 -4a 位于第一行第二列，则它的位于主基线的符号的flag值为0, “插位于第二行第一列，所以根号“”的/Zag值为62,而 + a ”位于第二行第二列，则它的位2于主基线的符号-,+g”的伽g值为0。线性代数式的子式主基线以外层次的数学符号按照文献43的规定来标记flag值。J +屏-2ya1+ a2”的每个子式的所有符号的标志位值如图3所示。flag1flag=6-flag=Oflag=

48、62 查询线性代数式的子式总数，执行（4）,否则执行（3）；（3）查询线性代数式的子式信息表，并对包含查询线性代数式子式的数据库中的 子式进行解析，将解析结果存入LatList表中，否则执行（2）；（4）查询线性代数式信息表，并根据suid找到对应线性代数式，对该线性代数式 进行解析，并将特征存入表OatList中；（5）算法终止。其中，数据表LaExp、SuExp OatList LatList所包含的具体的列属性的名称、含 义以及各表之间的关系如图4所示。假设用户输入的待查询线性代数式与为“a + by/2+bb1 4ac1i+12”，检索结果集中某一LaExpSuExp4expid线性代

49、数式切expid线性代数式汨fname文件名称suid子式idexpstrLaTeX字符串sustr子式LaTeX串OatListLatListexpid线性代数式Zdsuid子式idline行数nodeid节点汨colu列数sjine子式行号mx_yart矩阵变换s_colu子式列号dt_yart行列式变换length长度信息dt_key行列式的值leve层次信息same_su相同子式个数starloc起始位置信息flag标志位信息operate运算符/数weight运算符/数权重图4数据表列属性含义关系图a + b + c-2-1+ a2”。在对鸟(1,1) = % +尹进行包含匹配时,J

50、屏-4。? 线性代数式Eg为 J/ +屏a +b +c其LaTeX字符串 firaca+b+c2 ”被替换为垢(1,2) = ”竺三”匹配成功，“ frac ( (substitute+c 2 。a +b + c提取到的，的子式知(1，2)= ”一-”的特征信息包含的内容有：“a+b”在“生中的层次信息、标志位信息、位置信息(行号和列号)、运算数/符信息， 2具体信息如表2所示。表2结果子式特征信息表nodeexpfracsubstitute+c2level01111operate10100flag01115line11111colu22222当乌的四个子式同耳的每个子式均匹配完成后，再对耳进

51、行整体特征提取，提 取的内容包括：的矩阵变换信息、行列式变换信息、行列式的值信息、规模信息(行 数和列数)、相同子式数量信息，得到的结果线性代数式凡也的整体特征信息表如表3 所示。表3结果线性代数式整体特征信息表mx_yartdt_yartdtjkeysizesame_susjines_colu0002212.4本章小结本章对线性代数式的匹配模式、线性代数式的解析及其特征提取进行了研究。将线 性代数式的种类加以区分，有针对性地设计了矩阵匹配、行列式匹配和方程组匹配三种 匹配模式，改进了数学表达式的解析算法，使其满足线性代数式的解析要求，从整体和 局部两个方面提取线性代数式的特征，形成特征信息表

52、，为后续的相似度计算提供数据 基础。第3章线性代数式检索结果相似度排序线性代数式种类丰富、特征复杂，计算数据集中线性代数式与待查询线性代数式之 间的相似度，并依此对检索结果进行排序十分困难，考虑到犹豫模糊集在处理多隶属度 决策问题上的优势，在全面提取线性代数式结构、语法、语义等特征的基础上，建立线 性代数式特征集合，利用犹豫模糊集相关理论求解线性代数式之间的相似度，使排序结 果更加合理、准确。3.1犹豫模糊集相关技术犹豫模糊集27定义为：设X是一个非空集合，则称E = x&X(1)为犹豫模糊集，其中如3)称为犹豫模糊元素，它是元素X对于集合已的几个可能 的隶属度的集合，其元素值在0,1上分布2

53、7】。在进行决策问题分析时，通常采用计算距离相似性测度的方法，该方法存在诸多优 势，如可以方便的获取两个方案的差距或者相似性，常见的标准距离测度有：标准汉明 距离、标准欧几里得距离、Hausdorff距离等。文献44中犹豫模糊集的距离测度被定义为：设肱和N为关于集合X =气,易,.,琳的两个犹豫模糊集，则肱和N之间的距离 测度为表示为d(M,N),且满足下面的条件：0d(M,N)l；d(肱,N)=0,当且仅当M =N时成立；d(M,N) = d(N,M)。相似性测度网被定义为：设肱和N为关于集合X =*,&,，吒的两个犹豫模糊集，则肱和N之间的相似 性测度为s(M,N),且满足下面的条件：0s

54、(M,N)0,罗仃)0)为M对应中第/大的犹豫模糊元素值，同理 噂 g 为N对应中第，大的犹豫模糊元素值，/, =max(ZM(x),/A,(x)表示垢0)和 勾(改)中元素个数最大值44】。M和N的相似度网表示为s(M,N) = l-dM,N)(3)式中，s(M,N)为犹豫模糊集肱和N的相似度。3.2基于犹豫模糊集的线性代数式相似度评价原理与多属性决策问题类似，在利用犹豫模糊集原理解决线性代数式相似度评价问题时, 首先，要全面考察线性代数式的多方面特征，设计相应的评价属性，并为每个属性给出 一组评价标准；其次，要为每个评价标准构造与之相对应的隶属度函数，将特征值带入 得出其隶属度值，形成犹豫

55、模糊集合；最后，应用相似度距离公式，计算犹豫模糊集合 间的距离，从而得出线性代数式间的最终的相似度。在进行线性代数式相似度评价时，乌和凡均为LaTeX字符串形式，利用2.2节提 出的改进的线性代数式解析算法将它们进行解析，并将结果保存于数据库中。线性代数 式的评价属性采用双层属性形式，如图5所示。双层属性模式能够从多个角度对线性代 数式的特征进行考察，提升了线性代数相似度评价的全面性。线性代数式的双层评价属 性的详细介绍如下所示。一级属性为局部属性，用集合形式表示为耳,念,包括：线性代数式的结 构属性，运算数属性和运算符属性等。其中，涵盖了 Eq（i,j）和耳% Q,/）所处的位置（即 该子式

56、位于第几行第几列），Eq（i,j）处于EI（h（k,l）的起始位置，Eq（i,j）在耳% （/J）中所处 层次，在Erq （k,l）中的Eq（i,j）与上一层次符号的相对位置关系（标志位信息），Eq（i,j）和 E/k,l）的长度，各个字符是否为运算数或运算符等信息。二级属性为整体属性，用集 合形式表示为An+1,Am+2,.,A,包括：线性代数式的规模属性（即线性代数式是几行 几列），线性代数式包含相同子式数量属性，线性代数式的变换属性（矩阵变换和行列 式变换）等。每个评价属性均包含一组评价标准，每个评价标准对应一个隶属度函数，即每个局 部评价属性包含的评价标准，用集合形式表示为indpi，

57、indp2，.ndps，其中 p = （m为局部属性总数），相应的隶属度函数用集合形式表示为 右1,2,，右3。每个整体评价属性包含的评价标准，用集合形式表示为 ind,indind,其中0 = m + l,m + 2,.,（秫为局部属性总数，为评价属性总 数），相应的隶属度函数用集合形式表示为/例,儿2,，扁3。将提取到的局部属性特征值带入相应的隶属度函数得到局部属性隶属度值。同理将 提取到的整体属性特征值带入其隶属度函数得到整体属性隶属度值。基于犹豫模糊集的线性代数式评价原理图如图5所示。提取特征值代入隶属度函数评价属性!=评价标准集I=犹豫模糊集hf图5线性代数式评价原理图3.3基于犹豫

58、模糊集的线性代数式相似度评价流程犹豫模糊集可以用多个可能值集合的形式来表示某一对象隶属于该模糊集的程度, 这样就能更好解决多属性决策问题。所以要全面且合理地选择决策问题的属性，再针对 不同属性设置相应的评价标准才能得出较为准确的结果，线性代数式相似度评价过程也 是如此。对线性代数式进行相似度评价的流程分为特征提取、隶属度计算、相似度计算等三 个步骤。具体的评价流程如下：步骤1：按每个属性所对应的属性评价标准进行特征提取，按先后顺序分别提取出 取出线性代数式的局部属性特征值和整体属性特征值。步骤2：将提取的局部属性特征值和整体属性特征值带入相应的隶属度函数进行计 算，形成如图5所示的局部属性犹豫

59、模糊集和整体属性犹豫模糊集。步骤3：根据针对线性代数式变型的广义犹豫模糊集标准距离公式，计算各类犹豫 模糊集之间的距离，得到待评价线性代数式间的相似度完成排序。基于犹豫模糊集的线性代数式评价流程图如图6所示。图6线性代数式评价流程图3.4线性代数式相似度评价相似度评价是否合理与特征的选取以及隶属度函数的构造密切相关，所以在进行线 性代数式相似度评价时，要综合考虑其各方面的特征，全面地对线性代数式的各个特征 1 ax 2进行刻画。例如，线性代数式的子式的位置特征，“，c ”和“ c ”都含有子式“2”，b 23 ），但“2”位于“”的第二行第二列，位于“”的第一行第二列，即它在两个线性代数式中所

60、处的位置不同，在考察它们与待查询线性代数式的相似度时要考虑到子 式的位置关系；线性代数式的规模特征，例如：2x2矩阵和3x3矩阵，二者的规模不同， 影响着它们与待查询线性代数式的相似程度。本文将线性代数式属性特征归纳为两部分，分别是局部属性特征和整体属性特征。 其中，局部属性特征包括结构属性、运算数属性、运算符属性，整体属性包括矩阵变换 属性、行列式变换属性、行列式的值属性、规模属性、相同子式数量属性。每个评价属 性分别包含一个或多个评价标准，不同的检索模式评价标准不同，将个别属性设置为1 来表示该属性值对该匹配模式的相似度评价没有影响，如表4所示。表4线性代数式评价属性表属性种类评价属性评价