[轉載]敏感詞過濾，PHP實現的Trie樹

原文地址：http://blog.11034.org/2012-07/trie_in_php.html

?

項目需求，要做敏感詞過濾，對于敏感詞本身就是一個CRUD的模塊很簡單，比較麻煩的就是對各種輸入的敏感詞檢測了。用Trie樹來實現是比較通用的一種辦法吧，之前一直沒機會用過這種數據結構，正好試著寫了一下。

因為用PHP實現，關聯數組用的很舒服。第一個要解決的是字符集的問題，如果在Java中就比較好辦統一的Unicode，在PHP中因為常用 UTF-8字符集，默認有1-4個字節不同的長度來表示一個字符，于是寫了個Util類來將普通的UTF-8字符串轉換成字符數組，每一個元素是一個 UTF-8串形成的字符。這一點比較容易實現的，根據UTF-8字符集的格式而來就好。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

public static function get_chars($utf8_str){ ????$s = $utf8_str; ????$len = strlen($s); ????if($len == 0) return array(); ????$chars = array(); ????for($i = 0;$i < $len;$i++){ ????????$c = $s[$i]; ????????$n = ord($c); ????????if(($n >> 7) == 0){?????? //0xxx xxxx, asci, single ????????????$chars[] = $c; ????????} ????????else if(($n >> 4) == 15){???? //1111 xxxx, first in four char ????????????if($i < $len - 3){ ????????????????$chars[] = $c.$s[$i + 1].$s[$i + 2].$s[$i + 3]; ????????????????$i += 3; ????????????} ????????} ????????else if(($n >> 5) == 7){? //111x xxxx, first in three char ????????????if($i < $len - 2){ ????????????????$chars[] = $c.$s[$i + 1].$s[$i + 2]; ????????????????$i += 2; ????????????} ????????} ????????else if(($n >> 6) == 3){? //11xx xxxx, first in two char ????????????if($i < $len - 1){ ????????????????$chars[] = $c.$s[$i + 1]; ????????????????$i++; ????????????} ????????} ????} ????return $chars; }

?

?

?

字符單位確認以后，就是寫Trie樹了。簡單的算法，從根路徑開始給每個字符建一個關聯數組，當字符串結束的時候，用一個null表示結尾。

刪除一個串，只要找到串中任意一個字符的子元素數量為1，就表示只有這個串了，整個刪除就好了；若子元素數量大于1，則繼續根據字符找下去，直到末尾的null。

查找一個串（完全匹配），一直根據字符找到null為止就表明存在，任一字符不存在就表明串不存在。

驗證一個長串是否含有任一串，這邊算法比較挫，按照每個字符開始都在Trie樹種搜索一遍，走的回頭路比較多，復雜度有O(n * m)，n為長串長度，m為Trie樹深度，不過因為中文Trie樹深度很淺，勉強還過得去（英文字符串深度很長）。

然后因為PHP沒有全局緩存的機制，每次都要從數據庫中讀取全部的敏感詞，然后建立Trie樹再去匹配串的話太麻煩了，采取的辦法是將Trie內部 的關聯數組序列化后直接保存在數據庫中，每次只要讀取這條數據，然后反序列化，Trie樹就回來了。當然進行串的插入和刪除，將更新這個序列化數據。

可改進的地方：

當某一條路徑只有這個串即關聯數組數量為1時，可以壓縮子樹

改進Trie樹為AC自動機，即每個節點都添加一個失敗指針，指向匹配失敗后回到樹的哪個節點，這樣就僅僅是O(n)的復雜度了。建樹的過程比較復雜，對每個插入的串的子串進行處理，運行時查詢的效率非常高

貼代碼：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

class TrieTree{ ?? ????public $tree = array(); ?? ????public function insert($utf8_str){ ????????$chars = &UTF8Util::get_chars($utf8_str); ????????$chars[] = null;??? //串結尾字符 ????????$count = count($chars); ????????$T = &$this->tree; ????????for($i = 0;$i < $count;$i++){ ????????????$c = $chars[$i]; ????????????if(!array_key_exists($c, $T)){ ????????????????$T[$c] = array();?? //插入新字符，關聯數組 ????????????} ????????????$T = &$T[$c]; ????????} ????} ?? ????public function remove($utf8_str){ ????????$chars = &UTF8Util::get_chars($utf8_str); ????????$chars[] = null; ????????if($this->_find($chars)){??? //先保證此串在樹中 ????????????$chars[] = null; ????????????$count = count($chars); ????????????$T = &$this->tree; ????????????for($i = 0;$i < $count;$i++){ ????????????????$c = $chars[$i]; ????????????????if(count($T[$c]) == 1){???? //表明僅有此串 ????????????????????unset($T[$c]); ????????????????????return; ????????????????} ????????????????$T = &$T[$c]; ????????????} ????????} ????} ?? ????private function _find(&$chars){ ????????$count = count($chars); ????????$T = &$this->tree; ????????for($i = 0;$i < $count;$i++){ ????????????$c = $chars[$i]; ????????????if(!array_key_exists($c, $T)){ ????????????????return false; ????????????} ????????????$T = &$T[$c]; ????????} ????????return true; ????} ?? ????public function find($utf8_str){ ????????$chars = &UTF8Util::get_chars($utf8_str); ????????$chars[] = null; ????????return $this->_find($chars); ????} ?? ????public function contain($utf8_str, $do_count = 0){ ????????$chars = &UTF8Util::get_chars($utf8_str); ????????$chars[] = null; ????????$len = count($chars); ????????$Tree = &$this->tree; ????????$count = 0; ????????for($i = 0;$i < $len;$i++){ ????????????$c = $chars[$i]; ????????????if(array_key_exists($c, $Tree)){??? //起始字符匹配 ????????????????$T = &$Tree[$c]; ????????????????for($j = $i + 1;$j < $len;$j++){ ????????????????????$c = $chars[$j]; ????????????????????if(array_key_exists(null, $T)){ ????????????????????????if($do_count){ ????????????????????????????$count++; ????????????????????????} ????????????????????????else{ ????????????????????????????return true; ????????????????????????} ????????????????????} ????????????????????if(!array_key_exists($c, $T)){ ????????????????????????break; ????????????????????} ????????????????????$T = &$T[$c]; ????????????????} ????????????} ????????} ????????if($do_count){ ????????????return $count; ????????} ????????else{ ????????????return false; ????????} ????} ?? ????public function contain_all($str_array){ ????????foreach($str_array as $str){ ????????????if($this->contain($str)){ ????????????????return true; ????????????} ????????} ????????return false; ????} ?? ????public function export(){ ????????return serialize($this->tree); ????} ?? ????public function import($str){ ????????$this->tree = unserialize($str); ????} ?? }

總結

以上是生活随笔為你收集整理的敏感词过滤，PHP实现的Trie树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。