智能撥號(hào)匹配算法（一）

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

    智能撥號(hào)是指，呃不用解釋了，國(guó)內(nèi)撥號(hào)軟件都帶的大家都知道，就是輸入姓名拼音的一部分就可快速搜索出聯(lián)系人的撥號(hào)方式。如下圖

    智能匹配，很容易想到的就是先把九宮格輸入鍵盤(pán)上輸入的數(shù)字轉(zhuǎn)換成可能的拼音組合，然后再用這些可能的拼音與聯(lián)系人列表中的姓名拼音一一匹配，取匹配度最高的排到最前，但是這有一個(gè)問(wèn)題就是數(shù)組對(duì)應(yīng)的可能的拼音組合實(shí)在是點(diǎn)兒多，跑一下下面的代碼就知道了。如果想智能一些的話還要先剔除一些不可能的拼音組合實(shí)在有點(diǎn)麻煩。

public static HashMap<Character, String[]> keyMaps;

public static void main(String[] args) {
	keyMaps = new HashMap<Character, String[]>();
	keyMaps.put('0', new String[0]);
	keyMaps.put('1', new String[0]);
	keyMaps.put('2', new String[] { "a", "b", "c" });
	keyMaps.put('3', new String[] { "d", "e", "f" });
	keyMaps.put('4', new String[] { "g", "h", "i" });
	keyMaps.put('5', new String[] { "j", "k", "l" });
	keyMaps.put('6', new String[] { "m", "n", "o" });
	keyMaps.put('7', new String[] { "p", "q", "r", "s" });
	keyMaps.put('8', new String[] { "t", "u", "v" });
	keyMaps.put('9', new String[] { "w", "x", "y", "z" });

	List<String> lss = getPossibleKeys("726");
	System.out.println(lss.size());
}

public static ArrayList<String> getPossibleKeys(String key) {
	ArrayList<String> list = new ArrayList<String>();
	if (key.length() > 0) {
		if (key.contains("1") || key.contains("0")) {
			list.add(key);
		} else {
			int keyLen = key.length();
			String[] words;
			if (keyLen == 1) {
				words = keyMaps.get(key.charAt(0));
				for (int i = 0; i < words.length; i++) {
					list.add(words[i]);
				}
			} else {
				ArrayList<String> sonList = getPossibleKeys(key.substring(
						0, key.length() - 1));
				words = keyMaps.get(key.charAt(key.length() - 1));
				for (int i = 0; i < words.length; i++) {
					for (Iterator<String> iterator = sonList.iterator(); iterator
							.hasNext();) {
						String sonStr = iterator.next();
						list.add(sonStr + words[i]);
					}
				}
			}
		}
	}
	return list;
}

    所以可以反過(guò)來(lái)想，為什么一定要匹配拼音呢。其實(shí)我們可以匹配數(shù)字，將姓名的拼音轉(zhuǎn)化成九宮格上的數(shù)字，比如張三就是94264,726。用輸入的數(shù)字來(lái)匹配這些數(shù)字，匹配次數(shù)將大大減少。匹配出的數(shù)值越高，匹配度越強(qiáng)。

下面先定義一下幾個(gè)匹配規(guī)則

1. 完全匹配。用來(lái)匹配姓名和電話號(hào)碼。指輸入字符串與聯(lián)系人內(nèi)某一匹配項(xiàng)完全匹配。無(wú)加減分項(xiàng)。

   PanZhiHui-->PanZhiHui

2. 前置首字母完全匹配。用來(lái)匹配姓名。指輸入字符串與聯(lián)系人前幾個(gè)首字母完全匹配。用來(lái)匹配姓名。是前置首字母溢出匹配的特殊形式。 無(wú)加分項(xiàng)，減分項(xiàng)為不匹配的首字母?jìng)€(gè)數(shù)。

   PZH-->PanZhiHui。+2-0
   PZ-->PanZhiHui。+2-1

3. 前置首字母溢出匹配。用來(lái)匹配姓名。指在匹配首字母的情況下，還匹配了某一個(gè)或者幾個(gè)首字母后一段連貫的字符串。加分項(xiàng)為匹配到的首字母?jìng)€(gè)數(shù)，減分項(xiàng)為不匹配的首字母?jìng)€(gè)數(shù)。

   PanZH-->PanZhiHui。+1-0
   PZhiHui-->PanZhiHui。+1-0
   PZHui-->PanZhiHui。+1-0
   PZHu-->PanZhiHui。+1-0
   PZhi-->PanZhiHui。+1-1

4. 前置段匹配。用來(lái)匹配姓名。指一個(gè)長(zhǎng)度為N的連貫字符與聯(lián)系人內(nèi)某一匹配項(xiàng)的前N個(gè)字符完全匹配。是前置首字母溢出匹配的特殊形式。

   panzh-->PanZhiHui

