注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

长风明志的博客

不要也不能做下一个谁,应该且可以做第一个自己

 
 
 

日志

 
 

编辑距离  

2012-04-11 22:32:31|  分类: 搜索引擎 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
编辑距离,又称Levenshtein距离(也叫做Edit Distance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
  例如将kitten一字转成sitting:
  sitten (k→s)
  sittin (e→i)
  sitting (→g)
  俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
      为了比较网页结构的相似度,可以把字符相等的判断用HTMLParser返回的Node类型来代替。


应用

  DNA分析
  拼字检查
  语音辨识
  抄袭侦测


算法

  动态规划经常被用来作为这个问题的解决手段之一。
  整数 Levenshtein距离(字符串 str1[1..m], 字符串 str2[1..n])
  //声明变量, d[i , j]用于记录str1[1...i]与str2[1..j]的Levenshtein距离
  int d[0..m, 0..n]
  //初始化
  for i from 0 to m
  d[i, 0] := i
  for j from 0 to n
  d[0, j] := j
  //用动态规划方法计算Levenshtein距离
  for i from 1 to m
  for j from 1 to n
  {
  //计算替换操作的代价,如果两个字符相同,则替换操作代价为0,否则为1
  if str1[i]== str2[j] then cost := 0
  else cost := 1
  //d[i,j]的Levenshtein距离,可以有
  d[i, j] := minimum(
  d[i-1, j] + 1, //在str2上j位置删除字符(或者在str1上i-1位置插入字符)
  d[i, j-1] + 1, //在str2上j-1位置插入字符(或者在str1上i位置删除字符)
  d[i-1, j-1] + cost // 替换操作
  )
  }
  //返回d[m, n]
  return d[m, n]
  评论这张
 
阅读(360)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017