智能撥號匹配算法（二）

    完整源碼在我的github上 https://github.com/NashLegend/QuicKid    

    接上篇，下面是幾個匹配算法的詳情：

1.完全匹配

    完全匹配很簡單了，只要判斷string是否相等就行了。這里要判斷所有拼音和所有號碼。如果拼音已經(jīng)符合，就不再判斷號碼。反正是一個人……

private ScoreAndHits completeMatch(String reg) {
	ScoreAndHits scoreAndHits = new ScoreAndHits(-1, 0f,
			new ArrayList<PointPair>());
	for (int i = 0; i < fullNameNumberWithoutSpace.size(); i++) {
		String str = fullNameNumberWithoutSpace.get(i);
		if (reg.equals(str)) {
			scoreAndHits.nameIndex = i;
			scoreAndHits.score = Match_Level_Complete;
			scoreAndHits.pairs.add(new PointPair(i, -1));
			scoreAndHits.matchLevel = Level_Complete;
			return scoreAndHits;
		}
	}
	for (int i = 0; i < phones.size(); i++) {
		PhoneStruct phone = phones.get(i);
		if (reg.equals(phone.phoneNumber)) {
			scoreAndHits.nameIndex = i;
			scoreAndHits.score = Match_Level_Complete;
			scoreAndHits.pairs.add(new PointPair(i, -1));
			scoreAndHits.matchType = Match_Type_Phone;
			scoreAndHits.matchLevel = Level_Complete;
			return scoreAndHits;
		}
	}
	// 走到這里說明沒有匹配
	return new ScoreAndHits(-1, 0f, new ArrayList<PointPair>());
}

2.前置首字母溢出匹配。（能不能想個好聽的名字）

private ScoreAndHits foreAcronymOverFlowMatch(String reg) {
        // 因為有可能是多音字，所以這個方法用來對比不同拼音的匹配度，并取最大的那個
	ScoreAndHits scoreAndHits = new ScoreAndHits(-1, 0f,
			new ArrayList<PointPair>());
	for (int i = 0; i < fullNameNumber.size(); i++) {
		ArrayList<String> names = fullNameNumber.get(i);
		ScoreAndHits tmpscore = foreAcronymOverFlowMatch(names, reg);
		if (tmpscore.score > scoreAndHits.score) {
			scoreAndHits = tmpscore;
			scoreAndHits.nameIndex = i;
		}
	}
	scoreAndHits.matchLevel = Level_Fore_Acronym_Overflow;
	return scoreAndHits;
}

// 在第一個字母確定的情況下，第二個字母有可能有三種情況
// 一、在第一個字母所在單詞的鄰居位置charAt(x+1);
// 二、在第二個單詞的首字母處
// 三、以上兩種情況皆不符合，不匹配，出局

private ScoreAndHits foreAcronymOverFlowMatch(ArrayList<String> names,
		String reg) {
	// 用來得出某一個拼音的匹配值。
	ScoreAndHits scoreAndHits = new ScoreAndHits(-1, 0f,
			new ArrayList<PointPair>());
	if (names.get(0).charAt(0) == reg.charAt(0)) {
	        //其實(shí)crossWords()方法才是求匹配值的方法，lol
		OverflowMatchValue value = crossWords(names, reg, 0, 0, 0);
		int cross = crossWords(names, reg, 0, 0, 0).crossed;
		if (cross > 0) {
			scoreAndHits.score = Match_Level_Fore_Acronym_Overflow + cross
					* Match_Score_Reward - (names.size() - cross)
					* Match_Miss_Punish;
			scoreAndHits.pairs = value.pairs;
		}

	}
	return scoreAndHits;
}

