PHP字典树(Trie树)定义与实现方法示例

PHP字典树(Trie树)定义与实现方法示例

定义

Trie树,也叫字典树或者单词查找树,是一种树形数据结构,常用于统计或者排序字符串数据集。它能够高效地支持字符串数据的插入、查找和前缀搜索等操作,时间复杂度与字符串长度有关,对于一定量的字符串集合,它的查找效率比哈希表更高。

Trie树与二叉查找树最大的不同在于,Trie树每个节点不仅仅存储一个关键码,而是存储一个关键码序列。Trie树的核心思想是利用字符串之间的公共前缀,将重复的前缀合并在一起,从而减少了存储空间,提高了查找效率。

实现

定义类

我们定义一个Trie树类TrieTree,它有以下三个属性:

  • $root:根节点,初始时为空;
  • $count:Trie树中单词的数量,初始为0;
  • $size:Trie树中节点的数量,初始为1(根节点)。
class TrieTree {
    private $root;
    private $count;
    private $size;

    public function __construct() {
        $this->root = new TrieNode();
        $this->count = 0;
        $this->size = 1;
    }
}

定义节点类

我们定义Trie树中的节点类TrieNode,它有以下三个属性:

  • $char:该节点存储的字符;
  • $isEnd:是否为单词结尾,初始为false;
  • $children:该节点的子节点,初始为空数组。
class TrieNode {
    public $char;
    public $isEnd;
    public $children;

    public function __construct($char = null) {
        $this->char = $char;
        $this->isEnd = false;
        $this->children = [];
    }
}

插入单词操作

Trie树的插入操作需要遍历整个单词,然后将单词的每个字符依次插入到Trie树中。

public function insert($word) {
    $node = $this->root;
    for ($i = 0; $i < strlen($word); $i++) {
        $char = $word[$i];
        if (!isset($node->children[$char])) {
            $node->children[$char] = new TrieNode($char);
            $this->size++;
        }
        $node = $node->children[$char];
    }
    if (!$node->isEnd) {
        $node->isEnd = true;
        $this->count++;
    }
}

查找单词操作

Trie树的查找操作需要遍历整个单词,然后判断每个字符是否存在于Trie树中。

public function search($word) {
    $node = $this->root;
    for ($i = 0; $i < strlen($word); $i++) {
        $char = $word[$i];
        if (!isset($node->children[$char])) {
            return false;
        }
        $node = $node->children[$char];
    }
    return $node->isEnd;
}

查找前缀操作

Trie树的查找前缀操作需要遍历前缀,然后判断每个字符是否存在于Trie树中。

public function startsWith($prefix) {
    $node = $this->root;
    for ($i = 0; $i < strlen($prefix); $i++) {
        $char = $prefix[$i];
        if (!isset($node->children[$char])) {
            return false;
        }
        $node = $node->children[$char];
    }
    return true;
}

示例

示例1:插入单词和查找单词操作

我们创建一个Trie树对象,插入若干个单词,然后查找某些单词是否存在。

$trie = new TrieTree();
$trie->insert('apple');
$trie->insert('banana');
$trie->insert('orange');
$trie->insert('pear');

echo $trie->search('apple'); // true
echo $trie->search('pear'); // true
echo $trie->search('watermelon'); // false

示例2:查找前缀操作

我们创建一个Trie树对象,插入一些单词,然后查找以某个前缀开头的单词个数。

$trie = new TrieTree();
$trie->insert('apple');
$trie->insert('banana');
$trie->insert('orange');
$trie->insert('pear');

echo $trie->startsWith('a'); // true
echo $trie->startsWith('ab'); // false
echo $trie->startsWith('pe'); // true

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:PHP字典树(Trie树)定义与实现方法示例 - Python技术站

(0)
上一篇 2023年5月27日
下一篇 2023年5月27日