5. 后置首字母完全匹配。用來(lái)匹配姓名。指輸入字符串匹配除第一個(gè)首字母以外的其他幾個(gè)連續(xù)首字母。 無(wú)加分項(xiàng)，減分項(xiàng)為不匹配的首字母?jìng)€(gè)數(shù)。

   ZH-->PanZhiHui

6. 后置首字母溢出匹配。用來(lái)匹配姓名。后置首字母完全匹配的情況下，還匹配了某一個(gè)或者幾個(gè)首字母后一段連貫的字符串。加分項(xiàng)為匹配的首字母的數(shù)量，減分項(xiàng)為不匹配的首字母?jìng)€(gè)數(shù)。

   ZHu-->PanZhiHui。+1-0
   Zh-->PanZhiRui。+1-1

7. 后置段匹配。用來(lái)匹配姓名。指有一串長(zhǎng)度為N的連貫字符與與聯(lián)系人內(nèi)某一匹配項(xiàng)的后半部的一段N個(gè)字符串匹配，且此連貫字符的開(kāi)頭位置必須是某一首字母位置。是后置首字母溢出匹配的特殊形式，同時(shí)意味著后置首字母溢出匹配事實(shí)上不需要加分項(xiàng)，只要保證后置首字母完全匹配的加分項(xiàng)比它大就足夠了。

   ZhiHui/Zhi/Hui-->PanZhiHui

8. 后置無(wú)頭匹配。用來(lái)匹配姓名和電話號(hào)碼。指一串連貫字符在前7種全部未匹配成功的情況下，卻被包含在字符串里。加分項(xiàng)為-index，減分項(xiàng)為長(zhǎng)度差

   hiHui-->PanZhiHui

每個(gè)規(guī)則都有一個(gè)基礎(chǔ)數(shù)值，以及加分減分項(xiàng)，基本數(shù)值不同。取減分項(xiàng)為0.001，加分項(xiàng)為1。至于為什么，在下一段。

查詢時(shí)匹配以上8種，其他情況不匹配。

匹配的原則是匹配盡可能多的單詞。

上面這些名字完全是臨時(shí)胡編亂造的好么 0.0

排列規(guī)則

1. 查詢出的列表將按匹配度排序，匹配度是一個(gè)float(當(dāng)然double也一樣)，優(yōu)先級(jí)別從高到低如下（減分項(xiàng)足夠小以至于高優(yōu)先級(jí)的匹配度無(wú)論如何減分都仍然會(huì)高于下面的優(yōu)先級(jí)，因此減分項(xiàng)事實(shí)上只用來(lái)區(qū)別同一優(yōu)先級(jí)中不同聯(lián)系人匹配程度的高低）。

• 完全匹配，對(duì)應(yīng)的基礎(chǔ)數(shù)值為4000。

• 前置首字母完全匹配、前置首字母溢出匹配、前置段匹配，這三個(gè)其實(shí)都可以視作前置首字母溢出匹配，對(duì)應(yīng)的基礎(chǔ)數(shù)值為3000。（當(dāng)只有一個(gè)字母時(shí)，按規(guī)則#1算）

• 后置首字母完全匹配、后置首字母溢出匹配、后置段匹配，這三個(gè)其實(shí)都可以視作后置首字母溢出匹配。對(duì)應(yīng)的基礎(chǔ)數(shù)值為2000。（當(dāng)只有一個(gè)字母時(shí)，按規(guī)則#5算）

• 后置無(wú)頭匹配。對(duì)應(yīng)的基礎(chǔ)數(shù)值為1000。（可以考慮摒棄此匹配，沒(méi)有人會(huì)這么按，而按鍵出錯(cuò)的可能性導(dǎo)致無(wú)頭匹配的可能性又極小，往往不是想要的結(jié)果）

  
  

  
  

輸入的一列查詢字符串將同時(shí)與聯(lián)系人的名字和電話匹配。對(duì)于一個(gè)聯(lián)系人，他的名字可能有多種發(fā)音，這時(shí)候要取匹配度最高的。對(duì)于一個(gè)聯(lián)系人，他可能有兩個(gè)甚至更多的電話號(hào)碼，匹配的時(shí)候要分別匹配，而不是單獨(dú)取匹配度最高的。

    好了，先寫(xiě)一個(gè)類(lèi)Contact。

    添加幾個(gè)常量，看字面意思應(yīng)該看得懂。

static final int Match_Type_Name = 1;
static final int Match_Type_Phone = 2;

static final int Level_Complete = 4;
static final int Level_Fore_Acronym_Overflow = 3;
static final int Level_Back_Acronym_Overflow = 2;
static final int Level_Headless = 1;
static final int Level_None = 0;

