T9拨号盘搜索和排序算法

一. 背景

今日头条为何能突破bat的壁垒，很大程度在于它精确的推荐算法，能够根据用户的喜爱推荐适合用户的资讯，不断根据用户的浏览记录构建用户的偏好生态圈，进而精准投放流量。

大家平常拨打电话应该都有用T9拨号盘吧，输入几个数字后一般会把当前通讯录匹配中的联系人显示出来并高亮显示命中的字符，根据输入的数字串显示哪些联系人数据以及这些联系人数据如果排序显得十分重要，站在用户角度，尽可能的少输入数字并能把用户想拨打的联系人优先显示到前列，这里面涉及的算法就尤为重要了，在此感谢产品mm对权重分配的打磨。

二. T9匹配和排序思路

加载本地通讯录，本地通讯录作为数据源；
获取本地通话记录，通话记录作为其中一项影响因子；
本地联系人的名字转化为T9键盘上对应的数字，根据输入的数字串进行匹配；
根据首字母匹配、全拼匹配、号码匹配三种类型确认匹配的数据源；
根据各项影响因子分别计算对应的权重，最终累加权重作为联系人排序的依据。

三. 联系人实体类

拿名字曾轶可拨号盘输入95举例，注意曾是多音字

t9.png

联系人SimpleContact

字段	值	类型	描述
mName	曾轶可	String	名字
mNumber	13912345678	String	号码
isFirstMatch	true	boolean	是否首字母匹配
firstCharactorCounts	2	int	拼音匹配到多少汉字
numberMatchId	-1	int	号码匹配的下标
pinyinMatchId	(10,13)	List<Integer>	关键字在全拼中的下标
startIndex	1	int	keyword在contact首字母拼接字符串的起始位置
searchType	1	int	搜索类型（拼音SEARCH_TYPE_PINYIN1，号码SEARCH_TYPE_NUMBER2）
PinYin		PinYin	拼音类
simplePinyinIndex	0	int	记录用的是哪个首字母拼接字符串
hightLighter	12	List<Integer>	高亮的字符位置
mSearchWeight	0	float	权重
spaceIndexList	null	List<Integer>	名字中空格的下标

拼音PinYin

字段	值	类型	描述
firstMatchId	0 10 13	List<Integer>	首字母在全拼中的下标
mNormalPinyin	zeng_ceng yi ke	String	words每个汉字的拼音拼接，并且每个汉字拼音之间用空格隔开
mT9Pinyin	9364_2364 94 53	String	和normalPinyin对应，转化为T9上数字
nameArray	zeng_ceng yi ke	String[]	words中每个汉字的拼音
normalPinyinFirstList	zyk cyk	List<String>	首字母
simplePinyin	zyk	String	words拼音首字母的拼接
t9PinyinFirstList	995 295	List<String>	首字母对应的t9数字

四. 匹配数据源逻辑

