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

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

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

Trie樹(shù)的類(lèi)定義：

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

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

class TrieNode { //Trie樹(shù)結(jié)點(diǎn)類(lèi)定義
friend class Trie;
protected:
enum { branch, element } NodeType; //結(jié)點(diǎn)類(lèi)型
union NodeType { //根據(jù)結(jié)點(diǎn)類(lèi)型的兩種結(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ù)對(duì)象指針
} elem;
}
}

class Trie { //Trie樹(shù)的類(lèi)定義
private:
TrieNode *root, *current;
public:
RecordNode* Search ( const keyType & );
int Insert ( const KeyType & );
int Delete ( const KeyType & );
}

10.3.2 Trie樹(shù)的搜索

為了在Trie樹(shù)上進(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樹(shù)的搜索算法：

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ù)的搜索算法在最壞情況下搜索的時(shí)間代價(jià)是 O(l)。其中, l 是Trie樹(shù)的層數(shù)(包括分支結(jié)點(diǎn)和元素結(jié)點(diǎn)在內(nèi))。

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

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

10.3.3 在Trie樹(shù)上的插入和刪除

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

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

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

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

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

Trie ,又稱(chēng) 單詞查找樹(shù) ,是一種 樹(shù) 形結(jié)構(gòu)，用于保存大量的 字符串 。它的優(yōu)點(diǎn)是：利用字符串的公共 前綴 來(lái)節(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)過(guò)的 字符 連接起來(lái)，為該 節(jié)點(diǎn) 對(duì)應(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é) （不包括 指針 占用的空間）

問(wèn)題：

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

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

　　b) 部分URL可能沒(méi)有文件名，例如http://www.abc.com/，這類(lèi)統(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è)簡(jiǎn)單的論壇系統(tǒng)，以數(shù)據(jù)庫(kù)儲(chǔ)存如下數(shù)據(jù)：

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

　　每天論壇訪(fǎng)問(wèn)量300萬(wàn)左右，更新帖子10萬(wàn)左右。

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

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

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

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

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

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

    
      第一題
    
  

    
      　　簡(jiǎn)評(píng)
    
  

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

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

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

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

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

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

      
    
  

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

importjava.net. * ;
importjava.io. * ;
importjava.util. * ;

/**/ /* *
*@authortzy
*在j2sdk1.4.2下測(cè)試通過(guò)
*/
public class FileNameStat
... {
private StringsrcPath; // 要統(tǒng)計(jì)的文件路徑
private MapstatMap; // 用于統(tǒng)計(jì)的map

public FileNameStat(StringsrcPath)
... {
this .srcPath = srcPath;
statMap = new TreeMap();
}

/**/ /* 獲得要統(tǒng)計(jì)的URL的文件名 */
public StringgetFileName(StringurlString)
... {
URLurl = null ;
StringfilePath = null ;
StringfileName = 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 (MalformedURLExceptione)
... {
}
return fileName;
}

/**/ /* 統(tǒng)計(jì)指定文件名的個(gè)數(shù) */
public void stat(Stringfilename)
... {
Integercount = 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()throwsFileNotFoundException,IOException
... {
BufferedReaderbfin = new BufferedReader( new FileReader( this .srcPath));
Stringtemp = null ;
while ((temp = bfin.readLine()) != null )
... {
stat(getFileName(temp));
}
}

/**/ /* 輸出統(tǒng)計(jì)結(jié)果 */
public void result()
... {
Iteratorit = statMap.entrySet().iterator();
while (it.hasNext())
... {
Map.Entryentry = (Map.Entry)(it.next());
System. out .println((entry.getKey().equals( "" ) ? " 空文件名 " :entry.getKey()) + " 的個(gè)數(shù)是 " + entry.getValue());
}
}

public static void main(String[]args)throwsException
... {
FileNameStatfns = 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)主要是對(duì)數(shù)據(jù)庫(kù)的操作。
    

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

      
        

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

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

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

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

Trie Tree and some DS&Athm sample