在第0層，所有的關(guān)鍵碼根據(jù)它們第0位字符, 被劃分到互不相交的27個(gè)類中。

因此，root→brch.link[i] 指向一棵子Trie樹，該子Trie樹上所包含的所有關(guān)鍵碼都是以第 i 個(gè)英文字母開頭。

若某一關(guān)鍵碼第 j 位字母在英文字母表中順序?yàn)?i ( i = 0, 1, ?, 26 ), 則它在Trie樹的第 j 層分支結(jié)點(diǎn)中從第 i 個(gè)指針向下找第 j+1 位字母所在結(jié)點(diǎn)。當(dāng)一棵子Trie樹上只有一個(gè)關(guān)鍵碼時(shí)，就由一個(gè)元素結(jié)點(diǎn)來代替。在這個(gè)結(jié)點(diǎn)中包含有關(guān)鍵碼，以及其它相關(guān)的信息，如對應(yīng)數(shù)據(jù)對象的存放 地址等。

Trie樹的類定義：

const int MaxKeySize = 25; //關(guān)鍵碼最大位數(shù)

typedef struct { //關(guān)鍵碼類型
char ch[MaxKeySize]; //關(guān)鍵碼存放數(shù)組
int currentSize; //關(guān)鍵碼當(dāng)前位數(shù)
} KeyType;

class TrieNode { //Trie樹結(jié)點(diǎn)類定義
friend class Trie;
protected:
enum { branch, element } NodeType; //結(jié)點(diǎn)類型
union NodeType { //根據(jù)結(jié)點(diǎn)類型的兩種結(jié)構(gòu)
struct { //分支結(jié)點(diǎn)
int num; //本結(jié)點(diǎn)關(guān)鍵碼個(gè)數(shù)
TrieNode *link[27]; //指針數(shù)組
} brch;
struct { //元素結(jié)點(diǎn)
KeyType key; //關(guān)鍵碼
recordNode *recptr; //指向數(shù)據(jù)對象指針
} 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樹上進(jìn)行搜索，要求把關(guān)鍵碼分解成一些字符元素, 并根據(jù)這些字符向下進(jìn)行分支。

函數(shù) Search 設(shè)定 current = NULL, 表示不指示任何一個(gè)分支結(jié)點(diǎn), 如果 current 指向一個(gè)元素結(jié)點(diǎn) elem，則 current→elem.key 是 current 所指結(jié)點(diǎn)中的關(guān)鍵碼。

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;
}

經(jīng)驗(yàn)證，Trie樹的搜索算法在最壞情況下搜索的時(shí)間代價(jià)是 O(l)。其中, l 是Trie樹的層數(shù)(包括分支結(jié)點(diǎn)和元素結(jié)點(diǎn)在內(nèi))。

在用作索引時(shí)，Trie樹的所有結(jié)點(diǎn)都駐留在磁盤上。搜索時(shí)最多做 l 次磁盤存取。

當(dāng)結(jié)點(diǎn)駐留在磁盤上時(shí)，不能使用C++的指針 (pointer) 類型, 因?yàn)镃++不允許指針的輸入 / 輸出。在結(jié)點(diǎn)中的 link 指針可改用整型(integer) 實(shí)現(xiàn)。

10.3.3 在Trie樹上的插入和刪除

示例：插入關(guān)鍵碼bobwhite和bluejay。
a. 插入 x = bobwhite 時(shí)，首先搜索Trie樹尋找 bobwhite 所在的結(jié)點(diǎn)。
b. 如果找到結(jié)點(diǎn), 并發(fā)現(xiàn)該結(jié)點(diǎn)的 link[‘o’] = NULL。x不在Trie樹中, 可以在該處插入。插入結(jié)果參看圖。
c. 插入 x = bluejay時(shí)，用Trie樹搜索算法可找到包含有 bluebird 的元素結(jié)點(diǎn)，關(guān)鍵碼bluebird 和 bluejay 是兩個(gè)不同的值，它們在第5個(gè)字母處不匹配。從 Trie樹沿搜索路徑，在第4層分支。插入結(jié)果參看圖。

在Trie樹上插入bobwhite和bluejay后的結(jié)果 ：

示例：考慮在上圖所示Trie樹中刪除bobwhite。此時(shí)，只要將該結(jié)點(diǎn)link[‘o’]置為0 (NULL)即可，Trie樹的其它部分不需要改變。

考慮刪除 bluejay。刪除之后在標(biāo)記為δ3 的子Trie樹中只剩下一個(gè)關(guān)鍵碼，這表明可以刪去結(jié)點(diǎn)δ3 ，同時(shí)結(jié)點(diǎn) ρ 向上移動(dòng)一層。對結(jié)點(diǎn)δ2 和δ1 可以做同樣的工作，最后到達(dá)結(jié)點(diǎn)б。因?yàn)橐鸳? 為根的子Trie樹中有多個(gè)關(guān)鍵碼，所以它不能刪去，令該結(jié)點(diǎn)link[‘l’] = ρ即可。

為便于Trie樹的刪除, 在每個(gè)分支結(jié)點(diǎn)中設(shè)置了一個(gè) num 數(shù)據(jù)成員，它記載了結(jié)點(diǎn)中子女的數(shù)目。

Trie,又稱單詞查找樹,是一種樹形結(jié)構(gòu)，用于保存大量的字符串。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來節(jié)約存儲(chǔ)空間。

性質(zhì)

它有3個(gè)基本性質(zhì)：

1. 根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。
2. 從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對應(yīng)的字符串。
3. 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。

例子

這是一個(gè)Trie結(jié)構(gòu)的例子：

