一种基于层次索引的数学表达式检索方法

摘要

本发明提供了一种基于层次索引的数学表达式检索方法。该方法基于事先建立好的索引来实现。索引建立的过程包括对LaTeX格式的数学表达式进行解析，形成表达式的哈希值层次结构树，通过插入结点构造Treap树，形成KP映射索引层和倒排索引层。检索时，用户输入的LaTeX格式数学表达式被以同样的方式解析及形成哈希值层次结构树，再从索引的KP映射索引层和倒排索引层中进行检索，实现对数学表达式的精确检索或同构检索。本发明采用双层索引结构，兼顾了数学表达式信息的完整性和检索的效率与功能，具有较丰富的检索模式和较高的检索效率。本发明受国家自然科学基金资助（项目批准号：61375075）。

主权项

一种基于层次索引的数学表达式检索方法，其特征是，包括如下步骤：a、将待检索的数学表达式以LaTeX格式表示，数学表达式中的运算符和运算数均称为节点；b、对LaTeX式进行解析，得出表达式中每一节点所在的层次；表达式中第一个节点所在的层次为第一层；引起节点层次发生变化的节点称为触发点，由触发点所引起的层次发生了变化的节点所在的层次为相应触发点所在层次的下一层；c、根据表达式中每一节点所在的层次，将数学表达式以层次结构树的形式表示；将层次结构树中的第一层设为主层次；d、计算主层次中所有节点构成的节点串的哈希值，并将其作为主层次的键值；计算主层次中所有运算符节点构成的节点串的哈希值，并将其作为主层次的优先值；同时提取数学表达式的层次结构树中每一层中的运算符编码串和运算数编码串；e、将主层次的键值、优先值以及主层次中的运算符编码串和运算数编码串均插入层次结构树的主层次中，将除主层次以外的其他层次中的运算符编码串和运算数编码串插入对应的层次中，形成数学表达式的哈希值层次结构树；f、根据数学表达式的哈希值层次结构树，从预先建立的索引中进行精确检索或同构检索；所述预先建立的索引包括KP映射索引层和倒排索引层；所述KP映射索引层是通过插入若干结点而构成的Treap树结构，在Treap树中，每一结点是由数学表达式主层次的键值和优先值组成的；所述倒排索引层包括与Treap树中每一结点所对应的数学表达式的哈希值层次结构树；从预先建立的索引中进行精确检索，具体为：将待检索数学表达式的主层次的键值和优先值作为目标键值和优先值；从KP映射索引层中找到包含目标键值和优先值的结点，并从倒排索引层中找到与该结点对应的数学表达式的哈希值层次结构树；将待检索数学表达式的哈希值层次结构树与从倒排索引层中找到的数学表达式的哈希值层次结构树从主层次开始逐层进行对比，若每一层中的运算符编码串、运算数编码串及触发点均对应相同，则检索成功，否则检索失败；从预先建立的索引中进行同构检索，具体为：将待检索数学表达式的主层次的优先值作为目标优先值；从KP映射索引层中找到包含目标优先值的结点，并从倒排索引层中找到与该结点对应的数学表达式的哈希值层次结构树；将待检索数学表达式的哈希值层次结构树与从倒排索引层中找到的数学表达式的哈希值层次结构树从主层次开始逐层进行对比，每一层进行对比时仅比较触发点及运算符编码串，某一层对比结果相同，则该层匹配成功；若主层次没有匹配成功，则检索失败；在主层次匹配成功后，其他层次匹配的层数越多，则对应表达式与待检索表达式的结构相似度越高，最后将主层次匹配成功的所有与待检索表达式的结构具有相似度的表达式均作为检索结果。