请教关于字符串检索的算法

本帖最后由 osmanthusgfy 于 2010-07-28 20:22 编辑

现在有一个关于字符串检索的算法的问题向大叫请教:
在逻辑上有一个大小不定的字符串的集合(1>.可以理解这些保存在一个文本文件中或则式xml中,或则是其他组织方式,组织方式可以自定义;2>.字符串的长度是任意的),
这个集合的大小是不断增加的,也就是说不能对集合的元素的数量进行假设.
规定不能使用数据库,要考虑IO和检索算法的效率,现在给定一个任意长度的字符串,要求在这个字符串集合中检索,判断这个集合中是否包含给定的字符串.
要求算法必须式高效的,字符串必须保存在文件中,文件可以是一个,多个(要求考虑IO的问题),可以是文本的,或则是二进制,或则是自定义的.也就是说,数据存储的结构是开放的.

我的理解就是要实现类似数据库的select功能.
这问题太开放了,强调的是高效率.
请问大家有什么好的算法或则模型?
谢谢大家!!!!

本帖最后由 yulihua49 于 2010-07-28 23:57 编辑





正则表达式搜索是非常快的，但我不知道他的算法。

压缩算法里有一种搜索重复字符串的hash算法，速度非常快，这我知道。但功能有限。

给你的算法大致如下：
把文本分为32K1块，每块一个索引，由索引头和链表构成。

short head[32768],lnk[32768];
全部初始化成-1；
在数据块里，指针p从data[0]开始，一步1字节的走，将其后3字节hash成15bit，以此为下标，head[hash]此位置的值如果是-1，就把偏移量（p-data）存在这里里。
如果不是-1，就把他移到lnk里，新hash的下标处，新hash的下标存在head里。这样，所有hash值相同的地址构成一个链表。

n=p-data;
if(head[hash]==-1) head[hash]=n;
else lnk[n]=head[hash],head[hash]=n;


检索时，key的头3字节hash成15bit，在head里查到链头，沿着链找数据地址，进行串比较，一块一块的，直到找到。