KPM算法快速检索文本

2023-12-26 11:09:31

说到检索文本java的String.indexOf,方法其实已经性能很不错了,contains方法其实也是调用了indexOf方法,所以一般情况下使用contains方法也是完全够用的,简单了解了一下indexOf的原理

String.indexOf

在 Java 1.8 中,String 类的 indexOf 方法主要使用的是经过优化的朴素字符串匹配算法(Naive String Matching Algorithm)。这个算法是一种简单但有效的字符串搜索算法,它在每一步比较字符串中的字符,并在不匹配时按步骤移动。Java 的 indexOf 方法结合了一些额外的优化,例如朴素算法的预处理和 Boyer-Moore 算法的一些思想,以提高性能。

  1. 朴素算法: 从头到尾逐个比较字符,如果发现不匹配,将字符串向前移动一位重新比较。这是一种简单但不是最高效的算法。

  2. 预处理: 预处理目标字符串,构建一个部分匹配表(Partial Match Table),这样可以根据不匹配字符的信息来跳过一些比较。这类似于 KMP 算法中的最长前缀后缀数组。

  3. Boyer-Moore 的启发式规则: 有时候会使用 Boyer-Moore 算法中的一些启发式规则,例如坏字符规则(Bad Character Rule)和好后缀规则(Good Suffix Rule),以提高性能。

所以说contains一般情况下都满足我们的需求,由于最近研究大文本的检索,了解到了KMP算法,所以记录一下KMP的原理

KMP

原理

KMP(Knuth-Morris-Pratt)算法是一种用于在字符串中高效搜索子串的算法。它的目标是避免在搜索过程中重复比较已经比较过的字符,从而提高搜索效率。KMP算法的核心思想是通过预处理模式串(要搜索的子串),构建一个最长前缀后缀数组(即LPS数组),以便在不匹配的时候能够跳过一些字符的比较。

  1. 构建最长前缀后缀数组(LPS数组): 对于模式串(要搜索的子串),从左到右遍历,对每个位置计算最长相等的真前缀和真后缀的长度。这样就得到了LPS数组,它存储了每个位置对应的最长相等真前缀和真后缀的长度。

  2. 使用LPS数组进行匹配: 在实际搜索时,维护两个指针,一个指向文本串,一个指向模式串。当字符匹配时,两个指针同时移动;当不匹配时,利用LPS数组跳过一些字符,使模式串的某一前缀和文本串的当前位置开始匹配。

这种方法能够避免在文本串中重复比较已经比较过的字符,从而提高了搜索的效率。KMP算法的时间复杂度是O(N+M),其中N是文本串的长度,M是模式串的长度。

示例

public class KMPAlgorithm {
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";

        int index = kmpSearch(text, pattern);

        if (index != -1) {
            System.out.println("在索引 " + index + " 处找到模式");
        } else {
            System.out.println("在文本中未找到模式");
        }
    }

    // 构建最长前缀后缀数组
    private static int[] computeLPSArray(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m]; // 初始化最长前缀后缀数组

        int len = 0; // 保存最长相等前缀后缀的长度
        int i = 1;   // 从模式串的第二个字符开始遍历

        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1]; // 不匹配时,回溯到前一个字符的最长前缀后缀长度
                } else {
                    lps[i] = 0; // 如果len已经为0,则表示当前字符无法与前面的字符构成相等的前缀后缀
                    i++;
                }
            }
        }

        return lps;
    }

    // KMP搜索算法
    private static int kmpSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        int[] lps = computeLPSArray(pattern); // 构建最长前缀后缀数组

        int i = 0; // 文本索引
        int j = 0; // 模式索引

        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }

            if (j == m) {
                return i - j; // 匹配成功,返回匹配的起始位置
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1]; // 利用最长前缀后缀数组跳过一部分字符
                } else {
                    i++;
                }
            }
        }

        return -1; // 未找到模式
    }
}

文章来源:https://blog.csdn.net/winerpro/article/details/135186163
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。