Rubin's Blog

  • 首页
  • 关于作者
  • 隐私政策
享受恬静与美好~~~
分享生活的点点滴滴~~~
  1. 首页
  2. 数据结构和算法
  3. 正文

算法之字符串匹配

2022年 1月 5日 773点热度 0人点赞 0条评论

字符串匹配这个功能,是非常常见的功能,比如"Hello"里是否包含"el"?

Java里用的是indexOf函数,其底层就是字符串匹配算法。主要分类如下:

BF算法

原理

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

这种算法的字符串匹配方式很“暴力”,当然也就会比较简单、好懂,但相应的性能也不高

比方说,我们在字符串 A 中查找字符串 B,那字符串 A 就是主串,字符串 B 就是模式串

我们在主串中,检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串,看有没有跟模式串匹配的

代码实现

package com.rubin.algorithm.charsetmatch;

/**
 * 暴力匹配算法,也叫朴素匹配算法
 * 我们每次都比对 m 个字符,要比对 n-m+1 次,所以,这种算法的最坏情况时间复杂度是 O(n*m)
 * m:为匹配串长度
 * n:为主串长度
 */
public class BruteForce {

    public static boolean isMatch(String origin, String match) {
        for (int i = 0; i <= (origin.length() - match.length()); i++) {
            if (origin.substring(i, i + match.length()).equals(match)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isMatch("ccaaac", "caaac"));
        System.out.println(isMatch("ccaaac", "abc"));
    }

}

RK算法

原理

RK 算法的全称叫 Rabin-Karp 算法,是由它的两位发明者 Rabin 和 Karp 的名字来命名的

每次检查主串与子串是否匹配,需要依次比对每个字符,所以 BF 算法的时间复杂度就比较高,是O(n*m)。我们对朴素的字符串匹配算法稍加改造,引入哈希算法,时间复杂度立刻就会降低

RK 算法的思路是这样的:我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等,那就说明对应的子串和模式串匹配了(这里先不考虑哈希冲突的问题)。因为哈希值是一个数字,数字之间比较是否相等是非常快速的,所以模式串和子串比较的效率就提高了

代码实现

package com.rubin.algorithm.charsetmatch;

/**
 *  Rabin-Karp 算法
 *
 *  RK 算法的思路是这样的:我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式
 * 串的哈希值比较大小。如果某个子串的哈希值与模式串相等,那就说明对应的子串和模式串匹配了(这
 * 里先不考虑哈希冲突的问题)。因为哈希值是一个数字,数字之间比较是否相等是非常快速的,所以模
 * 式串和子串比较的效率就提高了
 *
 * T = O(m+n)
 * m:为匹配串长度
 * n:为主串长度
 *
 * 适用于匹配串类型不多的情况,比如:字母、数字或字母加数字的组合 62 (大小写字母+数字)
 */
public class RabinKarp {

    public static boolean isMatch(String origin, String match) {
        int matchhash= str2hash(match);
        for (int i = 0; i <= (origin.length() - match.length()); i++) {
            if (matchhash == str2hash(origin.substring(i, i + match.length()))) {
                return true;
            }
        }
        return false;
    }

    private static int str2hash(String str) {
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            hash *= 26;
            hash += (str.charAt(i) - 97);
        }
        return hash;
    }

    public static void main(String[] args) {
        System.out.println(isMatch("ccaaac", "caaac"));
        System.out.println(isMatch("ccaaac", "abc"));
    }

}

BM算法

原理

BF 算法性能会退化的比较严重,而 RK 算法需要用到哈希算法,而设计一个可以应对各种类型字符的哈希算法并不简单

BM(Boyer-Moore)算法。它是一种非常高效的字符串匹配算法,滑动算法

在这个例子里,主串中的 c,在模式串中是不存在的,所以,模式串向后滑动的时候,只要 c 与模式串有重合,肯定无法匹配。所以,我们可以一次性把模式串往后多滑动几位,把模式串移动到 c 的后面

BM 算法,本质上其实就是在寻找这种规律。借助这种规律,在模式串与主串匹配的过程中,当模式串和主串某个字符不匹配的时候,能够跳过一些肯定不会匹配的情况,将模式串往后多滑动几位

