G
g622
Unregistered / Unconfirmed
GUEST, unregistred user!
有n个长约为2000字节的字符串
如何最快找出其中哪个和第n+1个约2000字节的串最接近？
接近可以用编辑距离(或者其他标准)来描述
如何最快找出其中哪个和第n+1个约2000字节的串最接近？
接近可以用编辑距离(或者其他标准)来描述
C
creation-zy
Unregistered / Unconfirmed
GUEST, unregistred user!
如果仅仅是相同位置的的字符可能不同的话，进行简单的统计分析即可。如果存在错位的
话，就要用到DNA拼接的匹配算法了
//Str0:匹配目标（第n+1个字符串）
//返回值为0-1的小数
function Match(Str0,Str1:String)
ouble;
var
i,n,s:Integer;
begin
if Length(Str0)>Length(Str1) then
n:=Length(Str1)
else
n:=Length(Str0);
s:=0;
for i:=0 to ndo
if Str0=Str1 then
Inc(s);
Result:=s/Length(Str0);
end;
DNA: http://www.delphibbs.com/delphibbs/dispq.asp?lid=1302097
话，就要用到DNA拼接的匹配算法了
//Str0:匹配目标（第n+1个字符串）
//返回值为0-1的小数
function Match(Str0,Str1:String)
ouble;var
i,n,s:Integer;
begin
if Length(Str0)>Length(Str1) then
n:=Length(Str1)
else
n:=Length(Str0);
s:=0;
for i:=0 to ndo
if Str0=Str1 then
Inc(s);
Result:=s/Length(Str0);
end;
DNA: http://www.delphibbs.com/delphibbs/dispq.asp?lid=1302097
G
g622
Unregistered / Unconfirmed
GUEST, unregistred user!
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1302097
是鸟枪法测序用的 不仅仅是拼接 还是个寻优问题
我需要的这个算法的平均复杂度必须接近o
才勉强能用
另：一个子串P与子串Q的编辑距离为k，是指对子串P最多进行k位字符的插入/删除/替代，可得到子串Q。
是鸟枪法测序用的 不仅仅是拼接 还是个寻优问题
我需要的这个算法的平均复杂度必须接近o
才勉强能用另：一个子串P与子串Q的编辑距离为k，是指对子串P最多进行k位字符的插入/删除/替代，可得到子串Q。
C
creation-zy
Unregistered / Unconfirmed
GUEST, unregistred user!
需要详细数据：
1.n的大致范围；
2.编辑距离的平均水平为多少？
3.最接近的字符串的编辑距离一般大致为多少？(0-10? 10-50? 50-100? ...)
4.对最接近的字符串来说，平均每个匹配断点和下一个匹配点的编辑距离是多少？
>>平均复杂度必须接近o
有难度...
1.n的大致范围；
2.编辑距离的平均水平为多少？
3.最接近的字符串的编辑距离一般大致为多少？(0-10? 10-50? 50-100? ...)
4.对最接近的字符串来说，平均每个匹配断点和下一个匹配点的编辑距离是多少？
>>平均复杂度必须接近o
有难度...
G
g622
Unregistered / Unconfirmed
GUEST, unregistred user!
1）n一般在5000~10000
2）平均为80％
3）最接近的编辑距离（也就是允许的上限为）为10％，也就200个字节以内
4）上限为整体长度的10％
呵呵 确实有难度 我现在被这个挡了1个月了
2）平均为80％
3）最接近的编辑距离（也就是允许的上限为）为10％，也就200个字节以内
4）上限为整体长度的10％
呵呵 确实有难度 我现在被这个挡了1个月了
L
LeeChange
Unregistered / Unconfirmed
GUEST, unregistred user!
平均复杂度限制在O?
呵呵，关注．
?呵呵，关注．
C
creation-zy
Unregistered / Unconfirmed
GUEST, unregistred user!
麻烦老兄给一两个有代表性的测试用数据（可以放在xianjun.vicp.net上），n在1000
上下就可以了，WinRAR 3.x最高压缩比——我看看是不是可以知难而退。
ps:平均复杂度限制在O的要求太离谱了，这个系统开发之前都是怎么做的呢（手工?）？
），n在1000上下就可以了，WinRAR 3.x最高压缩比——我看看是不是可以知难而退。
ps:平均复杂度限制在O
的要求太离谱了，这个系统开发之前都是怎么做的呢（手工?）？
D
DarwinZhang
Unregistered / Unconfirmed
GUEST, unregistred user!
"有n个长约为2000字节的字符串 "
"n一般在5000~10000"
"我需要的这个算法的平均复杂度必须接近o才勉强能用"
只要顺序比较，复杂度还不是O?
倒是这个算法的耗时不在O,因为比较字符的长度2000和 n 相差无几。
我想可以先设计一个快速的粗略算法对可能的相同性做一个快速判断，
排除约95%以上的字符串，（可以允许一定的弃真和纳伪概率）
再对剩下的5%左右的字符串进行精确的比较。
"n一般在5000~10000"
"我需要的这个算法的平均复杂度必须接近o
才勉强能用"只要顺序比较，复杂度还不是O
?倒是这个算法的耗时不在O
,因为比较字符的长度2000和 n 相差无几。我想可以先设计一个快速的粗略算法对可能的相同性做一个快速判断，
排除约95%以上的字符串，（可以允许一定的弃真和纳伪概率）
再对剩下的5%左右的字符串进行精确的比较。
G
g622
Unregistered / Unconfirmed
GUEST, unregistred user!
我现在用的试验数据是随机生成的串
如果串数目是n,平均长度是m,待匹配长度也是m,
用一般动态规划的方法求近似距离，我记得复杂度是o(m*m*n)
如果串数目是n,平均长度是m,待匹配长度也是m,
用一般动态规划的方法求近似距离，我记得复杂度是o(m*m*n)
D
DarwinZhang
Unregistered / Unconfirmed
GUEST, unregistred user!
楼主，怎么忽然又冒出个m了？这个代号一出来可是可以变化到极大的。[
]
本来复杂度是一个很粗略的估计。假如字符串长度是m的话，
那么无论如何总要遍历全部的字符才行，复杂度最少也要O(n*m)才行，[
]
居然要O,你是不是要消遣我？[]
因为你的字符量极不是太大，我觉得用复杂度来衡量程序的快慢是不恰当的。
我的思想是用将偏差太远的字符串快速滤掉，然后再仔细的比较。
如果是随机字符串我估计可以快速滤掉99%的字符串了。
假如粗略的算法是精确算法的1/10,那么时间只有全部用精确算法的 0.1+0.01=0.11=1/9，
我能想到的也只能到这里了。[]
]本来复杂度是一个很粗略的估计。假如字符串长度是m的话，
那么无论如何总要遍历全部的字符才行，复杂度最少也要O(n*m)才行，[
]居然要O
,你是不是要消遣我？[]因为你的字符量极不是太大，我觉得用复杂度来衡量程序的快慢是不恰当的。
我的思想是用将偏差太远的字符串快速滤掉，然后再仔细的比较。
如果是随机字符串我估计可以快速滤掉99%的字符串了。
假如粗略的算法是精确算法的1/10,那么时间只有全部用精确算法的 0.1+0.01=0.11=1/9，
我能想到的也只能到这里了。[
]
G
g622
Unregistered / Unconfirmed
GUEST, unregistred user!
怎么能是消遣呢
如果上述问题是精确匹配，且不考虑空间复杂度，dfsa+bm算法的时间复杂度甚至低于o.
如果上述问题是精确匹配，且不考虑空间复杂度，dfsa+bm算法的时间复杂度甚至低于o
.
L
LeeChange
Unregistered / Unconfirmed
GUEST, unregistred user!
时间复杂度低于O? O(logN) or O(1)?
继续学习.
汗呀...
? O(logN) or O(1)?继续学习.
汗呀...
G
g622
Unregistered / Unconfirmed
GUEST, unregistred user!
假设最小模式串(就是那n个中的一个最短的)长度是 minlen
上面我说的复杂度是o(m/minlen) 和 n无关 ，注意n是模式串的数目，m是待匹配的长度
上面我说的复杂度是o(m/minlen) 和 n无关 ，注意n是模式串的数目，m是待匹配的长度
D
DarwinZhang
Unregistered / Unconfirmed
GUEST, unregistred user!
to g622:
1.如果上述问题是精确匹配，且不考虑空间复杂度，dfsa+bm算法的时间复杂度甚至低于o.
对不起,我不晓得什么是dfsa+bm算法,但我知道,如果您的数学模型抽象成字符串,那么复杂度必然是>=O(n*m),原因是你必须遍历字符集. 除非您的数学模型抽象成其他的数据结构.
很显然,你说的精确匹配和我的精确算法的意义是不同的,你的精确匹配是起始位置字符相同
而且不管后面的字符排列,而我说的精确算法并非这个含义.
假如是string变量,因为有一个长整型标定了字符长度,所以这样的比较是经过预处理的.
可以到达O,假如是排好序的,可以到O(log(2,n)),但是排序列的复杂度已经达到O了,
问题是这时候的数学模型不是字符串而是整数了.
如过是pchar类型,那么只好先比较一下,这样一来复杂程度仍然是O(n*m)
2."上面我说的复杂度是o(m/minlen) 和 n无关 "
不和n相关,我都不晓得你在说什么了.这个模型我完全不了解.
我也记得不久前有个barton,也是,自己在自己的领域应该是有造诣的,
可是不肯把问题的数学模型抽象出来,怎么讨论?
每个人的专攻方向都不同,精力也有限度.
1.如果上述问题是精确匹配，且不考虑空间复杂度，dfsa+bm算法的时间复杂度甚至低于o
. 对不起,我不晓得什么是dfsa+bm算法,但我知道,如果您的数学模型抽象成字符串,那么复杂度必然是>=O(n*m),原因是你必须遍历字符集. 除非您的数学模型抽象成其他的数据结构.
很显然,你说的精确匹配和我的精确算法的意义是不同的,你的精确匹配是起始位置字符相同
而且不管后面的字符排列,而我说的精确算法并非这个含义.
假如是string变量,因为有一个长整型标定了字符长度,所以这样的比较是经过预处理的.
可以到达O
,假如是排好序的,可以到O(log(2,n)),但是排序列的复杂度已经达到O了,问题是这时候的数学模型不是字符串而是整数了.
如过是pchar类型,那么只好先比较一下,这样一来复杂程度仍然是O(n*m)
2."上面我说的复杂度是o(m/minlen) 和 n无关 "
不和n相关,我都不晓得你在说什么了.这个模型我完全不了解.
我也记得不久前有个barton,也是,自己在自己的领域应该是有造诣的,
可是不肯把问题的数学模型抽象出来,怎么讨论?
每个人的专攻方向都不同,精力也有限度.