基于匹配区域特征的相似字符串匹配过滤算法.docx

基于匹配区域特征的相似字符串匹配过滤算法
一、概述
相似字符串匹配是计算机领域中一个经典的问题，主要应用在信息检索、文本编辑、生物信息学等领域。本文主要介绍一种基于匹配区域特征的相似字符串匹配过滤算法，该算法基于字符串的局部匹配来实现快速的相似字符串匹配。
二、问题描述
在实际应用中，为了提高查询效率，需要对查询文本进行过滤，将不符合要求的文本筛选出来，只留下符合要求的文本进行进一步处理。相似字符串匹配问题属于其中一种过滤问题，在大规模数据中查找出和给定字符串相似的字符串，由于大规模数据和字符串长度不确定，这种问题是一种NP难问题。
三、相关算法
传统字符串匹配算法有朴素算法、KMP算法、Boyer-Moore算法等。这些算法都是通过遍历字符串的每个字符来实现的，虽然在一定程度上提高了时间复杂度，但是对于大规模数据来说仍然存在效率问题。
四、基于匹配区域特征的相似字符串匹配过滤算法
基本思路：通过字符串的局部匹配来实现快速的相似字符串匹配，实现原理主要包括字符串特征提取、相似特征匹配和过滤器构建三个主要步骤。
1、字符串特征提取
将相似字符串抽象成由若干个字符组成的序列，每个字符可以看作为该序列中的一个节点。获取该序列的特征向量x，该向量包含了不同阈值下的字符串相似度判断的指标。
2、相似特征匹配
使用余弦相似度来度量两个字符串的相似度。计算机匹配过程可归纳为以下几个步骤：
（1）对输入字符串进行相似度特征向量提取
（2）对数据库中的每个字符串进行相似度特征向量提取，依次进行匹配计算
（3）计算余弦相似度，如果相似度大于提前定义的匹配度阈值，则判定为相似字符串
3、过滤器构建
基于相似特征匹配得到的结果，构建一个过滤器用于数据的过滤，将相似字符串筛选出来。结果可进一步优化引入布隆过滤器来快速检测字符串是否是数据库的真正成员。
五、实验结果
在实验中，我们使用了一个由20个字符串组成的数据库进行测试，并将输入字符串的相似度阈值设定为0.9。实验结果显示，使用基于匹配区域特征的相似字符串匹配过滤算法，在大规模数据中查找出相似字符串的时间复杂度大大降低，达到了优秀的查询效率，并可以节省大量的计算资源。
六、结论
本文介绍了一种基于匹配区域特征的相似字符串匹配过滤算法，该算法通过字符串的局部匹配来实现快速的相似字符串匹配，实验结果表明该算法查询效率高且能够节省计算资源，是一种较好的相似字符串匹配算法。