À propos de la définition et de la méthode d'implémentation de l'arborescence du dictionnaire PHP

Cet article présente principalement la définition et la méthode d'implémentation de l'arbre de dictionnaire PHP (arbre de Trie). Il décrit brièvement le concept d'arbre de dictionnaire et analyse la définition et l'utilisation de l'arbre de dictionnaire sous forme d'exemples auxquels les amis dans le besoin peuvent se référer. it

L'exemple de cet article décrit la définition et la méthode d'implémentation de l'arborescence du dictionnaire PHP (Trie tree). Partagez-le avec tout le monde pour référence, comme suit :

Le concept de l'arbre de Trie (explication de Baidu) : L'arbre de dictionnaire, également connu sous le nom d'arbre de recherche de mots, arbre de Trie, est une structure arborescente et une variante d'arbre de hachage. Les applications typiques servent à compter, trier et enregistrer un grand nombre de chaînes (mais sans s'y limiter), elles sont donc souvent utilisées par les systèmes de moteurs de recherche pour les statistiques de fréquence des mots de texte. Ses avantages sont les suivants : utiliser le préfixe commun des chaînes pour réduire le temps de requête, minimiser les comparaisons de chaînes inutiles et l'efficacité des requêtes est supérieure à celle des arbres de hachage.

Je crois comprendre qu'il est utilisé pour la recherche de chaînes. Chaque nœud ne contient qu'un seul caractère. Par exemple, si le mot « monde » est saisi, la structure de l'arborescence est :

<.>

A ce moment, entrez le mot "worab", et la structure de l'arbre sera :

Donc chaque nœud doit aussi avoir un champ is_end pour identifier s'il s'agit du mot de fin. Par exemple, l'utilisateur saisit wor et recherche tous les mots commençant par wor. Supposons qu'il existe maintenant un mot qui est wor et que la recherche commence à partir de "w". Lorsque "r" est récupéré, il faut juger que le mot est wor. is_end du nœud "r" est vrai et wor est ajouté. Accédez à la liste des résultats et continuez la recherche ci-dessous.

Code d'implémentation PHP :

<?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;; // 输出带上搜索前缀
}

Ce qui précède est l'intégralité du contenu de cet article, j'espère qu'il sera utile pour l'apprentissage de chacun. Pour obtenir de l'aide, veuillez faire attention au site Web PHP chinois pour plus de contenu connexe !

Recommandations associées :

Ce qui précède est l'intégralité du contenu de cet article. J'espère qu'il sera utile à l'étude de chacun. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois !

Recommandations associées :

À propos de l'analyse de l'utilisation de l'interface de sérialisation personnalisée de PHP Serialisable

À propos de la façon dont PHP implémente les listes chaînées Définition et fonctions d'inversion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!