• 1

  • 459

数据结构与算法<四>

云哥

关注云计算

2星期前

其他更多java基础文章:
java基础学习(目录)


这系列是根据极客时间《数据结构与算法之美》这个课程做的笔记

本篇目录

  • 广度和深度优先算法
  • BF及RK算法
  • BM算法
  • KMP算法
  • Sunday算法
  • Trie树
  • AC自动机

广度和深度优先算法

广度优先搜索(BFS)

广度优先搜索(Breadth-First-Search)简称BFS,其实是一种“地毯式”层层推进的搜索策略,(先查找离起始顶点最近的,然后是次近的,依次往外搜索)

有三个重要辅助变量visited,queue,prev

  • visited是用来记录已经被访问的顶点,用来避免顶点被重复访问。如果顶点q被访问,那相应的visited[q]会被设被设置为true。
  • queue是一个队列,用来存储已经被访问,但相连的顶点还没被访问的顶点。因为广度优先搜索是逐层访问的,只有把第k层的顶点都访问完成之后,才能访问第k+1层的顶点。当我们访问到第k层的时,要把第k层的顶点记录下来,稍后才能通过第k层来找第k+1层的顶点。
  • prev用来记录搜索路径。当我们从顶点s开始,广度优先搜索到顶点t后,prev数组中存储的就是搜索的路径。不过这个路径是反向存储的,prev[w]存储的是,顶点w是从哪个前驱顶点遍历过来的。

BFS的时间复杂度

时间复杂度:终止顶点t离起始顶点s很远,需要遍历完整个图才能找到。此时每个顶点都要进出一遍队列,每个边也都会被访问一次。

所以广度优先搜索的时间复杂度是O(V+E),V表示顶点的个数,E表示边的个数。 因为,对于一个连通图来讲,一个图中的所有顶点都是连通的,E肯定要大于等于V-1,所以广度优先搜索复杂度也可简写为O(E)

BFS的空间复杂度

空间复杂度:广度优先搜素的空间消耗主要在几个辅助变量visited数组,queue队列,prev数组上。这三个存储空间的大小都不会超过顶点的个数,所以空间复杂度是O(V)

深度优先搜索(DFS)

深度优先搜索(Depth-First-Search)简称。最直观的例子就是走迷宫。 深度优先搜素用的是一种比较著名的算法思想,回溯思想。这种思想解决问题的过程,非常适合用递归来实现。

深度优先搜索代码实现也用到了prev,visited变量以及print()函数,作用于广度优先搜索代码实现里相同。但深度优先搜索代码实现里。有个比较特殊的变量found,他的作用是,当我们已经找到终止顶点t之后,我们就不再递归继续查找了。深度优先搜索找出来的路径,并不是顶点 s 到顶点 t 的最短路径。

 

DFS的时间复杂度

时间复杂度:每条边最多会被访问两次,一次是遍历,一次是回退。所以DFS的时间复杂度是O(E),E表示边的个数。

DFS的空间复杂度

空间复杂度:深度优先搜素算法的消耗内存主要是visited,prev数组和递归调用栈。Visited,prev数组的大小跟顶点的个数V成正比,递归调用栈的最大深度不会超过顶点的个数,所以总的空间复杂度就是O(V)。

更多精讲

图的基本算法(BFS和DFS)

BF及RK算法

字符存储匹配算法是各种编程语言都会提供的字符匹配函数的底层依赖,它可以分为单模式匹配和多模式匹配算法。

单模式匹配:BF算法和RK算法,RK算法是BF算法的改进,它巧妙借助了哈希算法,提升了匹配的效率。

