引言
开发系统的过程中我们最常遇到的搜索场景是 LIKE 模糊搜索，也就是按连续子串来通配，比如搜索书籍名称中有 “爱” 的，则可以匹配 “爱的教育”、“简爱”、“张爱玲全集” 等。但怎么说，这种方式虽是模糊搜索，但似乎还是有精确的成分在里面，毕竟匹配的是连续的字符串，对于一些灵活性要求更高的搜索场景则不太适用，比如今天想分享的——按拼音首字母、全拼、半拼来搜索的算法，当我们搜索 “yg”、“yangguang”、“yaguan” 的时候，都可以匹配词语 “阳光”。拼音搜索在通讯录场景有广泛应用，通常用来查询姓名使用，可以提升系统的使用体验。常见的一些搜索引擎比如 ElasticSearch 已提供了相应的拼音插件支持拼音搜索，但如果我们只是用在几百个人的姓名搜索上，引入搜索引擎未免太重。此时，我们可以考虑使用一些拼音搜索的工具包来快速实现，下面总结下之前自己写的一个工具的实现思路。
基本思路
最早接到这个需求是在老师与某运营商合作的总机客服系统里，需要支持客服按拼音快速搜索客户昵称，而且客户的昵称还可能是中英夹杂的。开头我也没有思路，后来决定分而治之，先只考虑被搜索字符串为 “纯汉字” 的场景，通过观察我们进行拼音搜索的过程可以发现，没有人会倒着输入拼音，也不会乱序输入，这是不符合拼音规范的，而总是前缀输入的：
$$yg, yangguang, yagua, gu, guan\ \ =>\ \ 阳光$$
像上面例子那样，如果我们单独看 “阳” 和 “光” 两个单字，加上 “阳光”，搜索的拼音其实都是前缀而已，绝对不会出现 “yagguang” 匹配了 “阳光” 的情况。有了拼音前缀这个限定以后，事情其实就简化很多了。那问题来了，这里的拼音前缀到底是 “谁” 的缀？我们总要先确定好研究对象，再去求前缀吧。按照上面的示例显然是 “阳”、“阳光”、“光” 了，这个拆解组合在计算机里面有个更规范的术语叫做子串。因此第一步，我们其实要先求到被搜索串的所有子串才行：
$${{阳光}}\ \ =>\ \ 阳, 阳光, 光 $$
单个汉字的拼音前缀比较容易得到，按照每次往前步进一个字符单位求即可：
$${{阳}}\ \ =>\ \ y, ya, yan, yang $$$${{光}}\ \ =>\ \ g, gu, gua, guan, guang $$
但对于像 “阳光” 这样的多个汉字的子串要怎么求它的前缀呢？其实想一下搜索的过程大概就知道，不外乎就是每个单字之间进行排列组合即可。我们不妨用简单的数学公式表示：假如一个由 \({{n}}\) 个汉字组成的子串，把它的第 \({{i}}\) 个单字的拼音前缀看作一个集合 \({{X_i}}\)，然后最终合法的模式串（即搜索时的字符串）则是这些集合的笛卡尔积，表示为：
$${{X_1}}\ \times\ {{X_2}}\ \times\ {{X_3}}\ \times\ {\cdots}\ \times\ {{X_i}}\ \ \ ({{i}}\ \leq\ {{n}})$$
有了这个公式，那么上面的 “阳” 和 “光” 两个单字的拼音前缀集合 \({{X_阳}}\) 和 \({{X_光}}\) 首先就可以像下面这样表示：
$${{X_阳}}=\{y, ya, yan, yang\}$$$${{X_光}}=\{g, gu, gua, guan, guang\}$$
它们的笛卡尔积可以表示为：
$${{X_阳}}\ \times\ {{X_光}}=\{(y,g),(y,gu),(y,gua),(y,guan),(y,guang),$$$$ (ya,g),(ya,gu),(ya,gua),(ya,guan),(ya,guang),$$$$(yan,g),(yan,gu),(yan,gua),(yan,guan),(yan,guang),$$$$(yang,g),(yang,gu),(yang,gua),(yang,guan),(yang,guang)\}$$
由此，我们便可以认为上面集合中的每个元素都是一个合法的模式串，输入他们中任意一个都将匹配到 “阳光”。最后别忘了，还有 “阳” 和 “光” 两个单字子串，最终把所有子串的合在一起才是全部的合法模式串：
$${{X_阳}}\ \cup\ ({{X_阳}}\ \times\ {{X_光}})\ \cup \ {{X_光}}=\{y, ya, yan, yang\}\ \cup$$$$\{(y,g),(y,gu),(y,gua),(y,guan),(y,guang),$$$$ (ya,g),(ya,gu),(ya,gua),(ya,guan),(ya,guang),$$$$(yan,g),(yan,gu),(yan,gua),(yan,guan),(yan,guang),$$$$(yang,g),(yang,gu),(yang,gua),(yang,guan),(yang,guang)\}\ \cup$$$$\{g, gu, gua, guan, guang\}$$
计算机表示
上面仅是数学表示方式，我们还需要转换成计算机可以识别的形式。这里需要应用到正则表达式，因为它本身就是对一类字符串的规则描述，但我们不需要用到很复杂的语法和符号，只会使用到控制优先级的 \(()\) 以及或运算\(|\)。首先 \({{X_阳}}\) 和 \({{X_光}}\) 两个单字子串的正则表达式可分别表示为：
$${{reg_阳}} = (y|ya|yan|yang)$$$${{reg_光}} = (g|gu|gua|guan|guang)$$
同理，上面的笛卡尔积 \({{X_阳}}\ \times\ {{X_光}}\) ，也就可以表示为下面这个正则表达式：
$${{reg_{阳光}}} = ((y|ya|yan|yang)\ (g|gu|gua|guan|guang))$$
这个表达式很好理解，最外面的一对括号表示整个字符串，然后里面第一对括号表示第一个汉字的拼音前缀，用或表示可选择的前缀有哪几个，第二对括号表示第二个汉字的拼音前缀。
最后，把 “阳”、“阳光”、“光” 三个子串的正则用或运算符\(|\)拼接起来即是全部匹配到 “阳光” 的正则表达式：
$$reg = {{reg_阳}} | {{reg_{阳光}}} | {{reg_光}} = (y|ya|yan|yang) | ((y|ya|yan|yang)\ (g|gu|gua|guan|guang)) | (g|gu|gua|guan|guang)$$
算法流程
上面说了那么多，其实总结起来这个算法的流程就是：
- Step1 切字：将被匹配字符串切分为单个汉字
- Step2 求子串：求被匹配字符串的所有子串
- Step3 求子串正则：
- 单字：求出拼音前缀（可基于现成的 pinyin4j 工具包），将所有前缀顺次用或运算符\(|\)分隔得到
- 多字：基于上面的单字正则，用括号运算符 \(()\) 包裹每个单字，再顺次拼接起来得到
- Step4 拼接子串正则：基于 Step3 求到的每个子串的正则，将每个用括号运算符 \(()\) 包裹，再以或运算符\(|\)分隔得到
- Step5 匹配：使用正则匹配函数检测输入的模式串是否匹配 Step4 生成的正则（主流语言的核心库一般都会提供，内部基于回溯算法实现）
拓展：中英混合搜索
前面讲述的是被匹配串全部为汉字的场景，相对比较简单，但现实情况却是，经常要中英混合搜索（或者其他非汉字字符）。为实现这种场景的搜索支持，我们需要基于上面算法的基本骨架进行一些改动。这里以 “阳sunny光” 这个汉字与非汉字串构成的串为例，说明改动的地方：
- Step1 切字：汉字仍然是一个一切，非汉字串则按最长连续来切。比如切为 “阳”、“sunny”、“光”
- Step2 求子串：同上
- Step3 求子串正则：
- 单汉字：同上的基础，再增加一个全拼正则，比如 “阳” 将对应两个正则：\(y|ya|yan|yang\) 和 \(yang\)
- 多汉字：同上
- 汉字+非汉字串：此时需要区分汉字与非汉字串的位序关系，分别求前缀、后缀、子串、本身四种正则，比如 \(sunny\) 将对应：
- 汉字在前：汉字用全拼，非汉字串用前缀。比如：\(阳sunny => (yang)\ (s|su|sun|sunn|sunny)\)
- 汉字在后：非汉字串用后缀，汉字用前缀。比如：\(sunny光 => (y|ny|nny|unny|sunny)\ (g|gu|gua|guan|guang)\)
- 前后都有汉字：前面汉字用全拼，非汉字串用本身，后面汉字用前缀。比如：\(阳sunny光 => (yang)\ (sunny)\ (g|gu|gua|guan|guang)\)
- 前后都无汉字：非汉字串用子串。比如：\(sunny => (s|su|sun|sunn|sunny|u|un|unny|n|nn|nny|n|ny|y)\)
- Step4 拼接子串正则：基于 Step3 求到的每个子串的正则，将每个用括号运算符 \(()\) 包裹，再以或运算符\(|\)分隔得到
- Step5 匹配：同上
最终将得到匹配 “阳sunny光” 的一个正则表达式：
$$reg = {{reg_阳}}|{{reg_{阳sunny}}}|{{reg_{阳sunny光}}}|{{reg_{sunny}}}|{{reg_{sunny光}}}|{{reg_光}}=$$$$((y|ya|yan|yang)|$$$$(yang)\ (s|su|sun|sunn|sunny)|$$$$(yang)\ (sunny)\ (g|gu|gua|guan|guang)|$$$$(s|su|sun|sunn|sunny|u|un|unny|n|nn|nny|n|ny|y)|$$$$(y|ny|nny|unny|sunny)\ (g|gu|gua|guan|guang)|$$$$(g|gu|gua|guan|guang))$$
结语
以上就是汉语拼音搜索算法的实现思路，可能还有更好的解法，欢迎留言交流~ 把上面这个搜索算法用到工程里面的时候，其实也还有值得优化的地方，比如生成正则表达式的过程不必在搜索的时候即时生成，而可以事先生成后存到缓存或数据库里，等到搜索的时候读取出来匹配即可，当然这只适用于匹配串不经常发生改变的场景。另外需要注意的是，由于采用正则匹配，其内部本质是基于回溯，如果匹配串长度很长，性能容易变慢，因此本算法仅适合一些类似于人名、国家、昵称之类的短词搜索。如果想看更详细的源码或引用工具包，可以戳这里，是基于 Java 语言实现的。