论文部分内容阅读
随着互联网的发展和普及,信息已实现了全球的共享与交互。目前,文本已成为人们使用最频繁、最广泛的信息载体,但大量的文本信息使得个人的接受能力严重超载。如何从这些文本信息中快速、准确地获取最需要的内容一直是计算机技术研究中的基础问题。近似串匹配技术是最直接的解决方法,它能从一个较长的文本串中找出与给定模式串近似程度满足一定要求的所有子串,它在文本检索、生物信息学、信号处理、入侵检测等领域有着广泛的应用。因此,研究提高近似串匹配速度的相关技术在实际应用中具有深远的意义。本文主要研究基于q-gram过滤的近似串匹配技术。通过细致分析存在匹配串的匹配区域,从匹配区域中提取了多个新特征。由此本文中提出了四个近似串匹配无损过滤算法,即一个全局匹配算法和三个局部匹配算法。本文的主要内容如下:1)提出一种基于q-gram命中特征的近似串全局匹配算法。通过对模式串和文本串进行等大小的逻辑分块,从分块中提取了三个q-gram命中新特征,即q-gram命中的均匀性、有效q-gram命中的区域性和去除冗余q-gram命中的无影响性。新算法过滤阶段中采用了新的过滤区选择方案,同时使用新特征优化后的过滤准则对过滤区进行过滤。实验结果显示,新算法在过滤过程中获得了较高的过滤效率,且新算法受匹配错误率的影响较小,整体性能较好,新算法是一个适合各种匹配错误率的近似串全局匹配算法。2)提出一种基于对角线特征的近似串局部匹配算法。通过分析二个编辑距离不大于k的字符串的编辑距离矩阵,从中提取了三个对角线新特征,即编辑路径所跨有效对角线总数特征、编辑路径上有效对角线q-gram命中总数特征和单条对角线q-gram命中数特征。新算法的过滤阶段中利用新对角线特征进行过滤区选择,同时采用新对角线特征优化后的过滤准则对过滤区进行过滤。实验结果显示,与QUASAR算法和SWIFT算法相比,新算法获得了最高的过滤效率,新算法较适合匹配错误率较低,且窗口长度较短的近似串局部匹配。3)提出了一种基于二次过滤的近似串局部匹配算法。通过对经典的KS1算法过滤思想和q-gram命中数过滤技术的细致分析,提出了一种结合KS1算法和q-gram命中数过滤的过滤方案。新算法的过滤阶段中包含二次过滤,第一次过滤为种子过滤,抛弃了所有不含种子的文本区域,第二次过滤为q-gram命中数过滤,抛弃了那些虽然含有种子但q-gram命中数不满足条件的文本区域。实验结果显示,与其他算法相比,新算法在较短的过滤时间内获得了最高的过滤效率,新算法是一个适合不同窗口长度、不同匹配错误率的近似串局部匹配算法。4)提出了一种基于连续匹配块的近似串局部匹配算法。通过对查询串和文本串进行等大小的逻辑分块,从分块中提取了一个连续匹配块特征,即含有匹配串的匹配区域中至少包含一个z连续匹配块。新算法的过滤阶段中利用连续匹配块特征进行过滤区选择,并采用基础q-gram过滤定理对过滤区进行过滤。实验结果显示,与其他算法相比,新算法在更短的过滤时间内就获得了较高的过滤效率,新算法是一个适合不同窗口长度、不同匹配错误率的近似串局部匹配算法。