baidu笔试题 数据检索问题 from smth

三、 现有两个文件，

a)数据文件A，格式为：关键词、IP地址、时间

，记录条数为1000万左右，该文件是无序排列的。

b)数据文件B是关键词ID到关键词的对应表文件，格式为：ID、关键词，记录条数在100万左右，也是无序排列的。该对应表中的记录是一一对应的，不存在ID或者关键词重复的情况。

要求将数据文件A对应的关键词替换为B中的ID，生成新的数据文件C，数据文件C的格式为：关键词ID、IP地址、时间。

请设计一个程序，实现上述功能，并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G，硬盘足够大。(至少要给出关键算法和设计思路)

简评：

如何对海量数据进行快速检索，这是搜索引擎的必需考虑的问题。这又涉及到数

据结构和算法。　　因此，要想进入百度，就必须熟悉一些基本的算法和数据结构。
思路及解决方案如下：

1: 设计用TRIE树实现关键词到其对应id的快速词典查找

TRIE树的每一个节点为一个包含256个元素的数组，同时指针指向其下一级节点


节点定义如下：

struct trienode
 {
 int   id;
 struct trienode *child[256];
 }TRIENODE;


如果TRIE树的某个节点的指针为NULL，说明从跟节点到当前节点的路径构成文件
B中的一个关键词，

在其节点的id保存该关键词的id;如果指针不为NULL，则id对应为0或者一个无穷
大的整数，标志从根节点

到当前节点的路径不是一个完整的关键词。

将关键词转化为二进制无符号char型数组，即对于汉字等双字节字符视为两个无
符号char型整数，

每个元素的取值范围在0到255之间。

2：生成文件b的TRIE树

步骤1：依次读取文件b的每一行，对每一行执行步骤2到步骤5

步骤2：读取关键词id和关键词，令为key

步骤3：依次读取key的每一个字符，对每一个字符，执行步骤4

;

步骤4：如果该字符对应的指针为NULL，则创建其儿子节点;

步骤5：为当前节点的对应字符id置为关键词id

3：根据A文件生成C文件

步骤1：依次读取文件A的每一行，对每一行执行步骤2到步骤5

步骤2：分别获取当前行关键词、ip地址和时间

步骤3：令关键词key=c1c2...cm，对c1到cm每个字符，执行步骤4

步骤4：获取根节点的第c1个元素指针，转移到节点node1，

根据node1的第c2个元素指针，转移到node2...

根据nodem的第cm个元素，获取关键词的id

步骤5：往文件c中写入一行数据，格式为关键词的id、ip地址和时间

4：复杂度分析

生成文件B的TRIE树过程时间复杂度为O(n*m)，其中n为文件b行数，m为文件b关
键词的最大长度。TRIE的空间复杂度为O(n*m)，n和m含义同上，但由于实际应用中关
键词之间可能会有很多前缀相同现象，所以实际耗费空间并不会很高。

生成C文件的时间复杂度同样为O(n*m)，n为文件a行数，m为文件a关键词的最大
长度，因为有了TRIE树之后，给定一个关键词获得其id的时间复杂度为关键词长度。
生成C文件的过程除了TRIE树空间外基本不需要太多额外的空间，空间复杂度为O(1)
，由于系统有1G的可用内存，TRIE占用的空间在几十兆到200M之间(与关键词集合有
关)，因此本方法完全可行。