论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2006-12-19 23:14 |只看该作者 |倒序浏览

我有一个非常长的数值，大概几千位，要与另外一个数值比较，另外一个数值很短，也就几位。我希望能够知道第2个数值是否是第一个数值的子集。举个短点的例子，比如第一个数为1234567890，第二个是456，这样就匹配上了。而如果是543，就不能匹配上。如果在C下边就好办了，问题是我要把第一个数值放到数据库中，不可能放那么大的数，所以我希望有种算法把几千个数值变为几十个能放到数据库中，然后具有一定的特征，然后再与第二值个比较时能够知道它是否是原来那几千位里边的数值。
谢谢！

文库|博客

langue

版主

论坛徽章:: 0

2楼 [报告]

发表于 2006-12-19 23:17 |只看该作者

字符串匹配？

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

cugb_cat

版主

论坛徽章:: 0

3楼 [报告]

发表于 2006-12-19 23:20 |只看该作者

在数据库里能把那个大数以文本的格式存放吗？

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

Edengundam

家境小康

论坛徽章:: 0

4楼 [报告]

发表于 2006-12-19 23:22 |只看该作者

你完全能用 varchar 来储存这个数据( 反正已经大到没有直接办法进行数值运算了, 当字符串多好 )
然后你用WHERE XXX LIKE '%456%' 去匹配这个字符串就 OK 了.
varchar 一般都能轻松到 8K ^_^ 再不行就大对象吧

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

ArXoR

稍有积蓄

论坛徽章:: 0

5楼 [报告]

发表于 2006-12-20 11:56 |只看该作者

存储随便怎么截取分段存就好了
匹配用kmp算法...

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

terry322

白手起家

论坛徽章:: 0

6楼 [报告]

发表于 2006-12-20 13:18 |只看该作者

en ,谢谢，我想也只能这样了，那种数学算法好像没有。比如md5,但不能反解析。
但varchar类型可能不行，就用text类型吧，然后做匹配。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

shaohui

白手起家

论坛徽章:: 0

7楼 [报告]

发表于 2007-04-30 12:58 |只看该作者

很经典的算法KMP就可以了。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

uppet

丰衣足食

论坛徽章:: 0

8楼 [报告]

发表于 2007-05-01 12:58 |只看该作者

对于这种问题，，前面几个兄台说得都是很对的。。。
不过，也存在更快的方法。。。。

现在情况是在N长串中搜M小串。。。。。N很大,M很小。。。

用KMP复杂度为O(N)。。。

如果你用Suffix Tree来对N长串做一个预处理，可以得到一个时间复杂度为O(M)的算法。。。
也就是说~在长度为1亿的文章中想知道'小楼一夜听春雨'这句话有没有出现，只需要比较strlen("小楼一夜听春雨")次就可以了。。。。

很诱人吧？？？？

DNA科学研究领域很多人用的就是这个方法~

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

GKL 该用户已被删除	9楼 [报告] 发表于 2007-05-01 13:24 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽
GKL 该用户已被删除	实战分享：从技术角度谈机器学习入门\| 【大话IT】RadonDB低门槛向MySQL集群下战书 \| ChinaUnix打赏功能已上线！ \| 新一代分布式关系型数据库RadonDB知多少？

ArXoR

稍有积蓄

论坛徽章:: 0

10楼 [报告]

发表于 2007-05-01 13:36 |只看该作者

原帖由 uppet 于 5/1/07 12:58 发表
对于这种问题，，前面几个兄台说得都是很对的。。。
不过，也存在更快的方法。。。。

现在情况是在N长串中搜M小串。。。。。N很大,M很小。。。

用KMP复杂度为O(N)。。。

如果你用Suffix Tree来对N长串做 ...

这个东西常数很大... 海量数据而且多查询时的确得用这玩意了

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

12 / 2 页下一页

返回列表

Chinaunix › 论坛 › 程序设计 › C/C++ › 超难算法问题，谁能帮我解决

[算法] 超难算法问题，谁能帮我解决 [复制链接]

浏览过的版块