在這個(gè)Trie結(jié)構(gòu)中，保存了t、to、te、tea、ten、i、in、inn這8個(gè)字符串，僅占用8個(gè)字節(jié)（不包括指針占用的空間）

問題：

　　一、 一個(gè)文本文件有多行，每行為一個(gè)URL。請編寫代碼，統(tǒng)計(jì)出URL中的文件名及出現(xiàn)次數(shù)。

　　a) 文件名不包括域名、路徑和URL參數(shù)，例如http://www.rs.com/n.op/q/rs?id=1中的文件名是rs。

　　b) 部分URL可能沒有文件名，例如http://www.abc.com/，這類統(tǒng)計(jì)為“空文件名”。

　　c) 出現(xiàn)在不同URL中的相同文件名視為同一文件名，例如http://www.ceshi.com/hi.php和ftp://ftp.cdef.com/hi.php為同一文件名

　　文件內(nèi)容示例如下：

　　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/

　　二、 一個(gè)簡單的論壇系統(tǒng)，以數(shù)據(jù)庫儲(chǔ)存如下數(shù)據(jù)：

　　用戶名，email，主頁，電話，聯(lián)系地址，發(fā)帖標(biāo)題，發(fā)帖內(nèi)容，回復(fù)標(biāo)題，回復(fù)內(nèi)容。

　　每天論壇訪問量300萬左右，更新帖子10萬左右。

　　請給出數(shù)據(jù)庫表結(jié)構(gòu)設(shè)計(jì)，并結(jié)合范式簡要說明設(shè)計(jì)思路。

　　三、 現(xiàn)有兩個(gè)文件，

　　a)數(shù)據(jù)文件A，格式為：關(guān)鍵詞、IP地址、時(shí)間，記錄條數(shù)為1000萬左右，該文件是無序排列的。

　　b)數(shù)據(jù)文件B是關(guān)鍵詞ID到關(guān)鍵詞的對應(yīng)表文件，格式為：ID、關(guān)鍵詞，記錄條數(shù)在100萬左右，也是無序排列的。該對應(yīng)表中的記錄是一一對應(yīng)的，不存在ID或者關(guān)鍵詞重復(fù)的情況。

　　要求將數(shù)據(jù)文件A對應(yīng)的關(guān)鍵詞替換為B中的ID，生成新的數(shù)據(jù)文件C，數(shù)據(jù)文件C的格式為：關(guān)鍵詞ID、IP地址、時(shí)間。

　　請?jiān)O(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)上述功能，并分析時(shí)間復(fù)雜度和空間復(fù)雜度。運(yùn)行程序所使用的服務(wù)器的內(nèi)存為1G，硬盤足夠大。(至少要給出關(guān)鍵算法和設(shè)計(jì)思路)

　第一題

　　簡評(píng)

　　百度的主要業(yè)務(wù)是搜索，搜索的基本原理如下

　　1．編寫爬蟲程序到互聯(lián)網(wǎng)上抓取網(wǎng)頁海量的網(wǎng)頁。

　　2．將抓取來的網(wǎng)頁通過抽取，以一定的格式保存在能快速檢索的文件系統(tǒng)中。

　　3．把用戶輸入的字符串進(jìn)行拆分成關(guān)鍵字去文件系統(tǒng)中查詢并返回結(jié)果。

　　由以上3點(diǎn)可見，字符串的分析，抽取在搜索引擎中的地位是何等重要。

　　因此，百度的筆試面試題中，出現(xiàn)這樣的題就變得理所當(dāng)然了。 

　　以下是該題的java實(shí)現(xiàn)，代碼如下：

import java.net.*; import java.io.*; import java.util.*;   /** * @author tzy * 在j2sdk1.4.2下測試通過 */ public class FileNameStat {         private String srcPath;//要統(tǒng)計(jì)的文件路徑         private Map statMap;//用于統(tǒng)計(jì)的map                 public FileNameStat(String srcPath)         {                this.srcPath=srcPath;                statMap=new TreeMap();         }                 /*獲得要統(tǒng)計(jì)的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;         }                 /*統(tǒng)計(jì)指定文件名的個(gè)數(shù)*/         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);                  }                 /*統(tǒng)計(jì)的主方法*/         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));                }         }                 /*輸出統(tǒng)計(jì)結(jié)果*/         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()) + "的個(gè)數(shù)是" + entry.getValue());                }               }                 public static void main(String[] args) throws Exception         {                FileNameStat fns=new FileNameStat("src.txt");//指定成待統(tǒng)計(jì)文件                fns.start();                fns.result();          } }

　　第二題

　　這道題也與百度的業(yè)務(wù)有關(guān)，百度現(xiàn)在除了搜索外，還有貼吧，知道，博客等重要產(chǎn)品。

　　同時(shí)也在積極的探索社區(qū)化，包括前不久宣布進(jìn)軍電子商務(wù)領(lǐng)域，搜索之外的這些產(chǎn)品，

其主要功能的實(shí)現(xiàn)主要是對數(shù)據(jù)庫的操作。

　　因此，想進(jìn)入百度，也需要對數(shù)據(jù)庫有一定的認(rèn)識(shí)。

 　　實(shí)現(xiàn)思路及數(shù)據(jù)庫設(shè)計(jì)：

其他字段略，根據(jù)需要添加

　　如何對海量數(shù)據(jù)進(jìn)行快速檢索，這是搜索引擎的必需考慮的問題。這又涉及到數(shù)據(jù)結(jié)構(gòu)和算法。

　　因此，要想進(jìn)入百度，就必須熟悉一些基本的算法和數(shù)據(jù)結(jié)構(gòu)。