最短编辑距离
当然，现实生活中也存在汉字拼音没打错，是词语选错了；或者n-gram检查合理但词语不存在，例如：

文章插图


文章插图
这时就用到最短编辑距离了，对于这种热搜词，我们仅需记录n-Top，然后用最短编辑距离计算相似度，提供相似度最高的那个候选项就可以了 。
编辑距离，又称距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数 。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符 。例如将一字转成：
（k→s）
（e→i）
（→g）
俄罗斯科学家 在1965年提出这个概念 。它是一种DP动态规划算法，在POJ或ACM算法书上有类似的题目 。主要思想如下：
首先定义这样一个函数Edit(i, j)，它表示第一个字符串的长度为i 的子串到第二个字符串的长度为j 的子串的编辑距离 。显然可以有如下动态规划公式：
if （i == 0 且 j == 0），Edit(i, j) = 0
if （i == 0 且 j > 0），Edit(i, j) = j
if （i > 0 且j == 0），Edit(i, j) = i
if （i ≥ 1 且 j ≥ 1），Edit(i, j) = min{ Edit(i-1, j) + 1, Edit(i, j-1) + 1, Edit(i-1, j-1) + F(i, j) }，
其中，当第一个字符串的第i 个字符不等于第二个字符串的第j 个字符时，F(i, j) = 1；否则，F(i, j) = 0 。

文章插图
#include #include using namespace std;#define min(a,b) (a
中文语法纠错
之前参加了中文语法错误诊断评测CGED（ACL- ）比赛，我负责的是 部分，我们来看官方给出的样例（、、、分别对应4种语法错误）：
比赛过程中有想到使用依存树来解决（语法搭配错误）问题，语法搭配与其说是语法范畴，倒不如说是语义概念，例如“那个电影”我们判断“个”错了是依据“电影”一词来判断，又如“吴先生是修理脚踏车的拿手”判断“拿手”错了是依据“是”一字，“拿手”是动词，怎么能采用“是+名词”结构呢？但是当时事情比较多各种手忙脚乱前途未卜，所以没做出来 。后来上网查论文看到一篇《基于n-gram及依存分析的中文自动差错方法》，记得是2年前看到过的，当时对依存树还不理解所以没在意论文的后半部，现在理解了，写东西也有个理论支撑，没想到想法好有缘分^_^ 。
词与词之间的搭配是看两者之间的语义关联强度，而依存树的边正可以用来体现这种语义关联度，如果一个句子存在语法错误，那么建成依存树也应该存在一条边是不合理的，我们可以用这条边来判断是否出现了语法错误 。在上述论文中作者将其称之为用来作长距离的中文纠错，而n-gram则是短距离中文纠错 。

• 上一页
• 1
• 2
• 3
• 下一页

• 漏洞扫描神器Xray，从入门到使用
• 在计算机英语中 memory的中文意思是
• 从产品经理的角度算一算：做一个App需要多少钱？
• 关于在Visual Studio中无法使用中文输入法的问题
• 英飞凌TLF35584电源管理芯片中文手册解读【万字长文】
• 【C/C++ 数据结构 】广义表深度解析：从原理到C/C++实现
• Paul Graham：创业须从小事做起
• Java日常练习5 Java从入门到放弃篇16
• 语义分割算法性能比较_语义分割江湖的那些事儿——从旷视说起
• 内卷卷到10后，程序员培养需要从小开始吗？