BM 算法包含两部分,分别是坏字符规则(bad character rule)和好后缀规则(good suffix shift)

  • 坏字符规则

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

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

字符 c 与模式串中的任何字符都不可能匹配。这个时候,我们可以将模式串直接往后滑动三位,将模式串滑动到 c 后面的位置,再从模式串的末尾字符开始比较

坏字符 a 在模式串中是存在的,模式串中下标是 0 的位置也是字符 a。这种情况下,我们可以将模式串往后滑动两位,让两个 a 上下对齐,然后再从模式串的末尾字符开始,重新匹配

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

第一次移动3位

c在模式串中不存在,所以 xi = -1,移动位数 n = 2 - (-1) = 3

第二次移动2位

a在模式串中存在,所以 xi = 0,移动位数 n = 2 - 0 = 2

  • 好后缀规则

我们把已经匹配的我们拿它在模式串中查找,如果找到了另一个跟{u}相匹配的子串{u},那我们就将模式串滑动到子串{u}与主串中{u}对齐的位置

如果在模式串中找不到另一个等于{u}的子串,我们就直接将模式串,滑动到主串中{u}的后面,因为之前的任何一次往后滑动,都没有匹配主串中{u}的情况

过度滑动情况:

当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候,并且重合的部分相等的时候,就有可能会存在完全匹配的情况

所以,针对这种情况,我们不仅要看好后缀在模式串中,是否有另一个匹配的子串,我们还要考察好后缀的后缀子串(c),是否存在跟模式串的前缀子串(c)匹配的

如何选择坏字符和好后缀:我们可以分别计算好后缀和坏字符往后滑动的位数,然后取两个数中最大的,作为模式串往后滑动的位数

代码实现

坏字符:

如果我们拿坏字符,在模式串中顺序遍历查找,这样就会比较低效

可以采用散列表,我们可以用一个256数组,来记录每个字符在模式串中的位置,数组下标可以直接对应字符的ASCII码值,数组的值为字符在模式串中的位置,没有的记为-1

bc[97]=a

bc[98]=b

bc[100]=d

有重复的字母以后面的位置为准

package com.rubin.algorithm.charsetmatch;

/**
 * BM(Boyer-Moore)算法。它是一种非常高效的字符串匹配算法,滑动算法.
 * 我们本例只讲解坏字符算法
 *
 * T = O(N/M)
 * n:主串长度
 * m:模式串长度
 */
public class BoyerMoore {

    private static final int[] BC = new int[256];

    private static void generateBC(String match) {
        // 这里只负责处理英文字母 不负责汉字 空字符的处理
        char[] chars = match.toCharArray();
        for (int i = 0; i < BC.length; i++) {
            BC[i] = -1;
        }
        for (int i = 0; i < chars.length; i++) {
            int ascii = chars[i];
            BC[ascii] = i;
        }
    }

