Java实现Sunday百万级数据量的字符串快速匹配算法

Z时代
2024-01-10
分类：综合

java

背景

在平时的项目中,几乎都会用到比较两个字符串时候相等的问题,通常是用==或者equals()进行,这是在数据相对比较少的情况下是没问题的,当数据库中的数据达到几十万甚至是上百万千万的数据需要从中进行匹配的时候,传统的方法显示是不行的,影响匹配的效率,时间也会要很久,用户体验很差的,今天就要介绍一种字符串匹配的算法Sunday。接下来就详细介绍了

Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。相比于另外几个著名的字符串匹配算法，KMP以及BM算法而言，Sunday算法不仅理解起来比较容易，而且往往能有更好的速度。

首先i,j两个指针指示的位置（也就是从头开始匹配），当发现失配的时候就判断子串的后一位在母串的字符即空格（k标记处）是否在子串中存在？如果存在则将该位置和子串中的该字符对齐，在从头开始匹配。如果不存在就将子串向后移动，和母串k+1处的字符对齐，再进行匹配。重复上面的操作直到找到，或母串被找完结束。

　　如上图，这次比较还是失配，但是k位置的e在子串中出现了，而且第一个就是，最后一个也是，这时候一定要将子串中靠后出现的e和母串中的e对齐如下图。

再从i,j开始进行比较。。。。。
代码如下

package per.zh.tess4j;

/***
* 字符串快速匹配sunday算法
* sunday与horspool优于strstr、BM、KMP，BM匹配速度相当于KMP的三倍。
* (1)strstr():c语言的库函数
* (2)KMP(Knuth-Morris-Pratt)算法
* (3)BM(Boyer-Moore)算法
* (4)Horspool算法
* (5)Sunday算法
* @author lenovo
* @date 2019年3月22日
* description:
*/
public class SundayTest {

　　public static void main(String[] args) {
　　　　String s="abcdebcdbcdegbcde";
　　　　String p="bcdeg";
　　　　Sunday(s, p);

　　}

　　//注意每次都是从后向前
　　public static int contains(char[] str,char ch){
　　　　for(int i=str.length-1;i>=0;i--){
　　　　　　if(str[i]==ch){
　　　　　　return i;
　　　　　　}
　　　　}
　　　　return -1;
　　}

　　/**
　　* 匹配字符串
　　* @param s 目标字符串
　　* @param p 需要匹配的字符串
　　*/

　　public static void Sunday(String s,String p){
　　　　char[] sarray = s.toCharArray();
　　　　char[] parray = p.toCharArray();
　　　　int slen=s.length();
　　　　int plen=p.length();
　　　　int i=0,j=0;
　　　　while(i<=slen-plen+j){//这句话控制索引i,j的范围
　　　　　　if(sarray[i]!=parray[j]){//假如主串的sarry[i]与模式串的parray[j]不相等
　　　　　　if(i==slen-plen+j){
　　　　　　　　break;//假如主串的sarry[i]与模式串的parray[j]不相等,并且i=slen-plen+j,说明这已经
　　　　　　　　//是在和主串中最后可能相等的字符段比较了,并且不相等,说明后面就再也没有相等的了,所以
　　　　　　　　//跳出循环,结束匹配
　　　　　　}
　　　　　　//假如是主串的中间字段与模式串匹配，且结果不匹配
　　　　　　//则就从模式串的最后面开始,(注意是从后向前)向前遍历,找出模式串的后一位在对应的母串的字符是否在子串中存在
　　　　 int pos=contains(parray, sarray[i+plen-j]);
　　　　if(pos==-1){//表示不存在
　　　　　　i=i+plen+1-j;
　　　　　　j=0;
　　　　}else{
　　　　　　i=i+plen-pos-j;
　　　　　　j=0;
　　　　}
　　 }else{//假如主串的sarry[i]与模式串的parray[j]相等,则继续下面的操作
　　　　　　if(j==plen-1){//判断模式串的索引j是不是已经到达模式串的最后位置，
　　　　　　　　//j==plen-1证明在主串中已经找到一个模式串的位置,
　　　　　　　　//且目前主串尾部的索引为i,主串首部的索引为i-j,打印模式串匹配的第一个位置
　　　　　　　　System.out.println("the start pos is "+(i-j)+" the end pos is "+i);
　　　　　　　　//然后主串右移一个位置,再和模式串的首字符比较,从而寻找下一个匹配的位置
　　　　　　　　i=i-j+1;
　　　　　　　　j=0;
　　　　　　}else{
　　　　　　　　//假如模式串的索引j!=plen-1,说明模式串还没有匹配完,则i++,j++继续匹配,
　　　　　　　　i++;
　　　　　　　　j++;
　　　　　　}
　　　　}
　　 }
　}