Trie树的定义(转)
Trie树是一棵度 m ≥ 2 的树,它的每一层分支不是靠整个关键码的值来确定,而是由关键码的一个分量来确定。
如下图所示Trie树,关键码由英文字母组成。它包括两类结点:元素结点和分支结点。元素结点包含整个key数据;分支结点有27个指针,其中有一个空白字符‘b’,用来终结关键码;其它用来标识‘a’, ‘b’,..., ‘z’等26个英文字母。
在第0层,所有的关键码根据它们第0位字符, 被划分到互不相交的27个类中。
因此,root→brch.link[i] 指向一棵子Trie树,该子Trie树上所包含的所有关键码都是以第 i 个英文字母开头。
若某一关键码第 j 位字母在英文字母表中顺序为 i ( i = 0, 1, ?, 26 ), 则它在Trie树的第 j 层分支结点中从第 i
个指针向下找第 j+1
位字母所在结点。当一棵子Trie树上只有一个关键码时,就由一个元素结点来代替。在这个结点中包含有关键码,以及其它相关的信息,如对应数据对象的存放
地址等。
Trie树的类定义:
const int MaxKeySize = 25; //关键码最大位数
typedef struct { //关键码类型
char ch[MaxKeySize]; //关键码存放数组
int currentSize; //关键码当前位数
} KeyType;
class TrieNode { //Trie树结点类定义
friend class Trie;
protected:
enum { branch, element } NodeType; //结点类型
union NodeType { //根据结点类型的两种结构
struct { //分支结点
int num; //本结点关键码个数
TrieNode *link[27]; //指针数组
} brch;
struct { //元素结点
KeyType key; //关键码
recordNode *recptr; //指向数据对象指针
} elem;
}
}
class Trie { //Trie树的类定义
private:
TrieNode *root, *current;
public:
RecordNode* Search ( const keyType & );
int Insert ( const KeyType & );
int Delete ( const KeyType & );
}
10.3.2 Trie树的搜索
为了在Trie树上进行搜索,要求把关键码分解成一些字符元素, 并根据这些字符向下进行分支。
函数 Search 设定 current = NULL, 表示不指示任何一个分支结点, 如果 current 指向一个元素结点 elem,则 current→elem.key 是 current 所指结点中的关键码。
Trie树的搜索算法:
RecordNode* Trie::Search ( const KeyType & x ) {
k = x.key;
concatenate ( k, ‘b’ );
current = root;
int i = 0; //扫描初始化
while ( current != NULL && current→NodeType != element && i <= x.ch[i] ) {
current = current→brch.link[ord (x.ch[i])];
i = i++;
};
if ( current != NULL && current→NodeType == element && current→elem.key == x )
return current→recptr;
else
return NULL;
}
经验证,Trie树的搜索算法在最坏情况下搜索的时间代价是 O(l)。其中, l 是Trie树的层数(包括分支结点和元素结点在内)。
在用作索引时,Trie树的所有结点都驻留在磁盘上。搜索时最多做 l 次磁盘存取。
当结点驻留在磁盘上时,不能使用C++的指针 (pointer) 类型, 因为C++不允许指针的输入 / 输出。在结点中的 link 指针可改用整型(integer) 实现。
10.3.3 在Trie树上的插入和删除
示例:插入关键码bobwhite和bluejay。
a. 插入 x = bobwhite 时,首先搜索Trie树寻找 bobwhite 所在的结点。
b. 如果找到结点, 并发现该结点的 link[‘o’] = NULL。x不在Trie树中, 可以在该处插入。插入结果参看图。
c. 插入 x = bluejay时,用Trie树搜索算法可找到包含有 bluebird 的元素结点,关键码bluebird 和 bluejay 是两个不同的值,它们在第5个字母处不匹配。从 Trie树沿搜索路径,在第4层分支。插入结果参看图。
在Trie树上插入bobwhite和bluejay后的结果 :
示例:考虑在上图所示Trie树中删除bobwhite。此时,只要将该结点link[‘o’]置为0 (NULL)即可,Trie树的其它部分不需要改变。
考虑删除 bluejay。删除之后在标记为δ3 的子Trie树中只剩下一个关键码,这表明可以删去结点δ3 ,同时结点 ρ
向上移动一层。对结点δ2 和δ1 可以做同样的工作,最后到达结点б。因为以б
为根的子Trie树中有多个关键码,所以它不能删去,令该结点link[‘l’] = ρ即可。
为便于Trie树的删除, 在每个分支结点中设置了一个 num 数据成员,它记载了结点中子女的数目。
Trie,又称单词查找树,是一种树形结构,用于保存大量的字符串。它的优点是:利用字符串的公共前缀来节约存储空间。
性质
它有3个基本性质:
- 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
例子
这是一个Trie结构的例子:
在这个Trie结构中,保存了t、to、te、tea、ten、i、in、inn这8个字符串,仅占用8个字节(不包括指针占用的空间)
问题:
一、 一个文本文件有多行,每行为一个URL。请编写代码,统计出URL中的文件名及出现次数。
a) 文件名不包括域名、路径和URL参数,例如http://www.rs.com/n.op/q/rs?id=1中的文件名是rs。
b) 部分URL可能没有文件名,例如http://www.abc.com/,这类统计为“空文件名”。
c) 出现在不同URL中的相同文件名视为同一文件名,例如http://www.ceshi.com/hi.php和ftp://ftp.cdef.com/hi.php为同一文件名
文件内容示例如下:
http://www.test.com/abc/de/fg.php?id=1&url=http://www.test.com/index.html
http://www.ceshi.com/hi.jsp
ftp://ftp.ceshi.com/hi.jsp
http://www.hello.com/cw/hi.jsp?k=8
http://www.hi.com/jk/l.html?id=1&s=a.html
http://www.rs.com/n.op/q/rs?id=1
http://www.abc.com/
二、 一个简单的论坛系统,以数据库储存如下数据:
用户名,email,主页,电话,联系地址,发帖标题,发帖内容,回复标题,回复内容。
每天论坛访问量300万左右,更新帖子10万左右。
请给出数据库表结构设计,并结合范式简要说明设计思路。
三、 现有两个文件,
a)数据文件A,格式为:关键词、IP地址、时间,记录条数为1000万左右,该文件是无序排列的。
b)数据文件B是关键词ID到关键词的对应表文件,格式为:ID、关键词,记录条数在100万左右,也是无序排列的。该对应表中的记录是一一对应的,不存在ID或者关键词重复的情况。
要求将数据文件A对应的关键词替换为B中的ID,生成新的数据文件C,数据文件C的格式为:关键词ID、IP地址、时间。
请设计一个程序,实现上述功能,并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G,硬盘足够大。(至少要给出关键算法和设计思路)
第一题
简评
百度的主要业务是搜索,搜索的基本原理如下
1.编写爬虫程序到互联网上抓取网页海量的网页。
2.将抓取来的网页通过抽取,以一定的格式保存在能快速检索的文件系统中。
3.把用户输入的字符串进行拆分成关键字去文件系统中查询并返回结果。
由以上3点可见,字符串的分析,抽取在搜索引擎中的地位是何等重要。
因此,百度的笔试面试题中,出现这样的题就变得理所当然了。
以下是该题的java实现,代码如下:
import java.net.*;
import java.io.*;
import java.util.*;
/**
* @author tzy
* 在j2sdk1.4.2下测试通过
*/
public class FileNameStat
{
private String srcPath;//要统计的文件路径
private Map statMap;//用于统计的map
public FileNameStat(String srcPath)
{
this.srcPath=srcPath;
statMap=new TreeMap();
}
/*获得要统计的URL的文件名*/
public String getFileName(String urlString)
{
URL url=null;
String filePath=null;
String fileName=null;
try
{
url=new URL(urlString);
filePath=url.getPath();
int index=0;
if ((index=filePath.lastIndexOf("/"))!=-1)
{
fileName=filePath.substring(index+1);
}
else
{
fileName="";
}
}
catch(MalformedURLException e)
{
}
return fileName;
}
/*统计指定文件名的个数*/
public void stat(String filename)
{
Integer count=null;
if(statMap.get(filename)!=null)
{
count=(Integer)statMap.get(filename);
count=new Integer(count.intValue()+1);
}
else
{
count=new Integer(1);
}
statMap.put(filename,count);
}
/*统计的主方法*/
public void start() throws FileNotFoundException,IOException
{
BufferedReader bfin=new BufferedReader(new FileReader(this.srcPath));
String temp=null;
while((temp=bfin.readLine())!=null)
{
stat(getFileName(temp));
}
}
/*输出统计结果*/
public void result()
{
Iterator it=statMap.entrySet().iterator();
while(it.hasNext())
{
Map.Entry entry=(Map.Entry)(it.next());
System.out.println((entry.getKey().equals("")?"空文件名":entry.getKey()) + "的个数是" + entry.getValue());
}
}
public static void main(String[] args) throws Exception
{
FileNameStat fns=new FileNameStat("src.txt");//指定成待统计文件
fns.start();
fns.result();
}
}
|
第二题
简评:
这道题也与百度的业务有关,百度现在除了搜索外,还有贴吧,知道,博客等重要产品。
同时也在积极的探索社区化,包括前不久宣布进军电子商务领域,搜索之外的这些产品,
其主要功能的实现主要是对数据库的操作。
因此,想进入百度,也需要对数据库有一定的认识。
实现思路及数据库设计:
1,该论坛主要有两个实体对象,用户和帖子;对于帖子对象,有一个问题:回复的帖子是否应该跟主题帖子存放在同一个表里?
考虑到每天更新10万帖子,说明帖子数比较多,为了方便主题的呈现,我一般都把主题贴和回帖分别放在不同的表中,把主题贴和回帖分开可以提高查询效率(300万的访问量每天)。
2,按照1中的思路,该论坛由两个对象(用户和帖子)变成三个实体对象,分别是用户,主题帖子,回复帖子;
3,上述三个对象存在三个关系,分别是:
用户--主题帖,一个用户可以发0个或多个帖子,一个帖子对应一个用户(一对多关系),
主题帖--回复帖:一个主题有0个或多个回复帖子,一个回复帖子对应一个主题(一对多关系);
用户--回复贴:一个用户可以回0个或多个帖,一个帖子对应一个用户(一对多关系)。
还存在对回复贴的回复,这个考虑用fatherId来表示。
4,由于三个关系 “用户--主题帖,主题帖--回复帖,用户--回复贴”
都是一对多关系,根据表设计一般原则,可以将这两个关系独立建立表,也可以不另外建表而将一对多的关系体现在实体表中;然而,表间的连接查询是非常耗资源
的,所以应尽量减少表间连接,那么对三个关系不应该分别建表,而是把用户的id作为主题表和回帖表的外键,把主题贴id作为回帖表的外键。
5,鉴于以上考虑,该论坛的三个表如下所示
表名:t_user_info (用户信息表)
字段名 |
类型 |
缺省值 |
中文含义 |
约束 |
备注 |
id |
Int |
|
用户编号 |
PRI |
Auto_increment |
Name |
Varchar(30) |
|
用户名 |
|
|
Email |
Varchar(50) |
|
|
|
|
Phone |
Varchar(30) |
|
|
|
|
Addr |
Varchar(200) |
|
|
|
|
其他字段略,根据需要添加
表名:main_content_info (主题帖信息表)
字段名 |
类型 |
缺省值 |
中文含义 |
约束 |
备注 |
id |
Int |
|
贴编号 |
PRI |
Auto_increment |
Title |
Varchar(200) |
|
发帖标题 |
|
|
Content |
Text |
|
发帖内容 |
|
|
UserID |
Int |
|
用户编号 |
|
外键 |
其他字段略,根据需要添加
表名:sub_content_info (回复贴信息表)
字段名 |
类型 |
缺省值 |
中文含义 |
约束 |
备注 |
id |
Int |
|
贴编号 |
PRI |
Auto_increment |
Title |
Varchar(200) |
|
发帖标题 |
|
|
Content |
Text |
|
发帖内容 |
|
|
UserID |
Int |
|
用户编号 |
|
外键 |
FatherID |
Int |
|
父编号 |
|
|
MainID |
Int |
|
主题帖编号 |
|
外键 |
其他字段略,根据需要添加
6,符合范式分析:
上述表中每个字段不可再分,首先满足1NF;
然后数据库表中的每个实例或行都是可以被惟一地区分(id),不存在部分依赖,因此满足2NF;
t_user_info (用户信息表)和main_content_info (主题帖信息表)不存在任何传递依赖,至少属于BCNF;
但是sub_content_info (回复贴信息表)不满足3NF,因为存在如下传递依赖:id-->FatherID,FatherID-->MainID。
范式并不是越高越好,sub_content_info表只满足2NF却更有效率,也是当今论坛较主流的设计。
第三题
简评:
如何对海量数据进行快速检索,这是搜索引擎的必需考虑的问题。这又涉及到数据结构和算法。
因此,要想进入百度,就必须熟悉一些基本的算法和数据结构。
思路及解决方案如下:
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之间(与关键词集合有关),因此本方法完全可行。
posted on 2007-12-13 20:07
wqwqwqwqwq 阅读(1734)
评论(0) 编辑 收藏