本文同步发布在掘金：
掘金--如何实现一个高效的拼音匹配库？
如果本文对你有帮助，麻烦点个star! pinyin-math
首先看看列表效果：
再看看长多音字符串：
在线演示地址：pinyin-match
接下来讲讲实现
探索微信的拼音匹配规则
通过参考微信，分为两种情况，一种不包含多音字，一种包含，我们先从简单的开始。
1.不包含多音字，以“你真好（nizhenhao）”为例
命中匹配： 完整的拼音输入√ （当然只输入 zhenhao / hao 也是OK的）
拼音首字母 √
* 最后一个音未输入完整 √（打字打到一半）
无法命中匹配： 起始字母不是分词点 x (z)henhao
有的采用缩写有的采用全写 x niz(hen)hao
2.包含多音字以“骑马（qima jima）”为例直接套用非多音字的规则就OK
匹配规则总结
- 起始字母必须为拼音分词点
- 除了最后一个字，不允许存在有的输入为全写，有的为缩写（注意最后一个字的拼音也只允许从前往后按顺序输入到一半）
- 多音字只需把对应的多音列举出来，套用上述规则即可
接下来用JS来实现一个匹配库pinyin-match.js
步骤：
1. 对输入的拼音进行分词 2. 将中文转为拼音 3. 第一步分词的结果和第二步的拼音进行匹配，返回是否命中
1.拼音分词
需要对输入的拼音进行合法性检测，以及分词的处理,这一步是匹配算法高效的关键
首先举个例子： 在搜索的时候，输入"jinan" 能匹配哪些读音的字呢？ ji nan (如：济南) jin an (如：晋安)除此之外，还要考虑输入不完整的情况 ji nan(g) (如：济囊) jin an(g) (如：金昂) ji na n(eng) (如：济那能) jin a n(a) (如：金阿拿) ……还有好多好多好多 就不写了 j i n a n (最后还要考虑每个字都是首字母，不过因为没有i开头的拼音，所以这里没有）
本着循序渐进的原则，我们先解决拼音输入是完整的情况，即最前面的两种。
这里的核心算法其实就是 word-break，先附上leetcode的链接Word Break II
关于word-break
word-break解决的问题如下：
给定一个字符串s和单词字典dict,求出s根据dict拆分出的所有可能。
例子：
let s = ‘catsanddog’
const dict = ['cat', 'cats', 'and', 'sand', 'dog']
wordBreak(s) // return ['cat sand dog', 'cats and dog']
先用一张图来说明一下思路：
总结一下这个算法：
1. 从第一个字符p开始，查找是否在字典中。不在字典中，字符p+1，重新查找；如果在字典中，记录下命中的词，进行2 2. 如果有剩余字符串，对剩余字符串重复1；如果没有剩余的字符串，则完成当次查找，找到的命中词即可构成完整句子。回溯到上一次成功的状态，字符p+1继续进行1。 3. 退出的条件为把整个字符串丢进去字典查的时候（即字符p++++++++1，一直到末尾） 代码实现：
function wordBreak(s) {
let result = [] // 当前处理的结果
let solutions = [] // 保存完整的结果
getAllSolutions(0, s, result, solutions)
return solutions
}
function getAllSolutions(start, s, result, solutions) {
if (start === s.length) { // 后续没有s，即找到了命中结果，存如solutions
solutions.push(result.join(' '))
return
}
for (let i = start; i < s.length; i++) {
let piece = s.substring(start, i + 1) // 这个piece即上面说的字符p
if (dict.indexOf(piece) !== -1) {
result.push(piece)
getAllSolutions(i + 1, s, result, solutions) // 命中一个词，向后找（递归该方法即可）
result.pop() // 回溯到上一次结果 然后往后找
}
}
}
以上就是分词算法的核心实现了，接下来我们对这个算法再做进一步的优化--剪枝，所谓剪枝就是把已经确认后续不会有完整结果的index存下来，下次再遇到直接跳过即可，我们对上述的dict做一个扩展，加入两个个词san an 去掉 and
const dict = ['cat', 'cats', 'san', 'an', 'sand', 'dog']
按照上述的算法，过程图解如下：
注意上图的两个红框部分，因为 ddog 已经被证明过，后续无法命中了，所以后面再遇到ddog 直接跳过即可。我们用一个possible数组来记录后续有没有可能找到结果，初始化为true，possible的长度为catsanddog的长度（10）,然后对 getAllSolutions进行补充
function getAllSolutions(start, s, result, solutions, possible) {
if (start === s.length) { // 后续没有s，即找到了命中结果，存如solutions
solutions.push(result.join(' '))
return
}
for (let i = start; i < s.length; i++) {
let piece = s.substring(start, i + 1)
if (dict.indexOf(piece) !== -1 && possible[i + 1]) {
result.push(piece)
let beforeChange = solutions.length // 记录下当前结果的长度，等下一次getAllSolutions返回，如果没变化，说明后续找不到结果
getAllSolutions(i + 1, s, result, solutions, possible) // 命中一个词，向后找（递归该方法即可）
if (solutions.length === beforeChange) {
possible[i + 1] = false
}
result.pop() // 回溯到上一次结果 然后往后找
}
}
}
OK，现在如果给到一个完整的拼音字典dict(所有汉字的读音,大概是400个出头)，调用wordBeak('jinan')输出如下
完整的拼音可能有六种，这里的n也被当做一个完整的拼音是因为字典库里存在汉字的拼音是n
接下来我们继续改进wordBreak函数，使它可以输出我们前面提到的，输入不完整的情况
1. 比如 'jinan' 应当可以匹配 '济囊' （打字打到一半）
针对这种打字打到一半的情况，其实就是最后一个音不需要完整匹配，仅需从前往后匹配即可，例： （例子简化一下拼音字典，只有3个音）
s = 'jinani'
dict = ['ji', 'na', 'ning']
用图来演示一下wordBreak过程（跟之前一样）
这里就不贴整段代码了，通过上图我们可以知道，最后一块piece并不一定需要在字典库中找到匹配项，仅需在字典中存在某个音x，x.indexOf(piece) === 0即可：
dict.some(item => item.indexOf(piece) === 0)
- 假定输入的所有字符全部是首字母
这种情况就简单多了，直接把输入的每个字符拆开即可（实际上这里偷懒了，因为有些单音，并不在字典中，不过这点影响可以忽略）
把上述两种不完整的情况也考虑进去，我们就完成了最核心的wordBreak函数了。接下来看看中文转成拼音的方法
2.中文转拼音
1.首先需要找一个拼音字典，从开源库pinyinjs找到了一个比较合适的字典，收录了6763个常用汉字，原始字典的结构如下图：
2.实现一个pinyin(cn)，使其能输出对应中文的拼音，方法很简单，这里简单说下思路即可：
首先把原始字典转为pinyinMap 以中文为key，然后直接在这个map里查找对应的中文即可（记得考虑多音字）pinyinMap如下：
3.将分词的结果和中文pinyin进行匹配
直接用代码展示,以输入 'cengd', 匹配'我曾大'为例：
var a = getPinyin('我曾大') // a = ['wo', 'zeng ceng', 'da'] 通过pinyin函数的结果整理得出
var b = getFullKey('cengd') // b = [['ceng d', ['c', 'e', 'n', 'g', 'd']] 通过wordBreak的结果整理得出
匹配函数为源码中的 getIndex函数，受限于篇(懒)幅(惰)，这里用图来展示匹配过程：
b中存在一个元素，能完整连续匹配上a（当然这里也要考虑最后一个音 仅需部分匹配即可）
写在最后
本文主要讲解了pinyin-match中 比较核心的分词算法，其余部分简单做了一下演示，并没有完整分析pinyin-match的所有方法（比如获取匹配的index,原文存在空格影响index等问题），如果对文章中没说明的地方有疑问，欢迎在评论区提出~
如果有帮助，请点个star！pinyin-math