相关文章

  • PHP session反序列化漏洞超详细讲解

    下面是“PHP session反序列化漏洞超详细讲解”的完整使用攻略,包括漏洞描述、漏洞原理、漏洞利用和两个示例。 漏洞描述 PHP session反序列化漏洞是一种常见的Web应用程序漏洞,攻击者可以利用这个漏洞执行任意代码从而获取Web应用程序的控制权。这个漏洞的原因是PHP在处理session数据时,使用了不安全的反序列化方法,导致攻击者可以构造恶意的…

    PHP 2023年5月12日
    00
  • 利用php输出不同的心形图案

    以下是利用PHP输出不同心形图案的完整攻略: 准备工作 首先需要安装PHP环境。如果您已经完成了安装,可以开始下一步。 实现过程 1. 创建一个HTML页面 在你的本地计算机上创建一个HTML文件index.html,用以下代码进行文件的基本定义和HTML结构的编写: <!DOCTYPE html> <html> <head&g…

    PHP 2023年5月26日
    00
  • 基于PHP生成静态页的实现方法

    当网站访问量较大时,为了提高网站性能和减轻服务器压力,使用静态页面可以是一种不错的选择。本文将详细讲解如何基于 PHP 生成静态页。 实现方法 首先,在 PHP 中使用 ob_start() 开启输出缓冲区,并把输出的内容存储到缓冲区,这样就能在缓冲区的内容中进行处理。 “`php “` 然后,在 PHP 中使用 file_put_contents() …

    PHP 2023年5月27日
    00
  • PHP学习笔记之字符串编码的转换和判断

    下面是《PHP学习笔记之字符串编码的转换和判断》的完整攻略。 字符编码介绍 在讲解字符串编码的转换和判断之前,先简单介绍一下字符编码的概念。字符编码是计算机中用于存储和处理文本字符的方式。目前常见的字符编码有:ASCII码、Unicode和UTF-8编码等。 其中,ASCII码只能表示128个字符,不支持中文字符;Unicode则可以表示几乎所有的字符,但是…

    PHP 2023年5月26日
    00
  • 基于php-fpm的配置详解

    基于 php-fpm 的配置详解 什么是 php-fpm PHP-FPM(FastCGI Process Manager),是 PHP 官方提供的一个 FastCGI 进程管理器。它可以管理运行 PHP 的 FastCGI 进程,以便更好地使用服务器的资源并提高 PHP 应用程序的响应速度。 安装和启动 php-fpm 安装 php-fpm 可以通过包管理器…

    PHP 2023年5月27日
    00
  • PHP开发需要注意的安全问题

    PHP开发需要注意的安全问题 在PHP开发的过程中,一定要非常注意安全问题,以防止黑客攻击,保障系统的安全稳定。以下是一些PHP开发中需要注意的安全问题及对应的解决方法。 1. SQL注入 SQL注入是指黑客通过在SQL语句中插入恶意代码,从而破坏数据库安全的一种攻击方式。攻击者可以通过SQL注入获取数据库中的数据,修改数据,甚至是破坏整个数据库系统。 如何…

    PHP 2023年5月23日
    00
  • 两种设置php载入页面时编码的方法

    当运行 PHP 脚本时,页面的编码格式至关重要,因为它确定了页面中的字符集类型。在 PHP 中设置页面编码格式的方法有两种: 在代码中设置页面编码格式 可以通过在 PHP 代码中添加一个特殊的标记来设置页面的编码格式,该标记告诉服务器该页面的字符集类型。这种方法非常简单,你只需要在 php 文件的开头添加以下代码块: header(‘Content-Type…

    PHP 2023年5月26日
    00
  • 微信小程序getPhoneNumber获取用户手机号

    下面我将详细讲解“微信小程序getPhoneNumber获取用户手机号”的完整攻略。 1. 获取用户手机号的前提条件 在使用getPhoneNumber获取用户手机号之前,必须满足以下条件: 该用户已经授权过小程序获取用户手机号; 开启了“获取用户手机号”权限; 正在使用微信运行的环境; 用户允许小程序使用手机号码。 2. 如何获取用户手机号 获取用户手机号…

    PHP 2023年5月30日
    00
合作推广
合作推广
分享本页
返回顶部