PHP實現搜尋聯想功能(基於字典樹演算法)

2020-07-16 10:05:59
搜尋聯想功能是各大搜尋引擎具備的基礎功能,如下圖所示,這個功能簡化了使用者的輸入行為,並且能夠給使用者推薦熱門的搜尋詞,下面我們來講一下如何用php實現搜尋聯想的功能。

企業微信截圖_15922885713947.png

實現原理

搜尋聯想功能拆解一下由兩部分組成

1、給定一個查詢詞,找出以他為字首的其他目標查詢詞

2、對目標查詢詞進行排序,選出權重高的若干個查詢詞

本篇中重點講解一下第一部分的實現,這裡使用Trie樹,也叫字典樹,這個資料結構來解決這個問題。通過Trie樹可以很方便快速的找到已該字串為字首的目標字串。

什麼是Trie樹

Trie樹,即字典樹,又稱單詞查詢樹或鍵樹,是一種樹形結構,是一種雜湊樹的變種。典型應用是用於統計和排序大量的字串(但不僅限於字串),所以經常被搜尋引擎系統用於文字詞頻統計。它的優點是:最大限度地減少無謂的字串比較,查詢效率往往比雜湊表高。

Trie的核心思想是空間換時間。利用字串的公共字首來降低查詢時間的開銷以達到提高效率的目的。

它有3個基本性質:

1、根節點不包含字元,除根節點外每一個節點都只包含一個字元。

2、從根節點到某一節點,路徑上經過的字元連線起來,為該節點對應的字串。

3、每個節點的所有子節點包含的字元都不相同。

假如我們有如下字串

hello,hi,today,touch,weak

那麼構造出來的Trie樹如下圖所示

企業微信截圖_15922885809834.png

當查詢的時候只需要從根開始按字元沿著樹進行深度遍歷,就可以把已該詞為字首的其他查詢詞查詢出來。

程式碼實現

用於實現搜尋聯想功能的核心方法有兩個:

1、將查詢詞的資料集構建成Trie樹

2、查詢以某個查詢詞為字首的所有查詢詞

第一步:構建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;
    }

第二步:查詢字首詞

查詢字首詞即給定一個字串,查詢樹中所有以該串為字首的字串,也就是聯想的過程。

首先呼叫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;
    }

程式碼與測試結果

完整程式碼:

<?php
class TrieTree {
    private $tree;
    public function __construct($strList) {
        $this->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);

將’春風十里’,‘春天在哪裡’,‘一百萬個可能’,‘一千年以後’,‘後來’,‘後來的我們’,‘春天裡’,'後會無期’這些歌名作為資料集,構建一個Trie樹並進行測試。

可以看到輸出以下結果

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

查詢以「春為字首的字串」

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

以上就是PHP實現搜尋聯想功能(基於字典樹演算法)的詳細內容,更多請關注TW511.COM其它相關文章!