当前位置: 首页 > 面试 > 正文

拼写纠错-百度笔试

关键字:
1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

题目:

在用户输入英文单词时,经常发生错误,我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典,请你设计一个拼写纠错的程序。

(1)请描述你解决这个问题的思路;

(2)请给出主要的处理流程,算法,以及算法的复杂度;

(3)请描述可能的改进(改进的方向如效果,性能等等,这是一个开放问题)。

网上流传解答:

(1)思路:字典以字母键树组织,在用户输入同时匹配

(2)流程:

每输入一个字母:

沿字典树向下一层,

a)若可以顺利下行,则继续至结束,给出结果;

b)若该处不能匹配,纠错处理,给出拼写建议,继续至a);

算法:

1.在字典中查找单词

字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母一个字母匹配.算法时间就是单词的长度k。

2.纠错算法

情况:当输入的最后一个字母不能匹配时就提示出错,简化出错处理,动态提示可能处理方法:

(a)当前字母前缺少了一个字母:搜索树上两层到当前的匹配作为建议;

(b)当前字母拼写错误:当前字母的键盘相邻作为提示;(只是简单的描述,可以有更多的)根据分析字典特征和用户单词已输入部分选择(a),(b)处理

复杂性分析:影响算法的效率主要是字典的实现与纠错处理

(a)字典的实现已有成熟的算法,改进不大,也不会成为瓶颈;

(b)纠错策略要简单有效,如前述情况,是线性复杂度;

(3)改进

策略选择最是重要,可以采用统计学习的方法改进。

剖析:

先看一下通过搜索示例分析Google中文纠错功能的实现过程。

       键入关键词	   纠错提示
1	氯华钠	   氯化钠
2	氯哈钠	   -
3	摆渡	   -
4	摆度	   百度

从上例可知,Google是通过同音词的对比来纠错的,音不同则无法纠错。也就是说,只有错误的同音词才会被纠正,而正确的同音词是不会有纠错提示的。

考虑到中文输入法一般可以分成拼音输入法和字形输入法,纠错提示任务依然任重而道远。甚至英文也不会让人舒服:考虑手写输入情况下,英文单词之间的单词空格也不会那么容易辨认——或许采用英文分词是个好办法。

首先讨论如何发现错误的位置,再讨论如何纠错。如1992年由施得胜等提出的基于统计的中文错字侦测法,主要是提出文章中自动侦测错字所在位置的方法。该论文是以统计的方法,在训练大量的文句库后,得到单词词词频表及连续强度表,再以这两个表为基础,经由评分函数计算出被怀疑的单字词所得之分数,若小于门限值,则标示为错字。其实验数据显式检错率可达70%以上。

张照煌博士于1994年提出一种自动侦错被订正中文文书中错别字的方法。其方法为事先整理含字形、字音、字义或输入码相近字所形成的‘综合近义子集’代换原文,产生候选字串,其次利用语言模型评分,找出评分最高的候选字串,即可自动侦测文书中的错别字;但是事先准备的‘综合近义子集’会因为搜集不足、过量的子集会造成误判,另外近似子集代换后,所产生的候选字串数量庞大,在中文的检错方面势必造成软体的负担。
pinxie

常见的英文单词纠错法有:,主要有误拼词典法、词形距离法、最小编辑距离法、相似键法、骨架键法、N-gram法、基于规则的技术、词典及神经网络技术。

(1)误拼字典法。收集大规模真实文本中拼写出错的英文单词并给出相应的正确拼写,建造一个无歧义的误拼字典。在进行英文单词拼写检查时,查找误拼字典,如命中,则说明该单词拼写有误,该词的正确拼写字段为纠错建议。该方法的特点是侦错和纠错一体化,效率高。但英文拼写错误具有随机性,很难保证误拼字典的无歧义性和全面性,因此查准率低、校对效果差。

(2)词形距离法。这是一种基于最大相似度和最小串间距离的英文校对法。其核心思想是构造单词的似然性函数,如该单词在词典中,则单词拼写正确;否则,按照似然性函数,在词典中找到一个与误拼单词最相似的词作为纠错候选词。该方法的特点是节省存储空间,能反映一定的常见拼写错误统计规律,是一种模糊校对法。

