Beispiel für die Implementierungsdefinitionsmethode des Wörterbuchbaums Trie in PHP

In diesem Artikel werden hauptsächlich die Definitions- und Implementierungsmethoden des PHP-Wörterbuchbaums (Trie-Baum) vorgestellt und die Definition und Verwendung des Wörterbuchbaums anhand von Beispielen analysiert it

Das Beispiel in diesem Artikel beschreibt die Definition und Implementierungsmethode des PHP-Wörterbuchbaums (Trie-Baum). Teilen Sie es wie folgt mit allen als Referenz:

Das Konzept des Trie-Baums (Erklärung von Baidu): Der Wörterbuchbaum, auch bekannt als Wortsuchbaum, Trie-Baum, ist eine Baumstruktur und eine Hash-Baum-Variante. Typische Anwendungen sind das Zählen, Sortieren und Speichern einer großen Anzahl von Zeichenfolgen (aber nicht nur Zeichenfolgen), weshalb sie häufig von Suchmaschinensystemen für Statistiken zur Worthäufigkeit von Texten verwendet werden. Seine Vorteile sind: Die Verwendung des gemeinsamen Präfixes von Zeichenfolgen verkürzt die Abfragezeit, minimiert unnötige Zeichenfolgenvergleiche und die Abfrageeffizienz ist höher als bei Hash-Bäumen.

Nach meinem Verständnis wird es für die Zeichenfolgensuche verwendet. Wenn beispielsweise das Wort „Welt“ eingegeben wird, lautet die Struktur des Baums:

Geben Sie zu diesem Zeitpunkt das Wort „worab“ ein und die Struktur des Baums sieht wie folgt aus:

Jeder Knoten muss also auch einen haben Feld is_end, um festzustellen, ob es sich um das Endwort handelt. Beispielsweise gibt der Benutzer „wor“ ein und sucht nach allen Wörtern, die mit „wor“ beginnen, und die Suche beginnt mit „w“. is_end des Knotens „r“ ist wahr und wor wird hinzugefügt. Gehen Sie zur Ergebnisliste und setzen Sie die Suche unten fort.

PHP-Implementierungscode:

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

Das obige ist der detaillierte Inhalt vonBeispiel für die Implementierungsdefinitionsmethode des Wörterbuchbaums Trie in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!