数学公式排序算法.ppt

数学公式排序算法,-初步探讨,排序要解决的问题,1. 用户查询公式与文档中公式的相关度（匹配程度）。 2. 文档本身质量的衡量,搜索过程中存在的问题,1. a+b 和 b+a 应该都要返回 2. x+y 和 a+b 等价公式不同变量标示符的返回 3. 完全匹配和部分匹配的如何返回？,一、数学公式的特点,1. 数学公式组成 数学公式主要由运算关系、运算、运算因子、标准函数(普通函数不含在内)、边界符等特征项构成。 运算关系包括：大于、小于、等于、约等于等等； 运算包括：求和、求商、求积、求积分、求微分、求解、各种变换(拉式变换)等； 运算因子：指要进行某种运算的数学表达式。运算因子可以分解，并包括特殊运算因子，如：矩阵、向量、数列等； 标准函数：高等数学中定义的标准函数，包括三角函数、反三角函数、对数函数等等； 边界符：指揭示运算逻辑关系或运算层级关系的符号，如大括号、中括号、括号等等。 变量标识符,对于以上特征除变量标识符和常量之外，其余都是有限的可以统计的。 数学公式的精髓：要表达的某种运算，运算是数学公式的关键特征。表征运算的符号 重要性 大于表征参与运算的变量和常量。 eg. a+b 和 x+y 其本质上没有区别,只是选取的变量不同。 因此描述和分析一个数学公式，需要以关键特征- 运 算为主线。 eg. 积分运算是一级关键特征，加法是二级关 键特征。 基于以上分析-基于特征向量空间的检索模型,基于特征向量空间的检索模型,1.表征运算的符号和表征参与运算的变量和常量视作不同的两类。 2.表征运算的符号有限，可构成一个空间。 3.具体实施过程。 eg. 如果将上述公式中所有的表征运算的符号作为一个向量的分量，而用所有的表征变量和常量的符号作为另一个向量的分量，用这样的向量空间描述：,基于特征向量空间的检索模型,向量空间 其中： 若每一个公式都按以上的表示方式表示，则公式库就是由以上相关的两个向量构成的向量集。然后对向量集进行分类，生成若干个不同类的向量集。在与数据库中的数学公式向量集对比时，首先对比高维向量i，如果该数学公式向量集中的高维向量中不包含积分号，则可以直接跳过该向量集，无需进行向量j的比较。,基于特征向量空间的检索模型,假如用户输入的数学公式对应的向量是： 其中： 将a,b的分量一次设为： 如果 则 否则为1；依此规则一一对比下去，这样a,b的距离就可以定义为：,基于特征向量空间的检索模型,显然如果I为0,则两个向量相同，返回该公式，设置一个合适的阈值M, 如果I处在（0，M）之间，认为他们相似，也将按相似程度按顺序返回公式。如果大于M，则认为两个向量完全不同，不返回该公式。 问题： 1. 如何对比？ 2. 运算符号和变量符号都相同但是二维布局不同的公式视作是同一个公式。如(x+2)/y和y/(x+2)。,公式权重法,MathDex提出N-grams匹配方法以提高精确度。在索引建立阶段，不仅为每个公式建立索引，同时记录其子公式出现的频率信息。 MathDex存储表达式的不同部分以进行并行查询，从方程不同部分匹配到的项具有不同的权重。不同公式可具有分子域、上标域、行域等。输入公式被解析，定义合适的域，然后查询被重写，在所选择领域匹配子项。越多子项匹配，相关度越高。,公式权重法,在MIaS(Math Indexer and Searcher)系统中也同样提出为公式在建立索引时分配一定的权值。在该系统中，在公式建立索引之前要对公式进行一系列处理如：排序，变量统一，常量统一等。其权重的计算依赖于处理过程的复杂度和子公式所处的位置。,MathWebSearch,1.正在做代码注释 2.存入数据库的数据结构 3.查询返回过程 4.欢迎有兴趣的人和我探讨,