static final float Match_Level_None = 0;
static final float Match_Level_Headless = 1000;
static final float Match_Level_Back_Acronym_Overflow = 2000;
static final float Match_Level_Fore_Acronym_Overflow = 3000;
static final float Match_Level_Complete = 4000;
static final float Match_Score_Reward = 1;
static final float Match_Miss_Punish = 0.001f;
static final int Max_Reward_Times = 999;
static final int Max_Punish_Times = 999;

    再添加下面幾條字段

    List<ArrayList<String>> fullNameNumber = new ArrayList<ArrayList<String>>();
    List<String> fullNameNumberWithoutSpace = new ArrayList<String>();
    List<String> abbreviationNumber = new ArrayList<String>();

    fullNameNumber是一個(gè)二維的ArrayList，它存放的是將一個(gè)聯(lián)系人打散后數(shù)字后的List。比如張三的fullNameString就是{{94264,726}},之所以是二維的，原因是有可能姓名是含有多音字……

    fullNameNumberWithoutSpace是聯(lián)系人姓名的全拼對(duì)應(yīng)的數(shù)字，比如張三就是{94264726},之所以是二維的，原因是有可能姓名是含有多音字……

    abbreviationNumber是聯(lián)系人姓名首字母對(duì)應(yīng)的數(shù)字，比如張三對(duì)應(yīng)的就是{97},之所以是二維的，原因是有可能姓名是含有多音字……

    在設(shè)置了Contact的名字后上面三個(gè)字段將同時(shí)生成數(shù)據(jù)。

    synchronized public void initPinyin() {
            String trimmed = name.replaceAll(" ", "");
            //將姓名轉(zhuǎn)化為拼音
            String fullNamesString = HanyuPinyinHelper.hanyuPinYinConvert(trimmed, false);
            for (Iterator<String> iterator = fullNamesString.iterator(); iterator
                    .hasNext();) {
                String str = iterator.next();
                ArrayList<String> lss = new ArrayList<String>();
                String[] pinyins = TextUtil.splitIgnoringEmpty(str, " ");
                String abbra = "";
                String fullNameNumberWithoutSpaceString = "";
                for (int i = 0; i < pinyins.length; i++) {
                    String string = pinyins[i];
                    String res = convertString2Number(string);
                    abbra += res.charAt(0);
                    fullNameNumberWithoutSpaceString += res;
                    lss.add(res);
                }
                abbreviationNumber.add(abbra);
                fullNameNumberWithoutSpace
                        .add(fullNameNumberWithoutSpaceString);
                fullNameNumber.add(lss);
            }
    }

給它一個(gè)match方法。下面調(diào)用的xxxMatch()方法都是針對(duì)四種不同種類(lèi)的匹配的對(duì)應(yīng)方法。

public float match(String reg) {
	// 無(wú)法通過(guò)第一個(gè)字母來(lái)判斷是不是后置匹配
	// 但是可以通過(guò)第一個(gè)字母判斷是不是前置匹配
	// match的原則是匹配盡可能多的字符
	// 事實(shí)上前五種匹配方式都可以使用crossMatch來(lái)實(shí)現(xiàn)
	ScoreAndHits scoreAndHits = new ScoreAndHits(-1, 0f,
			new ArrayList<PointPair>());
	if (!TextUtils.isEmpty(reg)) {
		boolean checkBack = !canPrematch(reg);
		if (!checkBack) {
			if ((scoreAndHits = completeMatch(reg)).score == 0f) {
				if ((scoreAndHits = foreAcronymOverFlowMatch(reg)).score == 0f) {
					checkBack = true;
				}
			}
		}
		if (checkBack) {
			if ((scoreAndHits = backAcronymOverFlowMatch(reg)).score == 0f) {
				scoreAndHits = backHeadlessParagraphMatch(reg);
			}
		}
	}
	scoreAndHits.reg = reg;
	matchValue = scoreAndHits;
	return scoreAndHits.score;
}

所有的xxxMatch返回的結(jié)果是一個(gè)自定義類(lèi)ScoreAndHits。

public static class ScoreAndHits {
	public float score = 0f;
	public int nameIndex;
	public ArrayList<PointPair> pairs = new ArrayList<PointPair>();
	public int matchType = Match_Type_Name;
	public int matchLevel = Level_None;
	public String reg = "";

	public ScoreAndHits(int nameIndex, float score,
			ArrayList<PointPair> pairs) {
		this.nameIndex = nameIndex;
		this.score = score;
		this.pairs = pairs;
	}
}

nameIndex是匹配到了第幾個(gè)拼音。score是匹配度。pairs是指匹配到的數(shù)字在對(duì)應(yīng)的二維list中的位置，用來(lái)將來(lái)高亮顯示匹配的字符用的。如果完全匹配的話，就用不到pairs了。

幾個(gè)匹配方法的具體內(nèi)容看下一篇，超過(guò)字?jǐn)?shù)限制，寫(xiě)不開(kāi)了