PHP实现支持中文的字典树

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

1. 辅助函数，字符串拆分函数，这个是借鉴了网上的函数，支持中文utf-8的字符串

[php] view plaincopy

1. /* 
2.     将可能含有中文的字符串进行拆分，如 “我爱北京” 转换成 array("我","爱","北","京") 
3. */  
4. function str_split_utf8($str)  
5. {  
6.     $split = 1;  
7.     $array = array();  
8.     for ($i = 0; $i < strlen($str);) {  
9.         $value = ord($str[$i]);  
10.         if ($value > 127) {  
11.             if ($value >= 192 && $value <= 223) {  
12.                 $split = 2;  
13.             } elseif ($value >= 224 && $value <= 239) {  
14.                 $split = 3;  
15.             } elseif ($value >= 240 && $value <= 247) {  
16.                 $split = 4;  
17.             }  
18.         } else {  
19.             $split = 1;  
20.         }  
21.         $key = null;  
22.         for ($j = 0; $j < $split; $j++, $i++) {  
23.             $key .= $str[$i];  
24.         }  
25.         array_push($array, $key);  
26.     }  
27.     return $array;  
28. }  

数组切分函数

[php] view plaincopy

1. /* 
2.     切分数组 
3. */  
4. function retSubArray($array,$start,$end)  
5. {  
6.     $retArray = array();  
7.     $count = 0;  
8.     foreach($array as $v)  
9.     {  
10.         if($count >= $end) break;   
11.         if($count >= $start )  
12.         {  
13.             $retArray[] = $v;  
14.         }  
15.         $count++;  
16.     }  
17.     return $retArray;  
18. }  

2. 字典树构建函数

[php] view plaincopy

1. /* 
2.     递归的将str_split_utf8生成的数组查到字典树中 
3. */  
4. function mkMapSub($wordArray, &$mapSubArray)  
5. {  
6.     $length = count($wordArray);  
7.     if ($length > 0) {  
8.         // 取出第一个字  
9.         $word = $wordArray[0];  
10.         // 查看字典树中是否匹配第一个字,没有的话就插入这个字  
11.         if (!isset($mapSubArray[$wordArray[0]])) {  
12.             $mapSubArray[$wordArray[0]] = array();  
13.         }  
14.         if($length == 1)  
15.         {// 只有一个字，就插入一个结束标识  
16.             $mapSubArray[$wordArray[0] . "end"] = 1;  
17.         }  
18.         // 已经插入的字出栈  
19.         array_shift($wordArray);  
20.         // 递归插入  
21.         mkMapSub($wordArray, $mapSubArray[$word]);  
22.     }  
23. }  

3. 查找函数

全词匹配

[php] view plaincopy

1. /* 
2.     递归查询词是否在字典树中 
3. */  
4. function wordInMap($str, &$map)  
5. {  
6.     if (count($str) == 1) {  
7.         // 一个字的情况  
8.         if (isset($map[$str[0]]) && $map[$str[0]] == array())   
9.         {   
10.             return true;  
11.         } else {    
12.         if( isset($map[$str[0] . "end"]) && $map[$str[0] . "end"] == 1 )  
13.         {    
14.             return true;  
15.         }  
16.             return false;  
17.         }  
18.     } else {  
19.         // 按字递归查找  
20.         $word = array_shift($str);  
21.         if (isset($map[$word])) {   
22.             return wordInMap($str, $map[$word]);  
23.         } else {  
24.             return false;  
25.         }  
26.     }  
27. }  

句子切词查找

[php] view plaincopy

1. /* 
2.     查找一个句子中是否在字典树中有词命中 
3. */  
4. function longStrInMap($str, &$map)  
5. {  
6.     if(wordInMap($str,$map))  
7.     {  
8.         return array($str);  
9.     }  
10.     $strArray = str_split_utf8($str);  
11.     $length = count($strArray);  
12.     $hasList = array();  
13.     for ($index = 0; $index < $length; $index++) {  
14.         $word = $strArray[$index];  
15.         if (isset($map[$word]))   
16.         {  
17.             //尝试测试子数组  
18.             for ($subIndex = $index; $subIndex <= $length; $subIndex++)  
19.             {  
20.                 $subStr = retSubArray($strArray,$index,$subIndex);   
21.                 if(wordInMap($subStr,$map))  
22.                 {  
23.                     $hasList[] = $subStr;  
24.                 }  
25.             }  
26.         }  
27.     }   
28.     $retArray = array();  
29.     foreach($hasList as $v)  
30.     {  
31.         $retArray[] = implode("",$v);  
32.     }  
33.     return $retArray;  
34. }  

4. 入口函数

[php] view plaincopy

1. /* 
2.     从源文件中读取数据 
3. */  
4. $words = array();  
5. $sAllMapDatas = file_get_contents("maplist");  
6. $aAllMapDatas = explode("\n",$sAllMapDatas);  
7. foreach($aAllMapDatas as $vDatas)  
8. {  
9.     $words[] = trim($vDatas);  
10. }  
11.   
12. // 根据词表建立map  
13. $map = array();  
14. foreach ($words as $vWord) {    
15.       $wordArray = str_split_utf8($vWord);  
16.         mkMapSub($wordArray, $map);    
17. }