/**
 * 返回一串字符能跨越另一串字符的長度，根據(jù)上面的匹配規(guī)則，要盡可能的多匹配單詞。若要保證
 * 能匹配最長的長度，只要保證下一個字符開始的一段字符能匹配最長的長度即可，換名話說，
 * 如果想要讓96758匹配最長的字符串，那么只要保證6758能匹配最長的字符串即可，
 * 然后758，再然后58……。例如，名字叫PanAnNing，輸入pan，那么應(yīng)該匹配三個首字母，
 * PAN,而不是第一姓的拼音Pan.這是一個遞歸。
 * 
 * 
 * @param names
 * @param regString
 *            匹配字符串
 * @param listIndex
 *            匹配到的list的第listIndex個單詞
 * @param strIndex
 *            匹配到第listIndex個單詞中的第strIndex個字母
 * @param regIndex
 *            regchar的匹配位置，比如匹配到了96758的7上，也就是regIndex==2.
 * @return
 */
private OverflowMatchValue crossWords(ArrayList<String> names,
		String regString, int listIndex, int strIndex, int regIndex) {
		//在進(jìn)入此方法時，第listIndex個單詞的第strIndex的字母肯定是
		// 與regString的第regIndex個字母相等的
	OverflowMatchValue result = new OverflowMatchValue(0, false);
	OverflowMatchValue reser = new OverflowMatchValue(0, false);//返回如果匹配到本單詞的下一個字母能得到的匹配值
	OverflowMatchValue impul = new OverflowMatchValue(0, false);//返回如果匹配到下一個單詞的第一個字母的匹配值
	
	// 仍然以【名字叫PanAnNing，輸入pan(其實(shí)對比的是數(shù)字，這里轉(zhuǎn)化成字母為了方便)】舉例
	// 假設(shè)這時listIndex，strIndex，regIndex都是0，所以現(xiàn)在匹配的是p字母，它毫無疑問對應(yīng)姓名的第一個P，
	// 那么下一步應(yīng)該怎么做呢，由上面所說【保證下一個字符開始的一段字符能匹配最長的長度即可】
	// 也就是說，我們輸入的pan中的第二個字母a匹配哪個位置將得到最優(yōu)結(jié)果。這個盒子中顯然有兩種情況。
	// 一是匹配姓氏Pan中的a，另一個是匹配名字AnNing中的A。
	// reser就表示如果a匹配到Pan中的a最終的匹配值。
	// impul就表示如果a匹配到AnNing中的A得到的最終的匹配值。
	
	if (regIndex < regString.length() - 1) {
	    //如果還沒匹配到最后一個字母，也就是regString還沒匹配到最后一個，那么將檢測如
	    //果將regString的下一個字母放到哪里將得到最優(yōu)結(jié)果
		char nextChar = regString.charAt(regIndex + 1);
		if (listIndex < names.size() - 1
				&& nextChar == names.get(listIndex + 1).charAt(0)) {
			impul = crossWords(names, regString, listIndex + 1, 0,
					regIndex + 1);
		}
		if (strIndex < names.get(listIndex).length() - 1
				&& nextChar == names.get(listIndex).charAt(strIndex + 1)) {
			reser = crossWords(names, regString, listIndex, strIndex + 1,
					regIndex + 1);
		}
		//如果上面兩個條件都不成立，那么就表示本次匹配失敗
	} else {
		result = new OverflowMatchValue((strIndex == 0) ? 1 : 0, true);
		result.pairs.add(0, new PointPair(listIndex, strIndex));
	}

	if (reser.matched || impul.matched) {
	    //如果其中任意一個方式可以匹配，那么結(jié)果最大的那個就是最優(yōu)結(jié)果
		if (impul.crossed > reser.crossed) {
			result = impul;
		} else {
			result = reser;
		}
		result.matched = true;
		result.crossed = ((strIndex == 0) ? 1 : 0)
				+ Math.max(result.crossed, result.crossed);
		result.pairs.add(0, new PointPair(listIndex, strIndex));
	}
	return result;
}

static class OverflowMatchValue {
	public int crossed = 0;
	public boolean matched = false;
	public ArrayList<PointPair> pairs = new ArrayList<PointPair>();

	public OverflowMatchValue(int c, boolean m) {
		this.crossed = c;
		this.matched = m;
	}
}

3.后置首字母溢出匹配。（能不能想個好聽的名字）

