带你读《图解算法小抄》二十四、字符串(1)

简介: 带你读《图解算法小抄》二十四、字符串(1)

二十四、字符串


1.Rabin-Karp算法


访问 www.coding-time.cn 阅读原文动画效果,体验更佳。

 

在计算机科学中,Rabin-Karp算法(或Karp-Rabin算法)是一种使用散列(哈希)的字符串搜索算法,由Richard M. Karp和Michael O. Rabin(1987年)创建。

1算法

Rabin-Karp算法通过使用哈希函数加速模式与文本中的子字符串的相等性测试。哈希函数是将每个字符串转换为其哈希值的数值的函数;例如,我们可以有hash('hello') = 5

 

该算法利用了这样一个事实:如果两个字符串相等,则它们的哈希值也相等。因此,字符串匹配(几乎)可以简化为计算搜索模式的哈希值,然后在具有该哈希值的输入字符串的子字符串中寻找匹配。

 

然而,这种方法存在两个问题。首先,由于存在大量不同的字符串和较少的哈希值,一些不同的字符串将具有相同的哈希值。如果哈希值匹配,模式和子字符串可能不匹配;因此,必须通过比较它们来确认搜索模式和子字符串的潜在匹配;对于较长的子字符串,这种比较可能需要很长时间。

 

幸运的是,对于合理的字符串,良好的哈希函数通常不会产生太多冲突,因此期望的搜索时间将是可接受的。

2使用的哈希函数

Rabin-Karp算法的性能关键在于高效计算文本的连续子字符串的哈希值。Rabin指纹是一种流行且有效的滚动哈希函数。

本示例中描述的多项式哈希函数不是Rabin指纹,但它同样有效。它将每个子字符串视为一些基数的数字,基数通常是一个大素数。

3复杂度

对于长度为n的文本和p个总长度为m的模式,其平均和最佳情况下的运行时间为O(n + m),空间复杂度为O(p),但最坏情况下的运行时间为O(n * m)。

4应用

该算法的一个实际应用是检测抄袭。给定源材料,该算法可以快速搜索论文中来自源材料的句子,忽略大小写和标点等细节。由于所寻找的字符串非常丰富,单字符串搜索算法是不实际的。

5参考资料

  • Wikipedia
  • YouTube编辑距离


2.编辑距离


编辑距离(Levenshtein distance)是一种衡量两个序列之间差异的字符串度量。简单地说,编辑距离是将一个字符串转换为另一个字符串所需的最少单字符编辑(插入、删除或替换)次数。

1定义

数学上,两个字符串 a 和 b(长度分别为 |a| 和 |b|)之间的编辑距离由下式给出:

image.png 其中, image.png 是指示函数,当image.png 时等于 0,否则等于 1, 而 image.png 是字符串 a 的前 i 个字符和字符串 b 的前 j 个字符之间的距离。

 

注意,最小值中的第一个元素对应删除(从 a 到 b),第二个元素对应插入,第三个元素对应匹配或不匹配,具体取决于相应的符号是否相同。

2示例

例如,字符串 kitten 和 sitting 之间的编辑距离为 3,因为以下三个编辑操作将一个字符串变成另一个字符串,而没有办法少于三个编辑操作:

 

  • kitten → sitten(用 "s" 替换 "k")
  • sitten → sittin(用 "i" 替换 "e")
  • sittin → sitting(在末尾插入 "g")。

3应用

编辑距离在许多应用中都有广泛的应用,例如拼写检查器、光学字符识别纠错系统、模糊字符串搜索以及基于翻译记忆的自然语言翻译辅助软件。


带你读《图解算法小抄》二十四、字符串(2)https://developer.aliyun.com/article/1347818?groupCode=tech_library

相关文章
|
3月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
1月前
|
算法
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
63 1
两个字符串匹配出最长公共子序列算法
|
3月前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
|
4月前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
268 1
|
4月前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
115 1
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
3月前
|
算法 C++
惊爆!KPM算法背后的秘密武器:一行代码揭秘字符串最小周期的终极奥义,让你秒变编程界周期大师!
【8月更文挑战第4天】字符串最小周期问题旨在找出字符串中最短重复子串的长度。KPM(实为KMP,Knuth-Morris-Pratt)算法,虽主要用于字符串匹配,但其生成的前缀函数(next数组)也可用于求解最小周期。核心思想是构建LPS数组,记录模式串中每个位置的最长相等前后缀长度。对于长度为n的字符串S,其最小周期T可通过公式ans = n - LPS[n-1]求得。通过分析周期字符串的特性,可证明该方法的有效性。提供的C++示例代码展示了如何计算给定字符串的最小周期,体现了KPM算法在解决此类问题上的高效性。
74 0
|
4月前
|
算法 Java
KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用
|
5月前
|
存储 算法 Java
Java数据结构与算法:用于高效地存储和检索字符串数据集
Java数据结构与算法:用于高效地存储和检索字符串数据集
|
5月前
|
算法 Java
Java数据结构与算法:字符串匹配算法之暴力匹配
Java数据结构与算法:字符串匹配算法之暴力匹配
|
5月前
|
算法 Java
Java数据结构与算法:字符串匹配算法之KMP算法
Java数据结构与算法:字符串匹配算法之KMP算法