【php】数据结构-PHP 字典树(Trie)的实现

• Z时代
• 2024-01-10
• 分类：技术分享

class Node{
public $isWord;
public $value;//可以存储表示其他信息
public $next; //这是一颗 Map 树，指向其他 25 个字母
public function __construct(){
$this->next = new BinarySearchTreeMap();
}
}

<?php
require $root . "/Map/BinarySearchTreeMap.php";
/**
* 字典树
* Class Trie
*/
class Trie
{
private $root = null;
private $size;
public function __construct() {
$this->root = new TrieNode();
}
/**
* 向字典树中添加
* @param string $word向字段树中添加元素
*/
public function add(string $word, $value) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$c = $word[$i];
if ($node->next->get($c) == null) {
$node->next->add($c, new TrieNode($value));
}
$node = $node->next->get($c);
}
if (!$node->isWord) {
$node->isWord = true;
$this->size++;
}
}
/**
* 查看单词 word 是否存在 Trie 树中
* @param $word
*/
public function contains($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$c = $word[$i];
if ($node->next->get($c) == null) {
return false;
}
$node = $node->next->get($c);
}
if ($node->isWord) {
return true;
} else {
return false;
}
}
/**
* 获取字段树节点信息
* @param $word
*/
public function get($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$c = $word[$i];
if ($node->next->get($c) == null) {
return null;
}
$node = $node->next->get($c);
}
return $node->value;
}
/**
* 判断某个字符串是否为单词前缀
* @param string $prefix
* @return bool
*/
public function isPrefix(string $prefix) {
$node = $this->root;
for ($i = 0; $i < strlen($prefix); $i++) {
$c = $prefix[$i];
if ($node->next->get($c) == null) {
return false;
}
$node = $node->next->get($c);
}
return false;
}
public function getSize() {
return $this->size;
}
}
class TrieNode
{
public $isWord = false;
public $next;
public $value = null;
public function __construct($value = null) {
$this->value = $value;
$this->next = new BinarySearchTreeMap();
}
}

<?php
require 'Trie.php';
$trie = new Trie();
$trie->add('qsx',123);
$trie->add('dog',456);
$trie->add('cat',789);
$trie->add('else',111);
$trie->add('good',111);
var_dump($trie->contains('qsx'));
var_dump($trie->contains('dog'));
var_dump($trie->contains('aaaa'));
var_dump($trie->contains('ddd'));
var_dump($trie->get('qsx'));
var_dump($trie->get('cat'));
var_dump($trie->get('dog'));
var_dump($trie->get('good'));
var_dump($trie->isPrefix('go'));
var_dump($trie->isPrefix('goo'));
var_dump($trie->isPrefix('goop'));

​这篇文章介绍一下字典树的实现原理，又称单词查找树、Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

1.字典树(Trie)示意图

2.节点定义

class Node{
public $isWord;
public $value;//可以存储表示其他信息
public $next; //这是一颗 Map 树，指向其他 25 个字母
public function __construct(){
$this->next = new BinarySearchTreeMap();
}
}

3.Trie 字典树类定义

如下定义了一个字典树(Trie)，其中add() 方法可以向 字典树 中添加单词，contains() 可以查询 字典树(Trie) 中是否包含某个单词,isPrefix() 方法可以判断字典树上是否有指定字符串前缀的单词：

<?php
require $root . "/Map/BinarySearchTreeMap.php";
/**
* 字典树
* Class Trie
*/
class Trie
{
private $root = null;
private $size;
public function __construct() {
$this->root = new TrieNode();
}
/**
* 向字典树中添加
* @param string $word向字段树中添加元素
*/
public function add(string $word, $value) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$c = $word[$i];
if ($node->next->get($c) == null) {
$node->next->add($c, new TrieNode($value));
}
$node = $node->next->get($c);
}
if (!$node->isWord) {
$node->isWord = true;
$this->size++;
}
}
/**
* 查看单词 word 是否存在 Trie 树中
* @param $word
*/
public function contains($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$c = $word[$i];
if ($node->next->get($c) == null) {
return false;
}
$node = $node->next->get($c);
}
if ($node->isWord) {
return true;
} else {
return false;
}
}
/**
* 获取字段树节点信息
* @param $word
*/
public function get($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$c = $word[$i];
if ($node->next->get($c) == null) {
return null;
}
$node = $node->next->get($c);
}
return $node->value;
}
/**
* 判断某个字符串是否为单词前缀
* @param string $prefix
* @return bool
*/
public function isPrefix(string $prefix) {
$node = $this->root;
for ($i = 0; $i < strlen($prefix); $i++) {
$c = $prefix[$i];
if ($node->next->get($c) == null) {
return false;
}
$node = $node->next->get($c);
}
return false;
}
public function getSize() {
return $this->size;
}
}
class TrieNode
{
public $isWord = false;
public $next;
public $value = null;
public function __construct($value = null) {
$this->value = $value;
$this->next = new BinarySearchTreeMap();
}
}

4.输出演示

<?php
require 'Trie.php';
$trie = new Trie();
$trie->add('qsx',123);
$trie->add('dog',456);
$trie->add('cat',789);
$trie->add('else',111);
$trie->add('good',111);
var_dump($trie->contains('qsx'));
var_dump($trie->contains('dog'));
var_dump($trie->contains('aaaa'));
var_dump($trie->contains('ddd'));
var_dump($trie->get('qsx'));
var_dump($trie->get('cat'));
var_dump($trie->get('dog'));
var_dump($trie->get('good'));
var_dump($trie->isPrefix('go'));
var_dump($trie->isPrefix('goo'));
var_dump($trie->isPrefix('goop'));

代码仓库 ：https://gitee.com/love-for-po...

扫码关注爱因诗贤

以上是 【php】数据结构-PHP 字典树(Trie)的实现 的全部内容， 来源链接： utcz.com/a/106150.html