跟前置首字母溢出匹配基本一樣，只不過匹配的第一個字母不再是姓的首字母。

private ScoreAndHits backAcronymOverFlowMatch(String reg) {
        //跟上面差不多
	ScoreAndHits scoreAndHits = new ScoreAndHits(-1, 0f,
			new ArrayList<PointPair>());
	for (int i = 0; i < fullNameNumber.size(); i++) {
		ArrayList<String> names = fullNameNumber.get(i);
		ScoreAndHits tmp = backAcronymOverFlowMatch(names, reg);
		if (tmp.score > scoreAndHits.score) {
			scoreAndHits = tmp;
			scoreAndHits.nameIndex = i;
		}
	}
	scoreAndHits.matchLevel = Level_Back_Acronym_Overflow;
	return scoreAndHits;
}

private ScoreAndHits backAcronymOverFlowMatch(ArrayList<String> names,
		String reg) {
	int score = 0;
	int punish = 0;
	ScoreAndHits scoreAndHits = new ScoreAndHits(-1, 0f,
			new ArrayList<PointPair>());
	// 有可能會調(diào)用多次crossWords，取決于名字的長度。這是跟前面的不同
	for (int i = 0; i < names.size(); i++) {
		String string = (String) names.get(i);
		if (string.charAt(0) == reg.charAt(0)) {
			OverflowMatchValue value = crossWords(names, reg, i, 0, 0);
			int cross = value.crossed;
			int lost = names.size() - cross;
			if (cross > score || cross == score && punish > lost) {
				scoreAndHits.pairs = value.pairs;
				score = cross;
				punish = lost;
			}
		}
	}
	if (score > 0) {
		scoreAndHits.score = Match_Level_Back_Acronym_Overflow + score
				* Match_Score_Reward - punish * Match_Miss_Punish;
		return scoreAndHits;
	} else {
		return new ScoreAndHits(-1, 0f, new ArrayList<PointPair>());
	}

}

4.后置無頭匹配。（難聽就難聽了，反正就那個意思）

private ScoreAndHits backHeadlessParagraphMatch(String reg) {
	// TODO，如果此人有兩個相似的號碼，那么就只能匹配出一個來了，這是很顯然不對的
	int punish = 0;
	ScoreAndHits scoreAndHits = new ScoreAndHits(-1, -1f,
			new ArrayList<PointPair>());
	scoreAndHits.matchLevel = Level_Headless;
	scoreAndHits.matchType = Match_Type_Phone;
	// 不匹配姓名
	for (int i = 0; i < phones.size(); i++) {
		PhoneStruct phone = phones.get(i);
		int sco = phone.phoneNumber.indexOf(reg);
		if (sco >= 0) {
			int lost = phone.phoneNumber.length() - reg.length();
			if (scoreAndHits.score < sco || sco == scoreAndHits.score
					&& punish > lost) {
				scoreAndHits.score = sco;
				scoreAndHits.nameIndex = i;
				punish = lost;
			}
			//pairs.add放到判斷外面是因為有可能匹配到同一個人的多個手機(jī)號碼。
			scoreAndHits.pairs.add(new PointPair(i, sco));
		}
	}
	if (scoreAndHits.score >= 0) {
		scoreAndHits.score = Match_Level_Headless - scoreAndHits.score
				* Match_Score_Reward - punish * Match_Miss_Punish;
	}
	return scoreAndHits;
}

//表示電話號碼的一個靜態(tài)類，將過濾掉開頭的+86以及系統(tǒng)可能自動生成的“-”以及其他非數(shù)字的字符以便于搜索
public static class PhoneStruct {
	public String phoneNumber;
	public int phoneType;
	public String displayType;

	public PhoneStruct(String number, int type) {
		phoneNumber = number.replaceAll("^\\+86", "").replaceAll("[\\]+",
				"");
		phoneType = type;
	}
}

到這里已經(jīng)可以得出輸入字符串與聯(lián)系人的匹配度了，剩下的事情就是調(diào)用和顯示了，但是這不是本文的重點(diǎn)