trie树(前缀树)详解——PHP代码实现

时间:2021-10-21 21:50:22

trie树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

一、Tire树的基本性质

  • 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  • 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  • 每个节点的所有子节点包含的字符都不相同。

Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起,比如我们有[b,abc,abd,bcd,abcd,efg,hii ]这个字符串集合,可以将其构建成下面这棵 Trie 树:

trie树(前缀树)详解——PHP代码实现

每个节点表示一个字符串中的字符,从根节点到红色节点的一条路径表示一个字符串(红色节点表示是某个单词的结束字符,但不一定都是叶子节点)。这样,我们就可以通过遍历这棵树来检索是否存在待匹配的字符串了

二、如何实现Tire树

Tire主要包含两个操作,一个是将字符串集合构造成 Trie 树。这个过程分解开来的话,就是一个将字符串插入到 Trie 树的过程。另一个是在 Trie 树中查询一个字符串。

Trie 树是个多叉树,在这里用数组来存储一个节点的所有子结点。

Trie树节点类,PHP代码实现:

 <?php
/**
* TrieNode.php
* Created on 2019/4/29 14:53
* Created by Wilin
*/ class TrieNode
{
public $data;
public $children = [];
public $isEndingChar = false; public function __construct($data)
{
$this->data = $data;
}
}

Trie树,PHP代码实现:

 <?php
/**
* Tire.php
* Created on 2019/4/29 14:57
* Created by Wilin
*/ include "TrieNode.php"; class Tire {
private $root; public function __construct() {
$this->root = new TrieNode('/'); //根节点
} public function getRoot() {
return $this->root;
} public function insert($text) {
$p = $this->root;
for ($i = 0; $i < mb_strlen($text); $i++) {
$index = $data = $text[$i]; if (empty($p->children[$index])) {
$newNode = new TrieNode($data);
$p->children[$index] = $newNode;
}
$p = $p->children[$index];
}
$p->isEndingChar = true;
} public function find($pattern) {
$p = $this->root;
for ($i = 0; $i < mb_strlen($pattern); $i++) {
$index = $data = $pattern[$i]; if (empty($p->children[$index])) {
return false;
}
$p = $p->children[$index];
}
if ($p->isEndingChar == false) {
return false;
}
return true;
}
} $trie = new Tire();
$strings = ['b','abc','abd','bcd','abcd','efg','hii'];
foreach ($strings as $str) {
$trie->insert($str);
}
if ($trie->find('bcd')) {
print "包含这个字符串\n";
} else {
print "不包含这个字符串\n";
}
print_r($trie->getRoot());

打印结果如下:

E:\www\tree\3>php Tire.php
包含这个字符串
TrieNode Object
(
[data] => /
[children] => Array
(
[b] => TrieNode Object
(
[data] => b
[children] => Array
(
[c] => TrieNode Object
(
[data] => c
[children] => Array
(
[d] => TrieNode Object
(
[data] => d
[children] => Array
(
) [isEndingChar] => 1
) ) [isEndingChar] =>
) ) [isEndingChar] => 1
) [a] => TrieNode Object
(
[data] => a
[children] => Array
(
[b] => TrieNode Object
(
[data] => b
[children] => Array
(
[c] => TrieNode Object
(
[data] => c
[children] => Array
(
[d] => TrieNode Object
(
[data] => d
[children] => Array
(
) [isEndingChar] => 1
) ) [isEndingChar] => 1
) [d] => TrieNode Object
(
[data] => d
[children] => Array
(
) [isEndingChar] => 1
) ) [isEndingChar] =>
) ) [isEndingChar] =>
) [e] => TrieNode Object
(
[data] => e
[children] => Array
(
[f] => TrieNode Object
(
[data] => f
[children] => Array
(
[g] => TrieNode Object
(
[data] => g
[children] => Array
(
) [isEndingChar] => 1
) ) [isEndingChar] =>
) ) [isEndingChar] =>
) [h] => TrieNode Object
(
[data] => h
[children] => Array
(
[i] => TrieNode Object
(
[data] => i
[children] => Array
(
[i] => TrieNode Object
(
[data] => i
[children] => Array
(
) [isEndingChar] => 1
) ) [isEndingChar] =>
) ) [isEndingChar] =>
) ) [isEndingChar] =>
)

参考资料:https://www.cnblogs.com/luosongchao/p/3239521.htmlhttps://articles.zsxq.com/id_qa0npqvszcmx.html

