联系人等拼音搜索算法与框架的心得

由于本人有些懒惰,不喜欢写博客之类的如有不妥还请见谅在完成我的通讯录项目的时候,需要用到T9和字符串匹配,在网上和github找了一通,发现并没有理想的算法,由于这部分算法即便现在不研究,以后肯定有用得着的地方,于是决定自己研究一下,

下面将研究了一个星期的成果公布出来,自己创造的小算法,如果有更好的还请提示一下,

此算法通配一切,qwer匹配,T9匹配

此算法不支持多音字,准确度为95%,目前未研究出100%的匹配算法,因为非常非常奇葩的组合并不常见,当然我认为又要考虑速度又要准确度,这就是矛盾的,我们能做的就是尽可能的平衡,想要支持多音字可以通过本自行演变,算法版本 1 > 时间复杂度 : 最优 O (m+n) m:输入长度 n:不匹配首字母

</pre><pre class="java" name="code"><pre name="code" class="java"> * @author Maizer麦泽
 * @version 1
 * @category search,arithmetic


	
	 * @param source
	 *            来源的拼音字符数组
	 * @param input
	 *            用户输入的字符
	 * @param colors
	 *            长度为二的数组,用来保存从颜色凸显,例如:王小二->汉字 拼音为:[wang][xiao][er] 用户输入:wanx
	 *            colors中会代入 0,2
	 * @return true匹配成功,false匹配失败

算法版本 2简单的优化了一下

</pre><pre class="java" name="code"><pre name="code" class="java">	/**
	 * 
	 * @param source
	 * @param input
	 * @param colors
	 * @return
	 */
	static int i = 0;

	public static boolean searchPinYin(Object[] source, String input, int[] colors) {
		int inputIndex = 0;
		int sourceLetter = 0;
		int letterIndex = 0;
		int start = -1;
		int end = 0;

		char[] inputbyte_carray = input.toCharArray();
		char[] sourcebyte_carray = source[sourceLetter].toString().toCharArray();

		// while (inputIndex > -1 && inputIndex < input.length() && sourceLetter
		// < source.length) {
		A: while (true) {
			i++;

			if (sourcebyte_carray.length == 1 && sourcebyte_carray[0] == ' ') {
				sourceLetter++;
				if (sourceLetter >= source.length) {
					break;
				}
				sourcebyte_carray = source[sourceLetter].toString().toCharArray();
				if (sourcebyte_carray[0] == inputbyte_carray[inputIndex - 1]) {
					letterIndex++;
				}
				// 以上此处可选,只是用来检测为空的字符
			} else if (inputbyte_carray[inputIndex] == sourcebyte_carray[letterIndex]) {
				letterIndex++;
				inputIndex++;
				end = sourceLetter;
				if (start == -1) {
					start = sourceLetter;
				}
				if (inputIndex >= inputbyte_carray.length) {
					break A;
				} else if (letterIndex == sourcebyte_carray.length) {
					letterIndex = 0;
					sourceLetter++;
					if (sourceLetter >= source.length) {
						break;
					}
					sourcebyte_carray = source[sourceLetter].toString().toCharArray();
					while (true) {
						if (sourcebyte_carray[letterIndex] != inputbyte_carray[inputIndex - 1]) {
							if (inputIndex >= inputbyte_carray.length) {
								break A;
							}
							if (sourcebyte_carray[letterIndex-1] == inputbyte_carray[inputIndex]) {
								inputIndex++;
							}
							break;
						}
						letterIndex++;
						if (letterIndex == sourcebyte_carray.length) {
							letterIndex = 0;
							sourceLetter++;
							if (sourceLetter >= source.length) {
								break A;
							}
							sourcebyte_carray = source[sourceLetter].toString().toCharArray();
						}
					}
				}
			} else if (letterIndex == 0 && inputIndex > 0) {
				inputIndex--;
				if (inputIndex <= 0) {
					start = -1;
				}
			} else {
				letterIndex = 0;
				sourceLetter++;
				if (sourceLetter >= source.length) {
					break;
				}
				sourcebyte_carray = source[sourceLetter].toString().toCharArray();
			}
		}
		if (inputIndex == input.length()) {
			if (colors != null) {
				if (colors.length >= 2) {
					colors[0] = start;
					colors[1] = end + 1;
				}
			}
			return true;
		}
		return false;
	}

2.框架部分对于拼音搜索,本来想全部使用字母树,进行组合查找,但是因为内耗太大问题,不了了之,所以我摘选了首列字母树,什么是首列字母树?

   首列字母树,就是将所有的拼音组合的首字母进行一个分类, 例如[wang][xiao][er],将w,x,e,分别分类到一个字母对象中,

   这样当用户输入w就可以快速的搜到该列,再由以上的搜索算法进行后续的摘选，当然也可以定制树的深度,比如多列字母树等,从而控制搜索速度

当然，还有最基本的最后搜索结果的重用