关键字查找算法

kunis

现在有一批中等数量级（十万级）的数据，格式如下：

ID                    NameInfo
0                  北京市人民政府

1                  国家安全局

2                 上海市人民政府

3                 八达岭长城
.......               ................


现在要对此文件建立关键字索引。（例如：输入 国家，可以快速的找到  国家安全局  。输入 人民 可以找到 北京市人民政府 和 上海市人民政府）；
要求建立的索引结构所占用的空间相对最少，但是关键字查找速度要很快。
现在考虑使用 Trie树，但是Trie树太浪费空间了。
不知大家有没有好的算法。尽情讨论！！！

[ 本帖最后由 kunis 于 2008-8-12 21:34 编辑 ]

newIT666

十万级，数据库轻松搞定

cugb_cat

关键字一共有多少个？可以考虑用哈希

ps,用开放寻址法解决冲突

[ 本帖最后由 cugb_cat 于 2008-8-12 21:10 编辑 ]

chenzhanyiczy

有几种吧：
1.hash法
2.利用xml

YangFree

原帖由 newIT666 于 2008-8-12 20:53 发表
十万级，数据库轻松搞定

同意。

qliu00

可以选择hash法
这样可以节省很多空间

kunis

我也想用数据库，可没有啊！一个内存只有10几M，主频只有200多MHZ的系统。跑不起来DBMS啊

kunis

原帖由 chenzhanyiczy 于 2008-8-12 21:09 发表
有几种吧：
1.hash法
2.利用xml

XML？ 一个XML引擎要占用多少空间啊，内存不足啊！

kunis

原帖由 cugb_cat 于 2008-8-12 21:09 发表
关键字一共有多少个？可以考虑用哈希

ps,用开放寻址法解决冲突

关键字有40W


你的意思是 构造一个hash函数

HashFunc(NameInfo)=ID?
其实我现在并不关注这个ID， 我是想当用户输入一个关键字的时候，我能找到所有包含该关键字的NameInfo，然后再考虑使用ID这个字段

[ 本帖最后由 kunis 于 2008-8-12 21:36 编辑 ]

chenzhanyiczy

假如你觉得tree树法都耗内存，那么hash法也将一样
至于xml，有专门的xml函数库，google 一下，free 的