집 > 기사 > 백엔드 개발 > PHP 사전 트리의 정의 및 구현 방법에 대해

PHP 사전 트리의 정의 및 구현 방법에 대해

不言원래의: 2018-06-19 11:15:532704검색

이 글에서는 주로 PHP 사전 트리(Trie tree)의 정의와 구현 방법을 소개하고, 사전 트리의 개념을 간략하게 설명하고, 필요한 친구들이 예제를 참고할 수 있도록 사전 트리의 정의와 활용 방법을 분석합니다. 이 글에서는

PHP 사전 트리(Trie tree)의 정의와 구현 방법을 설명합니다. 다음과 같이 참고할 수 있도록 모든 사람과 공유하세요.

Trie 트리의 개념(Baidu의 설명): 단어 검색 트리라고도 알려진 사전 트리인 Trie 트리는 트리 구조이며 해시 트리의 변형입니다. 일반적인 응용 프로그램은 많은 수의 문자열(문자열에 국한되지 않음)을 계산, 정렬 및 저장하는 것이므로 검색 엔진 시스템에서 텍스트 단어 빈도 통계를 위해 자주 사용됩니다. 장점은 문자열의 공통 접두사를 사용하여 쿼리 시간을 줄이고 불필요한 문자열 비교를 최소화하며 쿼리 효율성이 해시 트리보다 높다는 것입니다.

제가 이해한 바는 문자열 검색에 사용되는 것입니다. 각 노드에는 하나의 문자만 포함됩니다. 예를 들어 "world"라는 단어를 입력하면 트리의 구조는 다음과 같습니다. "worab"이 입력되면 트리의 구조는 다음과 같습니다.

따라서 각 노드에는 끝 단어인지 식별하기 위한 is_end 필드도 있어야 합니다. 예를 들어, 사용자가 wor를 입력하고 wor로 시작하는 모든 단어를 검색한다고 가정하면, 현재 wor라는 단어가 있고 "r"이 검색되면 is_end라고 판단해야 합니다. "r" 노드가 true이고 wor가 추가됩니다. 결과 목록으로 이동하여 아래에서 계속 검색하세요.

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

위 내용은 모두의 학습에 도움이 되기를 바랍니다.

PHP 사전 트리의 정의 및 구현 방법에 대해

관련 기사