更多百度笔试题汇总参见http://summerbell.iteye.com/blog/486677(百度笔试题汇总)
以及http://summerbell.iteye.com/blog/486792(百度笔试题目剖析——寻找热门查询 )
网上流传的百度笔试题目部分附有答案。但一家之言,难免偏颇。
题目:
在用户输入英文单词时,经常发生错误,我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典,请你设计一个拼写纠错的程序。
(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年提出一种自动侦错被订正中文文书中错别字的方法。其方法为事先整理含字形、字音、字义或输入码相近字所形成的‘综合近义子集’代换原文,产生候选字串,其次利用语言模型评分,找出评分最高的候选字串,即可自动侦测文书中的错别字;但是事先准备的‘综合近义子集’会因为搜集不足、过量的子集会造成误判,另外近似子集代换后,所产生的候选字串数量庞大,在中文的检错方面势必造成软体的负担。
常见的英文单词纠错法有:,主要有误拼词典法、词形距离法、最小编辑距离法、相似键法、骨架键法、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等模型,都可以利用目标词上下文中的词同现特征或搭配特征,采用最大似然估计法、互信息、相关度等方法检测文本中的错误,并通过相邻词间的转移概率确定纠错候选词,实现对目标词的校正。
参考文献:
中文自動校正輔助系統
网络搜索引擎中文纠错功能实例剖析
文本自动校对技术研究综述
- 大小: 25.4 KB
分享到:
相关推荐
### 百度往年实习生笔试题目解析 #### 一、公交车站牌设计 **设计要点:** 1. **信息清晰易读:** 设计时需确保站牌上的信息(包括车次、路线、方向等)清晰易读。考虑到不同人群的需求(如老年人、视力不佳者)...
3. **上下文分析**:更高级的拼写纠错系统可能会考虑单词的上下文信息,以提供更加准确的建议。 4. “拼写纠错测试文件”则可能包含了一些故意拼写错误的单词或短语,用以检验程序的纠错能力。 总的来说,这个Java...
在本文中,我们将探讨百度笔试题中的五个不同题目,涵盖编程、英文拼写纠错、热门查询统计、集合合并等知识点,这些都是计算机科学和软件工程领域中常见的问题。 首先,让我们看看第一道编程题。题目要求使用C语言...
互联网发展对快递业影响因素分析——基于主成分分析的方法.pdf
在“时间序列分析——基于R(第2版)案例数据”中,我们将会深入探讨如何利用R语言进行有效的时序分析。R语言是一种强大的开源编程环境,特别适合于数据分析、统计计算和图形绘制。以下是关于这个主题的一些关键知识...
详情见本人博客文章“python | 编译原理,语法分析——LL(1)文法实现 上” 详情见本人博客文章“python | 编译原理,语法分析——LL(1)文法实现 上” 详情见本人博客文章“python | 编译原理,语法分析——LL(1)...
本资源"时间序列分析——基于R(第2版)R程序"是一个关于如何使用R语言进行时间序列分析的教程或代码集,可能是书籍的配套源代码。第二版可能意味着它包含了更新的内容和改进的方法,适应了最新的R语言版本和时间...
### 整体网分析讲义——UCINET+软件应用知识点详解 #### 第一章 社会网络分析简介 ##### 1.1 研究社会关系的学问:社会网络分析 - **网络**:指由节点(或顶点)通过边(或线)连接起来形成的系统。在社会学中,...
Visual C++权威剖析——MFC原理、机制与开发实例pdf电子书
最新深度剖析——“工业互联网、能源互联网、工业4.0”pdf,提供“最新深度剖析——“工业互联网、能源互联网、工业4.0””免费资料下载,主要包括简要介绍工业互联网、三项集成等内容,可供学习使用。
Visual C++权威剖析——MFC原理、机制与开发实例pdf电子书
Visual C++权威剖析——MFC原理、机制与开发实例pdf电子书
《各大公司模电数电笔试题目》集合了众多企业针对模拟电子技术(模电)和数字电子技术(数电)的笔试题目与解答,是应聘者准备相关领域职位的重要参考资料。模电和数电是电子工程的基础学科,对于理解和设计电子系统...
工业互联网平台对工程机械融资租赁的作用分析——基于徐工汉云平台.pdf
标题与描述中的关键词“数值分析”以及提及的书籍“数值分析——钟尔杰”,为我们提供了一个清晰的主题方向:深入探讨数值分析这一数学分支的核心概念、方法及其应用领域。数值分析是一门研究如何通过计算机求解数学...
这份"百度笔试面试题目及答案1"资源包含了一份文档(百度题目1.doc)和一个名为merge.cpp的源代码文件,它们分别涵盖了编程技术和面试技巧方面的知识点。 首先,让我们深入探讨编程题目。merge.cpp很可能是一个实现...
《C#软件项目开发全程剖析——全面透视SharpDevelop软件的开发内幕》这本书是针对C#编程语言和开源集成开发环境(IDE)SharpDevelop的一份深度解析。SharpDevelop是一款专为.NET Framework设计的IDE,它提供了丰富的...
"时间序列分析——基于R(第2版)习题数据,时间序列分析基于r第二版答案,R language源码.zip"这个压缩包文件包含了与时间序列分析相关的教材习题数据、答案以及R语言源码,是学习和实践这一主题的宝贵资源。...
"网上搜集的百度笔试题"这一标题表明了资料的性质,即一组来自网络的百度公司笔试题目。这些题目可能是从各种来源整合而来,包括但不限于论坛、求职网站、历年真题集等。百度是中国知名的互联网巨头,其笔试环节通常...
《14.C#软件项目开发全程剖析——全面透视SharpDevelop软件的开发内幕》是一本深入探讨C#软件项目开发过程的专著,尤其侧重于开源IDE(集成开发环境)SharpDevelop的开发内幕。这本书旨在为读者揭示从项目规划、设计...