BF算法

  1. BF算法是Brute Force的缩写,中文译作暴力匹配算法,也叫朴素匹配算法。

  2. 两个概念:主串和模式串
    如在字符串A中查找字符串B,则字符串A就是主串,字符串B就是模式串 将主串长度记为n,模式串的长度记作m。因为是在主串中查找模式串,所以n>m

  3. BF算法的思想可概括为:我们在主串中,检查起始位置分别是0,1,2……n-m且长度为m的n-m+1个子串,看有没有更模式串匹配的。

     

  4. 极端情况下,如主串是“aaaaa…aaaaa”,模式串是“aaaab”。每次都比对m个字符,要比对n-m+1次,所以最坏的时间复杂度是O(m*n)

  5. 虽然BF算法时间复杂度很高,但在实际开发中使用的非常常见。

    • 原因1:实际软件开发中,大部分情况下,模式串和主串的长度都不会太长。每次模式串与主串中的子串匹配时,当中途不能遇到匹配的字符的时候,就可以停止,不需要全部对比一次。所以理论上最坏情况时间复杂度是O(m*n),但这更多的是统计意义上的,大部分情况中,这个算法执行的很高效。
    • 原因2:朴素字符串匹配算法思想简单,代码实现也非常简单,简单就意味着不容易出错。工程中,在满足性能要求的前提下,简单是首选,也是常说的KISS(keep it Simple and Stupid)设计原则。

RK算法:

  1. RK算法的全称是Rabin-Karp算法,是两位发明人的名字拼接。是BF算法的升级版
  2. BF算法的问题在于每次检查主串与子串是否匹配,需要依次对比每个字符,所以BF算法的时间复杂就比较高。但引入哈希算法,时间复杂度立即就会降低。
  3. RK算法的思路: 通过哈希算法对主串中的n-m+1个子串分别求哈希值,
    然后逐个于模式串的哈希值比较大小,如果相等就说明有对应的模式串。
  4. 通过哈希算法计算字符的哈希值时,需要遍历子串中的每个字符,这只提供了模式串与子串比较的效率,但整体的效率并没有提高。
  5. 为了提高哈希算法计算子串哈希值的效率,可以通过哈希算法的设计来解决。 假设要匹配的字符串的字符集中只包含k个字符,这就可以用一个k进制数来表示一个子串,这个k进制数转化成十进制,作为子串的哈希值。
  6. 这种哈希算法有个特点,在主串中,相邻两个子串的哈希值的计算公式有一定关系。
  7. 相邻额哈希值计算公式有交集:  
  8. 这个计算过程中,26m-1这部分的计算,我们可以通过查表的访求来提高效率。我们事物计算好 26^0、26^1、26^2、26^3…26^m-1,并且存储在一个长度为 m 的数组中,公式中的“次方”就对应数组的下标。这样直接从数组中取值,从而省去了计算时间。
  9. RK算法的时间复杂度:
    1. 整个RK算法包含两个部分,计算子串哈希值和模式串哈希值与子串哈希值之间的比较。
    2. 第一部分,只需要扫描一遍主串就能计算出所有子串的哈希值了,复杂度是O(n)。
    3. 模式串哈希值与每个子串哈希值之间的比较时间复杂度是O(1),总共需要比较n-m+1个子串的哈希值,所有,这部分的时间复杂度也是O(n)。
    复制代码
    所以RK算法整体时间复杂度就是O(n)
  10. 如果模式串很长,相应的主串中子串也会很长,通过上面的哈希算法计算得到的哈希值就可能很大,如果超过了计算机中整形数据可以表示范围,该如何解决?
    答:我们可以把字符串中每个字母的数字相加,最后得到的和作为哈希值。这种哈希算法产生的哈希值的数据范围就相对要小很多。
  11. 若出现哈希冲突如何解决?
    答:如果两值相等,比较子串中每个字符。

所以,哈希算法中的冲突概率要相对控制得低一些,如果存在大量冲突,就会导致RK算法的时间复杂度退化,效率下降。极端情况下,如果存在大量的冲突,每次都要对比子串和模式串本身,时间复杂度就会退化成O(n*m)。

BM算法

BM(Boyer-Moore)算法,是一种非常高效的字符匹配算法,有实验统计他的性能是著名的KMP算法的3到4倍。BM算法的原理复杂

BM算法的核心思想

将模式串和主串的匹配过程,看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时,BF算法和RK算法的做法是,模式串往后滑动一位,然后从模式串的第一个字符开始重新匹配。