trie树(前缀树)详解——PHP代码实现的更多相关文章

  1. AVL树平衡旋转详解

    AVL树平衡旋转详解 概述 AVL树又叫做平衡二叉树.前言部分我也有说到,AVL树的前提是二叉排序树(BST或叫做二叉查找树).由于在生成BST树的过程中可能会出现线型树结构,比如插入的顺序是:1, ...

  2. 9-11-Trie树&sol;字典树&sol;前缀树-查找-第9章-《数据结构》课本源码-严蔚敏吴伟民版

    课本源码部分 第9章  查找 - Trie树/字典树/前缀树(键树) ——<数据结构>-严蔚敏.吴伟民版        源码使用说明  链接☛☛☛ <数据结构-C语言版>(严蔚 ...

  3. css3浏览器私有属性前缀使用详解

    什么是浏览器私有属性前缀 CSS3的浏览器私有属性前缀是一个浏览器生产商经常使用的一种方式.它暗示该CSS属性或规则尚未成为W3C标准的一部分. 以下是几种常用前缀 -webkit- -moz- -m ...

  4. Python - 元组&lpar;tuple&rpar; 详解 及 代码

    元组(tuple) 详解 及 代码 本文地址: http://blog.csdn.net/caroline_wendy/article/details/17290967 元组是存放任意元素集合,不能修 ...

  5. Python - 字典&lpar;dict&rpar; 详解 及 代码

    字典(dict) 详解 及 代码 本文地址: http://blog.csdn.net/caroline_wendy/article/details/17291329 字典(dict)是表示映射的数据 ...

  6. 深度学习之卷积神经网络&lpar;CNN&rpar;详解与代码实现(一)

    卷积神经网络(CNN)详解与代码实现 本文系作者原创,转载请注明出处:https://www.cnblogs.com/further-further-further/p/10430073.html 目 ...

  7. C&num;的String&period;Split 分割字符串用法详解的代码

    代码期间,把代码过程经常用的内容做个珍藏,下边代码是关于C#的String.Split 分割字符串用法详解的代码,应该对码农们有些用途. 1) public string[] Split(params ...

  8. laravel 框架配置404等异常页面的方法详解(代码示例)

    本篇文章给大家带来的内容是关于laravel 框架配置404等异常页面的方法详解(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助. 在Laravel中所有的异常都由Handl ...

  9. Android java程序员必备技能,集合与数组中遍历元素,增强for循环的使用详解及代码

    Android java程序员必备技能,集合与数组中遍历元素, 增强for循环的使用详解及代码 作者:程序员小冰,CSDN博客:http://blog.csdn.net/qq_21376985 For ...

  10. &lbrack;LeetCode&rsqb; Implement Trie &lpar;Prefix Tree&rpar; 实现字典树&lpar;前缀树&rpar;

    Implement a trie with insert, search, and startsWith methods. Note:You may assume that all inputs ar ...

随机推荐

  1. 用Java编程找到两个字符串*有的字符

    这道题的算法思想是把字符串1中的每个字符与字符串2中的每个字符进行比较,遇到共同拥有的字符,放入另一个数组中,最后顺序输出即可 但是这道题的难点在于怎么排除重复的字符 public class bot ...

  2. js处理异常try&lbrace;&rcub;catch&lpar;e&rpar;&lbrace;&rcub;

    MXS&Vincene  ─╄OvЁ  &0000021─╄OvЁ  MXS&Vincene MXS&Vincene  ─╄OvЁ:今天很残酷,明天更残酷,后天很美好, ...

  3. map与set的遍历

    map有四种方式: 1.直接遍历 keySet 2.使用Iterator //注意next放回的对象是map.Entry<K,V>,而使用的iterator是通过entrySet返回的一个 ...

  4. JS onkeydown控制HTML Input 只录入浮点数值

    // -1) return false; return index == 0 } keychar = String.fromCharCode(keynum) var newVal = oriVal.s ...

  5. 针对iPhone的pt、Android的dp、HTML的css像素与dpr、设计尺寸和物理像素的浅分析

    最近被一朋友问到:css中设置一DOM的height:65px,请问显示的高度是否和Android的65dp的元素等高?脑子里瞬间闪现了一堆的概念,如dpr,ppi,dp,pt等,然而想了一阵,浆糊了 ...

  6. flask-日料网站搭建-数据库操作

    引言:想使用python的flask框架搭建一个日料网站,主要包含web架构,静态页面,后台系统,交互,目前已经copy完主页,不是前端太慢太慢. 本节知识:数据库的操作,模型建表,更新数据库. py ...

  7. Python中使用class&lpar;&rpar;,面向对象有什么优势 转自知乎

    https://www.zhihu.com/question/19729316 首先我是辣鸡,然后这个问题的确有点意思 首先,类是一个集合,包含了数据,操作描述的一个抽象集合 你可以首先只把类当做一个 ...

  8. android studio中编译单个文件

    网上搜到比较全的是这个:https://blog.csdn.net/u011368551/article/details/51980678 另外关于gradle如何编译单个文件,参考 https:// ...

  9. postman 请求种添加用户权限

    1. 打开postman, 在Tests输入以下内容: var jsonData =JSON.parse(responseBody);//获取body中返回的所有参数 postman.setGloba ...

  10. ciscn2018-pwn-wp

    前言 2018全国大学生网络安全竞赛 ,做了2 道题 task_supermarket change_desc 里面调用 realloc 会触发 uaf 利用 uaf 修改 obj->desc_ ...