一. 需求要求实现的效果
汉字支持汉字直接搜索、拼音全拼搜索、拼音简拼搜索
搜索匹配到的关键字高亮显示
搜索结果优先显示全部匹配、其次是拼音全拼匹配、拼音简拼匹配；关键字在结果字符串中位置越靠前，优先显示
支持搜索英文、汉字、电话号码及混合搜索
二. 需求分析
英文名称及电话号码的搜索直接使用完全匹配的方式即可
重难点是汉字的拼音相关的拼音全拼、简拼搜索，比如 “刘亦菲” 对应的搜索关键字有且只有以下三大类总计 25 种匹配汉字：“刘”、“亦”、“菲”、“刘亦”、“亦菲”、“刘亦菲”
简拼相关："l"、"y"、"f"、"ly"、"yf"、"lyf"
全拼相关："li"、"liu"、"liuy"、"liuyi"、"liuyif"、"liuyife"、"liuyifei"、"yi"、"yif"、"yife"、"yifei"、"fe"、"fei"
拼音的重难点还包括：比如搜索关键字为“xian”，既要匹配出“先”，也要匹配出“西安”
三. 代码设计
1. 整体流程
首先初始化原始的数据（包含汉语、英文、数字及随意组合），主要是将一个汉语字符串转化为汉语全拼拼音及每个拼音字母所对应汉字的位置 和 汉语简拼拼音和每个拼音字母对应汉字的位置，将初始化之后的信息缓存起来
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
+ (instancetype)personwithname:(nsstring *)name hanyupinyinoutputformat:(hanyupinyinoutputformat *)pinyinformat { wpfperson *person = [[wpfperson alloc] init]; /** 将汉字转化为拼音的类方法 * name : 需要转换的汉字 * pinyinformat : 拼音的格式化器 * @"" : seperator 分隔符 */ nsstring *completespelling = [pinyinhelper tohanyupinyinstringwithnsstring:name withhanyupinyinoutputformat:pinyinformat withnsstring:@""]; // 首字母所组成的字符串 nsstring *initialstring = @""; // 全拼拼音数组 nsmutablearray *completespellingarray = [[nsmutablearray alloc] init]; // 拼音首字母的位置数组 nsmutablearray *pinyinfirstletterlocationarray = [[nsmutablearray alloc] init]; // 遍历每一个字符 for (nsinteger x =0; x根据 uisearchresultsupdating 代理方法 - (void)updatesearchresultsforsearchcontroller:(uisearchcontroller *)searchcontroller 来实时获取输入的最新关键字，并遍历数据源，将匹配到的结果显示出来// 更新搜索结果- (void)updatesearchresultsforsearchcontroller:(uisearchcontroller *)searchcontroller { nslog(@"%@", searchcontroller.searchbar.text); [self.searchresultvc.resultdatasource removeallobjects]; for (wpfperson *person in self.datasource) { wpfsearchresultmodel *resultmodel = [wpfpinyintools searcheffectiveresultwithsearchstring:searchcontroller.searchbar.text.lowercasestring namestring:person.name completespelling:person.completespelling initialstring:person.initialstring pinyinlocationstring:person.pinyinlocationstring initiallocationstring:person.initiallocationstring]; if (resultmodel.highlightrang.length) { person.highlightloaction = resultmodel.highlightrang.location; person.textrange = resultmodel.highlightrang; person.matchtype = resultmodel.matchtype; [self.searchresultvc.resultdatasource addobject:person]; } }; // 将匹配结果按照产品规则进行排序 [self.searchresultvc.resultdatasource sortusingdescriptors:[wpfpinyintools sortingrules]]; // 刷新tableview dispatch_async(dispatch_get_main_queue(), ^{ [self.searchresultvc.tableview reloaddata]; });} |
匹配的过程是一个重难点，分别进行汉字直接匹配、拼音全拼匹配、拼音简拼匹配
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
+ (wpfsearchresultmodel *)searcheffectiveresultwithsearchstring:(nsstring *)searchstrlower namestring:(nsstring *)namestrlower completespelling:(nsstring *)completespelling initialstring:(nsstring *)initialstring pinyinlocationstring:(nsstring *)pinyinlocationstring initiallocationstring:(nsstring *)initiallocationstring { wpfsearchresultmodel *searchmodel = [[wpfsearchresultmodel alloc] init]; nsarray *completespellingarray = [pinyinlocationstring componentsseparatedbystring:@","]; nsarray *pinyinfirstletterlocationarray = [initiallocationstring componentsseparatedbystring:@","]; // 完全中文匹配范围 nsrange chineserange = [namestrlower rangeofstring:searchstrlower]; // 拼音全拼匹配范围 nsrange complaterange = [completespelling rangeofstring:searchstrlower]; // 拼音首字母匹配范围 nsrange initialrange = [initialstring rangeofstring:searchstrlower]; // 汉字直接匹配 if (chineserange.length!=0) { searchmodel.highlightedrange = chineserange; searchmodel.matchtype = matchtypechinese; return searchmodel; } nsrange highlightedrange = nsmakerange(0, 0); // mark: 拼音全拼匹配 if (complaterange.length != 0) { if (complaterange.location == 0) { // 拼音首字母匹配从0开始，即搜索的关键字与该数据源第一个汉字匹配到，所以高亮范围从0开始 highlightedrange = nsmakerange(0, [completespellingarray[complaterange.length-1] integervalue] +1); } else { /** 如果该拼音字符是一个汉字的首个字符，如搜索“g”， * 就要匹配出“gai”、“ge”等“g”开头的拼音对应的字符， * 而不应该匹配到“wang”、“feng”等非”g“开头的拼音对应的字符 */ nsinteger currentlocation = [completespellingarray[complaterange.location] integervalue]; nsinteger lastlocation = [completespellingarray[complaterange.location-1] integervalue]; if (currentlocation != lastlocation) { // 高亮范围从匹配到的第一个关键字开始 highlightedrange = nsmakerange(currentlocation, [completespellingarray[complaterange.length+complaterange.location -1] integervalue] - currentlocation +1); } } searchmodel.highlightedrange = highlightedrange; searchmodel.matchtype = matchtypecomplate; if (highlightedrange.length!=0) { return searchmodel; } } // mark: 拼音首字母匹配 if (initialrange.length!=0) { nsinteger currentlocation = [pinyinfirstletterlocationarray[initialrange.location] integervalue]; nsinteger highlightedlength; if (initialrange.location ==0) { highlightedlength = [pinyinfirstletterlocationarray[initialrange.length-1] integervalue]-currentlocation +1; // 拼音首字母匹配从0开始，即搜索的关键字与该数据源第一个汉字匹配到，所以高亮范围从0开始 highlightedrange = nsmakerange(0, highlightedlength); } else { highlightedlength = [pinyinfirstletterlocationarray[initialrange.length+initialrange.location-1] integervalue]-currentlocation +1; // 高亮范围从匹配到的第一个关键字开始 highlightedrange = nsmakerange(currentlocation, highlightedlength); } searchmodel.highlightedrange = highlightedrange; searchmodel.matchtype = matchtypeinitial; if (highlightedrange.length!=0) { return searchmodel; } } searchmodel.highlightedrange = nsmakerange(0, 0); searchmodel.matchtype = nsintegermax; return searchmodel;} |
2. 第三方依赖
首先筛选出一个比较全的第三方库 pinyin4objc用于汉语转拼音，拼音的 unicode 库比较全，一些新的汉字也都能转成拼音
但是由于该库好久没有更新，获取拼音文件部分代码不适合组件化的直接开发，因此我直接合到源文件里面了
汉语转拼音的格式
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
// 获取格式化器+ (hanyupinyinoutputformat *)getoutputformat { hanyupinyinoutputformat *pinyinformat = [[hanyupinyinoutputformat alloc] init]; /** 设置大小写 * casetypelowercase : 小写 * casetypeuppercase : 大写 */ [pinyinformat setcasetype:casetypelowercase]; /** 声调格式 ：如 王鹏飞 * tonetypewithtonenumber : 用数字表示声调 wang2 peng2 fei1 * tonetypewithouttone : 无声调表示 wang peng fei * tonetypewithtonemark : 用字符表示声调 wáng péng fēi */ [pinyinformat settonetype:tonetypewithouttone]; /** 设置特殊拼音ü的显示格式： * vchartypewithuandcolon : 以u和一个冒号表示该拼音，例如：lu: * vchartypewithv : 以v表示该字符，例如：lv * vchartypewithuunicode : 以ü表示 */ [pinyinformat setvchartype:vchartypewithv]; return pinyinformat;} |
3. 其他细节
排序规则
|
1
2
3
4
5
6
7
|
+ (nsarray *)sortingrules { // 按照 matchtype 顺序排列，即优先展示 中文，其次是全拼匹配，最后是拼音首字母匹配 nssortdescriptor *destype = [nssortdescriptor sortdescriptorwithkey:@"matchtype" ascending:yes]; // 优先显示 高亮位置索引靠前的搜索结果 nssortdescriptor *deslocation = [nssortdescriptor sortdescriptorwithkey:@"highlightloaction" ascending:yes]; return @[destype,deslocation];} |
四. 循环方法测试及优化选择过程
在优化遍历方法的过程中，测试了几种遍历方法，这里以输入关键字“wang”为测试数据，测试真机机型为iphone se 10.3
常规 for 循环
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/** 2017-12-06 12:02:51.943006 highlightedsearch[4459:1871193] w 2017-12-06 12:02:51.943431 highlightedsearch[4459:1871193] 开始匹配，开始时间：2017-12-06 04:02:51 +0000 2017-12-06 12:02:51.980588 highlightedsearch[4459:1871193] 匹配结束，结束时间：2017-12-06 04:02:51 +0000，耗时：0.0372 2017-12-06 12:02:52.284488 highlightedsearch[4459:1871193] wa 2017-12-06 12:02:52.284771 highlightedsearch[4459:1871193] 开始匹配，开始时间：2017-12-06 04:02:52 +0000 2017-12-06 12:02:52.316536 highlightedsearch[4459:1871193] 匹配结束，结束时间：2017-12-06 04:02:52 +0000，耗时：0.0318 2017-12-06 12:02:52.516826 highlightedsearch[4459:1871193] wan 2017-12-06 12:02:52.517121 highlightedsearch[4459:1871193] 开始匹配，开始时间：2017-12-06 04:02:52 +0000 2017-12-06 12:02:52.545542 highlightedsearch[4459:1871193] 匹配结束，结束时间：2017-12-06 04:02:52 +0000，耗时：0.0285 2017-12-06 12:02:52.838220 highlightedsearch[4459:1871193] wang 2017-12-06 12:02:52.838602 highlightedsearch[4459:1871193] 开始匹配，开始时间：2017-12-06 04:02:52 +0000 2017-12-06 12:02:52.880200 highlightedsearch[4459:1871193] 匹配结束，结束时间：2017-12-06 04:02:52 +0000，耗时：0.0417 */for (nsinteger i = 0; i < self.datasource.count; i++) { |
gcd 多线程循环
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
/** 2017-12-06 11:56:55.565738 highlightedsearch[4419:1869486] w 2017-12-06 11:56:55.566287 highlightedsearch[4419:1869486] 开始匹配，开始时间：2017-12-06 03:56:55 +0000 2017-12-06 11:56:55.626184 highlightedsearch[4419:1869486] 匹配结束，结束时间：2017-12-06 03:56:55 +0000，耗时：0.0601 2017-12-06 11:56:55.937535 highlightedsearch[4419:1869486] wa 2017-12-06 11:56:55.937842 highlightedsearch[4419:1869486] 开始匹配，开始时间：2017-12-06 03:56:55 +0000 2017-12-06 11:56:55.983074 highlightedsearch[4419:1869486] 匹配结束，结束时间：2017-12-06 03:56:55 +0000，耗时：0.0452 2017-12-06 11:56:56.344808 highlightedsearch[4419:1869486] wan 2017-12-06 11:56:56.347350 highlightedsearch[4419:1869486] 开始匹配，开始时间：2017-12-06 03:56:56 +0000 2017-12-06 11:56:56.414215 highlightedsearch[4419:1869486] 匹配结束，结束时间：2017-12-06 03:56:56 +0000，耗时：0.0690 2017-12-06 11:56:56.711174 highlightedsearch[4419:1869486] wang 2017-12-06 11:56:56.712013 highlightedsearch[4419:1869486] 开始匹配，开始时间：2017-12-06 03:56:56 +0000 2017-12-06 11:56:56.774761 highlightedsearch[4419:1869486] 匹配结束，结束时间：2017-12-06 03:56:56 +0000，耗时：0.0632 */dispatch_queue_t queue = dispatch_get_global_queue(dispatch_queue_priority_default, 0);dispatch_apply(self.datasource.count, queue, ^(size_t index) { |
enumerateobjectswithoptions 多线程循环
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
/** 2017-12-06 11:58:12.716606 highlightedsearch[4428:1869917] w 2017-12-06 11:58:12.717005 highlightedsearch[4428:1869917] 开始匹配，开始时间：2017-12-06 03:58:12 +0000 2017-12-06 11:58:12.780168 highlightedsearch[4428:1869917] 匹配结束，结束时间：2017-12-06 03:58:12 +0000，耗时：0.0633 2017-12-06 11:58:13.058590 highlightedsearch[4428:1869917] wa 2017-12-06 11:58:13.058841 highlightedsearch[4428:1869917] 开始匹配，开始时间：2017-12-06 03:58:13 +0000 2017-12-06 11:58:13.116964 highlightedsearch[4428:1869917] 匹配结束，结束时间：2017-12-06 03:58:13 +0000，耗时：0.0581 2017-12-06 11:58:13.397052 highlightedsearch[4428:1869917] wan 2017-12-06 11:58:13.397338 highlightedsearch[4428:1869917] 开始匹配，开始时间：2017-12-06 03:58:13 +0000 2017-12-06 11:58:13.460298 highlightedsearch[4428:1869917] 匹配结束，结束时间：2017-12-06 03:58:13 +0000，耗时：0.0630 2017-12-06 11:58:13.763888 highlightedsearch[4428:1869917] wang 2017-12-06 11:58:13.764263 highlightedsearch[4428:1869917] 开始匹配，开始时间：2017-12-06 03:58:13 +0000 2017-12-06 11:58:13.833888 highlightedsearch[4428:1869917] 匹配结束，结束时间：2017-12-06 03:58:13 +0000，耗时：0.0697 */dispatch_queue_t queue = dispatch_queue_create("wpf.updatesearchresults.test", dispatch_queue_serial);[self.datasource enumerateobjectswithoptions:nsenumerationconcurrent usingblock:^(id _nonnull obj, nsuinteger idx, bool * _nonnull stop) { |
forin 循环
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/** 2017-12-06 12:00:38.217187 highlightedsearch[4439:1870645] w 2017-12-06 12:00:38.217575 highlightedsearch[4439:1870645] 开始匹配，开始时间：2017-12-06 04:00:38 +0000 2017-12-06 12:00:38.253997 highlightedsearch[4439:1870645] 匹配结束，结束时间：2017-12-06 04:00:38 +0000，耗时：0.0364 2017-12-06 12:00:38.616430 highlightedsearch[4439:1870645] wa 2017-12-06 12:00:38.616807 highlightedsearch[4439:1870645] 开始匹配，开始时间：2017-12-06 04:00:38 +0000 2017-12-06 12:00:38.654969 highlightedsearch[4439:1870645] 匹配结束，结束时间：2017-12-06 04:00:38 +0000，耗时：0.0383 2017-12-06 12:00:38.948700 highlightedsearch[4439:1870645] wan 2017-12-06 12:00:38.949453 highlightedsearch[4439:1870645] 开始匹配，开始时间：2017-12-06 04:00:38 +0000 2017-12-06 12:00:38.986892 highlightedsearch[4439:1870645] 匹配结束，结束时间：2017-12-06 04:00:38 +0000，耗时：0.0378 2017-12-06 12:00:39.280979 highlightedsearch[4439:1870645] wang 2017-12-06 12:00:39.281563 highlightedsearch[4439:1870645] 开始匹配，开始时间：2017-12-06 04:00:39 +0000 2017-12-06 12:00:39.317743 highlightedsearch[4439:1870645] 匹配结束，结束时间：2017-12-06 04:00:39 +0000，耗时：0.0365 */for (wpfperson *person in self.datasource) { |
最终选择的是forin循环，因为一般情况下 enumerateobjectswithoptions 多线程是最快的，并且稍快于 dispatch_apply 方法，但是因为这个方法需要操作数组，因此必须将操作数据的那行代码加锁或者在指定线程进行，进行这个操作后效率反而不如其他单线程循环，考虑到搜索结果本来还要再次根据规则排序，就选择了 forin 循环
五. 为什么没有选择hash
首先最重要的一条是当前循环的方式也能满足需求（线上大概四千多条数据，使用过程中基本实时展现）
上文在需求分析中已举例，一个三个字的汉字对应的key值就有20多个甚至更多，在解析过程中是十分耗时的，但需求往往还存在类似微信的“群名称”匹配，每多一个字，对应的key值就多几个数量级
maptable在高并发情况下，需要不断进行resize（扩容 & rehash），并且在rehash 并发的情况下还可能形成链表环有个优化的思路，考虑到遍历的方式解析快，搜索匹配慢；hash的方式解析慢，搜索匹配快
通过遍历的方式先快速解析数据，此时搜索使用遍历的方式
然后再用hash的方式再次解析数据（考虑到hash表的扩容会使得瞬时效率的降低，为了避免频繁的扩容，先使用桶排序的方法将10个数字、26个英文字母、以及特殊符号开头的key分别放在37个字典里面，整体是一个数组。每个字典里面存放对应key和value），解析完成之后做个标记就采用hash的方式直接使用输入的key值去查询
配合db缓存，效果应该是很棒的
六. 多音字
简单测了一下拥有该功能的产品：
微信搜索（就是文中讲的该类型搜索）是在本地做的，不支持多音字
钉钉的搜索是服务器做的，支持多音字（但是简单测了一下一些基本的多音字存在bug）
七. 实际项目还要做哪些工作？
正常情况下不会将所有的匹配结果在第一时间全部显示，一般产品需求显示三五个即可，因此可以匹配出若干个结果后停止循环，点击更多再匹配剩余数据源
配合db和hashtable，每次只解析新增的数据源，解析一次后就缓存起来
八. 使用方法
1. 事例工程
|
1
2
3
|
git clone git@github.com:pengfeiwang666/highlightedsearch.gitcd exampleopen highlightedsearch.xcworkspace |
2. install
pod "highlightedsearch"
3. usage
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// wpfpinyindatamanager 依次添加数据源（标识符为了防止重名现象）+ (void)addinitializestring:(nsstring *)string identifer:(nsstring *)identifier// 更新搜索结果- (void)updatesearchresultsforsearchcontroller:(uisearchcontroller *)searchcontroller { ... ... for (wpfperson *person in [wpfpinyindatamanager getinitializeddatasource]) { wpfsearchresultmodel *resultmodel = [wpfpinyintools searcheffectiveresultwithsearchstring:keyword person:person]; if (resultmodel.highlightedrange.length) { person.highlightloaction = resultmodel.highlightedrange.location; person.textrange = resultmodel.highlightedrange; person.matchtype = resultmodel.matchtype; [resultdatasource addobject:person]; }} |
