简单实现字典树算法

介绍

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ，其中 k 为 key 的长度，与 Trie 中保存了多少个元素无关。Trie 的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。Trie 的缺点是空间消耗很高。Trie的核心思想是空间换时间。

Trie树的基本性质可以归纳为：

1）根节点不包含字符，除根节点意外每个节点只包含一个字符。

2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。

3）每个节点的所有子节点包含的字符串不相同。

Trie树有一些特性：

1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。

2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

3）每个节点的所有子节点包含的字符都不相同。

4）如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。

5）插入查找的复杂度为O(n)，n为字符串长度。

实现（PHP代码）

本文代码实现主要用于敏感词过滤。假如给定如下敏感词：

$word = [

'国军',

'江长生',

'大新闻',

'江长者',

'大长明',

];

首先我们要把这些敏感词加入到字典树中，树的结构如图1所示：

从图中我们可以清楚的看到树的结构，当一个子树的节点字符为null的时候表示这个敏感词在字典树中。

以下完整示例代码地址：

https://github.com/xiaodingchen/data-structures-demo/blob/master/tree/trie.php

生成树：

// UTF8Util::get_chars()这个方法是将普通的UTF-8字符串转换成字符数组，每一个元素是一个 UTF-8串形成的字符。

// 定义一个字典树

private $tree = [];

// 新增树节点

// 对于一个词，从根开始，沿着词的各个字符所对应的树中的节点分支向下走，直到词遍历完，将最后的节点标记为null，表示该词已插入Trie树。

public function insert($str)

{

$chars = UTF8Util::get_chars($str); // $chars = ['江', '长', '生'];

$chars[] = null; // 增加一个结束标识

$count = count($chars);

$T = &$this->tree; // 这里使用指针，用来做数据的更改

for($i=0; $i

$c = $chars[$i];

// 如果这个字符在树中没有节点，那就设置这个节点，如果有那就对其子树进行操作

if(!array_key_exists($c, $T)){

$T[$c] = [];

}

$T = &$T[$c];

}

}

查找

查找一个串，一直根据字符找到null为止就表明存在，任一字符不存在就表明串不存在。

// 查找一个字符串

public function find($str)

{

$chars = UTF8Util::get_chars($str);

$chars[] = null;

return $this->_find($chars);

}

private function _find($chars)

{

$count = count($chars);

$T = &$this->tree;

for($i=0; $i

$c = $chars[$i];

if(!array_key_exists($c, $T)){

return false;

}

$T = &$T[$c];

}

return true;

}

删除

删除一个串，只要找到串中任意一个字符的子元素数量为1，就表示只有这个串了，整个删除就好了；若子元素数量大于1，则继续根据字符找下去，直到末尾的null。

// 删除一个子字典树

public functionremove($str)

{

$chars= UTF8Util::get_chars($str);

$chars[]= null;

// 先查找子树是否存在

if(!$this->_find($chars)){

return;

}

$count=count($chars);

$T= &$this->tree;

for($i=; $i

$c= $chars[$i];

if(array_key_exists($c, $T)){

if(count($T[$c]) ==1){

unset($T[$c]);

return;

}

$T= &$T[$c];

}

}

}

过滤

现在我们可以把敏感词过滤，这个实现起来比较笨的，就是对要检查的文本进行全文检索，也就是把这段文本转换成字符集，然后对这个字符集一个一个在树中遍历。

/*

* 替换字符串中的敏感词

* @param string $str 待匹配的字符串

* @param string $replae 要替换成的字符

*

* @return bool|int

*/

public function contain_replace($str, $replace = '*')

{

$chars = UTF8Util::get_chars($str);

$chars[] = null;

$len = count($chars);

$Tree = &$this->tree;

// 全文检索

for($i=0; $i

$c = $chars[$i];

// 匹配起始字符(先确定起始字符)

if(array_key_exists($c, $Tree)){

$T = &$Tree[$c];

for($j = $i+1; $j

$c = $chars[$j];

// 统计这个起始字符组成的字符串是否在字典树中

if(array_key_exists(null, $T)){

$chars[$i] = $replace;

}

if(!array_key_exists($c, $T)){

break;

}else{

$chars[$j] = $replace;

}

$T = &$T[$c];

}

}

}

return implode('', $chars);

}

结果

使用示例

$tree = new TrieTree;

$word = [

'国军',

'江长生',

'大新闻',

'江长者',

'大长明',

];

foreach ($word as $value) {

$tree->insert($value);

}

$text = "经过大选，会议决定江长者当选为国军总司令";

print_r($tree->contain_replace($text));

输出结果如下：

参考文章：

https://www.cnblogs.com/endsock/p/3584161.html