java 拼音首字母 高效_如何实现一个高效的拼音匹配库?解决多音字,首字母匹配等问题...
发布日期:2021-08-20 01:25:27 浏览次数:2 分类:技术文章

本文共 4002 字,大约阅读时间需要 13 分钟。

首先看看列表效果:

35e53a4d6ab71454897902caf2604dca.png

再看看长多音字符串:

0896a1a13ec8f10074870d90cc38445e.png

在线演示地址:http://119.29.39.55:8686/

接下来讲讲实现

探索微信的拼音匹配规则

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

1.不包含多音字,以“你真好(nizhenhao)”为例

命中匹配:完整的拼音输入√ (当然只输入 zhenhao / hao 也是OK的)

31e7521c74857c00034500fde42d9684.png拼音首字母 √

6fa51281fa76faae47ac491162cbfbde.png最后一个音未输入完整 √(打字打到一半)

acbf78dbc054a59338d76998e4e08a4a.png

无法命中匹配:起始字母不是分词点 x   (z)henhao

41135e91fac81ffa0b35e3f19249da18.png有的采用缩写有的采用全写 x   niz(hen)hao

be2fef9c3881509b1c54299c639933e0.png

2.包含多音字以“骑马(qima jima)”为例

直接套用非多音字的规则就OK

a09ceee048aae7fff483d9907cec4664.png

f8a9948182b85f06e5fed48693ef4905.png

匹配规则总结起始字母必须为拼音分词点

除了最后一个字,不允许存在有的输入为全写,有的为缩写(注意最后一个字的拼音也只允许从前往后按顺序输入到一半)

多音字只需把对应的多音列举出来,套用上述规则即可

接下来用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']

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

4e3948e9d449fe0ba0c3188599f95e45.png

总结一下这个算法:从第一个字符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 去掉 andconst dict = ['cat', 'cats', 'san', 'an', 'sand', 'dog']

按照上述的算法,过程图解如下:

f46f83467e84696328604c480d3e0e39.png

注意上图的两个红框部分,因为 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')输出如下

df894b0712819d8b0886df682bd833b0.png

完整的拼音可能有六种,这里的n也被当做一个完整的拼音是因为字典库里存在汉字的拼音是n

7dfcae396b2c9bba38bfd841a39a4a57.png

接下来我们继续改进wordBreak函数,使它可以输出我们前面提到的,输入不完整的情况比如 'jinan' 应当可以匹配 '济囊' (打字打到一半)

针对这种打字打到一半的情况,其实就是最后一个音不需要完整匹配,仅需从前往后匹配即可,例: (例子简化一下拼音字典,只有3个音)s = 'jinani'

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

用图来演示一下wordBreak过程(跟之前一样)

46467812a300c58b42a42527e8eee2c5.png

这里就不贴整段代码了,通过上图我们可以知道,最后一块piece并不一定需要在字典库中找到匹配项,仅需在字典中存在某个音x,x.indexOf(piece) === 0即可:dict.some(item => item.indexOf(piece) === 0)假定输入的所有字符全部是首字母

这种情况就简单多了,直接把输入的每个字符拆开即可(实际上这里偷懒了,因为有些单音,并不在字典中,不过这点影响可以忽略)

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

2.中文转拼音

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

9b4d0c45a7c0b3303ce9132bf4ecc153.png

2.实现一个pinyin(cn),使其能输出对应中文的拼音,方法很简单,这里简单说下思路即可:

首先把原始字典转为pinyinMap 以中文为key,然后直接在这个map里查找对应的中文即可(记得考虑多音字)pinyinMap如下:

d07da1354830559ff1abb2b7a7121a50.png

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函数,受限于篇(懒)幅(惰),这里用图来展示匹配过程:

3280227397fd2d75fcea65161d14ccc5.png

简单总结这个匹配函数就是 b中存在一个元素,能完整连续匹配上a(当然这里也要考虑最后一个音 仅需部分匹配即可)

写在最后

本文主要讲解了pinyin-match中 比较核心的分词算法,其余部分简单做了一下演示,并没有完整分析pinyin-match的所有方法(比如获取匹配的index,原文存在空格影响index等问题),如果对文章中没说明的地方有疑问,欢迎在评论区提出~

如果有帮助,请点个star!pinyin-math

插个无关的: 本人最近在寻找新的工作机会,前端,base期望:广州>厦门>深圳(暂不考虑其他地方)

转载地址:https://blog.csdn.net/weixin_32141627/article/details/115041523 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:php 将中文字符转英文字母_php 提取字符串的中文首字母,如何考虑到英文和数字的情况...
下一篇:java外部类调用匿名内部类_Java匿名内部类访问外部变量,为何需被标志为final?...

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2024年03月16日 21时53分17秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql排序rank_MySQL_实现组内排序-Oracle中的rank()函数的功能 2019-04-21
vim自定义html,html - 寻找一种使用VIM在HTML中直接生成漂亮代码段的方法 - 堆栈内存溢出... 2019-04-21
python时间序列因果检验_用python做时间序列预测八:Granger causality test(格兰杰因果检验)... 2019-04-21
python numpy 函数详解_python使用numpy中的size()函数实例用法详解 2019-04-21
java spring上传文件_Java Spring文件上传,Java文件上传,Java通用文件上传 2019-04-21
linux 模拟键盘输入到进程,Linux 下模拟键盘输入 2019-04-21
linux服务器上已安装R 用户下载R包,R语言安装R package的2种方法 2019-04-21
linux 7 磁盘空间太小,Linux下磁盘保留空间的调整,解决df看到的空间和实际磁盘大小不一致的问题... 2019-04-21
linux下mysql 备份方法,Linux下mysql数据库备份方法小结 2019-04-21
bootstrap 页面垂直居中_iframe中如何让layer提示框显示在垂直居中的位置 2019-04-21
肺部ct重建_胸片检查容易漏诊肺癌,去年正常今年晚期常发生,体检一定要做CT... 2019-04-21
3dmax如何拆分模型_3D建模大佬如何制作出惊艳四方的游戏建模,看完这篇文章我知道了... 2019-04-21
x86so文件装换成arm64位_64位系统正式发布说明及介绍!! 2019-04-21
for循环中取出最大最小 累加_LeetCode之长度最小的子数组 2019-04-21
如何打开老公人脸识别_【话题】南宁已有小区启用人脸识别门禁,有人点赞有人忧... 2019-04-21
makex机器人程序_机器人教育为相城青少年叩开科学世界大门 2019-04-21
一寸照纯红色底图片_Ella陈嘉桦也是“时髦精”,穿玫红色西装配拼色半身裙,高级洋气... 2019-04-21
米哈游客户端笔试题_Garena校招 游戏客户端开发通关面经 2019-04-21
airpodspro没有弹窗_使用AirPods Pro一天的主观感受 2019-04-21
创建物化视图commit_视图及范式 2019-04-21