字符串匹配

lidongri 2008-07-11 09:27:33

/*两个字符串的相似度匹配
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;
}
关于这个相似度的计算是这样的
如果跳过一个数字，则相似度相应减去一定数值，利用容差值则不去管它。。
如果某个没有匹配到（字串中），也要减去
*/
因本人数学不好，所以无法给出数学模型，更无法用代码来描述
痛苦ing。。
请各位给出一个算法
说说想法也可以。。
谢谢

...全文

611 32 打赏收藏转发到动态举报

写回复

用AI写文章

32 条回复

切换为时间正序

请发表友善的回复…

发表回复

勇敢的天牛 2008-08-05

打赏
举报

俺戴眼镜的大胡子师兄研究这个...
怀念学校啊！

wangdeqie 2008-08-04

打赏
举报

lidongri 2008-07-31

打赏
举报

ok
自身算法功底不足，迷糊ing

我啃 2008-07-29

打赏
举报

现在关键看你的“估值函数”也就是你如何定义“相似度最高”
来确定动态规划是否正确，估值函数直接决定动态规划的正确性，如果子串不满足可加性，到时候就只能使用搜索+剪枝了

下午到晚上一直不在，明早才可能看到回复，可以Q我，明早再来看~

我啃 2008-07-29

打赏
举报

海浪，我有些问题，匹配时判断“最优”是长度匹配优先，还有差值匹配优先？
这里应该有一个最优判断的“估值函数”，就是给一个匹配评定一个分值，你必须给出

此外大致我的思路是：
设
p(attern) 模式串长度m
t(ext) 正文串长度n
a(llowance) 容差
l(ength) 最大间隔长度
1. 求出p中每一个符号在t中可以根据a匹配的匹配点复杂度O(m*n)
2. 使用动态规划+最优性剪枝

我啃 2008-07-29

打赏
举报

已经提请数学算法毛人审阅，看看他们有没有好办法

hslinux 2008-07-29

打赏
举报

复杂。

Angleyuhj 2008-07-27

打赏
举报

字符串匹配可以用正则式啊~

sitych 2008-07-26

打赏
举报

[Quote=引用 3 楼 yuexianhanshu 的回复:]
你这个根本就不是程序的问题，而是数学问题，
你去数学论坛问问，用什么样的数学方法解决，然后把数学算法用程序表示出来
给你一个数学论坛，山东大学的“数缘社区”，那里都是数学高手
http://www.mathmagic.cn/bbs/
[/Quote]

macfan 2008-07-26

打赏
举报

帮你up

lidongri 2008-07-25

打赏
举报

[Quote=引用 19 楼 biosli 的回复:]
不知道理解对不对，参与一下。

先将src排序O(logN)，然后将每一个sub加减一个allowance，这样就算出了几个范围。这样在已排序的src里找到在这个范围内的，遍历一遍O(n)。
这样就可以了。
[/Quote]
--
谢谢参与，不能排序的。
比如；一段波形，有很多相似的点，如果排序的话，结果是什么了，就变成递增或递减了，呵呵
我的需求就是不能排序，只能比较
郁闷ing。。。
到现在我也没写出一个合适的代码

yeliguo12345 2008-07-23

打赏
举报

帮顶，学习中

yeliguo12345 2008-07-22

打赏
举报

帮顶，学习中

biosli 2008-07-22

打赏
举报

不知道理解对不对，参与一下。

先将src排序O(logN)，然后将每一个sub加减一个allowance，这样就算出了几个范围。这样在已排序的src里找到在这个范围内的，遍历一遍O(n)。
这样就可以了。

lidongri 2008-07-15

打赏
举报

感谢ndsl的认真考虑。。
您把一个大体的思路已经搞明白了
算法对我帮助很大
根据您提供的算法，还要处理一下length的情况
另一种情况是这样的
对于：
src：1， 2， 3， 4， 5， 6
sub：1， 3， 7， 5
在这种情况下不太好解决。。
上面的例子中，相似度，也就是匹配上的数字是1.3，5。7作为一个数组中的杂数需要剔除，
就是这个杂数的剔除我摸不着头脑。
因为如果这样的话算法的复杂度会高N多。。。。
唉，再考虑一下。。
因为上面的算法都是理想状态下的
如果有中间截断的情况的话，问题貌似2个for循环解决不了
只能前面再加一个for循环。。。
-----
sorry，代码放在家里，今晚再整理一下，明天发上来。。。
效率可能很低，但是先实现功能再说。

蜀中巨富 2008-07-15

打赏
举报

看看数据结构的书，里面有详细的算法

ndsl3334 2008-07-15

打赏
举报



if(匹配）

   int ia = b[i-1][j-1] + score[i];

else {

	//下面这两步如果直接这么下去的话会把最终匹配结果的"跨度"拉的很大

	//因为有length

	//所以这里得加点条件限制一下

	int ib = b[i][j-1] + 0;

	int ic = b[i-1][j] + 0;

ndsl3334 2008-07-15

打赏
举报



//表b应该是这样的,横竖无所谓....

//X处的值为2^7 + 2^9 + 2^12

//别处的值还是不写了....

    66  430  36  50 

33

42

433

24

11

233

423     

111

33         

643

231

33          

543               X

ndsl3334 2008-07-15

打赏
举报



//大致说一下思路，可能不对

	//这个应该是动态规划，类似LCS

	//定义一个二维数组b,大小为两个字符串长度(一个数算一个长度单位),每个位置对应目前匹配最大分

	//如[2,3]表示src的前二个数与sub的前三个数的最大匹配分

	//然后初始化二维,各个元素为0;

	//然后在定义一个二维数组score,用来记录src里每个数的匹配分,第一个数的匹配分为2，第二为4，第三为8，第四为16依次类推....

	//然后看下面....



	memset(b,0,sizeof(b));  //先把b里的分都设置为0



	for (int i = 1; i <= m; ++i)  //DP

		for (int j = 1; j <= n; ++j) {

			if(匹配）

				int ia = b[i-1][j-1] + score[i];  //匹配的情况,得score[i]分

			else {

				int ib = b[i][j-1] + 0; //不匹配的情况一：得0分

			    int ic = b[i-1][j] + 0; //不匹配的情况二：得0分

			}

			b[i][j] = Max(ia,ib,ic);  //三种情况得分后，从中选取最大分，记录下来

		}





     //最后结果在b[m,n],因为src里每个数的匹配分是以2,4,8,16……的规律记录的

	 //所以可以根据最终结果为多少来判断匹配的数在第几个位置，也就知道sub在src里相似度最高的字串了

	 //举个例子，如果最后结果为12

	 //12 = 4 + 8 = 2^2 + 2^3

	 //所以在src里的数为第2个和第3个