概述
使用拼音或拼音首字母進行搜索匹配，可以減少輸入搀矫，提高交互效率。在查找和搜索時帶來效率提升刻肄，在 iOS中瓤球，app本地搜索功能，需要實現(xiàn)拼音或拼音首字母匹配敏弃。本文從算法流程及實現(xiàn)中遇到的問題來闡述卦羡，并附上源碼實現(xiàn)。
需求
輸入拼音或拼音首字母，匹配對應(yīng)漢字字符绿饵。若原字符串中對應(yīng)有非漢字欠肾，則進行原始字符匹配。
比如:中華民族 拟赊，輸入:zhonghua或zh,匹配輸出:中華刺桃；zhan勝困難，輸入:zhansheng或zhans,匹配輸出:zhan勝吸祟；
為了減少用戶的輸入瑟慈，支持不完全輸入搜索。即最后一個拼音不用完整輸入屋匕，比如::中華民族 葛碧，輸入:zhongh,匹配輸出:中華。
算法設(shè)計
首先过吻，需要將漢字轉(zhuǎn)化為拼音
蘋果 CFString.h 中提供了將字符轉(zhuǎn)化為帶音標的拼音的函數(shù)：
CFStringTransform(CFMutableStringRef string, CFRange *range, CFStringRef transform, Boolean reverse)
可以將漢字先轉(zhuǎn)化為帶音標的拼音进泼，然后將音標去除：
- (NSString *)stringByFoldingWithOptions:(NSStringCompareOptions)options locale:(nullable NSLocale *)locale
第2步，進入匹配流程
-
準備工作：
由于中文拼音的復(fù)雜性纤虽，以及原始字符串可能是中英文混合字符串乳绕，所以構(gòu)造一個輔助數(shù)組，存儲每個字符的拼音廓推；另外構(gòu)造一個數(shù)組刷袍，存儲每個字符的首個拼音字母。
將轉(zhuǎn)化后的拼音拼接在一起樊展，組成一個完整的字符串拼音
用圖表示的流程如下：
生成拼音及拼音首字母
根據(jù)原始字符串得到拼音呻纹、拼音首字母及單個字符拼音組成的數(shù)組。
比如,只含有漢字专缠、漢字與英文混合等樣式的字符串經(jīng)過轉(zhuǎn)換雷酪，可以得到下列結(jié)果。
| 字符串（M） | 拼音（Str） | 首字母（LA） | 拼音組成的數(shù)組（SA） |
|---|---|---|---|
| 夜來風 | YELAIFENG | YLF | YE,LAI,FENG |
| ALC花 | ALCHUA | ALCH | A,L,C,HUA |
| 半夢半醒 | BANMENGBANXING | BMBX | BAN,MENG,BAN,XING |
2.2 正式匹配
首先將待匹配的字符串轉(zhuǎn)換為大寫涝婉，通過待匹配的字符串（M）的首字母哥力，去步驟 2.1 中得到的拼音首字母字符串(LA)中定位到位置i，然后借助拼音數(shù)組SA,尋找第i個位置的字符串墩弯，從第i個位置開始尋找最少個數(shù)(len)的字符串吩跋，拼接組成的字符串以M為起始字符串。
尋找成功渔工，則匹配的字符串位于原始字符串i锌钮，長度為len；若拼接子字符串長度大于或等于待匹配字符串引矩，或直到LA最后一個字符串梁丘，仍然找不到拼接的字符串能以M為起始字符串侵浸。則需要在拼音首字母字符串(LA)中重新定位，在位置i后尋找新的位置氛谜，重新上一個步驟掏觉。直至遍歷到LA的末尾字符，仍然沒有找到值漫，則匹配失敗澳腹。
以2.1中的表最后一個字符串為例，搜索: banxing.
| 步驟 | 操作內(nèi)容 |
|---|---|
| 1 | banxing 轉(zhuǎn)換為大寫-> BANXING |
| 2 | BANXING 取首字母 -> B |
| 3 | BMBX 中匹配 B惭嚣，得到位置NSRange r1 =（0,1） |
| 4 | (BAN,MENG,BAN,XING)第一個位置起遵湖，匹配含有 BANXING 的最短拼接字符串 |
| 4.1 | 取第一個拼音字符串，一個元素晚吞，得到 BAN延旧，不包含BANXING |
| 4.2 | 取第一個拼音字符串，2個元素槽地，得到 BANMENG迁沫，不包含BANXING的前綴 |
| 4.3 | 判斷拼接的拼音子字符串BANMENG長度，為7捌蚊，與BANXING的長度相等集畅，結(jié)束此輪匹配 |
| 5 | BMBXBFS 中，從第一個B后面缅糟，即第二個位置開始匹配 B挺智，得到位置NSRange r2 =（1,1），新的起始位置為 r1.location+r2.location+r2.length=0+1+1=2 |
| 5.1 | (BAN,MENG,BAN,XING)第2個位置起窗宦，匹配含有 BANXING 的最短拼接字符串 |
| 5.2 | 取第2個拼音字符串(一個元素)赦颇，得到 BAN，不包含BANXING |
| 5.3 | 取第一個拼音字符串赴涵，2個元素媒怯，得到 BANXING， |
| 5.4 | 判斷拼接的拼音子字符串 BANXING 的長度髓窜，與待匹配字符串長度一致扇苞，繼續(xù)。 |
| 5.5 | 拼接的 字符串 BANXING 包含 BANXING 的前綴寄纵。 匹配的長度為2 |
| 5.6 | 返回原字符串r3=（2,2）,即從第2個元素開始2個長度的字符串鳖敷。即: 半醒 |
- 校驗并匹配
根據(jù)生成的拼音或拼音首字母，當待匹配字符串在上述2個字符串中其中一個里面存在時程拭，再進行匹配.
遇到的問題
之前哄陶，借助漢字轉(zhuǎn)拼音的第三方庫[NSString+Extensional]，將整個原始字符串通過函數(shù)pinyinForSort作為整體轉(zhuǎn)換得到拼音,由于該函數(shù)返回的字符串哺壶，相鄰的漢字拼音使用空格' '分割屋吨，因此可以進一步使用NSString 的函數(shù):
- (NSArray<NSString *> *)componentsSeparatedByString:(NSString *)separator
得到拼音字符數(shù)組SA。不過針對中英文混合的字符串山宾，相鄰的英文和中文會連在一起至扰，中間沒有空格分割。導(dǎo)致使用該庫的函數(shù)firstLettersForSort得到的拼音首字母字符串FS長度與SA長度不一致资锰。給后續(xù)匹配造成困難敢课。
下標列出全部轉(zhuǎn)換為大寫后的結(jié)果:
| 庫函數(shù)結(jié)果 | 修改后函數(shù)結(jié)果 | |
|---|---|---|
| 原始字符串 | YDB4測試服7 | YDB4測試服7 |
| 字符串拼音 | YDB4CESHIFU7 |
YDB4CESHIFU7 |
| 字符串拼音首字母 | YDB4CSF7 |
YDB4CSF7 |
| 字符串拼音數(shù)組 | YDB4CE,SHI,FU7 |
Y,D,B,4,CE,SHI,FU,7 |
詳細代碼
將代碼放在了Github spellMatch,若有不足，歡迎指正绷杜。有幫助的話直秆，不吝star。
