KMP算法和Stream文本查找

最近在解决高性能分析Stream数据时使用了Jakarta Regex的StreamCharacterIterator类,使得上千的Stream对象可以在1秒内完成检索匹配,对它的实现原理很感兴趣,就花时间来研究了一下它的源代码:查询高效的原因是KMP算法的部分搜索结合StringBuffer的定宽读取。这样我们无须转换整个Stream为字符串,也无须读取Stream的全部长度就能完成匹配操作。

KMP算法

  1. 如果要查询字符串 T 内部是否包含字符串 S,只需要查询 T 内部是否有与 S 等长度连续出现的字符;
  2. 设置初始值为 0k, m 分别为 T, S 的查询起始位置,从 T[0] 开始递增对比 S[0],如果 T[k] 不等于 S[i],则在下一次查询中重置 i0,继续从 T[k] 位置搜索下一个匹配字符,直到完全匹配或到达 T 字符串的终点。
    RE类内部的KMP算法实现:

    boolean caseIndependent = (matchFlags & MATCH_CASEINDEPENDENT) != 0;
    char[] prefix = program.prefix;
    for ( ; !search.isEnd(i + prefix.length - 1); i++)
    {
    int j = i;
    int k = 0;
    
    boolean match;
    do {
        // If there's a mismatch of any character in the prefix, give up
        match = (compareChars(search.charAt(j++), prefix[k++], caseIndependent) == 0);
    } while (match && k < prefix.length);
    
    // See if the whole prefix string matched
    if (k == prefix.length)
    {
        // We matched the full prefix at firstChar, so try it
        if (matchAt(i))
        {
            return true;
        }
    }
    }
    return false;
    

StringBuffer

在StreamCharactorIterator中,使用宽度为512的 StringBuffer 将 Stream 读取为字符串,再使用 charAt 读取字符指定位置的字符。

this.buff = new StringBuffer(512);
private int read(int n) throws IOException
{
    if (closed)
    {
        return 0;
    }

    int c;
    int i = n;
    while (--i >= 0)
    {
        c = is.read();
        if (c < 0) // EOF
        {
            closed = true;
            break;
        }
        buff.append((char) c);
    }
    return n - i;
}
© 2018 Silent River All Rights Reserved. 本站访客数人次 本站总访问量
Theme by hiero