站长图库

PHP实现搜索联想功能(基于字典树算法)

 发布时间 2020-06-19 12:30:28 热度 96

 Tag标签:  搜索联想字典树算法

搜索联想功能是各大搜索引擎具备的基础功能,如下图所示,这个功能简化了用户的输入行为,并且能够给用户推荐热门的搜索词,下面我们来讲一下如何用php实现搜索联想的功能。


5eec3f8886e00.jpg

实现原理

搜索联想功能拆解一下由两部分组成

1、给定一个查询词,找出以他为前缀的其他目标查询词

2、对目标查询词进行排序,选出权重高的若干个查询词

本篇中重点讲解一下第一部分的实现,这里使用Trie树,也叫字典树,这个数据结构来解决这个问题。通过Trie树可以很方便快速的找到已该字符串为前缀的目标字符串。

什么是Trie树

Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率往往比哈希表高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质:

1、根节点不包含字符,除根节点外每一个节点都只包含一个字符。

2、从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。

3、每个节点的所有子节点包含的字符都不相同。

假如我们有如下字符串

hello,hi,today,touch,weak

那么构造出来的Trie树如下图所示

5eec3fc2556ae.jpg

当查询的时候只需要从根开始按字符沿着树进行深度遍历,就可以把已该词为前缀的其他查询词查找出来。

代码实现

用于实现搜索联想功能的核心方法有两个:

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实现搜索联想功能(基于字典树算法)的详细内容,希望对大家有所帮助。



评论(0)条

    站长图库

    站长素材 - 建站资源分享平台

    猜你喜欢
    圣诞节雪花背景矢量素材下载

    圣诞节雪花背景矢量素材下载

    背景素材 103 2020-02-05

    圣诞节雪花背景矢量素材,适用于圣诞节场景设计使用。

    Z-BlogPHP响应式网址导航网站源码 微信分类导航主题模板

    Z-BlogPHP响应式网址导航网站源码 微信分类导航主题模板

    行业整站 294 2020-03-13

    Z-BlogPHP响应式网址导航网站源码 微信分类导航主题模板一、整体功能介绍1、网站logo可以在文字和图片之间切换;...

    人人商城V3_3.24.1企业开源完整全解密安装包+小程序前端

    人人商城V3_3.24.1企业开源完整全解密安装包+小程序前端

    微信源码 300 2020-06-29

    人人商城V3_3.24.1企业开源完整全解密安装包+小程序前端人人商城V3_3.24.1更新说明:1、修复 公众号 自定...

    世界杯专题jquery选项卡切换

    世界杯专题jquery选项卡切换

    图片特效 182 2020-01-10

    世界杯专题jquery选项卡切换是一款jquery tab选项卡插件制作的世界杯专题选项卡自动切换代码。