BM算法,本质上就是在寻找当模式串不匹配时,可以将模式串往后多滑动几位多的规律,提高匹配的效率

BM算法原理分析

BM算法包含两部分,分别是

  • 坏字符规则(bad character rule)
  • 好后缀规则(good suffix shift)

坏字符规则:

  1. 在BF,RK规则中,在匹配的过程中,都是按模式串的下标从小到大的顺序,依次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯。

  2. BM算法的匹配顺序比较特别,它是按照模式串下标从大到小的顺序,倒着匹配

  3. 从模式串的末尾往前倒着匹配,当我们发现某个字符没法匹配的时候,这个没有匹配的字符叫做坏字符(坏主串的字符)。

  4. 坏字符c在模式串中查找,发现模式串中并不存在这个字符,即,字符c与模式串中的任何字符都不可能匹配。这个时候就可以将模式串直接往后滑动三位,将模式串滑动到c后面的位置,再次从模式串的末尾字符开始比较。

  5. 这次发现模式串中最后一个字符d,还是无法跟主串中a匹配,但此时不能将模式串往后滑动三位。因为坏字符a在模式串中是存在的,模式串中下标是0的位置也是字符a。

  6. 当反生不匹配时,我们把坏字符对应的模式串中的字符下标记作si。如果坏字符在模式串中存在,我们把这个坏字符在模式串中的下标记作xi。如果不存在记作-1。模式串往后移动的位数就等于si-xi。

  7. 利用坏字符规则,BM算法在最好情况先的时间复杂度非常低,是O(n/m)。

  8. 不过,单纯使用坏字符规则还是不够得,因为根据si-xi计算出来的移动位数,有可能是负数,如主串是aaaaaaaaaaaaaaaa,模式串是baaaa。不但不会向后滑动模式串,还有可能倒退。所以BM算法还需要用到“好后缀规则”。

好后缀规则

  1. 好后缀规则实际上跟坏字符规则的思路很类似。

  2. 将已经匹配的bc叫做好后缀,记作{u}。我们那它在模式串中查找,如果找到了另一个跟{u}相匹配的字串{u},那我们就将模式串滑动到子串{u}与主串中{u}对齐的位置。  

  3. 但模式串中不存在等于{u}的子串时,不能直接将模式串滑动到主串{u}的后面。因为这会导致错过模式串和主串可以匹配的情况。  

  4. 如果好后缀在模式串中不存在可匹配的子串,那么一步步往后滑动模式串的过程中,只要主串中的{u}与模式串有重合,那肯定就无法完全匹配。但是当模式串滑动到前缀与主串中{u}的后缀有重合的时候,并且重合的部分相等的时候,就可能存在完全匹配的情况。  

    所以,针对这种情况,不仅要看好后缀在模式串中,是否有另一个匹配的子串,还要考察好后缀的后缀子串,是否存在跟模式串的前缀子串匹配的。
  5. 所谓某个字符串s的后缀子串,就是最后一个字符跟s对齐的子串,比如abc的后缀子串就包括c,bc。所谓前缀子串,找一个最长并且能跟模式串的前缀子串匹配的,假设是{v},然后将模式串滑动到如图所示的位置。  

好后缀和坏字符选用标准

1. 可以分别计算好后缀和坏字符往后滑动的位数,然后取两个中最大的,作为模式串往后滑动的位数。
2. 如果上面两种情况都不满足,那我们就需要将模式串向后移动到好后缀后面的位置。
复制代码

