关于php:数据结构PHP-字典树Trie的实现

​这篇文章介绍一下 字典树 的实现原理，又称 单词查找树、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…

扫码关注爱因诗贤