站長資訊網(wǎng)
算法簡介
將關(guān)鍵詞構(gòu)造成一顆樹，每個(gè)字都是一個(gè)節(jié)點(diǎn)。
遍歷需要過濾的語句，將語句的每個(gè)字都去樹中查找，看看是否存在。
實(shí)現(xiàn)難點(diǎn)
構(gòu)造一棵樹簡單，關(guān)鍵點(diǎn)是php中遍歷字符串需要自己正確的得到單個(gè)字符的長度。
簡單遍歷字符串的方法如下：
$strLen = mb_strlen($str); for ($i = 0; $i < $strLen; $i++) { echo mb_substr($str, $i, 1, "utf8"),PHP_EOL; }
登錄后復(fù)制
該方法是利用mb_*系列函數(shù)來正確截取每個(gè)字符，處理大量字符串時(shí)速度非常慢，我猜測(cè)是：mb_substr每截取一個(gè)字符，都要計(jì)算該字符串之前，有多少個(gè)字符。
正確的遍歷字符串的方式是按utf8的編碼規(guī)律來截取字符串，具體請(qǐng)看下文。
算法實(shí)現(xiàn)
<?php /** * 非法關(guān)鍵詞檢查 */ class SensitiveWords { protected $tree = null; protected $callIsNumeric = true; /** * 非法詞匯列表，一個(gè)非法詞匯占用一行 */ 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; } //存在純數(shù)字的非法詞匯 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); } //非法詞匯中沒有純數(shù)字的非法詞匯，待檢測(cè)字符串又是純數(shù)字的，則跳過不再檢查 if ($this->callIsNumeric && is_numeric($str)) { return array_unique($ret); } //挨個(gè)字符進(jìn)行判斷 $tree = $this->tree; $words = ''; for ($i = 0; $i < $strLen; $i++) { //unicode范圍 --> ord 范圍 //一字節(jié) 0-127 --> 0 - 127 //二字節(jié) 128-2047 --> 194 - 223 //三字節(jié) 2048-65535 --> 224 - 239 //四字節(jié) 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) { //四字節(jié) $word = $str[$i] . $str[$i + 1] . $str[$i + 2] . $str[$i + 3]; $i += 3; } else { //五字節(jié)php都溢出了 //Parse error: Invalid UTF-8 codepoint escape sequence: Codepoint too large continue; } //判斷當(dāng)前字符 $tree = $tree->getChild($word); if (is_null($tree)) { //當(dāng)前字不存在，則截取后再次循環(huán) $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; } } /** * 單個(gè)字符的節(jié)點(diǎn) */ class WordNode { //是否為非法詞匯末級(jí)節(jié)點(diǎn) public $end = false; //子節(jié)點(diǎn) 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; } }
登錄后復(fù)制
推薦學(xué)習(xí)：《PHP視頻教程》
php入門到就業(yè)線上直播課：立即學(xué)習(xí)
全程直播 + 實(shí)戰(zhàn)授課 + 邊學(xué) + 邊練 + 邊輔導(dǎo)
