输错字了怎么办?

  做输入法的时候,有一个很常见的问题,就是如果用户输错了拼音,怎么办?(嘉定用户用的是拼音输入法)

  比如说,我要打北京,拼音就是beijing,结果达成了beijnig,或者bejing,怎么办?

  首先,算法要做的就是区分到底是正确输入,还是错误输入。

  比如beijin这个到底算是beijing的错误输入,还是一个正确输入呢?

  这个的最好做法是做上下文判断,但这个算是高级要求,这里忽略。

  在不做上下文判断的情况下(感觉谷歌输入法和苹果是有上下文判断的,虽然很不靠谱,苹果的输入法我感觉在不靠谱程度上更甚),面对一个用户输入,我们先去做匹配,看能否匹配到词组。

  如果一个拼音输入可以匹配到一个存在的词组,那么就认为这是正确输入,不考虑错误输入的判定流程——当然,要走也可以,优先级调低(比如一页十个前6个是正确输入后4个做错误输入处理)。

  而,如果一个拼音输入没有匹配到任何已经存在的词组,那么就可以当作是错误输入,来做纠正。

  好了,重头戏来了——面对错误的输入,要怎么找到正确的输入?

  比如说,面对bejing或者beijnig,我怎么知道它的正确拼写应该是什么样的?

  这就是下一个问题——输入错误的种类。

  输入错误的种类其实是有限的,可以归为四大类:

  1,乱序,比如从beijing到beijnig

  2,遗漏,比如从beijing到bejing

  3,冗余,比如从beijing到beijiing

  4,误入,比如从beijing到baijing

  接下来的下一个问题,就是如何找到正确的拼写。

  这里牵扯到这么一个概念:给定拼音A和拼音B之间的“距离”(这里有个专有名词,就不引用了)

  比如说,同样是乱序,beijing到beijnig和到biejing的“距离”是一样的,都是乱序1。但beijing到biejnig的距离就为2,因为需要乱序两次。

  我们当然不可能将所有乱序、遗漏和冗余的可能性都来一遍——一个字符数为n的字符串的乱序1的可能为n-1,但乱序2的可能就是(n-1)(n-2),如果穷举所有乱序的可能,那就是(n-1)!的量级,碰到zhuangshangying这样的长词组直接嗝屁。

  所以,我们只能去搜寻所有错符距为1的词组,并从中找到正确的单词。

  这个做法在中文输入法(拼音是最常见的使用场景)和英文输入法(你不会不知道英文也有输入法吧?这个在手机上特别多)上都是最常用的做法。

  可以算得上是业界标准。


  但,我们的故事到此并没有结束。

  就如前面所说,从错符距1到错符距2,工作量是几何级上升的,所以Google和苹果基本都只考虑错符距1,我们公司以前的产品也遵守这个业界统一标准。

  但,这并不是我们不做错符距2的合理理由。

  因为,事实上,错符距2一样可以在非几何级上升情况下被解决的,也就是说,不需要将工作量从n-1上升到(n-1)(n-2)也一样可以完成错符距2的纠正。

  现在让我们以英语为例。

  比如单词transformer,变压器,变形金刚,或者morphism,automorphism,endomorphism,transmorphism。

  说这个不是在飚英语(话说GRE和雅思考完以后基本就不看英语了我擦……),而是在问你——发现没有,上面有什么规律?

  答对了,词根。

  英文单词的输入错误纠正目前和拼音一样,也是基于错符距1的,但这是将注意力放在“单词”这个整体上的,事实上却可以做进一步的拆分。

  英文单词都有词根,要么是前缀,要么是后缀,组合在一起。于是一个单词可以分解为:prefix?+body*+postfix?,?表示有或者没有,*表示若干个(很少看到四个词根拼成一个单词的。。。不过生物化学医药等专业领域的新造词一个单词冒出十来个词根也是正常)。

  比如说,transformer,就是trans + form + er(这个也算么??),transmorphism就是trans + morphism,automorphism就是auto + morphism。

  如果我们将单词以词根为单位做分解,然后对每个词根的部分做错符距1纠正,那么一个完整的单词就可以做到错符距2甚至错符距3的纠正,用户体验大增。

  而词根分解本身的工作量是n的量级,三个词根构成的单词的错符距3纠正也不过是4n的量级,比原本n^2甚至n^3的量级小了很多。

  在拼音输入中也是。

  我们输入shanghai,结果输成了shanghia或者shnaghai,那么现在的输入法(谷歌或者苹果)都能自动纠正,但如果你输成了shnaghia,就直接无能为力了。

  可,如果一个词组按照拼音来分解(这方面比英语词根分解要容易很多,因为中文一个单词的声母韵母及其组合比英语词根有规律太多了),那么上述shnaghia是可以被自动纠错的。

  可见,业界标准的错符距1其实也不过是一个习惯性规定而已,并不存在技术上的绝对壁垒。


  这点不单单输入法可以用,在搜索引擎上也可以用。

  毕竟,输入法说到底,其核心功能就是对词库的搜索,所以也就是一种小型搜索引擎而已。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,214评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,307评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,543评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,221评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,224评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,007评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,313评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,956评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,441评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,925评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,018评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,685评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,234评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,240评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,464评论 1 261
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,467评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,762评论 2 345

推荐阅读更多精彩内容

  • 笔记 谁控制的越精确,谁的优先级越高标签名:整个标签CLASS:相同的类型ID:一个id名称内联样式表>ID选择器...
    xiao生气阅读 266评论 0 0
  • 有人说,世上没有自认为百无一用的男子,也没有自以为最丑陋的女子。我不是一个睿智美艳的女子,自知无法享受众星捧月的殊...
    水滴air阅读 663评论 2 2
  • 我们必须学会在泪水里兑一点烈酒 而不是在酒里掺杂眼泪 真正看清一个人的时候其实也不会有太多的情绪 不会生气更不会在...
    笑起来真好看阅读 1,813评论 0 1
  • 【设计理念:重要的是将本质传达给别人】 佐藤可士和作品包罗万象,包括日本国立新美术馆的标识设计、优衣库、乐天等的品...
    宇涵Frida阅读 159评论 0 1
  • 昨天星期四,可以算是要放假了吧,因为星期五只有一节课,也就我要在课后去教学办值个班,其他也没有什么事了,昨天上午一...
    坚志阅读 129评论 0 0