BM算法代码实现

  1. “坏字符规则”本身不难理解。当遇到坏字符时,要计算往后移动的位数si-xi,其中xi的计算是重点,该如何查找坏字符在模式串中国出现的位置呢?
  2. 如果那坏字符,在模式串中顺序遍历查找,效率低下影响整个算法的性能。使用散列表将模式串中的每个字符及其下标都存在散列表中。这样就可以快速找到坏字符在模式串中的位置了。
  3. 好后缀的处理规则中最核心的内容:
    • 在模式中,查找跟好后缀匹配的另一个子串;
    • 在好后缀的后缀子串中,查找最长的,能跟模式前缀子串匹配的后缀子串;
  4. 引入 suffix 数组,其下标表示后缀子串的长度,而数组里面存储的是与这个后缀子串匹配的另一个子串在模式串中的起始位置。引入另外一个布尔型数组 prefix,来记录模式串的后缀子串是否能匹配其前缀子串。
  1. 我们拿模式串中下标从 0 到 i 的子串(i 可以是 0 到 m-2)与整个模式串,求公共后缀子串。如果公共后缀子串的长度为 k,那我们就记录 suffix[k] = j(j 表示公共后缀子串的起始下标)。如果 j=0,也就说公共后缀子串也是模式串的前缀子串,我们就记录 prefix[k]=true。
    我们把 suffix 数组和 prefix 数组的计算过程,用代码实现出来,就是下面这个样子:
// b 表示模式串,m 表示长度,suffix,prefix 数组事先申请好了
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
  for (int i = 0; i < m; ++i) { // 初始化
    suffix[i] = -1;
    prefix[i] = false;
  }
  for (int i = 0; i < m - 1; ++i) { // b[0, i]
    int j = i;
    int k = 0; // 公共后缀子串长度
    while (j >= 0 && b[j] == b[m-1-k]) { // 与 b[0, m-1] 求公共后缀子串
      --j;
      ++k;
      suffix[k] = j+1; //j+1 表示公共后缀子串在 b[0, i] 中的起始下标
    }
    i
    if (j == -1) prefix[k] = true; // 如果公共后缀子串也是模式串的前缀子串
  }
}
复制代码
  1. 按如下步骤进行匹配判断:
    • 先是匹配整个好后缀是否在模式串中存在,如果存在就后移到这个模式串相同的位置,匹配的方法就是suffix[k] 是否不等于 -1
    • 若整个好后缀不存在,则匹配好后缀子串是否满足有可匹配的前缀子串,匹配方法就是看prefix[k] 是否等于 true
    • 如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串,我们就将整个模式串后移 m 位。

代码实现如下:

// a,b 表示主串和模式串;n,m 表示主串和模式串的长度。
public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
  generateBC(b, m, bc); // 构建坏字符哈希表
  int[] suffix = new int[m];
  boolean[] prefix = new boolean[m];
  generateGS(b, m, suffix, prefix);
  int i = 0; // j 表示主串与模式串匹配的第一个字符
  while (i <= n - m) {
    int j;
    for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
      if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
    }
    if (j < 0) {
      return i; // 匹配成功,返回主串与模式串第一个匹配的字符的位置
    }
    int x = j - bc[(int)a[i+j]];
    int y = 0;
    if (j < m-1) { // 如果有好后缀的话
      y = moveByGS(j, m, suffix, prefix);
    }
    i = i + Math.max(x, y);
  }
  return -1;
}
 
// j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
  int k = m - 1 - j; // 好后缀长度
  if (suffix[k] != -1) return j - suffix[k] +1;
  for (int r = j+2; r <= m-1; ++r) {
    if (prefix[m-r] == true) {
      return r;
    }
  }
  return m;
}
复制代码
  1. 在不考虑效率的情况下,这两个操作都可以用“暴力”的匹配查找方式解决。但若要BM算法的效率高,需要:
    因为好后缀也是模式串本身的后缀子串,所以,可以在模式串和主串正式匹配之前,通过预处理模式串,预先计算好模式串的每个后缀子串。对应的另一一个可匹配子串的位置。

更多精讲

不用找了,学习BM算法,这篇就够了(思路+详注代码)

KMP算法

KMP在学习过程中觉得这两篇讲得更好
从头到尾彻底理解KMP
怎么理解kmp算法中的next数组?

Sunday算法

Sunday算法的思想和BM算法中的坏字符思想非常类似。 差别只是在于Sunday算法在失配之后,是取目标串中当前和模式串对应的部分后面一个位置的字符来做坏字符匹配。

BM算法和Sunday快速字符串匹配算法
【模式匹配】之 —— Sunday算法

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

云计算

459

相关文章推荐

未登录头像

暂无评论