Example of implementation definition method of dictionary tree Trie in PHP-PHP Tutorial-php.cn

Example of implementation definition method of dictionary tree Trie in PHP

黄舟

Release： 2023-03-16 15:04:01

Original

1494 people have browsed it

This article mainly introduces the definition and implementation method of PHP dictionary tree (Trie tree). It briefly describes the concept of dictionary tree and analyzes the definition and use of dictionary tree in the form of examples. Friends in need can refer to it

The example in this article describes the definition and implementation method of PHP dictionary tree (Trie tree). Share it with everyone for your reference, as follows:

The concept of Trie tree (Baidu's explanation): Dictionary tree, also known as word search tree, Trie tree, is a tree structure and a hash tree variant. Typical applications are for counting, sorting and saving a large number of strings (but not limited to strings), so they are often used by search engine systems for text word frequency statistics. Its advantages are: using the common prefix of strings to reduce query time, minimizing unnecessary string comparisons, and querying efficiency is higher than hash trees.

My understanding is that it is used for string search. Each node only contains one character. For example, if the word "world" is entered, the structure of the tree is:

At this time, enter the word "worab", and the structure of the tree will be:

So each node must also have a field is_end to identify whether it is the end word. For example, the user inputs wor and searches for all words starting with wor. Assume that there is a word now that is wor, and the search starts from "w". When "r" is retrieved, it needs to be judged that the is_end of the "r" node is true, and wor is added. Go to the results list and continue searching below.

PHP implementation code:

<?php
class Node{
  public $value;         // 节点值
  public $is_end = false;    // 是否为结束--是否为某个单词的结束节点
  public $childNode = array();  // 子节点
  /* 添加孩子节点--注意：可以不为引用函数，因为PHP对象赋值本身就是引用赋值 */
  public function &addChildNode($value, $is_end = false){
    $node = $this->searchChildNode($value);
    if(empty($node)){
      // 不存在节点，添加为子节点
      $node = new Node();
      $node->value = $value;
      $this->childNode[] = $node;
    }
    $node->is_end = $is_end;
    return $node;
  }
  /* 查询子节点 */
  public function searchChildNode($value){
    foreach ($this->childNode as $k => $v) {
      if($v->value == $value){
        // 存在节点，返回该节点
        return $this->childNode[$k];
      }
    }
    return false;
  }
}
/* 添加字符串 */
function addString(&$head, $str){
  $node = null;
  for ($i=0; $i < strlen($str); $i++) {
    if($str[$i] != &#39; &#39;){
      $is_end = $i != (strlen($str) - 1) ? false : true;
      if($i == 0){
        $node = $head->addChildNode($str[$i], $is_end);
      }else{
        $node = $node->addChildNode($str[$i], $is_end);
      }
    }
  }
}
/* 获取所有字符串--递归 */
function getChildString($node, $str_array = array(), $str = &#39;&#39;){
  if($node->is_end == true){
    $str_array[] = $str;
  }
  if(empty($node->childNode)){
    return $str_array;
  }else{
    foreach ($node->childNode as $k => $v) {
      $str_array = getChildString($v, $str_array, $str . $v->value);
    }
    return $str_array;
  }
}
/* 搜索 */
function searchString($node, $str){
  for ($i=0; $i < strlen($str); $i++) {
    if($str[$i] != &#39; &#39;){
      $node = $node->searchChildNode($str[$i]);
      // print_r($node);
      if(empty($node)){
        // 不存在返回空
        return false;
      }
    }
  }
  return getChildString($node);
}
/* 调用测试开始 */
$head = new Node;  // 树的head
// 添加单词
addString($head, &#39;hewol&#39;);
addString($head, &#39;hemy&#39;);
addString($head, &#39;heml&#39;);
addString($head, &#39;you&#39;);
addString($head, &#39;yo&#39;);
// 获取所有单词
$str_array = getChildString($head);
// 搜索
$search_array = searchString($head, &#39;hem&#39;);
// 循环打印所有搜索结果
foreach ($search_array as $key => $value) {
  echo &#39;hem&#39; . $value . &#39;<br>&#39;; // 输出带上搜索前缀
}

Copy after login

The above is the detailed content of Example of implementation definition method of dictionary tree Trie in PHP. For more information, please follow other related articles on the PHP Chinese website!