关键字查找算法(转存留用)

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

ID NameInfo
0 北京市人民政府

1 国家安全局

2 上海市人民政府

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


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

没理解错的话，应该是类似SQL查询中like子句的功能吧。




1、搞个词典库，把每个关键字编号；
40万关键字+编号，按4个汉字组词算，需要(4*2 + 4) * 40W = 4.8M空间。
搜索方式可以使用简单的二分查找（此时可以省去编号占用的空间）；但考虑这个库实际使用压力较大，采用hash较好。
记得哪里说过，hash数据量应该是存储区大小的7x%；以后再靠加大存储区去减少碰撞，效果已经不明显了。
采用悲观点的值，用8M空间吧。

如果内存紧张，可以不使用hash，改成按关键词排序后二分查找；这样查询效率稍微低一些，但可以节约4.8M空间（hash本身额外占用的3.2M，加上可以用关键词本身的数组下标当作编号而节约的每词4字节共1.6M的空间）。


2、把NameInfo切分，然后分析切分出的关键词在不在词典库里；在就把它记为关键字。

类似这样：
a、NameInfo 北京市人民政府
b、分词，分解为 北京 市 人民 政府 或 北京市 人民 政府
c、查词典，确认 北京 人民 政府 为关键字，且编号分别为123456 345667 456667
（根据你的举例，每条记录大概有3～4个关键字；以后都按4个关键字算；这些关键词仅用于建索引，不必实际存储）



3、另开一个指针数组，数组下标对应关键字编号（这需要40W × 4 = 1.6M字节），指针指向包含对应关键字的记录ID列表。

记录ID的列表可以采用动态分配或内存池。因为有10W记录，所以ID最少需要3字节；为以后扩充计，以下按四字节计算。
假设每条记录都有4个关键字，那么将需要4倍于记录数的节点空间（即需要4*4*10W=1.6M字节）；如果用单链表实现，则还需要额外的4个字节保存next指针，即一共3.2M空间。
（用数组可以比链表减少一半空间消耗，但插入删除比较慢）。

现在，内存中大概是这样：

词典区（8M）：
[关键字1 编号1][关键字2 编号2][关键字3 编号3]……

索引区（1.6M+3.2M=4.8M）
关键字编号=数组下标；

指针指向一个链表，链表保存对应的记录ID（或指向此记录的指针）



记录区（10W × 单条记录大小，假设你的系统还允许占用5M内存，则单条记录不能大于50字节；考虑一个ID要4字节，要求NameInfo不能大于23个汉字）
记录区可以是一个简单数组，此时ID可省略。



所有这些一共需要17.8M空间；若词典改成排序数组，则只需13M空间。
注意记录区ID字段按4字节计，但实际在记录区可以直接用数组下标代替ID，可节约10W×4=0.4M空间；此外，关键字编号只需3字节，前面全部是按4字节算的，也可以压缩一下。

总之，根据自己需要裁剪后，上面这个方案可以压缩到仅占用11M字节甚至更少。



以下按最优性能方案计算

插入效率：
需要若干次O(1)的hash查询（看分词算法的好坏了），以把分词结果对应到关键字编码上；然后建索引需要4次数组访问和4次链表插入操作（复杂度都是O(1)）。

查询效率:
需要一次O(1)的hash查询，以把用户输入的关键词对应到编码上；然后拿这个编码当下标访问数组，取得查询结果链表；再根据链表记载把所有合适记录打印出来。

总的来说，插入、查询效率都是O(1)；很容易扩充出删除操作（好像没这需求吧），且删除效率也是O(1)。


注意这个算法是个完全内存算法，它的响应速度是微秒甚至纳秒级；所以不必担心用二分法查找代替hash后会导致太大的性能损失。


如果将其改成完全磁盘算法（此时当然就不需要担心空间消耗了），即使考虑干扰因素，速度仍然可以保持在十几到几百毫秒的级别上。
——每秒显示25帧，人眼看起来就是连续动画，此时每帧就要滞留1000/25=40毫秒；200毫秒的延迟也不过是5个动画帧而已，一般用户感觉不到任何延迟。

当然，如果有外存的话，考虑40万关键字肯定不会用全、10W记录也不一定每一条都会访问到；那么最好的做法还是搞个cache，做成半内存算法：这样一方面不需要占用太多内存，同时还可以在大部分情况下保持微秒级响应速度。
（当然，如果用外存，还是直接用一些轻量级数据库更方便）