10.3778/j.issn.1673-9418.1609018
基于分割的字符串相似性查找算法
字符串相似性查找问题主要包括两方面,基于阈值的字符串相似性查找以及top-k字符串相似性查找.目前处理基于阈值的字符串相似性查找问题的算法多是基于过滤-验证框架的.基于该框架提出了PB-search算法,算法在过滤阶段首次加入One-Off条件过滤掉大量的无效匹配,并在验证阶段提出了一种新的验证算法MultiThreshold算法,大大减少了计算编辑距离的次数.在top-k字符串相似性查找问题方面,提出了两种基于分割思想的算法,Pb-topk算法和PbCount-topk算法.其中,Pb-topk算法采用差值递增的策略,减少了需处理的字符串数目;PbCount-topk算法采用匹配数目划分的策略,进一步缩小了候选集的规模.最后,通过在3个真实数据集上的实验结果,验证了提出算法的高效性.
字符串相似性查找、阈值、top-k、分割、编辑距离
12
TP301(计算技术、计算机技术)
The National Natural Science Foundation of China under Grant Nos.61202227,61602004
2018-01-22(万方平台首次上网日期,不代表论文的发表时间)
共14页
120-133