关于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() 办法能够判断字典树上是否有指定字符串前缀的单词：

<?phprequire $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.输入演示

<?phprequire '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...

扫码关注爱因诗贤