文档章节

几种单模式匹配算法的比较

叶大侠
 叶大侠
发布于 2012/11/14 12:21
字数 1306
阅读 223
收藏 1

1、蛮力法:

int  matching(char[] src,char[] p){
		int sLen = src.length;
		int pLen = p.length;
		for(int i=0;i<=(sLen-pLen);i++){
		   int j = 0; //模式P的下标
		   int k = i; //原串的下标
		   while(j<pLen){
			   if(src[k]!=p[j])
        		   break;
        	   k++;
        	   j++;
		   }
           if(j==pLen){
        	   return i;
           }
		}
		return -1;
	}

效率为O(n*m),n和m分别为原串和模式串的长度,原串指针要回溯...

效率改进:

 

static int indexOf(char[] source, int sourceOffset, int sourceCount,
                       char[] target, int targetOffset, int targetCount,
                       int fromIndex) {
	if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
	}
    	if (fromIndex < 0) {
    	    fromIndex = 0;
    	}
	if (targetCount == 0) {
	    return fromIndex;
	}

        char first  = target[targetOffset];
        int max = sourceOffset + (sourceCount - targetCount);

        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j] ==
                         target[k]; j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }

这是java类库中String的index方法,找到首个字符之后再用进行比较,如果字符串较为分散的情况下,效率还是可以的,但是如果是src:aaabaaabaaabaaaaaaaaabaaab   p:aaaab,这种情况就会沦为和蛮力法差不多了.

2、KMP算法:

public class KMP {
	private int[] next;

	/**
	 * 根据模式计算出next数组的各个值
	 */
	void initNext(char[] p) {
		int i = 0, j = 0; // i是串的移动下标,j是模式的移动下标
		next = new int[p.length];
		next[1] = 0;
		while (i < p.length) {
			if (j == 0 || p[i] == p[j]) {
				i++;
				j++;
				next[i] = j;
			} else {
				j = next[j];
			}
		}
	}

	int KMPMatching(char[] src, char[] p) {
		int i = 0, j = 0;
		while (i < src.length && j < p.length) {
			if (j == 0 || p[i] == p[j]) {
				i++;
				j++;
			} else {
				j = next[j];
			}
		}
		if (j == p.length)
			return i - j;
		return -1;
	}

}

 指针不需要回溯,效率升级为O(n+m),要提前构造next数字,如果是源字符串不长的情况下,该方法就没什么优势了.

 还有就是如果模式串p很长的话,该方法也不是很优的方法.

3、Horspool(BM的简化版)

private Map<Character, Integer> Table;//存储每个字符的移动表
	public Horspool() {
		initTable();
	}

	void initTable() {
		Table = new HashMap<Character, Integer>();
	}

	void shiftTable(char[] p) {
		int m = p.length;
		// 初始字母表移动值为模式的长度
		for (char ch = 'A'; ch <= 'z'; ch++) {
			Table.put(ch, m);
		}
		// 模式中前m-1个字符到模式最后一个字符的长度
		for (int j = 0; j < m - 1; j++)
			Table.put(p[j], m - j - 1);
	}

	/**
	 * 找到的话就返回串首所在的位置,否则返回-1
	 */
	int HorspoolMatching(char[] p, char[] src) {
		shiftTable(p);
		int m = p.length;
		int i = m - 1, j, k;
		while (i < src.length) {
			j = m - 1;
			k = 0;
			while (j >= 0 && src[i - k] == p[j]) {
				j--;
				k++;
			}
			// match the pattern,return the location
			if (j == -1)
				return i - m + 1;
			else
				i = Table.get(src[i]) + i;// 加上偏移值
		}
		return -1;
	}

和上面的不一样,这是从模式的右边开始比较向左移动比较的,它不需要对被搜索的字符串中的字符进行逐一比较,而会跳过其中某些部分。

   移动的距离为

    if(c不包含在模式的前m-1字符中) t(c) = m  else t(c) = 模式前m-1字符中最右边的c到模式末尾的距离

它的平均效率是很诱人的,属于O(n)级别的,但是也可见,在最差的情况下就沦为O(nm)了...除外,它还需要一个额外的索引表来存储各种可能出现的字符偏移值...虽然这样,在随机文件中的检索还是非常有用的,《算法分析与设计》的作者甚至说它的效率至少和它的前辈(BM和KMP)一样高.

4、BoyerMoore算法

public class BoyerMoore {

	// 坏符号移动表
	private Map<Character, Integer> badTable;

	// 好后缀移动距离
	private int[] goodSuffix;

	public BoyerMoore() {
		initTable();
	}

	void initTable() {
		badTable = new HashMap<Character, Integer>();
	}

	void initBadTable(char[] p) {
		int m = p.length;
		// 初始字母表移动值为模式的长度
		for (char ch = 'A'; ch <= 'Z'; ch++) {
			badTable.put(ch, m);
		}
		// 模式中前m-1个字符到模式最后一个字符的长度
		for (int j = 0; j < m - 1; j++)
			badTable.put(p[j], m - j - 1);
	}

	// 构造好后缀移动表
	void initGoodSuffix(char[] p) {
		int m = p.length;
		goodSuffix = new int[m - 1];
		for (int i = 0; i < m - 1; i++) {
			goodSuffix[i] = getSuffixLoc(p, i + 1, 0);
		}
	}

	/**
	 * 获取长度为len的后缀移动距离
	 */
	int getSuffixLoc(char[] p, int len, int lastLoc) {
		int j = getReverseLoc(p, lastLoc);
		if (j == -1) {
			return 0;
		}
		int m = p.length - 1;
		int k = 1;
		while (k < len && m - j >= k && p[m - k] == p[m - j - k]) {
			k++;
		}
		if (k == len)
			return j;
		if (j > 0 && getReverseLoc(p, j) == -1)
			return j;
		return getSuffixLoc(p, len, j);
	}

	/**
	 * 从最后开始数,最后一个字符在lastLoc之后的位置
	 */
	int getReverseLoc(char[] p, int lastLoc) {
		int m = p.length;
		char lastWord = p[m - 1];
		for (int i = m - 2 - lastLoc; i >= 0; i--) {
			if (p[i] == lastWord)
				return m - 1 - i;
		}
		return -1;
	}

	/**
	 * 匹配算法
	 */
	public int BoyerMooerMatching(char[] p, char[] src) {
		initBadTable(p);
		initGoodSuffix(p);
		int pLen = p.length, sLen = src.length;
		int i = pLen - 1; // src的下标
		int k = 0, j; // k为左移计数变量
		int lsLen, d1, d2;
		while (i < sLen) {
			j = pLen - 1; // 模式p的下标
			k = 0;
			while (j >= 0 && p[j] == src[i - k]) {
				j--;
				k++;
			}
			if (j == -1)
				return i - pLen + 1;
			if (j == pLen - 1) {
				i = i + badTable.get(src[i]);
			} else {
				lsLen = pLen - j - 1;
				d1 = badTable.get(src[i]) - (lsLen);
				d2 = goodSuffix[lsLen - 1];
				System.out.println("d1:" + d1 + ",d2:" + d2);
				i = i + (d1 > d2 ? d1 : d2);
			}
		}
		return -1;
	}


}

真正实现起来该算法还真不好弄...

BoyerMoore把情报工作可谓做到了极致...该算法的高效让它在最差的情况下也是线性的... 如果你匹配的文本很大,强烈建议使用该算法.

 

 

© 著作权归作者所有

共有 人打赏支持