（计算机软件与理论专业论文）网络数学搜索中的数学查询语言与索引的研究.pdf

摘要 目前，随着互联网的迅猛发展、w e b 信息的增加，用户要在信息海洋里查找 信息，就像大海捞针一样，搜索引擎技术恰好解决了这一难题。然而传统文本检 索系统在对数学公式和数学符号的搜索上具有很大的局限性，使得在科学、数学、 工程及科技方面无法满足用户对数学公式搜索的需求。与此同时，随着数学内容 计算机存储的深化以及浏览器对多种数学表示形式的支持使得基于公式的数学 搜索引擎的研究具备了可行性条件。 本文在对比研究了现有的一些数学搜索系统的实现方法和技术基础上，主要 针对目前数学检索中的两大重点和难点问题展开深入讨论。即如何建立一种通 用、有力的数学查询语言以及如何建立一种易于存储和查询的数学内容索引结 构。 在数学查询语言的建立方面，本文提出了一种基于x m l 的扩展机制，构建一 种符合m a t h m l 语言规范的数学查询语言m q l ( m a t hq u e r yl a n g u a g e ) 。该查询 语言通过在m a t h m l 语言规范的基础上定义一系列元数据标签来实现查询时的通 配符查询表达和组合查询表达。这些标签各自具有相应的属性，这些属性可以细 化查询描述，有效增强查询表达力度。 在数学内容索引的建立方面，为了同时支持面向数学内容显示结构的查询和 面向数学内容语义的查询，本文提出同时为数学内容建立p r e s e n t a t i o n 索引和 c o n t e n t 索引。其中，c o n t e n t 索引主要采用抽象树倒排索引结构，p r e s e n t a t i o n 贝j 采用n g r a m s 线性倒排索引结构。此外，论文中还描述了索引建立时公式中各子 公式的权值分配方法，以优化查询显示结果，提高搜索引擎查全率和相关度。 关键词m a t h m l ，数学查询语言，语义查询，索引，抽象树，倒排表 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e ta n dt h ef a s ti n c r e a s eo ft h ew e b i n f o r m a t i o np r e s e n t l y , i ti sd i f f i c u l tf o rt h eu s e r st os e a r c ht h e i rr e q u i r e di n f o r m a t i o n f r o mt h et r e m e n d o u si n f o r m a t i o n r e s o u r c e ，a sf i n d i n gan e e d l ei nah a y s t a c k f o r t u n a t e l yt h ep r o b l e mc o u l db er e s o l v e db ys e a r c he n g i n et e c h n o l o g y h o w e v e r ， b e c a u s et r a d i t i o n a lt e x tr e t r i e v a ls y s t e mh a ss i g n i f i c a n tl i m i t a t i o n so nt h es e a r c ho f m a t h e m a t i c a lf o r m u l a sa n dm a t h e m a t i c a ls y m b o l s ，i tc a n n o ts a t i s f yt h eu s e rd e m a n d f o rm a t h e m a t i c a lf o r m u l a ss e a r c hi nm a n ya s p e c t ss u c ha ss c i e n c e ，m a t h e m a t i c s ， e n g i n e e r i n ga n dt e c h n o l o g ya n ds oo n m e a n w h i l e ，w i t ht h ee n h a n c e m e n to fc o m p u t e r s t o r a g eo nm a t h e m a t i c a lc o n t e n t , a sw e l la st h ed e e p e n i n gs u p p o r to fav a r i e t yo f b r o w s e r si nt h ef o r mo fm a t h e m a t i c s ，i ti sf e a s i b l et oc a r r yo u tt h er e s e a r c ho nt h e s e a r c he n g i n ea b o u tm a t h e m a t i c a lf o r m u l a i nt h i sp a p e r ，b a s e do nac o m p a r a t i v es t u d yo fs o m ee x i s t i n gm a t h e m a t i c a l f o r m u l as e a r c hs y s t e mo ni m p l e m e n t a t i o na n dt e c h n i q u e s ，w em a i n l yf o c u so nt h et w o i m p o r t a n ta n dd i m c u l tp r o b l e m so nm a t h e m a t i c a lf o r m u l as e a r c h i no t h e rw o r d s w e p a yg r e a ta t t e n t i o nt oh o wt oe s t a b l i s hac o m m o n ，p o w e r f u lq u e r yl a n g u a g eo f m a t h e m a t i c sa n dh o wt oc o n s t r u c tam a t h e m a t i c a lc o n t e n ti n d e xs t r u c t u r ew h i c hi s e a s yt ob es t o r e da n di n q u i r e d w i t hr e s p e c tt oe s t a b l i s h m e n to fm a t h e m a t i c a lq u e r yl a n g u a g e ，w ep r o p o s ea m a t h e m a t i c a lq u e r yl a n g u a g e ( m a t hq u e r yl a n g u a g e ，m q l ) w h i c hi sb a s e do n e x t e n s i o no fx m la n da c c o r d sw i t ht h em a t h m ls p e c i f i c a t i o n t h eq u e r yl a n g u a g e i m p l e m e n t st h ew i l d c a r dq u e r ye x p r e s s i o na n dt h ec o m b i n a t i o nq u e r ye x p r e s s i o nb y d e f i n i n gas e r i e so fm e t a - d a t al a b e l sw h i c hi sb a s e do nm a t h m ls p e c i f i c a t i o n t h e s e l a b e l sh a v et h e i r a t t r i b u t e sw h i c hc a nb eu s e dt or e f i n e i n q u i r yd e s c r i p t i o na n d e n h a n c et h ee f f e c t i v eo fq u e r ye x p r e s s i o n a sr e g a r d sc o n s t r u c t i o no ft h em a t h e m a t i c a lc o n t e n ti n d e x ，i no r d e rt os u p p o r t s i m u l t a n e o u s l yt h ep r e s e n t a t i o nq u e r ya n ds e m a n t i cq u e r yo fm a t h e m a t i c a lf o r m u l a , w ee s t a b l i s hb o t ht h ec o n t e n t b a s e di n d e xa n dt h ep r e s e n t a t i o n b a s e di n d e xf o r m a t h e m a t i c a lc o n t e n t t h ec o n t e n t - b a s e di n d e xm a i n l yu s e st h ea b s t r a c t t r e ei n v e r t e d i n d e xs t r u c t u r e ，w h i l ep r e s e n t a t i o n b a s e di n d e xm a i n l yu s e sl i n e a rn g r a m si n v e r t e d i n d e xs t r u c t u r e i na d d i t i o n ，t h ep a p e ra l s od e s c r i b e st h ew e i g h te v a l u a t i o nm e t h o df o r e a c hs u b f o r m u l ad u r i n gt h ei n d e xe s t a b l i s h m e n to faf o r m u l a t h em e t h o dc a nb e u s e dt oo p t i m i z eq u e r yr e s u l t sa n di m p r o v e sr e c a l lr a t i oa n dc o r r e l a t i o no ft h es e a r c h e n g i n e k e y w o r d sm a t h m l ，m a t hq u e r yl a n g u a g e ，s e m a n t i cq u e r y ，i n d e x ，a b s t r a c t t r e e i n v e r t e dt a b l e 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发 表的成果、数据、观点等，均已明确注明出处。除文中已经注明 引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体，均己在文中以 明确方式标明。 本声明的法律责任由本人承担。 论文作者签名： 玉牛日期：型哟 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：趟导师签名：论文作者签名：鑫鱼当 导师签名： 兰州大学硕士论文网络数学搜索中的数学查询语言与索引的研究 1 1 研究背景及意义 第一章绪论 随着互联网的迅猛发展、w e b 信息的增加，用户要在信息海洋里查找信息， 就像大海捞针一样。“新摩尔定律”指出：因特网上的信息正以每6 个月翻一番盼 速度爆炸般地产生，它使任何上网寻求信息的人都难以选择。搜索引擎技术恰好 解决了这一难题。现阶段，基于文本的信息检索系统( 如g o o g l e ，百度等) 已经 得到了广泛的应用，为人们的学习、生活及科研工作提供了很大的便利。但随着 信息化的普及，人们对搜索引擎提出了更高的要求，希望能对数学公式和数学符 号进行更为有效的检索。然而现有基于文本的搜索弓f 擎在数学内容的搜索方面仅 限于基于关键词和字符串的搜索，在对数学公式和数学符号的搜索上具很大的局 限性，如在g o o g l e 搜索引擎上，无法输入和搜索形如i 。x 2 + 3 x d r 的公式，这使 得在科学、数学、工程及科技等方面无法满足用户对数学公式搜索的需求。 现阶段，随着信息化程度的不断提高和新技术的飞速发展，数学搜索引擎的 研究和开发已具备了一些必要的基础条件。首先，文本检索技术的相对成熟为数 学搜索的研究提供了基本的技术支持。其次，随着数字图书馆的不断建立和互联 网的不断发展，包含数学公式的文档资料也逐步采用计算机进行存储。起初，这 些数学公式和符号大多采用图像的形式存在于各种文档中，但随着基于x m l 的 数学标记语言的标准化，越来越多的网页中开始采用m a t h m l 1 、o p e n m a t h 2 、 l a t e x 3 和中缀格式表示和存储数学公式。再次，由于数学公式与普通文字相比， 具有更强的表达能力，可以更准确地表达一个概念或一个结论，而且目前出现了 很多的数学公式编辑软件，包括一些基于w e b 的数学公式编辑软件【4 】，加上浏览 器本身或插件的支持，在浏览器中显示数学公式己不存在问题，所以人们越来越 多地在网上使用数学公式来表达他们的思想，因而网络上的数学内容也在迅速积 累与扩展。以上为基于公式的网络数学搜索引擎的研究提供了可行性条件。 基于公式的数学搜索引擎的建立与研究对科学研究、教育、工程开发等都有 着极为重要的意义。一方面基于公式数学搜索引擎能够大大提高信息的检索效 率，另一方面基于公式数学搜索引擎也会促进相关文档资料的交流与共享。从短 兰州大学硕士论文网络数学搜索中的数学查询语言与索引的研究 期目标来看，数学搜索引擎可以满足用户的搜索需要，如当用户需要特定数学信 息时，他就可以通过数学符号或公式来搜索并得到该数学内容。从长期的目标来 看，数学搜索引擎对数学知识发现、管理及数学定理证明也有很大的帮助与促进 作用，如科学家可以通过数学搜索引擎来发现那些定理有相似的证明方法，从而 研究证明方法或发现新的证明方法。 近两年来，数学内容相关搜索研究已经逐步成为国际计算机技术的研究热 点，引起了政府、学术界、工业界的高度重视，各国纷纷开始启动相关科研项目 【5 ，6 ，7 ，1 0 ，1 4 ，比如美国自然科学基金项m a t h d e x 5 、美国国家数字图 书馆项目的子项目d l m fs e a r c hs y s t e m 8 等。当然总体来说这些研究项目均处于 起步阶段，在具体的研究内容上，如搜索界面和搜索查询语言的建立、索引的生 成与管理、相似度的计算和p a g e r a n k 算法，均还处于探索试验阶段，尚未形成成 套的基于公式的数学搜索理论与方法，还未构建出完整的基于公式的数学搜索系 统。在我国，基于公式的数学搜索研究几乎还处于空白阶段。 1 2 研究现状与对比分析 1 2 i 现有数学搜索引擎简介 现有可进行科学相关内容检索的搜索引擎可分为以下两大类：一类是不支持 数学内容识别的，另一类是支持数学内容识别的。第一类通过查找已提供的元数 据，可以执行比普通全文搜索引擎更好的数学内容搜索，但是不能处理数学操作， 比如g o o g l es c h o l a r 8 ，c i t e s e e r 9 等就属于该类搜索引擎。第二类可以根据它们 的数学识别方法分为以下两类：第一种采用基于语法的方法：如m a t h d e x 5 ，1 5 1 、 d l m fs e a r c h 1 0 ，1l ，1 2 ，1 3 ，1 4 ，1 5 】、l e a c t i v e m a t h 6 。第二种采用基于语义的方法： 如e g o m a t h 1 6 、m a t h w e b s e a r e h 7 ，1 7 1 。 以下我们对现有几个数学搜索引擎做简单介绍： 1 m a t h d e x m a t h d e x 是最早的能够进行数学内容识别的全文检索引擎，它基于a p a c h e 的 l u e e n e 18 】搜索引擎，于2 0 0 7 年初发表。关键特性有以下几点：支持无语义数学 内容文档的查询；支持不同数学编码数学内容的查询；同时支持数学符号和文本 2 兰州大学硕士论文网络数学搜索中的数学查询语言与索引的研究 的检索；尽可能满足用户的查询期望而不仅仅针对字面查询。 m a t h d e x 对于所有检索到的文件首先将其转换成x h r r m 乙+ m a t 蝴l 格式。文 件根据结构及与查询项的语法相似程度进行排序。m a t h d e x 提出n g r a m s 匹配方 法以提高精确度。在索引建立阶段，不仅为每个公式建立索引，同时记录其子公 式出现的频率信息。子公式出现的频率对增加复杂公式的匹配度有很大意义。 另外一个提高精确度的方法是将文件分为多个域，比如题目、正文等，并给 予不同权重。出现在标题中项的权重应高于出现在正文中项的权重。m a t h d e x 存 储表达式的不同部分以进行并行查询，从方程不同部分匹配到的项具有不同的权 重。不同公式可具有分子域、上标域、行域等。输入公式被解析，定义合适的域， 然后查询被重写，在所选择领域匹配子项。越多子项匹配，相关度越高。m a t h d e x 不能处理数学操作和等价性匹配。 m a t h d e x 索引了a r x i v 中2 5 0 0 0 个文件，1 2 0 0 0 个包含维基百科中数学相关的网 页，c o n n e x i o n s 中大约1 3 0 0 个页面，w o l f t a mm a t h w o r l d 中大约1 0 0 0 个页面。 2 d l m fs e a r c h d l m fs e a r c h 是为美国国家标准与技术研究所( n a t i o n a li n s t i t u t eo f s t a n d a r d s a n dt e c h n o l o g y ) 的数学公式数字图书馆( d i g i t a ll i b r a r yo fm a t h e m a t i c a l f u n c t i o n s ) 而建立的一个检索系统。据统计，美国国家数学公式数字图书馆中8 0 以上的用户手册或网页中包含数学公式并且数学公式的存储格式以t e x l a t e x 为 主。因此，d l m fs e a r c h 的目标公式格式主要针对于t e x l a t e x 格式，查询语言 也是基于l a t e x 。查询描述阶段，为了使用户能够表达模糊查询需求，d l m f s e a r c h 在l a t e x 格式基础上进行扩展，定义一系列元数据，这种查询语言是一种 文本化的查询语言。在索引建立阶段，d l m fs e a r c h 扩展文本信息检索的索引方 法。首先对数学对象进行线形化，即将所有非字母表中的数学符号都对应到字母 表中的一个字。其次界定并序列化数学对象的子项及表达式，最后按顺序将各子 项化为标准规范形式，即转化为已定义的规范顺序以免表述风格的不一致导致的 查询错误。该引擎的核心仍是基于文本的检索，与传统文本检索系统在本质上没 有差别。 3 l e a c t i v e m a t h l e a c t i v e m a t h 是一个基于w e b 的智能数学学习环境，主要目标是根据用户的 3 兰州大学硕士论文。网络数学搜索巾的数学查询语言与索引的研究 前期工作及实际知识水平为其提供个性化内容。目前，这个学习系统并未向公众 免费开放，而且并未查找到其可用的搜索系统。它是基于a p a c h el u c e n e 搜索引 擎的。 显然，这样的教育系统是需要一个搜索引擎的。该系统针对的数据源是 o m d o e 编码的具有语义的数学文件。索引阶段依赖于特殊的o m d o c 格式，其包 含语义信息以及其他的元数据。应用于现有真实文档则仍有一定问题。然而，使 用特殊的o m d o e 格式可以提高文档的相关度，使德搜索弓f 擎在特殊环境更加有 效。o m d o e 具有把文件分为被称之为项的内容单元的特性。这些项包括：定理， 练习，证明，定义等等。它们可以通过单一的标志符来定位，这有利于开发它仇 之间的关系。索引阶段，将o m d o e 的公式转换为特殊的包含信息深度的文本化 标记。子公式的深度信息包含于索引字符串中。搜索阶段将输入公式转化为具有 深度级别的表达式。目前，他们解决这一问题的办法是迭代索引库中从l 到最大 深度的公式。 4 e g o m a t h e g o m a t h 是一个基于e g o t h o rv 2 1 9 1 全文本搜索引擎的可识别数学内容的搜索 引擎。它的主要目的是适用于现实世界中不包含隐含语义信息的数学内容。它支 持p r e s e n t a t i o nm a t h m l 和c o n t e n tm a t h m l 表示方式，更侧重于针对p r e s e n t a t i o n m a t h m l 表示方式。对于p d f 文件，用i n 衄转换器转换为p r e s e n t a t i o nm a t h m l 标 记的数学文件。e g o m a t h 同时支持文本化查询和数学公式查询，这对于现实应用 更具有效性。e g o m a t h 并不是用一个单独的项来表示一个数学公式，复杂的公式 往往由一个项的有序集合来表示。后一个表达式可以由前一个表达式通过应用归 纳和变形来得到。这些规则试图降低全文索引库的最大缺陷静态特性。每个 集合中后面的公式都是由归纳而来的，因而可以匹配更多的表达式。在搜索阶段， 用户输入被分为简单文本查询和数学查询。然后，采用和索引阶段相同的算法处 理数学查询。算法产生n 个表达式，这些表达式通过“a n d ”操作符附加到简单 文本查询上。结果是执行1 1 个连续的查询操作。出于后面的查询项被匹配到的可 能性更大，因为后面的项比前面的更具有普遍性。每个数学文件都被分为数学部 分和文本部分进行存储。否则类似于“s i n ”的模糊查询就会即返回包含数学公 式“s i n ”的文档，又返回包含字符串“s i n ”的文档。 4 兰州大学硕士论文网络数学搜索中的数学奁询语言与索引的研究 e g o m a t h q 了查询语言采用类似- 于l a t e x 的表示方式。e g o m a t h 由于u i 设计仍未 完成直至目前仍未公布。目前，e g o m a t h 的索引库中已包含t c o n n e x i o n sp o r t a l 的 4 2 1 个文件，a r x i v 的1 9 1 5 个文件。 5 m a t h w e b s e a r c h m a t h w e b s e a r e h 是一个不依赖于全文检索引擎的数学搜索引擎。第一个可用 的版本诞生于2 0 0 7 年初，为了表现数学内容的准确性，它很大程度依赖于语义信 息，这具有很大的优势。但是当操作不具有语义信息的文件时，这会明显影响精 确度以及返回结果。 进行数学搜索时，m a t h w e b s e a r e h 采用了非文本化的查询方法。该方法中， 表达式被解析为置换树( 在符号数学系统如定理证明中应用较普遍) 。结果是产 生一个类似于树的结构，节点包含了对父节点的置换。为了进行子公式的查找， 它将每一公式的所有子公式单独的加入索引库中。尽管m a t h w e b s e a r c h 是最好的 数学识别搜索引擎，但它仍存在一定问题。一方面，具有相同语法的公式可能具 有不同的语义，另一方面，语法不同的公式可能具有相同的语义。 公式的每一次查找都要转换为置换树，这可能带来性能问题。由于该搜索引 擎不支持全文本的查找，因而在实用性上仍存在一定缺陷。目前，它可索引 c o n t e n tm a t h m l 文件。受限制的p r e s e n t a t i o nm a t h m l ， o p e n m a t h 格式的文件。 该数学搜索引擎前端w e b 搜索界面非常类似于m a t h d e x 但是查询语言有所不同。 它的查询语言扩展自m a t h m l 。他们的索引数据库包含c o n n e x i o n sp o r t a l 文档 3 4 0 0 项表达式数量大约为5 3 0 0 0 ( 包括子项7 7 0 0 0 ) 。w o l f r a mm a t h w o r l d 中 c o n t e n tm a t h m l 格式的公式8 7 0 0 0 个。 1 2 2 小结 综上所述，目前建立数学搜索系统主要有以下两种方法： 1 利用文本信息检索系统对数学关键词搜索。这是一种基于数学术语元数 据搜索，可以实现对数学内容进行粗粒度搜索，这种方法无需考虑数学搜索与通 用搜索的区别。这种方法通常可以同时支持文本搜索和数学公式搜索。但是不支 持更高级别的数学搜索，比如要搜索a 2 + c = 2 a ，舯a n - - i 以是任意相同的表达式， 这种查询就不能执行。这种方法最大的优势在于依赖一种已存在的成熟技术，但 5 兰州大学硕士论文 网络数学搜索中的数学查询语言与索引的研究 是它没有完全支持面向数学公式的查询。另一种相似的思想是依靠基于x m l 的 x q u e 呵搜索引擎。这两种方法的优势在于都依靠一种己存在的技术。但是它们 都没有提供完全面向数学的搜索方法。 2 对数学公式等内容进行细粒度搜索，对数学公式及部分子公式建立索引 并进行搜索，这种方法比文本信息检索系统具有更强大的功能，并且更加高效。 比如将模式匹配应用到基础编程语言中，在数据库中搜索数学文件并从中搜集到 结构化元数据以进行有效检索。 以上数学搜索引擎中，其中m a t h d e x 、d l m fs e a r c h 和l e a c t i v e m a t h 主要从 语法的角度，利用结构的数学公式进行检索。m a t h w e b s e a r c h 主要使用语义的方 法，e g o m a t h 贝, 1 同时使用两种方法。表1 1 对以上几个数学检索系统在查询语言、 支持可搜索数学公式格式、索引建立方法、是否支持数学公式语义查询等方面做 了简单的对比： 表1 1 ：数学检索系统对比表 数学检索数学支持数学表达格式索引方法支持语是否基框架 系统名称查询语言义查询于w e b原型 m a t h d e xm a t h m lm a t h m l 、l a t e x 、 文本检索否否无 ( p r e s e n t a t i o n ) o p e n m a t h 、中缀等 索引方法 d l m 【fl a t e x乃胁7 奴 文本检索否否 l u c e n e s e a r c h 索引方法 l e a c t i v e o p c n m a t h o m d o c 文本检索否是 l u c c r m m a t h 索引方法 e g o m a t h l a t e xm a t h m l 、p d f 文本检索是是 e g o t h o rv 2 索引方法 m a t h w e bm a t h m lc o n t e n tm a t h m l 、 置换树是是无 s e a r c h ( c o n t e n t )o p e n m a t h 、受限的索引 p r 墩- n t a t i o nm a t h m l 对该领域的研究一个重要的评估指标就是可用性。但是由于以上几个搜索引 擎仍未被使用，所以我们仅根据目前所获得的文献资料做一简单总结。如果考虑 6 兰州大学硕士论文网络数学搜索中的数学查询语言与索引的研究 实用性和万维网当前的发展状况，由于当前数学论文格式大多为p d f 格式不 直接支持公式语义，因而最适用w w w 的搜索引擎为是e g o m a t h 。但如果不考虑 文本的查询，并考虑到未来数学存储格式的发展方向，m a t h w e b s e a r c h 似乎是最 佳选择，因为它支持基于语义的数学内容检索。如果考虑到搜索引擎应用的特殊 领域，使它具有专业目的，l e a c t i v e m a t h 贝, l j 是最优选择，因为它支持专业的学习 环境。 兰州大学硕士论文 网络数学搜索中的数学查询语言与索引的研究 第二章m a t h s e a r c h 概述 2 1m a t h s e a r c h 系统架构与流程 m a t h s e a r c h 是一个可进行数学内容检索的基于公式的网络数学搜索引擎。其 能够实现对含有数学公式、数学符号的网页、文档、资料进行搜索。区别于目前 主流研究的数学搜索引擎实现方法，本文提出基于数学语义的数学公式检索方 法，使用语义检索方式，不仅可以实现基于字面显示和结构的数学公式检索，同 时可以实现基于数学公式语义的检索。如可以实现类似( x + y ) 2 、( ) 【+ y ) ( x + ”、 f + y 2 + 2 x y 之间的查询。m a t h s e a r c h 支持的具体查询包括：结构查询，即基于数 学公式原始结构的查询；语义查询，即基于数学公式语义的查询，包括不同结构， 不同表达方式的查询；通配符查询，m a t h s c a r c h 定义了一套相对完整的通配符表 示方法，可以满足用户通配符查询的输入需求；组合查询，即支持公式之间的 “与、“或 、“非等组合查询操作；抽象查询，即支持数学对象的抽象表示。 图2 1 显示了数学搜索引擎m a t h s e a r c h 系统流程的设计与实现构想：首先 m a t h s e a r c h 幂u 用一系歹l j 爬虫( c r a w l e r ) 进程从网络上收集信息，并判断其是否含 有数学相关的内容，如果有则开始下载相应的文档，并从文档中提取所需数学公 式、数学符号或数学相关内容；其次，为了同时支持基于数学显示方式的查询和 基于数学公式语义的查询，m a t h s e a r c h 为这些公式、符号和数学内容分别建立面 向数学公式显示的p r e s e n t a t i o n 索引和面向数学公式语义的c o n t e n t 索引。用户表达 查询需求时，既可以通过所见即所得的g u i 窗口输入要搜索的内容，也可以直接 通过输入数学搜索语言m q l ( m a t h e m a t i c a lq u e r yl a n g u a g e ) 来表达搜索需求； 然后m a t h s e a r c h 对m q l 进行解析，查找相应的数学内容，最后通过合理的算法对 这些网页连接建、- | r p a g e r a n k ，将结果排序列出，并将查找内容突出显示。 8 ! h 大学目论!月镕# 学控索中m # a w i 5 女d 日究 目21 数学搜索引擎m a t h s e c h 系统流穗设计构想 m a t h s e a r c h 采用l u c o n e 的系统原型。l u c e n e 是a p a c h e 软件基金会一个开源子 项目，是一个开放源代码的全文检索引擎工具包即它不是一个完整的全文检索 引擎，而是一个全文检索引擎的架构，提供了完整的查询引擎，索引引擎和部分 文本分析引擎。l u c e n e 的目的是为软件开发人员提供一个简单易用的工具包，以 方便的在目标系统中实现全文检索的功能，或者是以此为基础建立起完整的全文 检索引擎。l u c e n e 作为一个全文检索引擎，其具有如下突出的优点： ( 1 ) 索引文件格式独立于应用平台。l u c e n e 定义了一套以8 位字节为基础的索 引文件格式，使得兼容系统或者不同平台的应用能够共享建立的索引文件。 ( 2 ) 在传统全文检索引擎的倒| i 索引的基础上，实现了分块索引，能蟹针对 新的文件建立小文件索引，提升索引速度。然后通过与原有索引的台并，达到优 化的目的。 ( 3 ) 优秀的面向对象的系统架构，使得对于l u c e n e 扩展的学习难度降低，方 便扩充新功能。 ( 4 ) 设计了独立于语言和文件格式的文本分析接口，索引器通过接受t o k e n 流完成索引文件的创立，用户扩展新的语言和文件格式。只需要实现文车分析的 接口。 ( 5 ) 已经默认实现了一套强大的查询引擎，用户无需自己编写代码即使系统 可获得强大的查询能力，l u c e n e 的查询实现中默认实现了布尔操作、模糊查询 ( f u z z y s e a r c h ) 、分组查询等等。 “大学确* 立目镕散学拽索巾的数学矗* 言与索日l w r 当然l u c e n e 本身不具有数学公式搜索功能，本项目组拟在现有l u c e n e 基础上 开发和建立数学搜索引擎系统m a t h s e a r c h ，并引入计算机代数系统提供计算能力 及语义支持。 图2 2 显示了m a t h s e a r c h 主要的系统组成架构。m a t h s c a r c h 服务器主要由三部 分构成：网络服务器、索引服务器和搜索服务器。搜索服务器中运行着一系列网 络爬虫进程，不断地在网络中查找具有数学相关内容的网页或文档。对于搜索到 的数学内容，通过索引服务器建立数学内容索引阻便用户查询时进行快速查找。 用户进行查询操作时，首先将输入查询提交到网络报务器中，然后通过在索引服 务器中进行查询获得查询结果。另外，为了提高数学搜索引擎的查全率，增加数 学搜索引擎的智能性，也将用户查询提交到计算代数系统c a s ( c o m p u t e r a l g e b r as y s t e m ) 中进行计算处理，同时对这些计算结果也进行壹询操作，并按 计算步骤多少对查询结果进行一定程度降低权重的操作以优化结果返回显示。 2 2 相关背景知识介绍 图2 2m 劬s c 哪h 系统结构囤 2 2 1t e x l a t e x 表示数学公式 七十年代末，d o n a l dek n u t h 开发了第一个高质量的电子捧版系统t e x 。t e x 提供了套功能强大并且十分灵活的排版语言，它多达9 0 0 多条指令，并且t e x 有宏功能用户可以不断地定义自己适用的新命夸来扩展t e x 系统的功能。许 多人利用t e x 提供的宏定义功能对 r e x 进行了二次开发，其中比较著名的有美 兰州大学硕士论文网络数学搜索中的数学查询语言与索引的研究 国数学学会推荐的非常适合于数学家使用的a m s - t e x 以及适合于一般文章、报 告、书籍的l a t e x 系统。l a t e x 是由美国计算机学家l e s l i el a m p o r t 名e 2 0 世纪8 0 年代初期开发，是当今世界上最流行和使用最为广泛的t e x 宏集。t e x 可以看作 是一种专门用来排版的命令语言，l a t e x 实际是t e x 的宏命令。使用l a t e x 基本上 不需要使用者自己设计命令和宏等，因此，即使使用者并不是很了解t e x ，也可 以在短短的时间内生成高质量的文档。和w o r d 等流行的编辑软件比较，l a t e x 在 编排公式时不需考虑公式的位置和公式中字符的大小，l a t e x 会自动的将这些工 作严格按照国际标准给出。即t e x 系统的排版结果d v i ( d e v i c ei n d e p e n d e n t ) 文件与输出设备无关。d v i 文件可以显示、打印、照排，几乎可以在所有的输 出设备上输出。t e x 排版源文件及结果在各种计算机系统上互相兼容。由于具 有以上优势，l a t e x 的广泛应用，目前有很多科技文献中的公式都是用l a t e x 来描 述的。 2 2 2g a t h 地表示数学公式 1 9 9 8 年4 月，w 3 c 的数学工作组发布了基于x m l 语言标准的数学标记语言 m a t h m l1 0 版本，旨在解决数学表达式在w e b 中的传送、接收和处理，是计算机 之间交换数学信息的基本标准。m a t h m l 完全采用x m l 的定义规范，继承了x m l 的大部分优点，具有强大的数学公式表达能力。2 0 0 1 年2 月，w 3 c 公布了m a t h m l 2 0 标准，扩展了m a t h m l1 0 的符号集，改进了m a t h m l 与一些w 3 c 技术的集成。 m a t h m l 用于描述数学公式的结构和内容，它的出现使数学公式不仅可以在 w e b 上建立与传输，而且可以在其它应用程序中实现再利用和转换，满足用户对 数学公式的各种处理需求。m a t h m l 提供两种描述数学公式的标记：p r e s e n t a t i o n 标记和c o n t e n t 标记。 p r e s e n t a t i o n 标记大约有3 0 个，附带5 0 多种属性，主要目的是用来描述抽象数 学符号的二维结构，相当于一个数学符号构造器，把数学符号的语法结构表现出 来。如 标记表示该表达式是线性方向的， 标记表示上标符号， 表示下标符号。每一个表现标记都对应着唯一的一种符号模式，如一行、 上标或下标等。 下面我们用一个例子来说明如何使用m a t h m l 标记来描述数学表达式。 1 1 兰州大学硕士论文网络数学搜索中的数学查询语言与索引的研究 数学表达式为：而，对应的p r c s e n t a t i o n 标记如下： c o n t e n t 标记大约有1 2 0 个，其中大部分是空标记，附带的属性只有简单的1 2 种。如 标记主要用来对某个表达式应用一种运算操作，也可以生成一个 新的数学对象。上面的例子= 再了也可以使用c 。n t e n t 标记描述，如下所示： p r e s e n t a t i o n 标记和c o n t e n t 标记都可以完整地描述任何一个数学公式，但是它 们的侧重点不同：前者用来描述数学表达式的二维布局结构，它更注重表达式的 显示方式；后者描述用于计算和处理的数学信息，它更关注表达式的内在含义。 p r e s e n t a t i o n 标记和c o n t e n t 标记使得w e b 中的数学信息不仅是机器能读的，而 且是机器能理解的。为了同时从结构和语义两方面描述一个数学对象，二者还可 交叉使用形成混合编码，但不能相互替代。 近些年来，诸如a m a y a 、m o z i l l a 、n e t s c a p e 等浏览器都陆续实现了对m a t h m l 的内部支持。微软的i n t e r n e te x p l o r e r 在安装了m a t h p l a y e r 插件后也可以识 m a t h m l 。m a t h m l 有很多针对网络应用的优势，比如它使用文本方式，比映像 1 2 兰州大学硕士论文网络数学搜索中的数学查询语言与索引的研究 图的方式更节省存储空间，减少了对网络传输速度的影响，而且因为它是x m l 的一种应用，所以继承了x m l 的大部分优点。随着互联网的发展和m a t h m l 标 准的完善，m a t h m l 将成为w e b 应用上最重要的数学公式标准，并在各学科领域 内得到广泛的应用。 2 2 30 p e n 姚t h 表示数学公式 o p e n m a t h 是一个建议用来开发一系列语义丰富的数学对象表示标准的计划， 这些标准允许程序之间对这些对象进行交互通讯、允许数学对象在知识库中的存 储以及在w e b 上的发布。o p e n m a t h 最早由欧洲数学家所提出，发展到现在，已经 形成了一个国际性的o p e n m a t h 团体。该团体提出了一个数学对象的电子表示标 准，动机很明确：使用电子发布的数学信息十分匾乏，计算机程序中数学对象之 间的交流效率非常低下，因此十分有必要建立“一个表示数学对象的标准，以支 持它们在程序之间进行交互，保存在数据库中，或者发布到万维网上 。数学标 记语言( m a t h m l ) 是第一个w 3 c 组织推荐的x m l 语言，与之相似，o p e n m a t h 也是 一种x m l 应用。区别在于，m a t h m l 最初是处理数学对象的显示和交付，而 o p e n - m a t h 则着眼于数学语义或内容。o p e n m a t h 继承了x m l 的固有特征，用 o p e n m a t h 编码的数学对象可以在浏览器中显示、在系统之间交互、在数据库或 文件中进行存储或检索，甚至可以对其数学合理性进行验证。尽管m a t h m l 和 o p e n m a t h 之问具有很强的互补性，但人们更加关心的还是数