论文部分内容阅读
基于编辑距离的字符串近似查询算法一般是先给定阈值k，然后计算那些与查询串的编辑距离小于或等于忌的结果。但是对于近似子串查询，结果中有很多是交叠的，并且是无意义的，于是提出了一种局部最优化匹配的概念，只计算那些符合阈值条件，并且是局部最优的结果，这样不仅避免了结果的交叠，而且极大节省了时间开销。给出了支持局部最优化匹配的近似子串查询的定义，相应提出了一种基于gram索引的局部最优化近似子串查询算法，分析了子串近似匹配过程中的规律，研究了基于局部最优化匹配的边界限定和过滤策略，给出了一种过滤优化的局部最优化近