大文本字符串搜索算法

1. 引言

本文将介绍几种在大文本中搜索模式字符串的算法。我们将通过代码示例和简洁的数学背景来描述每种算法。

⚠️ 需要注意：这些算法并非复杂应用中实现全文搜索的最佳方案。要正确实现全文搜索，建议使用 Solr 或 ElasticSearch 等专业工具。

2. 算法详解

我们从最直观的朴素文本搜索算法开始，它有助于理解该任务的其他高级问题。

2.1 辅助方法

在开始前，先定义两个计算质数的辅助方法，它们将在 Rabin Karp 算法中使用：

public static long getBiggerPrime(int m) {
    BigInteger prime = BigInteger.probablePrime(getNumberOfBits(m) + 1, new Random());
    return prime.longValue();
}
private static int getNumberOfBits(int number) {
    return Integer.SIZE - Integer.numberOfLeadingZeros(number);
}

2.2 简单文本搜索

这个算法的名字已经说明了一切，它是最自然的解决方案：

public static int simpleTextSearch(char[] pattern, char[] text) {
    int patternSize = pattern.length;
    int textSize = text.length;

    int i = 0;

    while ((i + patternSize) <= textSize) {
        int j = 0;
        while (text[i + j] == pattern[j]) {
            j += 1;
            if (j >= patternSize)
                return i;
        }
        i += 1;
    }
    return -1;
}

算法思路非常直接：遍历文本，当遇到与模式首字符匹配的位置时，检查整个模式是否匹配。

若模式长度为 m，文本长度为 n，则时间复杂度为 *O(m(n-m + 1))*。

最坏情况出现在文本包含大量部分匹配时：

Text: baeldunbaeldunbaeldunbaeldun
Pattern: baeldung

2.3 Rabin Karp 算法

如前所述，当模式较长且包含大量重复元素时，简单文本搜索算法效率极低。

Rabin Karp 算法的核心思想是使用哈希值在文本中查找模式。算法开始时需计算模式的哈希值（称为指纹计算），详细原理可参考这里。

预处理步骤的时间复杂度为 *O(m)*，文本遍历为 *O(n)*，因此整体时间复杂度为 *O(m+n)*。

算法实现：

public static int RabinKarpMethod(char[] pattern, char[] text) {
    int patternSize = pattern.length;
    int textSize = text.length;      

    long prime = getBiggerPrime(patternSize);

    long r = 1;
    for (int i = 0; i < patternSize - 1; i++) {
        r *= 2;
        r = r % prime;
    }

    long[] t = new long[textSize];
    t[0] = 0;

    long pfinger = 0;

    for (int j = 0; j < patternSize; j++) {
        t[0] = (2 * t[0] + text[j]) % prime;
        pfinger = (2 * pfinger + pattern[j]) % prime;
    }

    int i = 0;
    boolean passed = false;

    int diff = textSize - patternSize;
    for (i = 0; i <= diff; i++) {
        if (t[i] == pfinger) {
            passed = true;
            for (int k = 0; k < patternSize; k++) {
                if (text[i + k] != pattern[k]) {
                    passed = false;
                    break;
                }
            }

            if (passed) {
                return i;
            }
        }

        if (i < diff) {
            long value = 2 * (t[i] - r * text[i]) + text[i + patternSize];
            t[i + 1] = ((value % prime) + prime) % prime;
        }
    }
    return -1;
}

最坏情况下时间复杂度为 *O(m(n-m+1))*，但平均复杂度为 *O(n+m)*。

此外还存在蒙特卡洛变种，速度更快但可能产生误匹配（假阳性）。

2.4 Knuth-Morris-Pratt 算法

简单文本搜索算法在文本包含大量模式部分匹配时效率低下。

Knuth-Morris-Pratt 算法通过计算位移表（shift table）解决该问题，位移表指示了应继续搜索模式候选的位置。

KMP 算法的 Java 实现：

public static int KnuthMorrisPrattSearch(char[] pattern, char[] text) {
    int patternSize = pattern.length;
    int textSize = text.length;

    int i = 0, j = 0;

    int[] shift = KnuthMorrisPrattShift(pattern);

    while ((i + patternSize) <= textSize) {
        while (text[i + j] == pattern[j]) {
            j += 1;
            if (j >= patternSize)
                return i;
        }

        if (j > 0) {
            i += shift[j - 1];
            j = Math.max(j - shift[j - 1], 0);
        } else {
            i++;
            j = 0;
        }
    }
    return -1;
}

位移表计算方法：

public static int[] KnuthMorrisPrattShift(char[] pattern) {
    int patternSize = pattern.length;

    int[] shift = new int[patternSize];
    shift[0] = 1;

    int i = 1, j = 0;
    
    while ((i + j) < patternSize) {
        if (pattern[i + j] == pattern[j]) {
            shift[i + j] = i;
            j++;
        } else {
            if (j == 0)
                shift[i] = i + 1;
            
            if (j > 0) {
                i = i + shift[j - 1];
                j = Math.max(j - shift[j - 1], 0);
            } else {
                i = i + 1;
                j = 0;
            }
        }
    }
    return shift;
}

该算法时间复杂度同样为 *O(m+n)*。

2.5 简单 Boyer-Moore 算法

Boyer 和 Moore 两位科学家提出了新思路：为何不从右向左比较模式与文本，同时保持从左向右的移动方向？

public static int BoyerMooreHorspoolSimpleSearch(char[] pattern, char[] text) {
    int patternSize = pattern.length;
    int textSize = text.length;

    int i = 0, j = 0;
    
    while ((i + patternSize) <= textSize) {
        j = patternSize - 1;
        while (text[i + j] == pattern[j]) {
            j--;
            if (j < 0)
                return i;
        }
        i++;
    }
    return -1;
}

如预期，该算法时间复杂度为 *O(m * n)*。但它启发了后续的启发式实现（坏字符规则和好后缀规则），显著提升了算法速度。更多细节可参考这里。

2.6 Boyer-Moore-Horspool 算法

Boyer-Moore 算法存在多种启发式实现变体，其中最简单的是 Horspool 变种。

该版本称为 Boyer-Moore-Horspool，解决了原始算法中的负位移问题（负位移问题在 Boyer-Moore 算法描述中有说明）。

与 Boyer-Moore 算法类似，最坏时间复杂度为 *O(m * n)*，平均复杂度为 *O(n)*。空间复杂度仅取决于字母表大小（256，对应 ASCII 字符集），与模式长度无关：

public static int BoyerMooreHorspoolSearch(char[] pattern, char[] text) {

    int shift[] = new int[256];
    
    for (int k = 0; k < 256; k++) {
        shift[k] = pattern.length;
    }
    
    for (int k = 0; k < pattern.length - 1; k++){
        shift[pattern[k]] = pattern.length - 1 - k;
    }

    int i = 0, j = 0;

    while ((i + pattern.length) <= text.length) {
        j = pattern.length - 1;

        while (text[i + j] == pattern[j]) {
            j -= 1;
            if (j < 0)
                return i;
        }
        
        i = i + shift[text[i + pattern.length - 1]];
    }
    return -1;
}

4. 总结

本文介绍了多种文本搜索算法。由于部分算法需要较强的数学背景，我们尝试以简洁方式呈现每种算法的核心思想。

✅ 所有源代码可在 GitHub 获取。

Persistence

REST

Security