(3)最小编辑距离法。通过计算误拼字符串与词典中某个词间的最小编辑距离来确定纠错候选词。所谓最小编辑距离是指将一个词串转换为另一个词串所需的最少的编辑操作次数(编辑操作是指插入、删除、易位和替换等)。还有人提出了反向最小编辑距离法,这种方法首先对每个可能的单个错误进行交换排列,生成一个候选集,然后,通过查词典看哪些是有

效的单词,并将这些有效的单词作为误拼串的纠错建议。

(4)相似键法。相似键技术是将每个字符串与一个键相对应。使那些拼写相似的字符串具有相同或相似的键。当计算出某个误拼字符串的键值之后,它将给出一个指针。指向所有与该误拼字符串相似的单词,并将它们作为给误拼字符串的纠错建议。

(5)骨架键法。通过构建骨架键词典,在英文单词出现错误时,先抽取出该错误单词的骨架键,然后再去查骨架键词典,将词典中与该单词具有相同骨架键的正确单词作为该单词的纠错建议。

(6)N-gram法。基于n元文法,通过对大规模英文文本的统计得到单词与单词问的转移概率矩阵。当检测到某英文单词不在词典中时。查转移概率矩阵,取转移概率大于某给定阈值的单词为纠错建议。

(7)基于规则的技术。利用规则的形式将通常的拼写错误模式进行表示,这些规则可用来将拼写错误蛮换为有效的单词。对于一个误拼字符串,应用所有合适的规则从词典中找到一些与之对应的单词作为结果,并对每个结果根据事先赋予生成它的规则的概率估计计算一个数值,根据这个数值对所有候选结果排序。

现有的基于上下文的文本错误校对方法有三类:①利用文本的特征,如字形特征、词性特征或上下文特征;②利用概率统计特性进行上下文接续关系的分析;③利用规则或语言学知识,如语法规则、词搭配规则等。

(1)利用文本上下文的同现与搭配特征可以将文本的校对过程描述为词排歧过程。若称待校对的词为目标词,则建立混淆集C={W1,…,Wn},其中的每个词均与文本中的目标词容易发生混淆或歧义。如假设C={from,form},如果在文本中出现from或from时,就将它看作是一个from与from之间的歧义,校对的任务就是根据上下文决定哪个词是我们想要的词。上下文相关的校对问题由语句和语句中要被校正的词构成,Bayesian方法和基于Winnow的方法都是将这样的问题表示成有效特征表,每一个有效特征表示目标词的上下文中有一个特殊的语言学模式存在。目前常使用的特征有两种类型:上下文的词和词的搭配。上下文词特征用来检查在目标词周围的±k个词的范围内是否有特殊词存在;词搭配则用来检测在目标词的周围f个相邻词和/或词性标注的状态。如假设目标词的混淆集为{weather,whether},

若置k=10,f=2,目标词的可用特征包括:

①目标词前后10个词范围内的cloudy;

②当前词后为to+动词。

特征①就预示着当前词应为weather;而②则用来检查词搭配,它表明当前词后紧接着一个“to+动词”的结构,表明当前词应取whether(如I don’t know whether to laugh or cry)。在这种方法中,主要要解决的问题包括混淆集的求取;目标词所在上下文中特征的表示,即如何将语句的初始文本表示转换为有效特征。

基于词语同现与搭配特征的校对方法有很多种,较好的有Bayesian方法和基于Winnow方法。各种N-gram模型,如长距离N-gram、触发对N-gram等模型,都可以利用目标词上下文中的词同现特征或搭配特征,采用最大似然估计法、互信息、相关度等方法检测文本中的错误,并通过相邻词间的转移概率确定纠错候选词,实现对目标词的校正。

参考文献:

中文自動校正輔助系統

网络搜索引擎中文纠错功能实例剖析

文本自动校对技术研究综述

一.计划解决的问题

1. 繁简转换
2. 拼音转汉字
3. 同音词拼写错误
4. 英文拼写错误
5. 形近词错误
6. 方言纠错

