如何实现一个拼音拼写纠错算法？

[faywong8888]

要求

如常见智能拼音输入法，用户输入的拼写有简拼（ zfb 、wx ）、局部简拼（ zhongguor ）、全拼（ nihao ），其中会有各种拼写错误（微位替换，w->a/s/d/e/q ，少字符，多字符，临近字符对调，整体转置 wang -> angw 等），请问要开发一个纠错算法把错误拼写纠回正确拼写，应该如何去设计，需要使用哪些数据结构/算法？

背景

自己是 Rime 重度用户，想为 Rime 输入法增加纠错模块。同时也想开一贴和众多 v 友研究下这个细分的领域技术。集思广益，启发彼此。开源输入法基本上纠错这块都做得不好。

[faywong8888]

微位替换 ->键位替换

[yyf1234]

算法叫 编辑距离

[katwalk]

对对对，经常输错相邻的拼音，期待楼主能找到解决的办法 🤗

[hhhhhh123]

@katwalk #3 现在的输入都有纠错功能。

[xzpjerry731]

补全还是纠错？

[lesterchen]

我现在用键盘打字最常见的错误情况是.拼音的字母顺序错了~

[jarry777]

迫切需要双拼纠错。
目前在用 gboard ，符号显示不全的 bug 得两年了吧都没人修

[hwdq0012]

vim spell 不知道怎么弄的,想想,好像是你自己维护一个字典,然后拼写的在字典里很像但不是的,就会有提示,按快捷键类似代码那样补全,就纠正了

]s 跳到下一个拼写问题的位置
[s 跳到上一个拼写问题的位置
z=选择正确拼写
zg 添加用户拼写
zw 删除用户拼写
:set spell 启用拼写
:set nospell

自己做的话我会用 myers 算法(git diff 算法好像也是这样),可以对比字典里的词语和正文的词语相似度
不过好像正文还需要分词一下,应该也有什么现成的中文分词工具吧

[katwalk]

@hhhhhh123 #4 太弱了，我用的搜狗。

[shot]

Rime 处理这个问题的标准答案是使用「模糊音」。

speller/algebra/+:
- derive/^([zcs])h/$1/ # z, c, s => zh, ch, sh
- derive/^([zcs])([^h])/$1h$2/ # zh, ch, sh => z, c, s
- derive/([aeio])n$/$1ng/ # ang, eng, ing, ong => an, en, in, on
- derive/([aeio])ng$/$1n/ # an, en, in, on => ang, eng, ing, ong
- derive/([iu])a(o|ng?)$/a$1$2/ # tain => tian

---------
启用模糊音会带来两个问题：
1. 候选词数目会大量增加。如“zhangk”会候选「展开」，不过我还没有体感到候选条目增加引起的性能卡顿；
2. 增加的候选词可能会带来预料之外的词频排序。还是“zhangk”，我机器上「展开」会排在「掌控」前面。

因为我用的是全拼，所以写了一个根据输入编码和候选词拼音匹配程度重新排序的插件，也算处理掉这个问题了。
https://github.com/HuangJian/rime-frost/blob/hj/js/sort_by_pinyin.js

[faywong8888]

@shot 感谢。我现在实现了一个中间态的检错-纠错算法，但效果不佳（可能不到 30% 的纠错成功率）。我按照你的思路（先扩散，再排序）来弄下。

[lotem]

貌似樓主回覆過這個 PR
https://github.com/rime/librime/pull/228

[faywong8888]

@lotem 是的。感谢 lotem 大佬过去对我的指导和帮助。

我尝试在拼写图（ syllable_graph ）中增加过 n-gram 拼音模型，用于筛选“候选的”的纠错拼写，但终归由于错误来源太多（键位临近、全拼简拼切分混杂、同音...）、数据质量一般导致效果不好。我最近反思下来，最难的一环是无法实现精确的检错（任意的键位按错、全拼和简拼组合的多种切分、同音、近音等...）。苦思不得其解。

[yfugibr]

对于键位纠错，我的一个想法是，不是在字符这一级进行纠错，而是在点击位置上纠错，点击一个按键的不同位置，效果应该是不同的，根据不同的按键距离，指数级的调整权重。比如输入 nu ，u 的点击位置偏右时更倾向于纠正为 ni ，点击位置足够偏右时，就可以在点击 nu 是出现“你”的候选项。

[yfugibr]

@yfugibr #14 目前纠错效果最好的 gboard 似乎就是用的这种纠错算法，但是 librime 应该没法获取到点击位置？

[yfugibr]

@yfugibr #15 至于相邻字符互换 nihoa -> nihao 这种，最好可以通过按键时间来纠错，时间间隔越小就越可能反转，但是同上，librime 应该还是没办法实现