更多百度笔试题汇总参见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
分享到:
相关推荐
SPD-Conv-main.zip
目录: 1-1 虚拟化技术发展史 1-2 虚拟化技术是什么 1-3 虚拟化技术的分类 1-4 虚拟化技术的优缺点(1) 1-4 虚拟化技术的优缺点 1-5 容器技术的发展 1-6 Docker的发展历史 1-7 Docker是什么 1-8 容器和虚拟机的区别(1) 1-9 容器和虚拟机的区别(2) 1-10 为什么要使用Docker 2-1 Docker的版本 2-2 Docker的安装 2-3 Docker服务启动 2-4 Docker服务信息 2-5 Docker使用初体验-Docker的运行机制 2-6 Docker使用初体验-Docker镜像仓库 2-7 Docker使用初体验-Docker镜像下载 2-8 Docker使用初体验-Docker镜像启动运行 2-9 Docker使用初体验-访问容器中的Tomcat服务 2-10 Docker使用初体验-Docker的网络访问机制 2-11 Docker使用初体验-进入Docker容器内部 2-12 Docker使用初体验-补充说明 3-1 Docker的体系架构(1) 3-2 Docker的体系架构(2)r ..........
《狼》教学设计
对于在外工作或生活的人来说,寻找合适的住房是首要解决的问题。传统的租房方式包括直接联系房东、通过房屋租赁公司或在线搜索房源。直接找房东可能耗时且不便,尤其是需要提前看房的情况;通过中介虽然方便,但需支付额外费用;而在线租房则提供了随时随地的便利性,因此越来越受到青睐。 本房屋租赁平台使用Java语言配合Idea开发环境进行构建,后端数据库选用了Mysql。平台提供了在线预约看房的功能,包括浏览出租房源、在线预约看房、收藏心仪房屋以及留言咨询等。该系统不仅方便了租房者在线预订和管理看房计划,也为房东提供了房屋信息发布和预订管理的便利。
四轮独立驱动横摆角速度控制,LQR 基于LQR算法的 基于二自由度动力学方程,通过主动转向afs和直接横摆力矩dyc实现的横摆角速度跟踪 ,模型包括期望横摆角速度,质心侧偏角,稳定性因素,lqr模块等模块,作为lqr入门强烈推荐。 还有详细的lqr资料说明,可以作为基本模板,和其他算法(mpc smc)做对比等
ESP8266、ESP32平台支持AIRKISS自动配网,但是实际使用中,发现失败的次数挺高的,影响体验,因此另辟他法,偶然发现EPS 支持webserver,通过webserver进行配网可大大提高成功率。 webserver.c实现网页的显示,及获取用户配置的wifi名称和密码; wifi_config.c根据是否已经配过网,决定是否开启ap配网模式还是st连接wifi模式; data_persistence.c实现保存用户设置的wifi名称和密码,防止断电后丢失;
圣诞节倒计时与节日活动管理系统是一个基于Python的桌面应用程序,旨在帮助用户庆祝和管理圣诞节期间的活动。随着圣诞节的临近,许多人希望能够清晰地了解距离节日还有多少时间,同时也希望能够有效地组织和安排各类活动,如家庭聚会、朋友聚会、圣诞晚会等。这个应用程序通过直观的用户界面和实用的功能,满足了这些需求。 该系统的核心功能包括一个实时更新的倒计时器,用户可以看到距离圣诞节还有多少天、小时、分钟和秒。倒计时器通过Python的datetime模块实现,确保准确性和实时性。用户可以自定义圣诞节的日期,以适应不同的庆祝习惯。 除了倒计时功能,用户还可以添加、编辑和删除节日活动。通过简单的输入框,用户可以记录活动的名称、时间和地点等信息。所有活动将以列表的形式展示,用户可以轻松查看即将到来的活动,并进行相应的管理。 在技术实现方面,该应用程序使用了Python的Tkinter库来构建图形用户界面。界面设计简洁明了,用户可以轻松地进行操作。程序还使用了matplotlib库来绘制活动的统计图表,帮助用户直观地了解活动安排情况。
双目立体匹配三维重建点云C++ 本工程基于网上开源代码进行修改,内容如下: 1.修改为 VS2015 Debug win32 版本,支持利用特征点和 OpenCV 立体匹配算法进行进行三维重建及显示,相关代码需要自行修改,代码中添加了修改注释。 2.工程依赖库为 OpenCV2.4.8,内部已完成 OpenCV 相关配置。 无论电脑中是否配置Opencv 都可以运行。 并且增加了点云保存,可以用MATLAB 显示点云。 一、操作步骤 1.解压后将 Reconstuction3d bin 中的所有 dll 拷贝到C: windows sysWOW64 或者system32 根据电脑版本决定,64 位为 sysWOW64。 2.双击 Reconstuction3d.sln 打开工程,运行后出现结果。 二、程序详解 Reconstuction3d.cpp 为程序主函数 cvFuncs.cpp 为特征点三维重建。 包含SIFT、SURF、FAST 等算法。 cvFuncs2.cpp 为视差图三维重建.包含 BM、SGBM 等算法可以选择两者中的一个进行重建,推荐特征点。 特征点三维重建流程:
course_s5_linux应用程序开发篇.pdf
ESP32+DS1302芯片【简单DIY制作时钟】
扑克牌数字检测48-CreateML、Darknet、Paligemma数据集合集.rarPCC3.0 Yolov8-V1 2023-12-04 5:04 PM ============================= *与您的团队在计算机视觉项目上合作 *收集和组织图像 *了解和搜索非结构化图像数据 *注释,创建数据集 *导出,训练和部署计算机视觉模型 *使用主动学习随着时间的推移改善数据集 对于最先进的计算机视觉培训笔记本,您可以与此数据集一起使用 该数据集包括4471张图像。 播放卡分类以创建格式注释。 将以下预处理应用于每个图像: *像素数据的自动取向(带有Exif-Arientation剥离) *调整大小为640x640(拉伸) 应用以下扩展用于创建每个源图像的2个版本: * 0到6像素之间的随机高斯模糊
政务大数据资源平台设计方案
【资源说明】 基于SSM框架一个比赛裁判管理系统校园赛事管理系统,主要技术(SpringMVC + Spring + Mybatis+Hui+Jquery+Ueditor)全部资料+详细文档+高分项目.zip 【备注】 1、该项目是个人高分项目源码,已获导师指导认可通过,答辩评审分达到95分 2、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 3、本项目适合计算机相关专业(人工智能、通信工程、自动化、电子信息、物联网等)的在校学生、老师或者企业员工下载使用,也可作为毕业设计、课程设计、作业、项目初期立项演示等,当然也适合小白学习进阶。 4、如果基础还行,可以在此代码基础上进行修改,以实现其他功能,也可直接用于毕设、课设、作业等。 欢迎下载,沟通交流,互相学习,共同进步!
ANSYS Fluent Tutorial Guide ANSYS Fluent是一种基于 Finite Element Method(有限元方法)的计算流体力学(CFD)软件,广泛应用于航空航天、汽车、能源、医药等领域。下面是ANSYS Fluent Tutorial Guide的知识点总结: 1. ANSYS Fluent简介 ANSYS Fluent是一个功能强大且灵活的CFD软件,能够模拟复杂的流体力学、热传导、质量传递等物理过程。该软件广泛应用于航空航天、汽车、能源、医药等领域,用于模拟、设计和优化各种流体力学系统。 2. ANSYS Fluent的主要特点 * 基于Finite Element Method(有限元方法),能够模拟复杂的几何形状和边界条件 * 支持多种物理模型,包括流体力学、热传导、质量传递、化学反应等 * 具有强大的后处理功能,能够输出丰富的结果数据 * 可以与其他ANSYS产品集成,实现多物理场耦合分析 3. ANSYS Fluent在航空航天领域的应用 * 飞机和导弹的气动设计 * 飞机发动机的热传导和燃烧模拟 * 航天器的热保护和气动设计 4. AN
JavaWeb教务系统是基于Java技术构建的网络应用程序,用于管理高校的教学事务。这个期末大作业可能涵盖了多个关键知识点,包括但不限于以下内容: 1. **Servlet与JSP**:JavaWeb开发的基础,Servlet用于处理服务器端逻辑,而JSP则用于生成动态网页。学生可能需要了解如何创建Servlet类,实现doGet或doPost方法,以及如何在JSP页面上使用EL(Expression Language)和JSTL(JavaServer Pages Standard Tag Library)标签。 2. **MVC模式**:Model-View-Controller模式是JavaWeb开发中常见的设计模式,用于分离业务逻辑、数据模型和用户界面。学生可能需要设计并实现一个MVC架构的教务系统,如Controller负责接收请求并调用Service,Service层处理业务逻辑,而Model层则封装数据。 3. **数据库操作**:项目可能涉及到MySQL或其他关系型数据库的使用,包括数据表的设计、SQL查询语句的编写以及JDBC(Java Database Connect
Python之正则表达式基础知识
《我的白鸽》教学设计
【资源说明】 基于Spring、SpringMVC、Mybatis的校园二手交易平台全部资料+详细文档+高分项目.zip 【备注】 1、该项目是个人高分项目源码,已获导师指导认可通过,答辩评审分达到95分 2、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 3、本项目适合计算机相关专业(人工智能、通信工程、自动化、电子信息、物联网等)的在校学生、老师或者企业员工下载使用,也可作为毕业设计、课程设计、作业、项目初期立项演示等,当然也适合小白学习进阶。 4、如果基础还行,可以在此代码基础上进行修改,以实现其他功能,也可直接用于毕设、课设、作业等。 欢迎下载,沟通交流,互相学习,共同进步!
非常好的音视频会议系统项目全套技术资料.zip
UR5 3D模型