二. 核心思路

1. 繁体转简体是可以独立出来,最先处理。

2. 其它的4步从查询日志中找出纠错的候选查询词,全部在线下计算。

多数拼写纠错算法基于2 个基本原则(Introduction to IR 3.3.1节):

1. 在多个拼写纠错的可选结果中,选择与原term 最相似的一个,当然这就要求有一个相似的标准。

2. 当两个候选term 与要纠错的term 一样相似时,选择最常见的那个term,比如,grunt和grant,都与grnt差不多相似,最简单的办法就是看grant和grunt 在文档中的各出现了多少次,将出现次数多的返回。另一种更常见的做法是把用户最常搜索的查询返回。再讨论一下纠错的功能如何展示的方案:

数据的问题:要进行纠错,首先要确定什么是正确的查询,最简单的想法就是确定一个阈值,比如说前80%的搜索查询算是正确的搜索词,但这有一个问题,比如在Introduction to IR里的一个例子,如果很多用户不太确定一个热搜词,britney spears,很多人搜索时用的是britian spears, britney’s spears, brandy spears, prittany spears,这些词都有可能是前80%的,所以最先就要对搜索查询进行过滤后,才能认为它们是正确的,过滤的方法可以是下面介绍的方法之一。

三.具体步骤

1.繁简转换:使用繁简转换表转换。

2. 拼音转汉字:拼音转汉字想法是较为直接的,建立一个以拼音为term的查询词索引,posting list中只保存查询频率最高的K个查询词。

 
zhijiucaotang	子九草堂, 子久草堂
xufuniuza	徐福牛杂, 许府牛杂, 徐府牛杂
shoujichongzhi	手机冲值, 手机充值

这一步可以在自动提示中使用,但自动提示与它的区别是,自动提示在拼音输入了一部分的情况下也要提示,比如输入 “xufu”就要提示“许府牛杂”。

3. 同音词拼音写:同音词拼音写也基于同样的想法,但是需要一个可能出错的查询词列表,这个列表可以为借鉴于下列几种情况 

1.以carot为例,返回有carot的文档,也返回一些包含纠错后的term carrot和torot的文档。

2. 与(1)相似,但仅当carot不在词典中时,返回纠错后的结果。

3. 与(1)相似,但仅当包含carot的文档数小于一个预定义的阈值时。

4. 当原始查询返回文档数小于预定义的阈值时,搜索引擎给出纠错后的词列表。

情况(1)相当于是对所有查询都进行纠错处理,发现那些搜索比较少的,就给出一个纠错提示,比如“天浴”搜索次数比较少,而“天娱”搜索次数比较多,那么在用户搜索“天浴”时就提示“天娱”,即使“天娱”也是一个正常的查询词。

情况(2)就是得到所以没有返回结果的查询列表。

情况(3)是一个查询它返回的文档数少于一个预定义阈值时,我认为这个是最合适的,因为文档中也可能有人把字写错,这样就有可能漏掉一些应该纠错的词,但这需要搜索引擎结合,看到底有多少返回了。

情况(4)就是我想应该用的表现形式。

4.英文拼写错误

在lucene中已有贡献者实现了spellchecker模块,主要算法有:Jaro Winkler distance,Levenstein Distance(Edit Distance),NGram Distance。

但Lucene中的实现过于简单,使用两两比较,时间复杂性是O(n2),可以用Introduction to IR中的3.3.4节中介绍的,k-gram与编辑距离结合的方法算。

5. 形近字错误

形近字一般是用户记错了形声字,或是使用五笔的用户输入错误。在网上可以下载SunWb_mb文件,它里面包含五笔的编码和笔画的编码,但字根比如“马”比“口”笔画更多,也更有代表性,但在这种方法中却是相同的。

6. 方言纠错:可以用soudex进行纠错.

本文固定链接: http://www.chepoo.com/spelling-correction-baidu-interview.html | IT技术精华网

【上一篇】
【下一篇】

拼写纠错-百度笔试:等您坐沙发呢!

发表评论