免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 3673 | 回复: 9

[算法] [请教]大规模字符串近似匹配的算法 [复制链接]

论坛徽章:
0
发表于 2006-07-03 09:48 |显示全部楼层
有这样一个问题,有一个很大的字符串文件,内容是N个字符串,N很大,假设>10W,
现在给一个字符串,从这个文件里找最相似的10个出来。

我本来想用edit distance,但是这样太慢,要对N个字符串中的每一个做一次edit distance,太慢,请教各位,有没有什么好的算法?
谢谢!~

论坛徽章:
0
发表于 2006-07-03 10:11 |显示全部楼层
怎样才算相似?
譬如:给的字符是 abcd,那么是abc相似多一点,还是abcde相似多一点.

论坛徽章:
0
发表于 2006-07-03 10:14 |显示全部楼层
算一样相似的吧,这个相似应该是说不一样的字的数目,这2个不一样的字都只有1个,所以,算一样相似的。

论坛徽章:
0
发表于 2006-07-03 10:23 |显示全部楼层
原帖由 wxp19831104 于 7/3/06 10:14 发表
算一样相似的吧,这个相似应该是说不一样的字的数目,这2个不一样的字都只有1个,所以,算一样相似的。

那abcde与edcba是一样的罗!
这样的话我也不知道有什么好的算法,等待高手解决,呵呵!
本来我还以为这种思想类似于优先队列式分支限界法呢.

论坛徽章:
0
发表于 2006-07-03 10:45 |显示全部楼层
这种情况我还没考虑,这是我的一个面试题。
那我觉得相似应该就是和求edit distance的概念一样,就是看插入或者改变几个字能使得2个串一样,这样,abcde和edcba还是不一样的,而且差别很大。
说说你的 优先队列式分支限界法。

论坛徽章:
0
发表于 2006-07-03 10:59 |显示全部楼层
学习学习

论坛徽章:
0
发表于 2006-07-03 11:12 |显示全部楼层
若给定字符串的第一个字符是'a'的话 那么第一个结点的左子树就是所有第一个字符是'a'的字符串
其余的都是右子树,以此类推,以优先级遍历,如果发现字符串数组中有字符串优先级小于该结点上的字符串,则选取一个取代它.
如字符串的长度为N
当n<=N
某结点左子树的优先级=该结点的优先级+1
右子树优先级不变
当n>N时
n层的优先级-1 依次类推.

论坛徽章:
0
发表于 2006-07-03 13:59 |显示全部楼层
没太看懂,这样行吗?

论坛徽章:
0
发表于 2006-07-03 22:16 |显示全部楼层
如果字符串相似是用edit distance来定义的话,那么只能对每个字符串作edit distance,如果不是的话,可以用别的来定义相似。。。

论坛徽章:
0
发表于 2006-07-04 09:16 |显示全部楼层
谢谢,这个是百度的笔试题,我也不知道它说的是什么意思,我把这个edit distance写上去了,但是又写效率低,否定了,因为我想他们的搜索引擎查东西都是几十ms,如果光这一项都这么慢,肯定不行。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP