Word PHP는 Trie 트리(사전 트리)를 구현합니다.

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

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

이때 "worab"이라는 단어를 입력하면 트리의 구조는

그러므로 각 노드에는 필드도 있어야 합니다. is_end 그것이 끝 단어인지 식별합니다. 예를 들어, 사용자가 wor를 입력하고 wor로 시작하는 모든 단어를 검색한다고 가정하면, 현재 wor라는 단어가 있고, "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] != &#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 = ''){
	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, '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>';  // 输出带上搜索前缀
}

위 내용은 단어 내용을 포함하여 Trie tree(딕셔너리 트리)의 단어 PHP 구현을 소개하고 있는데, PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되길 바랍니다.