PHP는 검색 연관 기능을 구현합니다(사전 트리 알고리즘 기반).
- 藏色散人앞으로
- 2020-06-16 14:28:174086검색
검색 연관 기능은 아래 그림과 같이 사용자의 입력 동작을 단순화하고 인기 검색어를 사용자에게 추천할 수 있는 기능입니다. .
구현 원리
검색 연관 기능은 두 부분으로 나뉩니다
1. 검색어가 주어지면 해당 검색어가 붙은 다른 검색어를 찾습니다
2. 가중치가 높은 여러 쿼리 단어를 선택합니다. 이 기사에서는 첫 번째 부분의 구현에 중점을 둡니다. 여기서는 사전 트리라고도 하는 Trie 트리가 이 문제를 해결하기 위한 데이터 구조로 사용됩니다. 이 문자열이 앞에 붙은 대상 문자열은 Trie 트리를 통해 쉽고 빠르게 찾을 수 있습니다.
트라이 트리란 무엇인가요트라이 트리, 즉 사전 트리는 단어 검색 트리 또는 키 트리라고도 알려져 있으며 트리 구조이며 해시 트리의 변형입니다. 일반적인 응용 프로그램은 많은 수의 문자열(문자열에 국한되지 않음)을 계산하고 정렬하는 데 사용되므로 검색 엔진 시스템에서 텍스트 단어 빈도 통계를 위해 자주 사용됩니다. 장점은 불필요한 문자열 비교를 최소화하고 쿼리 효율성이 해시 테이블보다 높은 경우가 많다는 것입니다.
Trie의 핵심 아이디어는 공간과 시간을 교환하는 것입니다. 문자열의 공통 접두사를 사용하면 쿼리 시간 오버헤드를 줄여 효율성을 높일 수 있습니다.
3가지 기본 속성이 있습니다:1. 루트 노드에는 문자가 포함되지 않으며 루트 노드를 제외한 각 노드에는 문자 하나만 포함됩니다.
2. 루트 노드부터 특정 노드까지 경로를 통과하는 문자들이 연결되어 해당 노드에 해당하는 문자열을 형성합니다.
3. 각 노드의 모든 하위 노드에는 서로 다른 문자가 포함됩니다.
다음 문자열이 있다고 가정합니다
hello，hi，today，touch，weak
그러면 구성된 Trie 트리는 아래와 같습니다
질의할 때 루트에서 문자만큼 트리의 깊이만 순회하면 됩니다. 그러면 단어는 다음과 같이 될 수 있습니다. 접두사에 대한 다른 검색어를 찾으세요.
검색 연관 기능을 구현하는 데는 두 가지 핵심 방법이 있습니다.
1. 검색어 데이터 세트를 Trie 트리로 구성합니다.
2. 특정 검색어 단어가 앞에 붙은 모든 검색어를 찾습니다.
1단계: Trie 트리 구축문자열에는 중국어와 영어가 있으므로 각 문자열은 다음 코드를 사용하여 분할되고 문자열은 문자 배열로 변환됩니다.$charArray = preg_split('/(?<!^)(?!$)/u', $str);
그런 다음 각 문자열에 대해 addWordToTrieTree 메서드를 실행합니다. 이 방법은 Trie 트리에 단어를 추가합니다.
public function buildTrieTree($strList) {
$tree = [];
foreach($strList as $str) {
$charArray = preg_split('/(?<!^)(?!$)/u', $str);
$tree = $this->addWordToTrieTree($charArray, $tree);
}
return $tree;
}
public function addWordToTrieTree($charArray, $tree) {
if (count($charArray) == 0) {
return [];
}
$char = $charArray[0];
$leftStr = array_slice($charArray, 1);
$tree[$char] = $this->addWordToTrieTree($leftStr, $tree[$char]);
return $tree;
}2단계: 접두어 단어 쿼리
접두어 단어를 쿼리합니다. 즉, 문자열이 주어지면 이 접두사가 붙은 모든 문자열을 쿼리합니다. 연결 과정인 트리의 문자열입니다. 먼저 findSubTree 메서드를 호출하여 Trie에서 접두사가 위치한 하위 트리를 찾은 다음 traverseTree 메서드를 호출하여 하위 트리를 순회하고 모든 문자열을 추출합니다. 여기서도 재귀적 메서드가 사용됩니다.
public function queryPrefix($prefix) {
$charArray = preg_split('/(?<!^)(?!$)/u', $prefix);
$subTree = $this->findSubTree($charArray, $this->tree);
$words = $this->traverseTree($subTree);
foreach($words as &$word) {
$word = $prefix . $word;
}
return $words;
}
public function findSubTree($charArray, $tree) {
foreach($charArray as $char) {
if (in_array($char, array_keys($tree))) {
$tree = $tree[$char];
} else {
return [];
}
}
return $tree;
}
public function traverseTree($tree) {
$words = [];
foreach ($tree as $node => $subTree) {
if (empty($subTree)) {
$words[] = $node;
return $words;
}
$chars = $this->traverseTree($subTree);
foreach($chars as $char) {
$words[] = $node . $char;
}
}
return $words;
}코드 및 테스트 결과
전체 코드:
tree = $this->buildTrieTree($strList);
}
public function queryPrefix($prefix) {
$charArray = preg_split('/(?<!^)(?!$)/u', $prefix);
$subTree = $this->findSubTree($charArray, $this->tree);
$words = $this->traverseTree($subTree);
foreach($words as &$word) {
$word = $prefix . $word;
}
return $words;
}
public function findSubTree($charArray, $tree) {
foreach($charArray as $char) {
if (in_array($char, array_keys($tree))) {
$tree = $tree[$char];
} else {
return [];
}
}
return $tree;
}
public function traverseTree($tree) {
$words = [];
foreach ($tree as $node => $subTree) {
if (empty($subTree)) {
$words[] = $node;
return $words;
}
$chars = $this->traverseTree($subTree);
foreach($chars as $char) {
$words[] = $node . $char;
}
}
return $words;
}
/**
* 将字符串的数组构建成Trie树
*
* @param [array] $strList
* @return void
*/
public function buildTrieTree($strList) {
$tree = [];
foreach($strList as $str) {
$charArray = preg_split('/(?<!^)(?!$)/u', $str);
$tree = $this->addWordToTrieTree($charArray, $tree);
}
return $tree;
}
/**
* 把一个词加入到Trie树中
*
* @param [type] $charArray
* @param [type] $tree
* @return void
*/
public function addWordToTrieTree($charArray, $tree) {
if (count($charArray) == 0) {
return [];
}
$char = $charArray[0];
$leftStr = array_slice($charArray, 1);
$tree[$char] = $this->addWordToTrieTree($leftStr, $tree[$char]);
return $tree;
}
public function getTree() {
return $this->tree;
}
}
$strList = ['春风十里','春天在哪里','一百万个可能','一千年以后','后来','后来的我们','春天里','后会无期'];
$trieTree = new TrieTree($strList);
print_r($trieTree->getTree());
$prefix = '春';
$queryRes = $trieTree->queryPrefix($prefix);
print_r($queryRes);'10마일의 봄바람', '봄은 어디에 있는가', '백만 개의 가능성', '천년 후', '나중에', '나중에'를 비교하세요. Us', 'In Spring', 'There Will Be No Time' 등의 노래 제목은 Trie 트리를 구성하고 테스트하기 위한 데이터 세트로 사용됩니다.
다음과 같은 출력 결과를 볼 수 있습니다.
트리 트리:
Array
(
[春] => Array
(
[风] => Array
(
[十] => Array
(
[里] => Array
(
)
)
)
[天] => Array
(
[在] => Array
(
[哪] => Array
(
[里] => Array
(
)
)
)
[里] => Array
(
)
)
)
[一] => Array
(
[百] => Array
(
[万] => Array
(
[个] => Array
(
[可] => Array
(
[能] => Array
(
)
)
)
)
)
[千] => Array
(
[年] => Array
(
[以] => Array
(
[后] => Array
(
)
)
)
)
)
[后] => Array
(
[来] => Array
(
[的] => Array
(
[我] => Array
(
[们] => Array
(
)
)
)
)
[会] => Array
(
[无] => Array
(
[期] => Array
(
)
)
)
)
)"spring"이라는 접두어가 붙은 문자열을 쿼리합니다
Array
(
[0] => 春风十里
[1] => 春天在哪里
[2] => 春天里
)위 내용은 PHP는 검색 연관 기능을 구현합니다(사전 트리 알고리즘 기반).의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!