    public static int isMatch(String origin, String match) {
        generateBC(match);
        char[] originChars = origin.toCharArray(),
                matchChars = match.toCharArray();
        int m = originChars.length, n = matchChars.length;
        int i = 0;
        while (i <= (m - n)) {
            int j;
            for (j = n - 1; j >= 0; j--) {
                if (matchChars[j] != originChars[i + j]) {
                    break;
                }
            }
            if (j < 0) {
                return i;
            }
            i = i + (j - BC[originChars[i + j]]);
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(isMatch("ccaaac", "caaac"));
        System.out.println(isMatch("ccaaac", "abc"));
    }

}

应用

BM算法比较高效,在实际开发中,特别是一些文本编辑器中,用于实现查找字符串功能

Trie树

原理

Trie 树,也叫“字典树”。它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题

比如:有 6 个字符串,它们分别是:how,hi,her,hello,so,see,我们可以将这六个字符串组成Trie树结构

Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起

其中,根节点不包含任何信息。每个节点表示一个字符串中的字符,从根节点到红色节点的一条路径表示一个字符串(红色节点为叶子节点)

Trie树的插入

Trie树的查找

当我们在 Trie 树中查找一个字符串的时候,比如查找字符串“her”,那我们将要查找的字符串分割成单个的字符 h,e,r,然后从 Trie 树的根节点开始匹配。如图所示,绿色的路径就是在 Trie 树中匹配的路径

Trie 树是一个多叉树

我们通过一个下标与字符一一映射的数组,来存储子节点的指针

假设我们的字符串中只有从 a 到 z 这 26 个小写字母,我们在数组中下标为 0 的位置,存储指向子节点a的指针,下标为 1 的位置存储指向子节点 b 的指针,以此类推,下标为 25 的位置,存储的是指向的子节点 z 的指针。如果某个字符的子节点不存在,我们就在对应的下标的位置存储 null

当我们在 Trie 树中查找字符串的时候,我们就可以通过字符的 ASCII 码减去“a”的 ASCII 码,迅速找到匹配的子节点的指针。比如,d 的 ASCII 码减去 a 的 ASCII 码就是 3,那子节点 d 的指针就存储在数组中下标为 3 的位置中

代码实现

package com.rubin.algorithm.charsetmatch;

/**
 * Trie 树,也叫“字典树”。它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题
 * 本示例只处理a-z26个英文字母
 *
 * 如果要在一组字符串中,频繁地查询某些字符串,用 Trie 树会非常高效。构建 Trie 树的过程,需要扫
 * 描所有的字符串,时间复杂度是 O(n)(n 表示所有字符串的长度和)。但是一旦构建成功之后,后续的
 * 查询操作会非常高效。每次查询时,如果要查询的字符串长度是 k,那我们只需要比对大约 k 个节点,
 * 就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说,构建好 Trie 树后,在其中
 * 查找字符串的时间复杂度是 O(k),k 表示要查找的字符串的长度
 */
public class TrieTree {

    private TrieNode root;

    public TrieTree() {
        root = new TrieNode('/');
    }

    static class TrieNode {
        char data;
        TrieNode[] children;
        boolean isLeaf;

        public TrieNode(char data) {
            this.data = data;
            children = new TrieNode[26];
            isLeaf = false;
        }
    }

    public void insert(String text) {
        char[] textChars = text.toCharArray();
        TrieNode p = root;
        for (int i = 0; i < textChars.length; i++) {
            int j = textChars[i] - 97;
            if (p.children[j] == null) {
                p.children[j] = new TrieNode(textChars[i]);
            }
            p = p.children[j];
        }
        p.isLeaf = true;
    }

    public boolean isMatch(String pattern) {
        char[] patternChars = pattern.toCharArray();
        TrieNode p = root;
        for (int i = 0; i < patternChars.length; i++) {
            int j = patternChars[i] - 97;
            if (p.children[j] == null) {
                return false;
            }
            p = p.children[j];
        }
        if (p.isLeaf == false) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        TrieTree trieTree = new TrieTree();
        trieTree.insert("hello");
        trieTree.insert("her");
        trieTree.insert("hi");
        trieTree.insert("how");
        trieTree.insert("see");
        trieTree.insert("so");
        System.out.println(trieTree.isMatch("ho"));
        System.out.println(trieTree.isMatch("how"));
        System.out.println(trieTree.isMatch("howw"));
    }

}

典型应用

利用 Trie 树,实现搜索关键词的提示功能

以上就是本文的全部内容了。欢迎小伙伴们积极留言交流~~~

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 数据结构和算法
最后更新:2022年 6月 9日

RubinChu

一个快乐的小逗比~~~

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复
文章目录
  • BF算法
    • 原理
    • 代码实现
  • RK算法
    • 原理
    • 代码实现
  • BM算法
    • 原理
    • 代码实现
    • 应用
  • Trie树
    • 原理
      • Trie树的插入
      • Trie树的查找
    • 代码实现
    • 典型应用
最新 热点 随机
最新 热点 随机
问题记录之Chrome设置屏蔽Https禁止调用Http行为 问题记录之Mac设置软链接 问题记录之JDK8连接MySQL数据库失败 面试系列之自我介绍 面试总结 算法思维
RocketMQ之集群与运维 Redis之核心原理 自定义简单的RPC框架 算法思维 Netty进阶 SpringCloud之微服务统一认证方案

COPYRIGHT © 2021 rubinchu.com. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

京ICP备19039146号-1