搜索话题自动补全功能，使用了什么数据结构和算法

搜索话题自动补全功能使用的数据结构有：1、字典树；2、哈希表；3、堆。使用的算法有：1、字符串匹配；2、快速排序；3、二分查找。字典树是一种树形数据结构，用于高效地存储和检索字符串类型的键值对。

一、搜索话题自动补全功能使用的数据结构有哪些

1、字典树

字典树（Trie）是一种树形数据结构，用于高效地存储和检索字符串类型的键值对。在搜索话题自动补全功能中，每一个节点代表着一个字符，从根节点到叶子节点的路径表示一个完整的关键词。因此，我们可以将搜索话题的所有关键词构建成一个字典树，并进行相关的查询操作。

核心思想：

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

基本性质：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符都不相同。

功能：

• 维护字符串集合（即字典）。
• 向字符串集合中插入字符串（即建树）。
• 查询字符串集合中是否有某个字符串（即查询）。
• 统计字符串在集合中出现的个数（即统计）。
• 将字符串集合按字典序排序（即字典序排序）。
• 求集合内两个字符串的LCP（Longest Common Prefix，最长公共前缀）（即求最长公共前缀）。

2、哈希表

哈希表是一种基于哈希函数实现的数据结构。在搜索话题自动补全功能中，我们可以通过哈希表来快速地进行字符串的查找和插入操作，同时还可以根据需求对数据进行排序、去重等操作。

构造方法：

• 直接定制法：哈希函数为关键字的线性函数如 H（key）=a*key+b，这种构造方法比较简便，均匀，但是有很大限制，仅限于地址大小=关键字集合的情况。
• 数字分析法：假设关键字集合中的每个关键字key都是由s位数字组成（k₁，k₂，……，k_n），分析key中的全体数据，并从中提取分布均匀的若干位或他们的组合构成全体。
• 平方取中法：如果关键字的每一位都有某些数字重复出现频率很高的现象，可以先求关键字的平方值，通过平方扩大差异，而后取中间数位作为最终存储地址。
• 折叠法：如果数字的位数很多，可以将数字分割为几个部分，取他们的叠加和作为hash地址。
• 除留余数法：用的较多，H（key）=key MOD p （p<=m m为表长），很明显，如何选取p是个关键问题。

哈希冲突的解决方法：

• 开放定制法
• 链地址法
• 公共溢出区法
• 再散列法

3、堆

堆是一种基于优先级的数据结构，可以用来维护一组元素的顺序。在搜索话题自动补全功能中，我们可以使用堆来进行搜索结果的排序和过滤操作，以保证得到优异的自动补全结果。

性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

算法实现：

向下调整算法：

• 先设定根节点为当前节点（通过下标获取，标记为cur），比较左右子树的值，找出更小的值，用child来标记。
• 比较child和cur的值，如果child比cur小，则不满足小堆的规则，需要进行交换。
• 如果child比cur大，满足小堆的规则，不需要交换，调整结束。
• 处理完一个节点之后，从当前的child出发，循环之前的过程。

向上调整算法：

• 先设定倒数的名列前茅个叶子节点为当前节点（通过下标获取，标记为cur），找出他的父亲节点，用parent来标记。
• 比较parent和cur的值，如果cur比parent小，则不满足小堆的规则，需要进行交换。
• 如果cur比parent大，满足小堆的规则，不需要交换，调整结束。
• 处理完一个节点之后，从当前的parent出发，循环之前的过程。

二、搜索话题自动补全功能使用的算法有哪些

1、字符串匹配

在匹配查询时，常用的算法有深度优先搜索（DFS）和广度优先搜索（BFS）。不过，由于字典树具有前缀匹配的优势，在实际应用中，更常采用基于字典树的前缀匹配算法。具体来说，我们可以通过遍历字典树，找到与当前输入串前缀相同的节点，然后将该节点下的所有关键词返回给用户。同时，为了提高查询的效率，可以在字典树上维护额外的信息，例如词频、相关度等，根据需要进行相应的排序和过滤操作。

经典的字符串匹配算法：

• 朴素的字符串匹配算法（Naive String Matching Algorithm）：就是穷举法，枚举法，也叫暴力匹配。是最低效最原始的算法。特点为无预处理阶段，对Pattern，可以从T的首或尾开始逐个匹配字母，比较顺序没有限制，最坏时间复杂度O((n-m+1)*m)。方法是使用循环来检查是否在范围n-m+1中存在满足条件P[1..m] = T[s+1..s+m]的有效位移s。
• KMP算法（Knuth-Morris-Pratt）：它的名字是由知名的三位科学家名字组合而成。KMP算法是一种高效的字符串查找算法，它性能高效的原因在于它会利用字符串匹配过程中失败的信息，从而减少字符串查找比较的次数。KMP算法借助了一个辅助的结构部分匹配表，部分匹配表是对搜索词分析产生的一个信息表，部分匹配值是某个字或字母对应的“前缀”和“后缀”的最长共有元素的长度。

2、快速排序

快速排序是一种常见的排序算法，具有时间复杂度为O(nlogn)的优异性能。在搜索话题自动补全功能中，我们可以使用快速排序来对搜索结果进行排序，以提高用户体验和搜索效率。

基本思想：

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键。

实现逻辑：

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

3、二分查找

二分查找是一种常见的查找算法，适用于有序数组或有序列表。在搜索话题自动补全功能中，我们可以利用二分查找算法来加速前缀匹配的搜索过程，提高查询效率。

代码框架：

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = (right + left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

延伸阅读1：自动补全搜索是什么

自动补全搜索，也称为“自动完成搜索”，它会在用户输入搜索关键词的同时，自动填充搜索框中的建议内容。这些建议内容通常是基于用户输入的前缀，以及过去的搜索行为和热门搜索等信息生成的。自动补全搜索可以帮助用户更快地输入搜索关键词，并且可以减少输入错误的可能性。相对于联想搜索，自动补全搜索更依赖于搜索引擎的算法和数据，通常会生成更少的搜索建议。