一、课程介绍
斯坦福大学于2012年3月在Coursera启动了在线自然语言处理课程,由NLP领域大牛Dan Jurafsky 和 Chirs Manning教授授课:
链接地址
以下是本课程的学习笔记,以课程PPT/PDF为主,其他参考资料为辅,融入个人拓展、注解,抛砖引玉,欢迎大家在“我爱公开课”上一起探讨学习。
课件汇总下载地址:斯坦福大学自然语言处理公开课课件汇总
二、最小编辑距离
1)定义
编辑距离(Minimum Edit Distance,MED),又称Levenshtein距离,是指两个字符串之间,由一个转成另一个所需要的最少编辑操作次数。允许的编辑操作包括:将一个字符替换成另一个字符(substitution,s),插入一个字符(insert,i)或者删除一个字符(delete,d),如下图所示:
在大学算法设计相关课程上,想必大家都已经学习过使用动态规划算法解最小编辑距离,形式化定义如下:

最终求得D(n,m)即为字符串X[0...n]与Y[0...m]之间的最小编辑距离。
2)应用
最小编辑距离通常作为一种相似度计算函数被用于多种实际应用中,详细如下: (特别的,对于中文自然语言处理,一般以词为基本处理单元)
- 拼写纠错(Spell Correction):又拼写检查(Spell Checker),将每个词与词典中的词条比较,英文单词往往需要做词干提取等规范化处理,如果一个词在词典中不存在,就被认为是一个错误,然后试图提示N个最可能要输入的词——拼写建议。常用的提示单词的算法就是列出词典中与原词具有最小编辑距离的词条。
这里肯定有人有疑问:对每个不在词典中的词(假如长度为len)都与词典中的词条计算最小编辑距离,时间复杂度是不是太高了?的确,所以一般需要加一些剪枝策略,如:
- 因为一般拼写检查应用只需要给出Top-N的纠正建议即可(N一般取10),那么我们可以从词典中按照长度依次为len、len-1、len+1、len-2、len-3、...的词条比较;
- 限定拼写建议词条与当前词条的最小编辑距离不能大于某个阈值;
- 如果最小编辑距离为1的候选词条超过N后,终止处理;
- 缓存常见的拼写错误和建议,提高性能。
- DNA分析:基因学的一个主要主题就是比较 DNA 序列并尝试找出两个序列的公共部分。如果两个 DNA 序列有类似的公共子序列,那么这些两个序列很可能是同源的。在比对两个序列时,不仅要考虑完全匹配的字符,还要考虑一个序列中的空格或间隙(或者,相反地,要考虑另一个序列中的插入部分)和不匹配,这两个方面都可能意味着突变(mutation)。在序列比对中,需要找到最优的比对(最优比对大致是指要将匹配的数量最大化,将空格和不匹配的数量最小化)。如果要更正式些,可以确定一个分数,为匹配的字符添加分数、为空格和不匹配的字符减去分数。
全局序列比对尝试找到两个完整的序列 S1和 S2之间的最佳比对。以下面两个 DNA 序列为例:
S1= GCCCTAGCG
S2= GCGCAATG
如果为每个匹配字符一分,一个空格扣两分,一个不匹配字符扣一分,那么下面的比对就是全局最优比对:
S1'= GCCCTAGCG
S2'= GCGC-AATG
连字符(-)代表空格。在 S2'中有五个匹配字符,一个空格(或者反过来说,在 S1'中有一个插入项),有三个不匹配字符。这样得到的分数是 (5 * 1) + (1 * -2) + (3 * -1) = 0,这是能够实现的最佳结果。
使用局部序列比对,不必对两个完整的序列进行比对,可以在每个序列中使用某些部分来获得最大得分。使用同样的序列 S1和 S2,以及同样的得分方案,可以得到以下局部最优比对 S1''和 S2'':
S1 = GCCCTAGCG
S1''= GCG
S2''= GCG
S2 = GCGCAATG
这个局部比对的得分是 (3 * 1) + (0 * -2) + (0 * -1) = 3。
- 命名实体抽取(Named Entity Extraction):由于实体的命名往往没有规律,如品牌名,且可能存在多种变形、拼写形式,如“IBM”和“IBM Inc.”,这样导致基于词典完全匹配的命名实体识别方法召回率较低,为此,我们可以使用编辑距离由完全匹配泛化到模糊匹配,先抽取实体名候选词。
具体的,可以将候选文本串与词典中的每个实体名进行编辑距离计算,当发现文本中的某一字符串的编辑距离值小于给定阈值时,将其作为实体名候选词;获取实体名候选词后,根据所处上下文使用启发式规则或者分类的方法判定候选词是否的确为实体名。
- 实体共指(Entity Coreference):通过计算任意两个实体名之间的最小编辑距离判定是否存在共指关系?如“IBM”和“IBM Inc.”, "Stanford President John Hennessy "和"Stanford University President John Hennessy"。
- 机器翻译(Machine Translation):
- 识别平行网页对:由于平行网页通常有相同或类似的界面结构,因此平行网页在HTML结构上应该有很大近似度。首先将网页的HTML标签抽取出来,连接成一个字符串,然后用最小编辑距离考察两个字符串的近似度。实际中,此策略一般与文档长度比例、句对齐翻译模型等方法结合使用,以识别最终的平行网页对。
-
自动评测:首先存储机器翻译原文和不同质量级别的多个参考译文,评测时把自动翻译的译文对应到与其编辑距离最小的参考译文上,间接估算自动译文的质量,如下图所示:
- 字符串核函数(String Kernel):最小编辑距离作为字符串之间的相似度计算函数,用作核函数,集成在SVM中使用。
3)变形
在基本的编辑距离基础上,结合实际应用,往往需要做一些变形或改进,如某些拼写错误相对其他更容易发生,同义词替换、虚词或修饰成分被删除(或插入)应该得到较小的惩罚,等等。
改进后的最小编辑距离公式如下所示:

