单词拼写检查之cutoff距离
前言
cutoff是一个比较冷门的概念,相比于DP经典算法的编辑距离,cutoff距离只局限于自然语言处理领域。提出cutoff距离的起因很简单,因为经典的编辑距离无法很好地衡量在字符串搜索过程中的编辑距离。
比如我们要对一个错误的字符串进行纠正,我们会用编辑距离去衡量可能正确字符串和错误字符串之间的差异。但是编辑距离有一个很大的问题就是对于自动机匹配过程存在缺陷,在自动机匹配的过程中编辑距离会变得很大。(很明显对于词库比较大的情况,必须要使用自动机)比如hello很有可能是hellx的正确单词,但是h和hellx的编辑距离是4,很明显就会存在自动机匹配难以进行的问题。
什么是cutoff?
针对上面提出的问题,kemal oflazer提出了cutoff算法。对于问题串stra和预测串strb,我们首先需要设置一个阈值,这个阈值作为编辑距离的限制条件。(也就是说符合编辑距离多少的为可能正确的单词)
定义strb的长度为blen,stra的长度为alen。l = max(1, blen - t),作为cutoff距离计算的下边界,u = min(alen, blen + t),作为cutoff距离计算的上边界。我们在计算cutoff距离的时候,就只需要计算min(ed(substr(stra,0,x),strb))(x>=l&&x<=u)即可。(此处substr表示截取0到x的字符为子串,包含x。ed表示编辑距离。min表示取最小值。)
例如reprter和repo的cutoff距离,计算过程如下:
如何实现?
这里给出cutoff算法的Python实现。
def ed_dis(stra, strb):
alen = len(stra)
blen = len(strb)
dp = [[0 for x in range(50)] for y in range(50)]
dp[0][0] = 0
for i in range(alen):
dp[i + 1][0] = i + 1
for j in range(alen):
dp[0][j + 1] = j + 1
for i in range(alen):
for j in range(blen):
if stra[i] == strb[j]:
dp[i + 1][j + 1] = min(min(dp[i + 1][j] + 1, dp[i][j + 1] + 1), dp[i][j])
else:
dp[i + 1][j + 1] = min(min(dp[i + 1][j] + 1, dp[i][j + 1] + 1), dp[i][j] + 1)
return dp[alen][blen]
def cutoff_dis(stra, strb):
"""
:param stra: 错误串
:param strb: 预测串
:return: CUTOFF距离
"""
t = 1 # threshold
alen = len(stra)
blen = len(strb)
l = max(1, blen - t)
u = min(alen, blen + t)
min_ed = 1e10
for i in range(l, u + 1):
suba = stra[0:i + 1]
min_ed = min(min_ed, ed_dis(suba, strb))
return min_ed
print(cutoff_dis('reprter', 'repo'))
cutoff距离如何使用?
计算出cutoff距离以后,究竟如何在自动机上使用cutoff距离?
具体的流程可以参考作者官方论文中给出的流程图。这个流程图是针对ababa这个问题串,对于aba和bab串形成的闭包进行单词推测。自动机的具体流程就不再详细描述了,一个很基础的自动机匹配流程,每次计算cutoff值作为权值即可。在大于阈值的权值结点处停止。
匹配的过程中对于一些特殊节点需要特殊标记,这种节点要求权值==阈值,且所有子节点无法继续扩展,也就是所有子节点权值大于阈值。可以看到图中有三个权值为1的结点符合这种要求。
对于这三个节点所对应的字符串,我们需要再次进行编辑距离计算,如果编辑距离恰好符合阈值,则该字符串是符合条件的字符串,也就是可能正确的字符串。
参考论文
Oflazer K. Error-tolerant finite-state recognition with applications to morphological analysis and spelling correction[J]. Computational Linguistics, 1996, 22(1): 73-89.
最新文章
- 递推 hdu 2048
- 自己动手写ORM框架
- Safari浏览器中对js Date对象的支持
- 基于HT的CSG功能构建HTML5的3D书架
- first day for new job
- MySQL 5.7.14 安装
- MAC 配置--Tomcat服务器
- linux下sshd_config的StrictModes参数
- java乱码详解(java中byte与char的转换)
- sql声明变量,及if -else语句、while语句的用法
- hihocoder 1175
- springcloud第四步:ribbon搭建服务负载均衡
- CloudStack 云计算平台框架
- Linux 常用命令和使用技巧
- String为什么是不可变的?
- 文件处理-智能检测编码的工具(chardet)
- Android Http 与断点续传
- ELKStack入门篇(二)之Nginx、Tomcat、Java日志收集以及TCP收集日志使用
- Activity研究
- 远程连接Oracle 服务器 解决Oracle查询中文乱码
热门文章
- SpringMVC 控制器默认支持GET和POST两种方式
- 通过!important设置css样式优先级
- JS 对象API之修改、删除对象的属性
- display:box;display:flex;弹性盒模型
- Python:猜拳游戏
- 用eNSP模拟
- java.lang.Exception: 资源处理失败,失败原因:com.mysql.jdbc.exceptions.jdbc4.MySQLSyntaxErrorException: Unknown column &#39;?????‰&#39; in &#39;where clause&#39;
- springboot(十七):使用Spring Boot上传文件
- Zabbix实战-简易教程--聚合(Aggreate)
- 微信小程序demo-环球小镇