智能拨号匹配算法（一）

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

    智能拨号是指，呃不用解释了，国内拨号软件都带的大家都知道，就是输入姓名拼音的一部分就可快速搜索出联系人的拨号方式。如下图

    智能匹配，很容易想到的就是先把九宫格输入键盘上输入的数字转换成可能的拼音组合，然后再用这些可能的拼音与联系人列表中的姓名拼音一一匹配，取匹配度最高的排到最前，但是这有一个问题就是数组对应的可能的拼音组合实在是点儿多，跑一下下面的代码就知道了。如果想智能一些的话还要先剔除一些不可能的拼音组合实在有点麻烦。

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;
}

    所以可以反过来想，为什么一定要匹配拼音呢。其实我们可以匹配数字，将姓名的拼音转化成九宫格上的数字，比如张三就是94264,726。用输入的数字来匹配这些数字，匹配次数将大大减少。匹配出的数值越高，匹配度越强。

下面先定义一下几个匹配规则

1. 完全匹配。用来匹配姓名和电话号码。指输入字符串与联系人内某一匹配项完全匹配。无加减分项。

   PanZhiHui-->PanZhiHui

2. 前置首字母完全匹配。用来匹配姓名。指输入字符串与联系人前几个首字母完全匹配。用来匹配姓名。是前置首字母溢出匹配的特殊形式。 无加分项，减分项为不匹配的首字母个数。

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

3. 前置首字母溢出匹配。用来匹配姓名。指在匹配首字母的情况下，还匹配了某一个或者几个首字母后一段连贯的字符串。加分项为匹配到的首字母个数，减分项为不匹配的首字母个数。

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

4. 前置段匹配。用来匹配姓名。指一个长度为N的连贯字符与联系人内某一匹配项的前N个字符完全匹配。是前置首字母溢出匹配的特殊形式。

   panzh-->PanZhiHui

5. 后置首字母完全匹配。用来匹配姓名。指输入字符串匹配除第一个首字母以外的其他几个连续首字母。 无加分项，减分项为不匹配的首字母个数。

   ZH-->PanZhiHui

6. 后置首字母溢出匹配。用来匹配姓名。后置首字母完全匹配的情况下，还匹配了某一个或者几个首字母后一段连贯的字符串。加分项为匹配的首字母的数量，减分项为不匹配的首字母个数。

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

7. 后置段匹配。用来匹配姓名。指有一串长度为N的连贯字符与与联系人内某一匹配项的后半部的一段N个字符串匹配，且此连贯字符的开头位置必须是某一首字母位置。是后置首字母溢出匹配的特殊形式，同时意味着后置首字母溢出匹配事实上不需要加分项，只要保证后置首字母完全匹配的加分项比它大就足够了。

   ZhiHui/Zhi/Hui-->PanZhiHui

8. 后置无头匹配。用来匹配姓名和电话号码。指一串连贯字符在前7种全部未匹配成功的情况下，却被包含在字符串里。加分项为-index，减分项为长度差

   hiHui-->PanZhiHui

每个规则都有一个基础数值，以及加分减分项，基本数值不同。取减分项为0.001，加分项为1。至于为什么，在下一段。

查询时匹配以上8种，其他情况不匹配。

匹配的原则是匹配尽可能多的单词。

上面这些名字完全是临时胡编乱造的好么 0.0

排列规则

1. 查询出的列表将按匹配度排序，匹配度是一个float(当然double也一样)，优先级别从高到低如下（减分项足够小以至于高优先级的匹配度无论如何减分都仍然会高于下面的优先级，因此减分项事实上只用来区别同一优先级中不同联系人匹配程度的高低）。

• 完全匹配，对应的基础数值为4000。

• 前置首字母完全匹配、前置首字母溢出匹配、前置段匹配，这三个其实都可以视作前置首字母溢出匹配，对应的基础数值为3000。（当只有一个字母时，按规则#1算）

• 后置首字母完全匹配、后置首字母溢出匹配、后置段匹配，这三个其实都可以视作后置首字母溢出匹配。对应的基础数值为2000。（当只有一个字母时，按规则#5算）

• 后置无头匹配。对应的基础数值为1000。（可以考虑摒弃此匹配，没有人会这么按，而按键出错的可能性导致无头匹配的可能性又极小，往往不是想要的结果）

  
  

  
  

输入的一列查询字符串将同时与联系人的名字和电话匹配。对于一个联系人，他的名字可能有多种发音，这时候要取匹配度最高的。对于一个联系人，他可能有两个甚至更多的电话号码，匹配的时候要分别匹配，而不是单独取匹配度最高的。

    好了，先写一个类Contact。

    添加几个常量，看字面意思应该看得懂。

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是一个二维的ArrayList，它存放的是将一个联系人打散后数字后的List。比如张三的fullNameString就是{{94264,726}},之所以是二维的，原因是有可能姓名是含有多音字……

    fullNameNumberWithoutSpace是联系人姓名的全拼对应的数字，比如张三就是{94264726},之所以是二维的，原因是有可能姓名是含有多音字……

    abbreviationNumber是联系人姓名首字母对应的数字，比如张三对应的就是{97},之所以是二维的，原因是有可能姓名是含有多音字……

    在设置了Contact的名字后上面三个字段将同时生成数据。

    synchronized public void initPinyin() {
            String trimmed = name.replaceAll(" ", "");
            //将姓名转化为拼音
            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);
            }
    }

给它一个match方法。下面调用的xxxMatch()方法都是针对四种不同种类的匹配的对应方法。

public float match(String reg) {
	// 无法通过第一个字母来判断是不是后置匹配
	// 但是可以通过第一个字母判断是不是前置匹配
	// match的原则是匹配尽可能多的字符
	// 事实上前五种匹配方式都可以使用crossMatch来实现
	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返回的结果是一个自定义类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是匹配到了第几个拼音。score是匹配度。pairs是指匹配到的数字在对应的二维list中的位置，用来将来高亮显示匹配的字符用的。如果完全匹配的话，就用不到pairs了。

几个匹配方法的具体内容看下一篇，超过字数限制，写不开了