一、Trie树简介
什么是Trie树？
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。 Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
Trie树基本性质：
1、根节点不包含字符，除根节点外每一个节点都只包含一个字符。 2、从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 3、每个节点的所有子节点包含的字符都不相同。
二、Trie树操作
插入操作示例:
class TTrie { private $dict = [[]]; //字典 private $input = 0; //字符串当前偏移 private $backtracking = 0; //字符串回溯位置 private $buffer = []; public function __construct($words) { $this->insert($words); } /** * 插入单词 * Function insert * @Author sakmon * @CreateTime 2019/4/25 15:42 * @param $word */ public function insert($word) { if (is_array($word)) { foreach ($word as $v) { $this->insert($v); } return; } $p = count($this->dict); $cur = 0; //当前节点号 foreach (str_split($word) as $c) { if (isset($this->dict[$cur][$c])) { //已存在就下移 , 相同前缀单词同一个节点 $cur = $this->dict[$cur][$c]; continue; } $this->dict[$p] = []; //创建新节点 $this->dict[$cur][$c] = $p; //在父节点记录子节点号 $cur = $p; //把当前节点设为新插入的 $p++; } $this->dict[$cur]['isWord'] = true; //一个词结束，标记叶子节点 } }
字典树生成示例：
单词查找示例：
/** * 单词查找 * Function find * @Author sakmon * @CreateTime 2019/4/25 17:24 * @param $word * @return bool */ public function find($word) { $len = strlen($word); $p = 0; for ($i = 0; $i < $len; $i++) { $c = $word{$i}; if (!isset($this->dict[$p][$c])) { //节点不存在 return false; } $p = $this->dict[$p][$c]; //子节点 } if (!isset($this->dict[$p]['isWord'])) { //判断是否为单词，避免相同前缀 return false; } return true; }
删除单词:
/** * Function remove * @Author sakmon * @CreateTime 2019/4/26 11:54 * @param $word */ public function remove($word) { if (!$this->find($word)) { //先判断单词是否存在 return false; } $len = strlen($word); $p = 0; $del = []; //需删除的相关联键 for ($i = 0; $i < $len; $i++) { $c = $word{$i}; $cur = $this->dict[$p][$c]; //子节点 if (count($this->dict[$cur]) == 1) { $del[] = [$p, $c]; } else { $del = []; } $p = $cur; //子节点 } foreach ($del as $key => $val) { unset($this->dict[$val[0]][$val[1]]); } if (count($this->dict[$p]) == 1) { //判断叶子是否只有一个元素，即isWord unset($this->dict[$p]); } else { unset($this->dict[$p]['isWord']); } return true; }
三、Trie树应用
/** * Function match * @Author sakmon * @CreateTime 2019/4/25 18:03 * @param $s * @return array */ public function match($s) { $cur = 0; //当前节点，初始为根节点 $i =& $this->input; //字符串当前偏移 $p =& $this->backtracking; //字符串回溯位置 $len = strlen($s); $dl = 0; while ($i < $len) { $c = $s{$i}; if (isset($this->dict[$cur][$c])) { //如果存在 $cur = $this->dict[$cur][$c]; //转到对应的位置 if (isset($this->dict[$cur]['isWord'])) { //是叶子节点，单词匹配！ $dl = $i - $p + 1; //最长匹配单词长度 } if (isset($this->dict[$cur][$s[$i + 1]])) {//检查下一个字符是否也能匹配，长度优先 $i++; continue; } if ($dl > 0) { //匹配单词成功 $this->buffer[] = substr($s, $p, $dl); //取出匹配位置和匹配的词 $i = $p + $dl - 1; $p = $i + 1; $dl = 0; } else { $p = $i + 1; //设置下一个回溯位置 } $cur = 0; //重置当前节点为根节点 } else { //不匹配 $cur = 0; //重置当前节点为根节点 $i = $p; //把当前偏移设为回溯位置 $p = $i + 1; //设置下一个回溯位置 } $i++; //下一个字符 } return $this->buffer; }
字符串检索示例 :
include_once('keywords.php'); $words = array_column($keywords , 'word'); $trie = new TTrie($words); //$matches = $trie->match('近年来，厦门聚焦发展电子信息、装备制造等五大产业集群，重点打造平板显示、半导体和华秋集成电路等12条千亿产业链，日前厦门发改委发布其招商地图及投资机会清单，对华强半导体与集成电路领域作出招商引资规划。'); $matches = $trie->match(' 5G究竟会给全球带来怎样的影响力？为何号称全球第一的美国屡屡对一中国企业处处压制，而不惜采用各种手段抹黑且极力阻止其开拓市场。这些行为对华为后面有何影响，勇敢的华为会否赢得5G跑道的比赛？ 重大事件回顾 去年12月，加拿大当局逮捕了华为首席财务官孟晚舟，以便向美国政府提出引渡请求。美国政府声称该公司通过隐瞒伊朗支付违反对该国的制裁来欺骗几家银行。 今年1月，司法部宣布对该公司的两个部门提出一系列指控，包括窃取T-Mobile USA的商业机密。同时，美国特朗普政府通过2019年的国防授权法禁止华为和中兴参与美国政府的大部分项目合作。 5月2日~3日，以美国特朗普政府为首，加拿大、澳大利亚、以色列、部分欧盟成员国（德国、法国、英国等）以及日本和韩国等30个国家在布拉格举行5G网络安全协议，并发布名为“布拉格提议”的声明。其中意味不言而喻，剑指中国华为。 5月15日，美国特朗普签署行政命令。其内容用意一句话来概括就是将华为列入黑名单，禁止其电信设备进入美国市场。该文件发布后，又将华为旗下70个子公司列入美国贸易黑名单。 华为为何受“照顾” 5g技术的重要性不言而喻，它将为我们社会带来全新的繁荣。它将促发各行各业许多新的东西，如远程医疗、自动驾驶、智慧城市、智慧工业等，以及赋予我们身边很多最基础的设施，如配电。这将使得它会成为我们生活中非常重要的一个部分。 然而，5G技术的竞争已经在进行中，而华为公司已经处于全球领先的地位。这一点或许是美国害怕和担心的。害怕的是一旦使用外国网络设备导致未来一些不可控因素的发生；担心的是5G领域已经落后于中国，美国全球5G影响力地位下降。 而这些所谓的“害怕”，华为已经多次强调并解释。过去三十年，华为一直保持良好的网络安全记录。去年年底华为追加投入20亿美元的初始专项预算升级网络系统软件。 但挥不去地总不是这些阴影，而是背后的“阴谋”。最近，美国官员一直以“网络安全”为由，禁止华为与美国政府签订合同，并敦促美国盟友也效仿。但是至今为止除了澳大利亚和日本以外，他们遭到了许多海外盟友的怀疑。 正如今天许多媒体报道的那样，美国特朗普政府15日再次挥舞权利的大棒意图遏制华为。不管是去年12月的孟晚舟被羁押事件，还是周三特朗普签署的行政命令，其意图已相当明显。 外界认为，不管是华为、爱立信，诺基亚和三星......，无论美国选择谁？都不该将政治权利导入商业竞争。 对华为影响如何？ 然而，更大的担忧可能是美国将华为列入美国商务部工业和安全局（BIS）所谓的实体名单。这意味着美国公司需要获得相关许可才能向华为出售或转让技术。而华为依赖英特尔和高通等美国公司的部分组件来生产智能手机和笔记本电脑。 此外，华为的消费者业务现在是收入最大的部门，占其总营收48.4%，被视为该公司的主要成长动能。对消费者群体的任何干扰都可能影响其整体业务。 但在过去几年中，华为一直在为其智能手机设计自己的芯片，以减少对其他公司的依赖。它有一系列称为Kirin的处理器和Balong 5000的调制解调器，搭载这些产品的设备将被允许连接到5G网络。 据IDC数据显示，在2018年，73％的华为智能手机包含了该公司自己的芯片。另外10％来自台湾的联发科技公司。剩下的17％来自高通公司，但这些主要是针对低端200美元以下的手机。 据笔者观察，如果美国特朗普政府铁心不与华为合作5G，在失去美国5G市场的同时，如果BIS有选择性的限制华为与美国企业合作，对华为ICT基础设施和部分智能终端设备的部件供货将会产生一定影响。 尽管如此，我们也有必要强调，美国只是世界的一部分。华为5G不会因为西方变黑，而东方不闪耀。 '); print_r($matches); exit;
