如何实现一个高效的拼音匹配库？解决多音字，首字母匹配等问题

如果本文对你有帮助，麻烦点个 star! pinyin-math
首先看看列表效果：

再看看长多音字符串：

在线演示地址：laosep.top/pinyin-matc…

接下来讲讲实现

探索微信的拼音匹配规则

通过参考微信，分为两种情况，一种不包含多音字，一种包含，我们先从简单的开始。

不包含多音字，以 “你真好（nizhenhao）” 为例

命中匹配：

完整的拼音输入√ （当然只输入 zhenhao / hao 也是 OK 的）
拼音首字母 √
最后一个音未输入完整 √（打字打到一半）

无法命中匹配：

起始字母不是分词点 x (z)henhao
有的采用缩写有的采用全写 x niz(hen)hao

包含多音字以 “骑马（qima jima）” 为例
直接套用非多音字的规则就 OK

匹配规则总结

起始字母必须为拼音分词点
除了最后一个字，不允许存在有的输入为全写，有的为缩写（注意最后一个字的拼音也只允许从前往后按顺序输入到一半）
多音字只需把对应的多音列举出来，套用上述规则即可

接下来用 JS 来实现一个匹配库 pinyin-match.js
步骤：

对输入的拼音进行分词
将中文转为拼音
第一步分词的结果和第二步的拼音进行匹配，返回是否命中

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']

先用一张图来说明一下思路：

总结一下这个算法：

从第一个字符 p 开始，查找是否在字典中。不在字典中，字符 p+1，重新查找；如果在字典中，记录下命中的词，进行 2
如果有剩余字符串，对剩余字符串重复 1；如果没有剩余的字符串，则完成当次查找，找到的命中词即可构成完整句子。回溯到上一次成功的状态，字符 p+1 继续进行 1。
退出的条件为把整个字符串丢进去字典查的时候（即字符 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 函数，使它可以输出我们前面提到的，输入不完整的情况

比如’jinan’ 应当可以匹配 ‘济囊’ （打字打到一半）
针对这种打字打到一半的情况，其实就是最后一个音不需要完整匹配，仅需从前往后匹配即可，例：（例子简化一下拼音字典，只有 3 个音）

s = 'jinani'
dict = ['ji', 'na', 'ning']

用图来演示一下 wordBreak 过程（跟之前一样）

这里就不贴整段代码了，通过上图我们可以知道，最后一块 piece 并不一定需要在字典库中找到匹配项，仅需在字典中存在某个音 x，x.indexOf(piece) === 0 即可：

  dict.some(item => item.indexOf(piece) === 0)

假定输入的所有字符全部是首字母
这种情况就简单多了，直接把输入的每个字符拆开即可（实际上这里偷懒了，因为有些单音，并不在字典中，不过这点影响可以忽略）

把上述两种不完整的情况也考虑进去，我们就完成了最核心的 wordBreak 函数了。接下来看看中文转成拼音的方法

2. 中文转拼音

首先需要找一个拼音字典，从开源库 pinyinjs 找到了一个比较合适的字典，收录了 6763 个常用汉字，原始字典的结构如下图：

实现一个 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

HL🌱数字花园

探索