站長資訊網
算法簡介
將關鍵詞構造成一顆樹，每個字都是一個節點。
遍歷需要過濾的語句，將語句的每個字都去樹中查找，看看是否存在。
實現難點
構造一棵樹簡單，關鍵點是php中遍歷字符串需要自己正確的得到單個字符的長度。
簡單遍歷字符串的方法如下：
$strLen = mb_strlen($str); for ($i = 0; $i < $strLen; $i++) { echo mb_substr($str, $i, 1, "utf8"),PHP_EOL; }
登錄后復制
該方法是利用mb_*系列函數來正確截取每個字符，處理大量字符串時速度非常慢，我猜測是：mb_substr每截取一個字符，都要計算該字符串之前，有多少個字符。
正確的遍歷字符串的方式是按utf8的編碼規律來截取字符串，具體請看下文。
算法實現
<?php /** * 非法關鍵詞檢查 */ class SensitiveWords { protected $tree = null; protected $callIsNumeric = true; /** * 非法詞匯列表，一個非法詞匯占用一行 */ public function __construct($path = __DIR__ . '/sensitiveWords.txt') { $this->tree = new WordNode(); $file = fopen($path, "r"); while (!feof($file)) { $words = trim(fgets($file)); if ($words == '') { continue; } //存在純數字的非法詞匯 if (is_numeric($words)) { $this->callIsNumeric = false; } $this->setTree($words); } fclose($file); } protected function setTree($words) { $array = $this->strToArr($words); $tree = $this->tree; $l = count($array) - 1; foreach ($array as $k => $item) { $tree = $tree->getChildAlways($item); if ($l == $k) { $tree->end = true; } } } /** * 返回包含的非法詞匯 * @param string $str * @return array */ public function check($str) { //先壓縮字符串 $str = trim(str_replace([' ', "n", "r"], ['', '', ''], $str)); $ret = []; loop: $strLen = strlen($str); if ($strLen === 0) { return array_unique($ret); } //非法詞匯中沒有純數字的非法詞匯，待檢測字符串又是純數字的，則跳過不再檢查 if ($this->callIsNumeric && is_numeric($str)) { return array_unique($ret); } //挨個字符進行判斷 $tree = $this->tree; $words = ''; for ($i = 0; $i < $strLen; $i++) { //unicode范圍 --> ord 范圍 //一字節 0-127 --> 0 - 127 //二字節 128-2047 --> 194 - 223 //三字節 2048-65535 --> 224 - 239 //四字節 65536-1114111 --> 240 - 244 //@see http://shouce.jb51.net/gopl-zh/ch3/ch3-05.html $ord = ord($str[$i]); if ($ord <= 127) { $word = $str[$i]; } elseif ($ord <= 223) { $word = $str[$i] . $str[$i + 1]; $i += 1; } elseif ($ord <= 239) { $word = $str[$i] . $str[$i + 1] . $str[$i + 2]; $i += 2; } elseif ($ord <= 244) { //四字節 $word = $str[$i] . $str[$i + 1] . $str[$i + 2] . $str[$i + 3]; $i += 3; } else { //五字節php都溢出了 //Parse error: Invalid UTF-8 codepoint escape sequence: Codepoint too large continue; } //判斷當前字符 $tree = $tree->getChild($word); if (is_null($tree)) { //當前字不存在，則截取后再次循環 $str = substr($str, $i + 1); goto loop; } else { $words .= $word; if ($tree->end) { $ret[] = $words; } } } return array_unique($ret); } protected function strToArr($str) { $array = []; $strLen = mb_strlen($str); for ($i = 0; $i < $strLen; $i++) { $array[] = mb_substr($str, $i, 1, "utf8"); } return $array; } } /** * 單個字符的節點 */ class WordNode { //是否為非法詞匯末級節點 public $end = false; //子節點 protected $child = []; /** * @param string $word * @return WordNode */ public function getChildAlways($word) { if (!isset($this->child[$word])) { $this->child[$word] = new self(); } return $this->child[$word]; } /** * @param string $word * @return WordNode|null */ public function getChild($word) { if ($word === '') { return null; } if (isset($this->child[$word])) { return $this->child[$word]; } return null; } }
登錄后復制
推薦學習：《PHP視頻教程》
php入門到就業線上直播課：立即學習
全程直播 + 實戰授課 + 邊學 + 邊練 + 邊輔導