/** 
* 根据关键字，返回搜索列表。 
* @param queryString  当前的搜索关键字 
* @param preInput    上一次的搜索关键字 
* @param searchCache  上一次的搜索结果列表 
* @param contactList   总搜索数据源列表
/
public static List<SimpleContact> searchT9StringInContacts(String queryString, String preInput, 
List<SimpleContact> searchCache,                                                           ArrayList<SimpleContact> contactList)

以首字母-全拼-号码依次优先级匹配：

首字母
根据首字母在全拼中的下标firstMatchId字段匹配当前输入数字串，若前者包含后者，则首字母命中，获取首字母匹配个数和数字串在全拼中的下标，设为拼音类型。
如曾轶可（zengyike），首字母完全匹配995(zyk)、首字母非完全匹配(9、5、99、95等)
全拼
若1不符合，根据mT9Pinyin（全拼音转化为t9数字）匹配输入数字串，若前者包含后者，则全拼命中，获取数字串在全拼中的下标，设为拼音类型。
如曾轶可（zengyike）,全拼完全匹配9364 94 53、全拼非完全匹配（936、93649、945、53等），全拼匹配必须连续，且以字的首字母开头，364就不符合规则
号码
若1和2不符合，根据mNumber（号码）匹配输入数字串，若前者包含后者，则号码命中，获取数字串在号码中的起始匹配位置，设为号码类型。
如曾轶可的号码为13912345678，只要是该号码的字串即可（39、123、5678等）。

高亮规则
不管是首字母、全拼还是号码匹配，都必须是连续的，命中首字母则对应的汉字高亮，匹配到几个则几个高亮。

五. 排序算法

整体的排序优先级是根据各项影响因子来累积权值，根据最终权重大小排个高低。
影响因子有：

联系人匹配类型（首字母匹配、全拼匹配、号码匹配）
完全匹配、非完全匹配
关键字的首字母在源数据的起始配置
名字长度
通话记录
名字高亮数量
T9上的字母顺序
根据各因子的权值、系数来控制算法的合理性

private static  int FirstMatch= 20;//首字母匹配初始值
private static  int AllFirstMatch=10000;//首字母全匹配
private static  int charMatch=15;//拼音匹配初始值
private static  int AllCharMatch=10000;//拼音完全匹配
private static  int numberMatch=10;//号码匹配初始值
private static  int AllNumberMatch=10000;//号码完全匹配
private static int NotAllCharMatchIni=600;//拼音字母非完全匹配初始值
private static int NotAllNumMatchIni=0;//号码非完全匹配初始值
private static  int Charorder=2;//字母顺序系数
private static  int StartIndexweight=1;//首字母位置系数
private static  float FirstCharactorCounts=0.5f;//首字母数量系数
private static  float NameCounts=0.05f;//名字数量系数
private static  int Fristchar=65;//第一位系数
private static  int Secondchar=15;//第二位系数
private static  int Thirdchar= 10;//第三位系数
private static  int CalllogNum=100;//通话纪录初始值
private static  int MaxCallLogNum=550;//通话记录最大数
private static int CalllogNumweight=1;//通话记录系数
private static int CharAsciiMax=127;//字母顺序最大值

详细算法和各因子权值公式

T9排序算法 .png

六. 该权值分配下的算法详述

根据权值分配的不同可实现不同的产品场景

1. 完全匹配

完全匹配的搜索结果一定高于非完全匹配的搜索结果。通话记录、名字高亮数量、字母顺序等，都不能使得非完全匹配的结果高于完全匹配结果。

在输入同样数字，符合完全匹配的情况下：首字母完全匹配＞拼音完全匹配＞号码完全匹配。

同是完全匹配情况下，则按照以下逻辑进行排序。

通话记录说明：

如数字426，对应源数据“黄安墨”（首字母完全匹配）、“汉”（拼音完全匹配）、426（号码完全匹配），默认排序位置：黄安墨＞汉＞426（号码），在无通话记录影响下，黄安墨（10000+20+0.5*3）＞汉（10000+15+0.5）＞426（10000+10）。

首字母完全匹配、拼音完全匹配、号码完全匹配，其中一个类型只要拥有通话记录，则一定会超越剩下两种无通话记录的类型。其余影响因素如首字母匹配数量、字母系数等，都无法帮助其超越。

如“汉”拥有了一条呼出记录，则汉分值调整为（10000+15+100+15+0.5），最新排名调整为汉＞黄安墨＞426。

在同样都拥有相同数量的通话记录情况下，首字母完全匹配+呼出/呼入1条＞拼音完全匹配+呼出/呼入1条＞号码完全匹配+呼入/呼出1条。

如黄安墨呼入1条分值为（10000+20+100+101+0.53）、汉呼出1条（10000+15+100+15*1+0.5）。则排名为黄安墨＞汉。

首字母匹配数量说明：

首字母匹配数量，在无通话记录影响，无字母系数、无完全匹配类型（拼音完全匹配&姓名完全匹配&号码完全匹配）影响，其数值表现比较明显。

如数字482，对应源数据“胡啊”（拼音完全匹配）、“花”（拼音完全匹配）、482（号码完全匹配），默认排序位置：胡啊＞花＞482。

计算其首字母匹配数量，胡啊命中2个首字母；花仅命中名字的一个首字母；482手机号码则不命中首字母数量，得分排名为胡啊（10000+15+2*0.5）＞花（10000+15+0.5）＞482（10000+10=10010）

字母顺序说明：

首字母系数数值，在无通话记录影响、无首字母匹配数量、无完全匹配类型（拼音完全匹配&姓名完全匹配&号码完全匹配）影响，其数值表现比较明显。

如输入“45”，对应源数据“胡凯”和“郭磊”，均属于首字母完全匹配。由于胡凯的“胡”占数字键盘4的第二位，郭磊的“郭”占数字键盘4的第一位，在字母系数权重处，郭磊比胡凯会多两分。且由于其余影响因素数值相同，则排位为郭磊＞胡凯。

首字母匹配数量数值要低于字母顺序。如输入“482”，对应源数据“胡啊”“瓜”，则胡啊分数为10000+15+0.5×2=10016，瓜分数10000+15+0.5×1+2（G比H多2）=10018，则排名为瓜＞胡啊。

2. 非完全匹配
完全匹配的搜索结果一定高于非完全匹配的搜索结果。通话记录、首字母匹配数量、字母顺序数值累加，都不能使得非完全匹配的结果高于完全匹配结果。

非完全匹配情况下，默认姓名非完全匹配的初始值（600分）要大于号码的非完全匹配。即无论“号码非完全匹配”的其他因子权重如何相加，都无法超越“姓名非完全匹配。”

若用户以数字作为姓名，纯数字姓名，则以首字母匹配进行搜索；若是汉字+数字，则根据用户输入的拨号盘数字，对应的是拼音搜索还是首字母搜索，来加对应分值。如源数据“盈盈23”，若用户输入992，则属于首字母不完全匹配搜索，若用户输入“946494642”则属于拼音不完全匹配搜索。

关键字的首字母命中源数据的位置。

在无通话记录影响情况下，输入同样数字，数字命中源数据位置1、2位分值，影响其排序。如输入数字“99”，对应源数据“郭盈盈”、“盈盈家”，由于第1个数字9命中郭盈盈名字的第二个首字母，命中“盈盈家”名字的第一个首字母，郭盈盈得分（600+15+20=635），盈盈家得分（600+65+20=685）。则排名“盈盈家”＞“郭盈盈”。

通话记录说明：

在同等源数据位置情况下，首字母非完全匹配、拼音非完全匹配，其中一个类型只要拥有通话记录，则一定会超越剩下剩下无通话记录的类型。其余影响因素如首字母匹配数量、字母系数等，都无法帮助其超越。

如数字26，对应源数据“阿宁家”（首字母非完全匹配）、“安家乐”（拼音非完全匹配），则“阿宁家”得分（600+65+20+0.52）；”安家乐”得分(600+65+15++0.7+0.51)。

在同等源数据位置情况下，在同样都拥有相同数量的通话记录情况下，首字母非完全匹配+呼出/呼入n条＞拼音非完全匹配+呼出/呼入n条。
在不同源数据位置情况下，首字母非完全匹配、拼音非完全匹配，则一定会超越剩下无通话记录的类型。其余影响因素如首字母匹配数量、字母系数等，都无法帮助其超越。
在不同源数据位置且都拥有通话记录的情况下，属于命中源数据位置后几位的源数据，需要比前面位置的源数据，多几条通话记录才能超越前面位置的源数据位置。

如99对应源数据“郭盈盈”“盈盈家”。若“盈盈家”呼出1条，“郭盈盈”呼出5条，则“盈盈家”得分（600+65+20+100+151+0.52）；郭盈盈得分（600+15+20+100+155+0.52），此时排名顺序：郭盈盈＞盈盈家。

拼音不完全匹配的字符长度：

拼音非完全匹配的字符长度，只有在其他因素不变的情况下，数值变化比较明显。
如4对应源数据“个杀个脚后跟”，“郭烧开后风给好得更快了”。则在其他数值相同的情况下，由于前者名称更短，则前者排名更高。

字母匹配数量说明：

首字母匹配数量，在无匹配命中源数据位置，无通话记录影响，无字母系数，无完全匹配类型（拼音完全匹配&姓名完全匹配&号码完全匹配）等因素影响，其数值表现比较明显。

如数字482，对应源数据“胡啊美”（拼音不完全匹配）、“花朵儿”（拼音不完全匹配）、4820（号码不完全匹配）。则胡啊美的分值（600+65+15+0.7+0.52），花朵儿分值（600+65+15+0.7+0.51），4820（20+10分）。排名为：胡啊美＞花朵儿＞4820

字母顺序说明：

首字母系数数值，在无通话记录影响、无首字母匹配数量、无完全匹配类型（拼音
完全匹配&姓名完全匹配&号码完全匹配）影响，其数值表现比较明显。

如输入“45”，对应源数据“胡凯和”和“郭磊和”，均属于首字母非完全匹配。由于胡
和的“胡”占数字键盘4的第二位，郭磊和的“郭”占数字键盘4的第一位，在字母系数权重处，郭磊和比胡凯和会多两分。且由于其余影响因素数值相同，则排位为郭磊和＞胡凯和。

首字母匹配数量数值要低于字母顺序。

如输入“45”，对应源数据“郭梅和”“胡磊和”，由于同在数字键盘4的G比H多2分，而郭梅和仅命中1个首字母，胡磊和命中2个首字母，则郭梅和分数为600+65+20+0.5×1+2（G比H多2），胡磊和分数为600+65+20+0.5×2，则排名为郭梅和＞胡磊。

七. T9Demo工程

话不多说，直接上工程，包括T9搜索和排序相关的实体和操作类以及一个简陋的界面。

项目图.png

工程链接:
https://github.com/tslearner/T9demo