kenmark 发表于 2008-7-29 10:42:34

一个字串匹配问题

两个字符串的相似度匹配
src:33, 42, 433, 24, 11, 233, 423, 111, 33, 643, 231, 33, 543
sub:66, 430, 36, 50
allowance:15
src:主串
sub:字串
allowance:容差值
隐含变量:lengh 大小为sub长度的1/3
现求一算法,求出sub在src里相似度最高的字串
1:类似于lcs算法,找到最大公共子串,但是这里有个容差值存在。其中最大子串中,66并不被匹配
2:length的意思是最大可以跨越的长度。例如430可以匹配到423, 但是36并不能匹配到111
,那么就可以用到length了往后移动可以发现符合条件的33

double GetSimRate(int src[], int srcSize, int sub[], int subSize, int allowance)
{
double simRate = 0.0;
//请补齐
reutrn simRate;
}
关于这个相似度的计算是这样的
如果跳过一个数字,则相似度相应减去一定数值,利用容差值则不去管它。。
如果某个没有匹配到(字串中),也要减去
转自http://topic.csdn.net/u/20080711/09/1e62d5d3-3d30-477e-82a0-f64fd2e22572.html
一个兄弟的问题,大家帮忙看看

无心人 发表于 2008-7-29 10:53:37

66最佳匹配是643还是634
如果存在636是否优先于643 634

kenmark 发表于 2008-7-29 11:07:07

66在本例里面没有匹配,因为正文中没有66+-15范围内的值,而且题目要求的只是模式串的子串
此外我对他的匹配评分有点问题,是长度优先还是差值最小优先,我已经问了~
题目似乎有些小瑕疵

mathe 发表于 2008-7-29 12:42:39

主要是评分函数没有定义清楚。定义清楚了以后,直接穷举应该算一种不错的方法了。但是用动态规划应该可以减少时间复杂度,但是空间复杂度不小。

chaoge 发表于 2008-7-29 15:52:58

这个问题已经有解决方案。如果你用过beyond compare这样的工具体会到。记得去年找到了一篇这样的文章,一直没时间仔细研究,不是很难,但是有点绕脑子,技巧性比较强。当然罗,已经是成型的理论,不是关公耍大刀。

kenmark 发表于 2008-7-30 08:14:06

原帖由 mathe 于 2008-7-29 12:42 发表 http://bbs.emath.ac.cn/images/common/back.gif
主要是评分函数没有定义清楚。定义清楚了以后,直接穷举应该算一种不错的方法了。但是用动态规划应该可以减少时间复杂度,但是空间复杂度不小。
嗯,不同的评分函数可能造成动归不正确,搜索加点剪枝可能是通行的办法,实现起来也比较容易

mathe 发表于 2008-7-31 08:06:52

原帖由 kenmark 于 2008-7-30 08:14 发表 http://bbs.emath.ac.cn/images/common/back.gif

嗯,不同的评分函数可能造成动归不正确,搜索加点剪枝可能是通行的办法,实现起来也比较容易
的确如此.
页: [1]
查看完整版本: 一个字串匹配问题