简单实现字典树算法

介绍

字典树又称单词查找树,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

  • 发表于:
  • 原文链接:https://kuaibao.qq.com/s/20180709G1HLGR00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券