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 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
laravel에 yo에서 angularJs&coffeescript를 사용할 수 있도록 한다.먼저 yo 명령을 사용할 수 있어야하므로 아래에서 설치 global에 설치한 곳에서 laravel의 프로젝트 루트로 이동. 클라이언트 코드를 관리하는 디렉토리를 만들고 이동합니다. 클라이언트 환경 만들기 이것으로 히...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.