`
viMory
  • 浏览: 56416 次
  • 性别: Icon_minigender_1
  • 来自: 土卫六
最近访客 更多访客>>
社区版块
存档分类
最新评论

关于资料上子串距离的一种尝试性纠正

阅读更多

             资料上的子串距离定义如下:    

 设uv分别为长度是nm的字,p是它们的最大公共子串的长度,uv的子串距离定义为dS(u, v) = n+m−2p

            先来看海明距离,他是计算同一位置的不同元素的个数,很明显左图的海明距离为3.但对于子串距离,如按定义去解那就是 8+8-2*5=6,公共子串长度为5嘛,所以子串距离应为6.但实际上看图只有2啊,是不是资料错了?下午还专门去找老师请教了一翻,吐血的是老师说他早就知道这个错误了,但没拿出解决方案。我怀疑这个定义中的公式写错了,应该是dS(u,v)=max(n,m)-p。怎么得出来的,是看图看出来的。只要拿长度最大的串减去最大公共子串就是子串距离了,另外一张图也证实了我这一看法:图中的海明距离为32,但子串距离仅为6,我的计算是32-26=6,而不是32+32-2*26。

              

            跟老师说了,他觉得也是这样的,但没看到定义前不知道到底正确不?网上又找不到子串距离的相关介绍。原文是英语的,不向国内出售版权。难道还要逼我去看那个组合数学。抓狂中...

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics