PHP は検索関連付け機能を実装します (辞書ツリー アルゴリズムに基づく)
- 藏色散人転載
- 2020-06-16 14:28:174023ブラウズ
検索関連付け機能は、主要な検索エンジンの基本機能です。次の図に示すように、この機能はユーザーの入力動作を簡素化し、人気のある検索語をユーザーに推奨できます。PHP を使用して検索を実装する方法について説明します。レノボの特徴。
#実装原理
検索関連付け機能は 2 つの部分に分かれています1. クエリが与えられた場合#2. ターゲット クエリ語を並べ替え、重みの高いクエリ語をいくつか選択します
この記事では、最初の部分の実装について説明することに重点を置きます。この問題を解決するためのデータ構造であるトライ ツリー (辞書ツリーとも呼ばれます)。この文字列が接頭辞として付けられたターゲット文字列は、トライ ツリーを通じて簡単かつ迅速に見つけることができます。
トライ ツリーとはトライ ツリー、つまり単語検索ツリーまたはキー ツリーとも呼ばれる辞書ツリーは、ツリー構造とハッシュ バリアントです。木の。一般的なアプリケーションは、多数の文字列 (文字列に限定されません) を数えたり並べ替えたりするためのもので、テキスト ワードの頻度統計のために検索エンジン システムでよく使用されます。その利点は、不必要な文字列比較を最小限に抑え、多くの場合、クエリ効率がハッシュ テーブルよりも高いことです。
Trie の核となるアイデアは、空間を時間と交換することです。文字列の共通プレフィックスを使用してクエリ時間のオーバーヘッドを削減し、効率を向上させます。
これには 3 つの基本プロパティがあります:1. ルート ノードには文字が含まれず、ルート ノードを除く各ノードには 1 文字だけが含まれます。
2. ルートノードからあるノードまで、パス上を通過する文字が接続されて、そのノードに対応する文字列が形成されます。
3. 各ノードのすべての子ノードには、異なる文字が含まれます。
次の文字列がある場合
hello，hi，today，touch，weak
構築されたトライ ツリーは次のようになります。
クエリを実行するときは、ツリーをルートから 1 文字ずつ検索すると、この単語が先頭に付く他のクエリ単語を見つけることができます。
検索関連付け機能を実装するには 2 つの主要なメソッドがあります:
1. クエリ ワード データ セットをトライ ツリーに構築します。
2. 特定のクエリ単語が接頭辞として付いているすべてのクエリ単語を検索します。
ステップ 1: トライ ツリーを構築します文字が存在するため注意してください。は中国語と英語の文字列であるため、次のコードを使用して各文字列が分割され、文字列が文字の配列に変換されます
$charArray = preg_split('/(?<!^)(?!$)/u', $str);
その後、各文字列に対して addWordToTrieTree メソッドが実行されます。
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: プレフィックス ワードをクエリするプレフィックス ワードをクエリします。つまり、文字列が与えられると、 query この文字列が接頭辞として付いているツリー内のすべての文字列が関連付けのプロセスです。
最初に findSubTree メソッドを呼び出して、プレフィックスが配置されているサブツリーをトライから見つけ、次に 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);「Spring Breeze Ten Miles」、「Where is Spring」、「One Million Possibilities」、「One Thousand」を変更します。 Years Later」、「Later」、「Later us」、「In the spring」、「There will no time after」、これらの曲のタイトルは、トライ ツリーを構築してテストするためのデータ セットとして使用されます。
次の出力結果が表示されます。
トライ ツリー:
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 中国語 Web サイトの他の関連記事を参照してください。