亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Trie Tree and some DS&Athm sample

系統 1574 0
Trie樹的定義(轉)

Trie樹是一棵度 m ≥ 2 的樹,它的每一層分支不是靠整個關鍵碼的值來確定,而是由關鍵碼的一個分量來確定。

如下圖所示Trie樹,關鍵碼由英文字母組成。它包括兩類結點:元素結點和分支結點。元素結點包含整個key數據;分支結點有27個指針,其中有一個空白字符‘b’,用來終結關鍵碼;其它用來標識‘a’, ‘b’,..., ‘z’等26個英文字母。

Trie Tree and some DS&Athm sample

在第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 Tree and some DS&Athm sample

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

考慮刪除 bluejay。刪除之后在標記為δ3 的子Trie樹中只剩下一個關鍵碼,這表明可以刪去結點δ3 ,同時結點 ρ 向上移動一層。對結點δ2 和δ1 可以做同樣的工作,最后到達結點б。因為以б 為根的子Trie樹中有多個關鍵碼,所以它不能刪去,令該結點link[‘l’] = ρ即可。

為便于Trie樹的刪除, 在每個分支結點中設置了一個 num 數據成員,它記載了結點中子女的數目。

Trie ,又稱 單詞查找樹 ,是一種 形結構,用于保存大量的 字符串 。它的優點是:利用字符串的公共 前綴 來節約存儲空間。

性質

它有3個基本性質:

  1. 根節點 不包含 字符 ,除根節點外每一個節點都只包含一個 字符
  2. 根節點 到某一 節點 路徑 上經過的 字符 連接起來,為該 節點 對應的 字符串
  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 實現,代碼如下:

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

/**/ /* *
*@authortzy
*在j2sdk1.4.2下測試通過
*/

public class FileNameStat
... {
private StringsrcPath; // 要統計的文件路徑
private MapstatMap; // 用于統計的map

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


/**/ /* 獲得要統計的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;
}


/**/ /* 統計指定文件名的個數 */
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);
}


/**/ /* 統計的主方法 */
public void start()throwsFileNotFoundException,IOException
... {
BufferedReaderbfin
= new BufferedReader( new FileReader( this .srcPath));
Stringtemp
= null ;
while ((temp = bfin.readLine()) != null )
... {
stat(getFileName(temp));
}

}


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

}


public static void main(String[]args)throwsException
... {
FileNameStatfns
= 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 曲強 Nicky 閱讀(689) 評論(0) 編輯 收藏

Trie Tree and some DS&Athm sample


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产亚洲精彩视频 | 日韩中文字幕免费在线观看 | 国内精品手机在线观看视频 | 久久亚洲精品tv | 精品国产一区二区三区香蕉事 | 国产成人丝袜网站在线观看 | 一区二区三区免费精品视频 | 神马影院我不卡手机版 | 国产99免费视频 | 成人国产一区二区三区精品 | 精品偷拍模特露出丝袜在线 | 人人夜| 最近中文2019视频在线 | 久久综合视频网站 | 91社区视频 | 欧美精彩狠狠色丁香婷婷 | 日韩欧美国产精品第一页不卡 | 四虎1515hh免费大炮社区 | 日日狠狠太爽爽 | 久久欧美精品欧美九久欧美 | 今天的恋爱未删减在线观看 | 成年女人视频播放免费观看 | 奇米狠狠色 | 一区二区三区国产精品 | 久草午夜 | 香蕉网久久 | 伊人一级 | 日韩精品免费一区二区 | 91麻精品国产91久久久久 | 狠狠2020| 日本精品久久久久中文字幕 1 | 奇米第四色视频 | 成人免费视频一区 | 日日摸夜夜添夜夜添毛片 | 97福利视频 | 欧美亚洲国产精品久久 | 亚洲系列中文字幕一区二区 | 欧美午夜精品久久久久免费视 | 爱爱视频免费网址 | 亚洲欧美国产五月天综合 | 在线视频 国产交换 |