PHP implements search association function (based on dictionary tree algorithm)

The search association function is a basic function of major search engines. As shown in the figure below, this function simplifies the user's input behavior and can recommend popular search terms to users. Let's talk about how to use PHP to implement search. Lenovo features.

Implementation principle

The search association function is broken down into two parts

1. Given a Query words and find other target query words prefixed with it

2. Sort the target query words and select several query words with high weight

This article will focus on explaining The implementation of the first part uses Trie tree, also called dictionary tree, this data structure to solve this problem. The target string prefixed by this string can be easily and quickly found through the Trie tree.

What is a Trie tree

Trie tree, that is, dictionary tree, also known as word search tree or key tree, is a tree structure and a hash Variants of tree. Typical applications are for counting and sorting a large number of strings (but not limited to strings), so they are often used by search engine systems for text word frequency statistics. Its advantages are: minimizing unnecessary string comparisons, and query efficiency is often higher than hash tables.

The core idea of ​​Trie is to exchange space for time. Use the common prefix of strings to reduce query time overhead to improve efficiency.

It has three basic properties:

1. The root node does not contain characters, and each node except the root node only contains one character.

2. From the root node to a certain node, the characters passing on the path are connected to form the string corresponding to the node.

3. All child nodes of each node contain different characters.

If we have the following string

hello，hi，today，touch，weak

The constructed Trie tree is as shown below

When querying, only By deeply traversing the tree character by character starting from the root, you can find other query words that are prefixed by this word.

Code implementation

There are two core methods for implementing the search association function:

1. Construct the query word data set into a Trie Tree

2. Find all query words prefixed by a certain query word

Step 1: Build a Trie tree

Note that because of a character The strings are in Chinese and English, so use the following code to split each string, convert the string into an array of characters

$charArray = preg_split(&#39;/(?<!^)(?!$)/u&#39;, $str);

, and then execute the addWordToTrieTree method on each string. This method will Words are added to the Trie tree, and the recursive method is used here

    public function buildTrieTree($strList) {
        $tree = [];
        foreach($strList as $str) {
            $charArray = preg_split(&#39;/(?<!^)(?!$)/u&#39;, $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;
    }

Step 2: Query the prefix word

Query the prefix word, that is, given a string, query All strings in the tree that are prefixed by this string are the process of association.

First call the findSubTree method to find the subtree where the prefix is ​​located from the Trie, and then call the traverseTree method to traverse the subtree and extract all the strings. The recursive method is also used here.

public function queryPrefix($prefix) {
        $charArray = preg_split(&#39;/(?<!^)(?!$)/u&#39;, $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;
    }

Code and test results

Complete code:

tree = $this->buildTrieTree($strList);
    }
    public function queryPrefix($prefix) {
        $charArray = preg_split(&#39;/(?<!^)(?!$)/u&#39;, $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(&#39;/(?<!^)(?!$)/u&#39;, $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);

Change 'Spring Breeze Ten Miles', 'Where is Spring', 'One Million Possibilities', 'One Thousand Years later', 'Later', 'Later us', 'In the spring', 'There will be no time later', these song titles are used as data sets to construct a Trie tree and test it.

You can see the following output results

Trie tree:

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
                                (
                                )
                        )
                )
        )
)

Query the string prefixed by "spring"

Array
(
    [0] => 春风十里
    [1] => 春天在哪里
    [2] => 春天里
)

The above is the detailed content of PHP implements search association function (based on dictionary tree algorithm). For more information, please follow other related articles on the PHP Chinese website!