PHP字典樹(shù)(Trie樹(shù))定義與實(shí)現(xiàn)方法示例
本文實(shí)例講述了PHP字典樹(shù)(Trie樹(shù))定義與實(shí)現(xiàn)方法。分享給大家供大家參考,具體如下:
Trie樹(shù)的概念(百度的解釋?zhuān)鹤值錁?shù)又稱(chēng)單詞查找樹(shù),Trie樹(shù),是一種樹(shù)形結(jié)構(gòu),是一種哈希樹(shù)的變種。典型應(yīng)用是用于統(tǒng)計(jì),排序和保存大量的字符串(但不僅限于字符串),所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是:利用字符串的公共前綴來(lái)減少查詢(xún)時(shí)間,最大限度地減少無(wú)謂的字符串比較,查詢(xún)效率比哈希樹(shù)高。
我的理解是用來(lái)做字符串搜索的,每個(gè)節(jié)點(diǎn)只包含一個(gè)字符,比如錄入單詞"world",則樹(shù)的結(jié)構(gòu)是:
這時(shí)再錄入單詞"worab",則樹(shù)的結(jié)構(gòu)為:
所以每個(gè)節(jié)點(diǎn)必須還要一個(gè)字段is_end標(biāo)識(shí)是否為結(jié)束單詞。比如用戶(hù)輸入wor,搜索所有wor開(kāi)頭的單詞,假設(shè)現(xiàn)在有一個(gè)單詞就是wor,從"w"開(kāi)始檢索,當(dāng)檢索到"r"的時(shí)候需要判斷"r"節(jié)點(diǎn)的is_end為true,則把wor加入到結(jié)果列表,然后繼續(xù)往下面檢索。
PHP實(shí)現(xiàn)代碼:
<?php class Node{ public $value; // 節(jié)點(diǎn)值 public $is_end = false; // 是否為結(jié)束--是否為某個(gè)單詞的結(jié)束節(jié)點(diǎn) public $childNode = array(); // 子節(jié)點(diǎn) /* 添加孩子節(jié)點(diǎn)--注意:可以不為引用函數(shù),因?yàn)镻HP對(duì)象賦值本身就是引用賦值 */ public function &addChildNode($value, $is_end = false){ $node = $this->searchChildNode($value); if(empty($node)){ // 不存在節(jié)點(diǎn),添加為子節(jié)點(diǎn) $node = new Node(); $node->value = $value; $this->childNode[] = $node; } $node->is_end = $is_end; return $node; } /* 查詢(xún)子節(jié)點(diǎn) */ public function searchChildNode($value){ foreach ($this->childNode as $k => $v) { if($v->value == $value){ // 存在節(jié)點(diǎn),返回該節(jié)點(diǎn) return $this->childNode[$k]; } } return false; } } /* 添加字符串 */ function addString(&$head, $str){ $node = null; for ($i=0; $i < strlen($str); $i++) { if($str[$i] != ' '){ $is_end = $i != (strlen($str) - 1) ? false : true; if($i == 0){ $node = $head->addChildNode($str[$i], $is_end); }else{ $node = $node->addChildNode($str[$i], $is_end); } } } } /* 獲取所有字符串--遞歸 */ function getChildString($node, $str_array = array(), $str = ''){ if($node->is_end == true){ $str_array[] = $str; } if(empty($node->childNode)){ return $str_array; }else{ foreach ($node->childNode as $k => $v) { $str_array = getChildString($v, $str_array, $str . $v->value); } return $str_array; } } /* 搜索 */ function searchString($node, $str){ for ($i=0; $i < strlen($str); $i++) { if($str[$i] != ' '){ $node = $node->searchChildNode($str[$i]); // print_r($node); if(empty($node)){ // 不存在返回空 return false; } } } return getChildString($node); } /* 調(diào)用測(cè)試開(kāi)始 */ $head = new Node; // 樹(shù)的head // 添加單詞 addString($head, 'hewol'); addString($head, 'hemy'); addString($head, 'heml'); addString($head, 'you'); addString($head, 'yo'); // 獲取所有單詞 $str_array = getChildString($head); // 搜索 $search_array = searchString($head, 'hem'); // 循環(huán)打印所有搜索結(jié)果 foreach ($search_array as $key => $value) { echo 'hem' . $value . '<br>'; // 輸出帶上搜索前綴 }
更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題:《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《PHP基本語(yǔ)法入門(mén)教程》、《php面向?qū)ο蟪绦蛟O(shè)計(jì)入門(mén)教程》、《php字符串(string)用法總結(jié)》、《php+mysql數(shù)據(jù)庫(kù)操作入門(mén)教程》及《php常見(jiàn)數(shù)據(jù)庫(kù)操作技巧匯總》
希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。
- php遍歷樹(shù)的常用方法匯總
- PHP實(shí)現(xiàn)二叉樹(shù)的深度優(yōu)先與廣度優(yōu)先遍歷方法
- PHP生成樹(shù)的方法
- PHP遞歸實(shí)現(xiàn)層級(jí)樹(shù)狀展開(kāi)
- php FLEA中二叉樹(shù)數(shù)組的遍歷輸出
- PHP實(shí)現(xiàn)的線索二叉樹(shù)及二叉樹(shù)遍歷方法詳解
- PHP Class&Object -- 解析PHP實(shí)現(xiàn)二叉樹(shù)
- PHP樹(shù)的深度編歷生成迷宮及A*自動(dòng)尋路算法實(shí)例分析
- PHP樹(shù)-不需要遞歸的實(shí)現(xiàn)方法
- PHP Class&Object -- PHP 自排序二叉樹(shù)的深入解析
- php實(shí)現(xiàn)的二叉樹(shù)遍歷算法示例
- PHP構(gòu)造二叉樹(shù)算法示例
相關(guān)文章
PHP has encountered an Access Violation 錯(cuò)誤的解決方法
一般是因?yàn)閑accelerator的問(wèn)題,windows下容易出現(xiàn)這個(gè)問(wèn)題。2010-01-01Thinkphp框架開(kāi)發(fā)移動(dòng)端接口(2)
這篇文章主要介紹了thinkphp框架開(kāi)發(fā)移動(dòng)端接口的第2種方法,實(shí)現(xiàn)移動(dòng)端訪問(wèn)自動(dòng)切換移動(dòng)主題模板,從而實(shí)現(xiàn)偽app訪問(wèn),感興趣的小伙伴們可以參考一下2016-08-08php程序之die調(diào)試法 快速解決錯(cuò)誤
經(jīng)??吹接谐跞隤HP道朋友對(duì)于php程序出現(xiàn)問(wèn)題素手無(wú)策的情況2009-09-09PHP圖像處理類(lèi)庫(kù)MagickWand用法實(shí)例分析
這篇文章主要介紹了PHP圖像處理類(lèi)庫(kù)MagickWand用法,較為詳細(xì)的分析了php中圖像處類(lèi)庫(kù)MagickWand的相關(guān)使用技巧,需要的朋友可以參考下2015-05-05php設(shè)計(jì)模式 State (狀態(tài)模式)
允許一個(gè)對(duì)象在其內(nèi)部狀態(tài)改變時(shí)改變它的行為,對(duì)象看起來(lái)似乎修改了它所屬的類(lèi)2011-06-06PHP實(shí)現(xiàn)適用于文件內(nèi)容操作的分頁(yè)類(lèi)
這篇文章主要為大家詳細(xì)介紹了PHP實(shí)現(xiàn)適用于文件內(nèi)容操作的分頁(yè)類(lèi),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2016-06-06