PHP 사전 트 리(Trie 트 리)정의 및 구현 방법 예시

이 실례 는 PHP 사전 트 리(Trie 트 리)의 정의 와 실현 방법 을 설명 한다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
트 리 트 리 의 개념(바 이 두 의 해석):사전 나 무 는 단어 찾기 트 리,트 리 트 리 라 고도 부 르 며 나무 구조 로 해시 나무의 변종 이다.전형 적 인 응용 프로그램 은 대량의 문자열 을 통계,정렬,저장 하 는 데 사용 되 기 때문에 검색엔진 시스템 에서 텍스트 주파수 통계 에 자주 사용 된다.문자열 의 공공 접 두 사 를 이용 하여 조회 시간 을 줄 이 고 불필요 한 문자열 비 교 를 최대한 줄 이 며 해시 트 리 보다 조회 효율 이 높다 는 것 이 장점 이다.
제 이 해 는 문자열 검색 을 하 는 데 사 용 됩 니 다.모든 노드 는 하나의 문자 만 포함 합 니 다.예 를 들 어 단어'World'를 입력 하면 나무의 구 조 는 다음 과 같 습 니 다.

이때'worab'이라는 단 어 를 입력 하면 나무의 구 조 는 다음 과 같다.

그래서 각 노드 마다 필드 가 있어 야 합 니 다 isend 표지 가 끝 단어 인지 여부 입 니 다.예 를 들 어 사용자 가 wor 를 입력 하고 모든 wor 로 시작 하 는 단 어 를 검색 합 니 다.현재 하나의 단어 가 wor 라 고 가정 하면'w'부터 검색 하고'r'를 검색 할 때'r'노드 의 is 를 판단 해 야 합 니 다.end 는 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] != ' '){
      $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 = ''){
  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] != ' '){
      $node = $node->searchChildNode($str[$i]);
      // print_r($node);
      if(empty($node)){
        //       
        return false;
      }
    }
  }
  return getChildString($node);
}
/*        */
$head = new Node;  //   head
//     
addString($head, 'hewol');
addString($head, 'hemy');
addString($head, 'heml');
addString($head, 'you');
addString($head, 'yo');
//       
$str_array = getChildString($head);
//   
$search_array = searchString($head, 'hem');
//           
foreach ($search_array as $key => $value) {
  echo 'hem' . $value . '<br>'; //         
}

더 많은 PHP 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.
본 논문 에서 말 한 것 이 여러분 의 PHP 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.