论文部分内容阅读
模糊查询技术解决了用户检索网络信息的困难,其核心思想主要是编辑距离算法。编辑距离是A.Leveshtein于1966年提出的,用于校验字符串或文本之间的相似程度,或视为将一个字符串通过原子变化为另一个字符串所需要的最小代价,其在模糊查询领域有着广泛的应用。编辑距离算法在求解两个字符串的相似问题时只考虑了编辑操作次数,而没有考虑字符串之间的公共子串对相似度的影响;在求解回溯路径时,并不能完全匹配出全部字符串变化步骤的可能性。针对这些问题,提出了基于改进编辑距离的字符串相似度求解算法,其中改进了字符串相似度度量公式及Levenshtein矩阵计算方法。在计算编辑距离时,以原有矩阵求出两字符串的最长公共子串,借鉴线性空间求NAKATSU算法求解全部回溯路径的思想,定义适合新LD矩阵求全部回溯路径的算法。实验采用智能ABC作为词典库,选取一个单词作为源串,一组与源串不同程度相似的单词作为目标串,把新相似度度量公式与现有的字符串相似度计算方法进行比较。基于动态规划的思想,在计算矩阵每一行时,会把每一行的最小值和文章定义的搜索强度值做比较,如果不满足一定条件则提前跳出矩阵,在某些特定情况下,该需求是有必要的。新公式与检索工具Lucene工具包的FuzzyQuery类做比较,减少了进入胜者表的目标串数,相似度的样本极差和标准差分别为0.331和0.150。实验结果表明改进的算法在不改变空间复杂度的情况下,计算字符串相似度的准确性更高,且查询方式更灵活。