拉宾-卡普算法
字符串匹配 / 维基百科,自由的 encyclopedia
在电脑科学中,拉宾-卡普算法(英语:Rabin–Karp algorithm)或卡普-拉宾算法(Karp–Rabin algorithm),是一种由理查德·卡普与迈克尔·拉宾于1987年提出的、使用散列函数以在文本中搜寻单个模式串的字符串搜索算法单次匹配。该算法先使用旋转哈希以快速筛出无法与给定串匹配的文本位置,此后对剩余位置能否成功匹配进行检验。此算法可推广到用于在文本搜寻单个模式串的所有匹配或在文本中搜寻多个模式串的匹配。
此条目已列出参考文献,但因为没有文内引注而使来源仍然不明。 (2018年9月) |
若要在一段文本中找出单个模式串的一个匹配,此算法具有线性时间的平均复杂度,其运行时间与待匹配文本和模式串的长度成线性关系。虽然平均情况下,此算法表现优异,但最坏情况下,其复杂度为文本长与模式串长的乘积。当在文本中搜寻多个匹配时,其具有线性时间的平均复杂度(与文本串长、模式串长、模式串所有匹配总长三者的和成线性关系)。相对地,另一种用于找出模式串所有匹配的AC自动机算法的最坏情况复杂度与文本串长、模式串长、模式串所有匹配总数(而非总长)成正比。
此算法的一个实际应用为内容相似度检验(英语:content similarity detection)(如论文查重)。在给定原材料与待查重论文的情况下,此算法可以迅速在论文中搜寻原材料中的句子,同时忽略诸如大小写与标点等细节。由于原材料中的字符串过多,故单字符串搜索算法在此处不适用。