Chinaunix

标题: 10万个字符串,检查相同的.怎么找? [打印本页]

作者: flw2 时间: 2006-09-23 18:57
标题: 10万个字符串,检查相同的.怎么找?
要排序?

作者: skai 时间: 2006-09-23 18:59
难，肯定求效率了，不会

作者: flw 时间: 2006-09-23 19:19
字符串有多长？
如果较短的话，可以构造一颗树。
如果较长的话，直接 md5 吧！

作者: susesuse 时间: 2006-09-23 20:25
trie树?
词典里面所有的单词的存储就可以用trie树实现.

作者: langue 时间: 2006-09-23 20:45
qsort？

作者: hiwoody 时间: 2006-09-23 21:37
提示: 作者被禁止或删除内容自动屏蔽

作者: namtso 时间: 2006-09-23 21:44
用hash_map

作者: 独孤九贱 时间: 2006-09-23 22:03

原帖由 flw2 于 2006-9-23 18:57 发表
要排序?

我觉得关键是如何先对这十万个字符串排序？？
个人觉得可以参考数据库的按字母“索引”，用树来根据字母构建，这样，匹配起来应该很快吧！

作者: mik 时间: 2006-09-23 22:15
hash 算法比较满意

作者: unix_web 时间: 2006-09-23 22:28

原帖由 flw 于 2006-9-23 19:19 发表
字符串有多长？
如果较短的话，可以构造一颗树。
如果较长的话，直接 md5 吧！

什么算法?

作者: rock_jq 时间: 2006-09-23 22:39
搞到数据库中去呵呵

作者: p4apple 时间: 2006-09-23 23:04
字符串可以提前处理吗，如果字符串很少变化，可以对字符串进行MD5编码，的到MD5 列表，然后对MD5列表排序，得到MD5编码索引，需要进行字符串查找时，先找具有相同MD5的字符串，然后仔细比较，速度应该很快的的。
如过数据时变动很大的， MD5索引可以用，hash ＋链表的方式。自持动态加载。

作者: JohnBull 时间: 2006-09-24 00:03
构建一个索引树！
讲课时用过这个例子，参考一下吧！

#define TREEWIDTH 256
typedef struct node_t {
struct node_t *next[TREEWIDTH];
int count;
} node_t;
/* 这个函数把一个word导入一个索引树，然后返回这个word以前曾经导入过多少次 */
int
indexword(node_t *head, const char *word)
{
int i;
node_t *cur,*new;
for (i=0,cur=head;;++i) {
if (word[i]=='\0') {
cur->count=cur->count+1;
if (cur->count > 1) {
return cur->count-1;
}
break;
}
if (cur->next[word[i]] == NULL) {
cur->next[word[i]] = (node_t*)malloc(sizeof(node_t));
if (cur->next[word[i]] == NULL) {
return -1;
}
}
cur=cur->next[word[i]];
}
return 0;
}

复制代码

作者: langue 时间: 2006-09-24 05:52
btree?

作者: BenBear 时间: 2006-09-24 12:25
可以直接将所有字符串排序，然后二分查找，这个也不慢的。

要算 hash 的话，也不需要 md5 那么复杂的，毕竟 md5 太长了，比较不方便。我习惯这样算 hash:

int hash_str(const char* str)
{
int h = 0;
while (*str)
h = h * 5 + *str++;
return h;
}

复制代码

也可以对字符串的 pair<hash, index> 按 hash 排序，先对 hash 进行二分查找，再比较实际值。

作者: liuty2006 时间: 2006-09-25 05:51

原帖由 BenBear 于 2006-9-24 12:25 发表
可以直接将所有字符串排序，然后二分查找，这个也不慢的。

要算 hash 的话，也不需要 md5 那么复杂的，毕竟 md5 太长了，比较不方便。我习惯这样算 hash:
[CODE]
int hash_str(const char* str)
{
int h ...

md5 什么意思?

作者: flw 时间: 2006-09-25 09:29

原帖由 liuty2006 于 2006-9-25 05:51 发表

md5 什么意思?

google md5

作者: liuty2006 时间: 2006-09-25 10:40

原帖由 flw 于 2006-9-25 09:29 发表

google md5

"MD5的全称是Message-Digest Algorithm 5（信息-摘要算法）" --- 好像用于加密,但与此查找相同字符串算法有什么关系?

作者: unix_os 时间: 2006-09-25 10:43

原帖由 liuty2006 于 2006-9-25 10:40 发表

"MD5的全称是Message-Digest Algorithm 5（信息-摘要算法）" --- 好像用于加密,但与此查找相同字符串算法有什么关系?

8懂这个木有关系。。。

有排序树。。。

作者: unix_os 时间: 2006-09-25 10:47

原帖由 BenBear 于 2006-9-24 12:25 发表
可以直接将所有字符串排序，然后二分查找，这个也不慢的。

要算 hash 的话，也不需要 md5 那么复杂的，毕竟 md5 太长了，比较不方便。我习惯这样算 hash:
[CODE]
int hash_str(const char* str)
{
int h ...

排序二分法么。。。

老师提问就问这个D。。。。。

:em11:

结果木有人回答上。。。

:em11:

作者: haterw 时间: 2006-09-25 10:55

原帖由 unix_os 于 2006-9-25 10:43 发表

8懂这个木有关系。。。

有排序树。。。

刚刚在googleBLOG里看到的
http://googlechinablog.com/2006/08/blog-post.html

作者: wxhltmn 时间: 2006-10-20 14:47
我发表了一个类似的主题,结果被锁贴,在回复中给了这个贴子的网址,结果还是没有解决问题,
有谁可以给出代码来解决这个问题啊
我在写代码时被卡住了,请指教

作者: JohnBull 时间: 2006-10-20 14:56

原帖由 wxhltmn 于 2006-10-20 14:47 发表
我发表了一个类似的主题,结果被锁贴,在回复中给了这个贴子的网址,结果还是没有解决问题,
有谁可以给出代码来解决这个问题啊
我在写代码时被卡住了,请指教

我贴代码了啊！

作者: wxhltmn 时间: 2006-10-20 15:54
对你的代码我看了,但是水平不够啊,将你的代码导入后就是无法运行,
对其中的变量和函数找不到头绪啊,能不能给一个完整点的呢,谢谢

作者: JohnBull 时间: 2006-10-20 16:30

原帖由 wxhltmn 于 2006-10-20 15:54 发表
对你的代码我看了,但是水平不够啊,将你的代码导入后就是无法运行,
对其中的变量和函数找不到头绪啊,能不能给一个完整点的呢,谢谢

其实就是Trie树，空间换时间。完整的代码在家里，晚上再说。

作者: delimy 时间: 2006-10-20 18:00
10W个串，如果短，得老多重复的了吧？信息熵编码啊，找个压缩算法就有思路了～trie不失为好办法。
重复少的话，觉的HASH比较好。MD4就行啦，快不少呢～

作者: beepbug 时间: 2006-10-21 06:54
尽管可以拿出许多种解法，包括未来世界的MD10000，但是，切合实际的、高效的，还是楼主自己说的：先排序。

作者: longshort 时间: 2006-10-21 08:16

10万个字符串,检查相同的.怎么找?

看楼主的题意，应该是按模式串找出指定的串共有多少吧？其实，如果不是为了实验新的算法，大可不必用hash之类，直接调用串比较函数不就完了么？

使用字符串比较用“strcmp()”，使用二进制串比较用“bcmp()”。具体使用看手册页。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)