找回密码
 欢迎注册
查看: 10500|回复: 6

[转载] 一个字串匹配问题

[复制链接]
发表于 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 ... 0-f64fd2e22572.html 一个兄弟的问题,大家帮忙看看
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-29 10:53:37 | 显示全部楼层
66最佳匹配是643还是634 如果存在636是否优先于643 634
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-7-29 11:07:07 | 显示全部楼层
66在本例里面没有匹配,因为正文中没有66+-15范围内的值,而且题目要求的只是模式串的子串 此外我对他的匹配评分有点问题,是长度优先还是差值最小优先,我已经问了~ 题目似乎有些小瑕疵
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-29 12:42:39 | 显示全部楼层
主要是评分函数没有定义清楚。定义清楚了以后,直接穷举应该算一种不错的方法了。但是用动态规划应该可以减少时间复杂度,但是空间复杂度不小。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-29 15:52:58 | 显示全部楼层
这个问题已经有解决方案。如果你用过beyond compare这样的工具体会到。记得去年找到了一篇这样的文章,一直没时间仔细研究,不是很难,但是有点绕脑子,技巧性比较强。当然罗,已经是成型的理论,不是关公耍大刀。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-7-30 08:14:06 | 显示全部楼层
原帖由 mathe 于 2008-7-29 12:42 发表 主要是评分函数没有定义清楚。定义清楚了以后,直接穷举应该算一种不错的方法了。但是用动态规划应该可以减少时间复杂度,但是空间复杂度不小。
嗯,不同的评分函数可能造成动归不正确,搜索加点剪枝可能是通行的办法,实现起来也比较容易
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-7-31 08:06:52 | 显示全部楼层
原帖由 kenmark 于 2008-7-30 08:14 发表 嗯,不同的评分函数可能造成动归不正确,搜索加点剪枝可能是通行的办法,实现起来也比较容易
的确如此.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-24 10:07 , Processed in 0.026964 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表