WuManber.java

package org.theyeasy.weixin.util;

import java.util.Vector;

public class WuManber {
	private int B=2;//���ַ�X�ĳ���(ģʽ����׺�ַ��ĸ���)

	private boolean initFlag = false;//�Ƿ��ʼ��
	private UnionPatternSet unionPatternSet = new UnionPatternSet();
	private int maxIndex = (int) java.lang.Math.pow(2, 16);
	private int shiftTable[] = new int[maxIndex];
	public Vector <AtomicPattern> hashTable[] = new Vector[maxIndex];
	private UnionPatternSet tmpUnionPatternSet = new UnionPatternSet();

	public WuManber() {
	}


	public static void main(String args[]){//����
		WuManber objWM=new WuManber();
		Vector<String> vKey=new Vector<String>();
		vKey.add("房款");
		vKey.add("是什么");
		vKey.add("电影");
		vKey.add("喜欢");
		vKey.add("你");

		if(objWM.addFilterKeyWord(vKey, 0)){

			String sResult=objWM.macth("你能告我最喜欢的电影是什么吗？",new Vector(0));

			System.out.println(sResult);
		}

		objWM.clear();

	}


	//ƥ��
	public String macth(String content, Vector <Integer> levelSet) {
		StringBuffer sResult=new StringBuffer();
		if (initFlag == false)
			init();
		Vector <AtomicPattern> aps = new Vector <AtomicPattern>();
		String preContent = content;//preConvert(content);
		int iSameCount=0;
		for (int i = 0; i  < preContent.length();) {
			char checkChar = preContent.charAt(i);
			if (shiftTable[checkChar] == 0) {
				Vector <AtomicPattern> tmpAps = new Vector <AtomicPattern>();
				tmpAps = findMathAps(preContent.substring(0, i + 1),hashTable[checkChar]);
				aps.addAll(tmpAps);
				if(tmpAps.size()>0){
					sResult.append(tmpAps.get(0).getPattern().str).append("|");
					iSameCount++;
				}
				i++;
			} else
				i = i + shiftTable[checkChar];
		}
		parseAtomicPatternSet(aps, levelSet);
		//sResult.append(" ����:").append(iSameCount).append("�����ϸ�");
		return sResult.toString();
	}


	//����ؼ���
	public boolean addFilterKeyWord(Vector<String> keyWord, int level) {
		if (initFlag == true)
			return false;
		UnionPattern unionPattern = new UnionPattern();
		Object[] strArray = keyWord.toArray();
		for (int i = 0; i  < strArray.length; i++) {
			String sPattern=(String)strArray[i];
			Pattern pattern = new Pattern(sPattern);
			AtomicPattern atomicPattern = new AtomicPattern(pattern);
			unionPattern.addNewAtomicPattrn(atomicPattern);
			unionPattern.setLevel(level);
			atomicPattern.setBelongUnionPattern(unionPattern);
		}
		tmpUnionPatternSet.addNewUnionPattrn(unionPattern);
		return true;
	}

	//��֤�ַ�
	private boolean isValidChar(char ch) {
		if ((ch >= '0' && ch  <= '9') || (ch >= 'A' && ch  <= 'Z') || (ch >= 'a' && ch  <= 'z'))
			return true;
		if ((ch >= 0x4e00 && ch  <= 0x7fff) || (ch >= 0x8000 && ch  <= 0x952f))
			return true;// �������ĺ��ֱ���
		return false;
	}

	//��װԭ��ģʽ��
	private void parseAtomicPatternSet(Vector <AtomicPattern> aps,Vector <Integer> levelSet) {
		while (aps.size() > 0) {
			AtomicPattern ap = aps.get(0);
			UnionPattern up = ap.belongUnionPattern;
			if (up.isIncludeAllAp(aps) == true) {
				levelSet.add(new Integer(up.getLevel()));
			}
			aps.remove(0);
		}
	}

	//����ԭ��ģʽ
	private Vector <AtomicPattern> findMathAps(String src,Vector <AtomicPattern> destAps) {
		Vector <AtomicPattern> aps = new Vector <AtomicPattern>();
		for (int i = 0; i  < destAps.size(); i++) {
			AtomicPattern ap = destAps.get(i);
			if (ap.findMatchInString(src) == true)
				aps.add(ap);
		}
		return aps;
	}
	//Ԥת�����ݣ����������ַ���
	private String preConvert(String content) {
		String retStr = new String();
		for (int i = 0; i  < content.length(); i++) {
			char ch = content.charAt(i);
			if (this.isValidChar(ch) == true) {
				retStr = retStr + ch;
			}
		}
		return retStr;
	}
	// shift table and hash table of initialize
	private void init() {
		initFlag = true;
		for (int i = 0; i  < maxIndex; i++)
			hashTable[i] = new Vector <AtomicPattern>();
		shiftTableInit();
		hashTableInit();
	}