三、参考资料
- Lecture Slides: Minimum Edit Distance
- http://en.wikipedia.org
- 双语平行网页挖掘系统的设计与实现
- 机器翻译系统评测规范
- Improved-Edit-Distance Kernel for Chinese Relation Extraction
http://www.aiuxian.com/article/p-1035687.html
大家可以加我个人微信号:scccdgf

相关推荐
在自然语言处理(NLP)领域,最小编辑距离还可以被用来评估机器翻译的质量,通过比对机器翻译结果与人工翻译或标准翻译,来量化翻译的准确性。此外,编辑距离也可以应用在信息检索和数据库查询中,帮助提高检索的...
【项目资源】: 单片机项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。
毕设工坊:专注于计算机毕业设计项目的交流与资源共享平台,涵盖各类技术文档、代码示例及实战经验分享,助力学子顺利完成学业挑战。
【window 可视化nvm管理node版本 nvm-desktop】
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
# 基于microbit编程语言的mymicrobit扩展插件项目 ## 项目简介 这是一个基于microbit编程语言的mymicrobit扩展插件项目。该项目旨在提供额外的功能和特性,以扩展microbit编程环境。通过此插件,用户可以轻松地在MakeCode环境中进行编程,实现对micro:bit设备的更多控制和功能实现。 ## 项目的主要特性和功能 1. 扩展性提供了丰富的积木块和代码库,允许用户轻松实现复杂的编程逻辑和功能扩展。 2. 图形化编程支持通过积木块形式的图形化编程,降低编程门槛,方便初学者快速上手。 3. 实时预览提供了积木块的实时预览功能,方便用户直观地了解代码块的逻辑和功能。 4. 与MakeCode无缝集成可以直接在MakeCode环境中导入和使用,无需额外的配置和安装。 ## 安装使用步骤
【项目资源】: 单片机项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
项目资源包含:可运行源码+sql文件 适用人群:学习不同技术领域的小白或进阶学习者;可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 项目具有较高的学习借鉴价值,也可拿来修改、二次开发。 有任何使用上的问题,欢迎随时与博主沟通,博主看到后会第一时间及时解答。 开发语言:Python 框架:django Python版本:python3.8 数据库:mysql 5.7 数据库工具:Navicat 开发软件:PyCharm 浏览器:谷歌浏览器
第三章-局域网-思维导图
内容概要:PT300机械故障综合模拟实验台由瓦仑尼安教学设备有限公司生产,旨在帮助用户深入了解振动特征知识及复杂转子振动频谱分析,实现精密振动分析和精准故障诊断。该实验台能模拟轴承故障、不平衡、不对中、设备松动、转子摩擦等多种机械故障现象,可进行不同转速下的轴承故障频率识别、转子静动平衡模拟试验、设备启停机测试等实验。设备采用高效节能ABB三相交流电动机,配备高精度转速控制和测量模块,确保运行稳定。此外,实验台还设有透明防震安全罩和互锁开关,保障实验安全。; 适合人群:高校师生、科研人员等需要学习或研究机械故障诊断相关理论知识和实践技能的人群。; 使用场景及目标:①用于高校等教育机构的教学,辅助学生理解机械故障诊断的理论知识和实践技能;②满足科研人员进行机械故障诊断算法验证、故障特征分析等科研需求。; 其他说明:PT300机械故障综合模拟实验台的每个部件均经过高精度加工,确保在不同振动状态下稳定运行。用户可根据期望分析特定部件的故障特征。设备尺寸为735mm(长)×310mm(宽)×350mm(高),保修一年,且提供免费操作指导服务。
【项目资源】: 适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。
内容概要:本文详细介绍了使用COMSOL Multiphysics的弱形式接口对三维光子晶体进行数值模拟的方法和技巧。文章通过具体的代码示例,解释了如何构建光子晶体的介电常数分布、设置弱形式PDE、处理电磁场切向连续性、应用Floquet周期边界条件以及特征值求解等关键步骤。特别强调了弱形式接口相比传统物理场接口的优势,如灵活性和对复杂边界的处理能力。文中还分享了一些实用的经验和注意事项,如布洛赫边界条件的实现、特征值求解器参数的优化配置以及网格划分的技巧。 适合人群:具备一定电磁学和数值模拟基础的研究人员或工程师,尤其是对光子晶体仿真感兴趣的读者。 使用场景及目标:①理解并掌握COMSOL弱形式接口在光子晶体仿真中的应用;②学习如何通过弱形式设置处理复杂的电磁场问题;③提高对光子晶体能带结构和带隙特性的认识;④掌握特征值求解和网格划分的最佳实践。 阅读建议:由于本文涉及较多的具体代码和物理概念,建议读者在阅读过程中结合COMSOL软件进行实际操作,同时查阅相关电磁理论书籍以加深理解。此外,对于文中提到的一些具体参数设置和技巧,可以通过尝试不同的配置来巩固所学知识。
# 基于Arduino平台的INSPTComputacion2项目 ## 项目简介 INSPTComputacion2是一个基于Arduino平台的开发项目。该项目旨在通过Arduino的硬件和软件能力,实现一系列计算和交互功能。通过此项目,用户可以体验到Arduino在嵌入式系统、物联网和微控制器等领域的强大功能。 ## 项目的主要特性和功能 该项目的主要特性和功能包括但不限于以下几点 1. 嵌入式系统开发利用Arduino的硬件资源,开发嵌入式系统应用。 2. 物联网应用实现Arduino与物联网技术的结合,进行数据采集、传输和控制。 3. 交互设计通过Arduino实现人机交互,如按钮控制、LED显示等。 4. 数据处理利用Arduino进行数据处理和分析,如温度、湿度等环境数据的采集和处理。 ## 安装使用步骤 以下是在已下载本项目源码文件后的安装使用步骤 1. 确保已安装Arduino IDE软件。
【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。
【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。
Python数据结构-学习笔记
该系统展示了一个电影在线购票系统的结构图,系统分为前台和后台两部分。前台包括首页、影院信息、电影信息、电影资讯和个人中心等模块,主要面向普通用户,提供电影浏览、选座购票、个人账户管理等功能。后台部分由管理员通过后台模块进行操作,包括系统首页、用户管理、场次管理、时间段管理、影院信息管理、电影分类管理、电影信息管理、订单管理和个人中心等模块,用于系统的维护和管理,如用户信息维护、电影和影院信息更新、订单处理等。整个系统旨在为用户提供便捷的在线购票体验,同时确保后台管理的高效和有序。
5G NR射频一致性自测用例 由于NR射频测试场景太多,全指标自动化跑测用时太久,本表格选取了主要场景的关键指标,以便于射频工程师对产品的NR射频指标进行初步摸底。 表格每一页概况: 1、NR TDD摸底指标N77/78/79/41 2、NR FDD摸底指标N1/3//5/8/28 附录1、各频段带宽所支持的SCS 附录2、各带宽SCS的RB配置 附录3、灵敏度测试的RB配置 附录4、摸底测试信道查询 附录5、各频段频率范围
【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。