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

码农天地 - 2020-11-01 01:13:37

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

扫码关注爱因诗贤

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。