	//���
	public void clear() {
		tmpUnionPatternSet.clear();
		initFlag = false;
	}

	//��ʼ����Ծ��
	private void shiftTableInit() {
		for (int i = 0; i  < maxIndex; i++)
			shiftTable[i] = B;
		Vector <UnionPattern> upSet = tmpUnionPatternSet.getSet();
		for (int i = 0; i  < upSet.size(); i++) {
			Vector <AtomicPattern> apSet = upSet.get(i).getSet();
			for (int j = 0; j  < apSet.size(); j++) {
				AtomicPattern ap = apSet.get(j);
				Pattern pattern = ap.getPattern();
				//System.out.print(pattern.charAtEnd(1)+"\t");
				if (shiftTable[pattern.charAtEnd(1)] != 0)
					shiftTable[pattern.charAtEnd(1)] = 1;
				if (shiftTable[pattern.charAtEnd(0)] != 0)
					shiftTable[pattern.charAtEnd(0)] = 0;
			}
		}
	}

	//��ʼ��HASH��
	private void hashTableInit() {
		Vector <UnionPattern> upSet = tmpUnionPatternSet.getSet();
		for (int i = 0; i  < upSet.size(); i++) {
			Vector <AtomicPattern> apSet = upSet.get(i).getSet();
			for (int j = 0; j  < apSet.size(); j++) {
				AtomicPattern ap = apSet.get(j);
				Pattern pattern = ap.getPattern();
				//System.out.println(pattern.charAtEnd(0));
				if (pattern.charAtEnd(0) != 0) {
					hashTable[pattern.charAtEnd(0)].add(ap);
				}
			}
		}
	}
}
	//ģʽ��
	class Pattern {
		public String str;

		Pattern(String str) {
			this.str = str;
		}
		public char charAtEnd(int index) {
			if (str.length() > index) {
				return str.charAt(str.length() - index - 1);
			} else
				return 0;
		}
		public String getStr() {
			return str;
		};
	}

	//ԭ��ģʽ��
	class AtomicPattern {
		public boolean findMatchInString(String str) {
			if (this.pattern.str.length() > str.length())
				return false;
			int beginIndex = str.length() - this.pattern.str.length();
			String eqaulLengthStr = str.substring(beginIndex);
			if (this.pattern.str.equalsIgnoreCase(eqaulLengthStr))
				return true;
			return false;
		}
		AtomicPattern(Pattern pattern) {
			this.pattern = pattern;
		};
		private Pattern pattern;
		public UnionPattern belongUnionPattern;
		public UnionPattern getBelongUnionPattern() {
			return belongUnionPattern;
		}
		public void setBelongUnionPattern(UnionPattern belongUnionPattern) {
			this.belongUnionPattern = belongUnionPattern;
		}
		public Pattern getPattern() {
			return pattern;
		}
		public void setPattern(Pattern pattern) {
			this.pattern = pattern;
		}
	}
	//��ͬ��ԭ��ģʽ����
	class SameAtomicPatternSet {
		SameAtomicPatternSet() {
			SAPS = new Vector <AtomicPattern>();
		};
		public Vector <AtomicPattern> SAPS;
	}

	//�ϲ���ģʽ��
	class UnionPattern {
		// union string
		UnionPattern() {
			this.apSet = new Vector <AtomicPattern>();
		}
		public Vector <AtomicPattern> apSet;
		public void addNewAtomicPattrn(AtomicPattern ap) {
			this.apSet.add(ap);
		}
		public Vector <AtomicPattern> getSet() {
			return apSet;
		}
		public boolean isIncludeAllAp(Vector <AtomicPattern> inAps) {
			if (apSet.size() > inAps.size())
				return false;
			for (int i = 0; i  < apSet.size(); i++) {
				AtomicPattern ap = apSet.get(i);
				if (isInAps(ap, inAps) == false)
					return false;
			}
			return true;
		}
		private boolean isInAps(AtomicPattern ap, Vector <AtomicPattern> inAps) {
			for (int i = 0; i  < inAps.size(); i++) {
				AtomicPattern destAp = inAps.get(i);
				if (ap.getPattern().str.equalsIgnoreCase(destAp.getPattern().str) == true)
					return true;
			}
			return false;
		}
		public void setLevel(int level) {
			this.level = level;
		}
		public int getLevel() {
			return this.level;
		}
		private int level;
	}

	//�ϲ���ģʽ������

	class UnionPatternSet { // union string set
		public Vector <UnionPattern> unionPatternSet;
		UnionPatternSet() {
			this.unionPatternSet = new Vector <UnionPattern>();
		}
		public void addNewUnionPattrn(UnionPattern up) {
			this.unionPatternSet.add(up);
		}
		public Vector <UnionPattern> getSet() {
			return unionPatternSet;
		}
		public void clear() {
			unionPatternSet.clear();
		}
	}