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 實現,代碼如下:



























































































更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
