一种用于搜索的智能提示的方法、模块和系统

1.一种用于搜索的智能提示方法，包括客户端和服务器，客户端与服务器通过网络相连，该方法包括以下步骤：
S21：客户端获取初始字符串；
S22：客户端发送初始字符串至服务器；
S29：服务器接收初始字符串；
S3：服务器根据初始字符串搜索热词获得候选词信息列表；
S41：服务器将候选词信息列表发送至客户端；
S49：客户端接收候选词信息列表；
S5：客户端根据候选词信息列表获取候选词列表；
S91：客户端展示候选词列表；
其特征在于，所述步骤S3包括：
S31：服务器根据分词器拆分初始字符串获得前缀词和后缀词；
S32：服务器根据前缀词和后缀词在同义词库中查找获得前缀同义词和后缀同义词；
S33：服务器遍历热词后缀树查找前缀匹配和或后缀匹配的热词，获得候选词信息列表；
S34：服务器根据用户历史搜索行为数据库的分析计算每个候选词的概率；
其中，所述的前缀词是由分词器将字符串拆分后得到的关键词中的第一个关键词；所述的后缀词是由分词器将字符串拆分后得到的关键词中的最后一个关键词；所述同义词库为服务器用于保存关键词之间同义关联关系的数据库；所述的热词后缀树为服务器根据热词库中的高频搜索热词依据广义后缀树的数据结构而建立；所述的热词库为服务器用于保存热词信息的数据库；所述热词信息包括热词、热词序号和热词搜索频次；所述的前缀匹配为热词的前缀与所述前缀词或前缀同义词相匹配；所述的后缀匹配为热词的后缀与所述后缀词或后缀同义词匹配；所述的用户历史搜索行为数据库用于保存历史行为信息；所述步骤S5包括：
S51：客户端根据本地历史搜索数据库计算候选词信息列表中每个候选词的本地相关度；
S52：客户端根据候选词的本地相关度、候选词信息计算每个候选词的点击预估值；
S53：客户端根据候选词的点击预估值从候选词信息列表选取候选词列表；
其中，所述本地历史搜索数据库为客户端用于保存本地历史搜索信息；所述本地历史搜索信息包括本地历史搜索字符串、本地历史搜索时间、本地历史搜索频次；所述步骤S51包括：
S511：用分词器将本地历史搜索数据库中的本地历史搜索字符串和候选词信息列表中的候选词拆分成关键词列表并计算每个关键词的统计频次；
S512：根据关键词列表中的关键词的统计频次构建关键词空间向量；
S513：根据候选词拆分的关键词在关键词列表中关键词的统计频次构建候选词空间向量；
S514：计算关键词空间向量与候选词空间向量的余弦值，获得候选词的本地相关度。
2.如权利要求1所述的用于搜索的智能提示方法，其特征在于，所述步骤S34包括：
S34a1：服务器在用户历史搜索行为数据库中查找原始字符串与初始字符串相同且点击热词与候选词相同的历史行为信息，获得候选词的点击频次；
S34a2：服务器根据对候选词的点击频次做归一化处理获得候选词的概率；
其中，所述的历史行为信息包括原始字符串、点击热词和点击频次。
3.如权利要求1所述的用于搜索的智能提示方法，其特征在于，所述步骤S34包括：
S34b1：根据候选词在用户历史搜索行为数据库查找历史行为信息；
S34b2：统计该历史行为信息下不同前缀匹配方式和不同后缀匹配方式下的点击频次；
S34b3：对不同前缀匹配方式和不同后缀匹配方式下的点击频次进行自然对数运算获得不同前缀匹配方式和不同后缀匹配方式下的logit值；
S34b4：根据二元线性回归参数方程计算公式 中参数
的值；
S34b5：根据公式 计算候选词的概率，其中 ；
S34b6；归一化处理各个候选词的候选词的概率；
其中，所述的历史行为信息包括点击热词、九种候选词匹配类型的点击频次；所述九种候选词匹配类型分别为：非匹配类型、前缀匹配类型、后缀匹配类型、前缀同义匹配类型、后缀同义匹配类型、前缀后缀匹配类型、前缀后缀同义匹配类型、前缀匹配后缀同义类型以及前缀同义后缀匹配类型。
4.如权利要求1所述的用于搜索的智能提示方法，其特征在于，所述步骤S511中所述的计算关键词的统计频次包括按时间加权计算的频次的步骤。
5.如权利要求1所述的用于搜索的智能提示方法，其特征在于，所述步骤S52中：
CTR = A×R×C；其中CTR为候选词的点击预估值；A为候选词的概率；R为候选词的本地相关度；C为根据候选词的类型确定的常数。
6.如权利要求1所述的用于搜索的智能提示方法，其特征在于，所述步骤S52中：
CTR = A×R×C×P；其中CTR为候选词的点击预估值；A为候选词的概率；R为候选词的本地相关度；C为根据候选词的类型确定的常数；P为候选词的搜索频次。
7.一种用于搜索的智能提示系统，包括客户端和服务器，客户端与服务器通过网络相连，其特征在于：
所述的服务器包括：
分词模块，用于拆分初始字符串获得前缀词和后缀词；所述的前缀词是由分词器将字符串拆分后得到的关键词中的第一个关键词；所述的后缀词是由分词器将字符串拆分后得到的关键词中的最后一个关键词；
同义扩展模块，用于根据前缀词和后缀词在同义词库中查找获得前缀同义词和后缀同义词；
后缀树遍历模块，用于遍历热词后缀树查找前缀匹配和或后缀匹配的热词，获得候选词信息列表；所述的前缀匹配为热词的前缀与所述前缀词或前缀同义词相匹配；所述的后缀匹配为热词的后缀与所述后缀词或后缀同义词匹配；
热词库构建模块，用于管理和维护用于保存热词信息的数据库；
后缀树构建模块，用于管理和维护热词后缀树；所述的热词后缀树为服务器根据热词库中的高频搜索热词依据广义后缀树的数据结构而建立；
历史行为分析模块，用于根据用户历史搜索行为数据库的分析计算每个候选词的概率；
用户历史搜索行为数据库模块，用于保存历史行为信息；
所述的客户端包括：
本地相关度计算模块，用于根据本地历史搜索数据库计算候选词信息列表中每个候选词的本地相关度；
点击预估值计算模块，用于根据候选词的本地相关度、候选词信息计算每个候选词的点击预估值；
候选词选取模块，用于根据候选词的点击预估值从候选词信息列表选取候选词列表；
本地历史搜索数据库存储模块，用于保存本地历史搜索信息，所述的本地历史搜索信息包括本地历史搜索字符串、本地历史搜索时间、本地历史搜索频次；
所述的本地相关度计算模块包括：
关键词分布统计模块，用于用分词器将本地历史搜索数据库中的本地历史搜索字符串和候选词信息列表中的候选词拆分成关键词列表并计算每个关键词的统计频次；
关键词空间向量构建模块，用于根据关键词列表中的关键词的统计频次构建关键词空间向量；
候选词空间向量构建模块，用于根据候选词拆分的关键词在关键词列表中关键词的统计频次构建候选词空间向量；
向量余弦计算模块，用于计算关键词空间向量与候选词空间向量的余弦值，获得候选词的本地相关度。

一种用于搜索的智能提示的方法、模块和系统\n技术领域\n[0001] 本发明涉及数据搜索、数据挖掘中的关键词搜索，尤其涉及关键词输入中的人工智能。\n背景技术\n[0002] 智能提示是一种帮助用户明确输入意图，方便用户快捷输入，提高用户体验的方法。智能提示主要应用于搜索引擎和开发平台中，可以根据用户的输入，通过下拉框或者标签等不同的展现形式，向用户进行自动提示。\n[0003] 目前主流搜索引擎主要是先统计服务器端保存的用户搜索历史数据，根据搜索词的搜索频率，建立热门词词典，当用户输入关键词后，根据字符串前缀匹配的方法，从热门词词典中查找候选提示词，再根据搜索频率筛选出提示词，依次展现在搜索框下方。这种智能提示，利用字符串前缀匹配查找候选提示词，可能会遗漏一些与搜索关键词相关的候选提示词。利用热门词词典中搜索频率筛选候选提示词，没有结合当前用户本地的搜索历史数据，可能会导致给出的提示词与用户搜索意图偏差。出现上述问题的根源在于习惯性语言表达方式。在中文中，修饰名词的词总是在被修饰词之前。比如“休闲裤”，其中“休闲”只是修饰词，而“裤”才是主要的名词。用户在客户端输入“休闲裤”后，按前缀匹配的方式筛选出的都是与“休闲”相关的内容。但实际上用户主要是想查找与“裤”相关的内容。这导致提示词与用户搜索意图出现明显偏差。\n发明内容\n[0004] 本发明所要解决的问题是搜索引擎中提示词合理性的问题。\n[0005] 为解决上述问题，本发明采用的方案如下：\n[0006] 根据本发明的一种用于搜索的智能提示方法，包括客户端和服务器，客户端与服务器通过网络相连，该方法包括以下步骤：\n[0007] S21：客户端获取初始字符串；\n[0008] S22：客户端发送初始字符串至服务器；\n[0009] S29：服务器接收初始字符串；\n[0010] S3：服务器根据初始字符串搜索热词获得候选词信息列表；\n[0011] S41：服务器将候选词信息列表发送至终端；\n[0012] S49：客户端接收候选词信息列表；\n[0013] S5：客户端根据候选词信息列表获取候选词列表；\n[0014] S91：客户端展示候选词列表；\n[0015] 其特征在于，所述步骤S3包括：\n[0016] S31：服务器根据分词器拆分初始字符串获得前缀词和后缀词；\n[0017] S32：服务器根据前缀词和后缀词在同义词库中查找获得前缀同义词和后缀同义词；\n[0018] S33：服务器遍历热词后缀树查找前缀匹配和或后缀匹配的热词，获得候选词信息列表；\n[0019] 其中，所述同义词库为服务器用于保存关键词之间同义关联关系的数据库；所述的热词后缀树为服务器根据热词库中的高频搜索热词依据广义后缀树的数据结构而建立；\n所述的热词库为服务器用于保存热词信息的数据库；所述热词信息包括热词、热词序号和热词搜索频次；所述的前缀匹配为热词的前缀与所述前缀词或前缀同义词相匹配；所述的后缀匹配为热词的后缀与所述后缀词或后缀同义词匹配。\n[0020] 进一步，根据本发明的用于搜索的智能提示方法，其特征在于，该方法还包括：\n[0021] S34：服务器根据用户历史搜索行为数据库的分析计算每个候选词的概率；\n[0022] 其中，所述的用户历史搜索行为数据库用于保存历史行为信息。\n[0023] 进一步，根据本发明的用于搜索的智能提示方法，其特征在于，所述步骤S34包括：\n[0024] S34a1：服务器在用户历史搜索行为数据库中查找原始字符串与初始字符串相同且点击热词与候选词相同的历史行为信息，获得候选词的点击频次；\n[0025] S34a2：服务器根据对候选词的点击频次做归一化处理获得候选词的概率；\n[0026] 其中，所述的历史行为信息包括原始字符串、点击热词和点击频次。\n[0027] 进一步，根据本发明的用于搜索的智能提示方法，其特征在于，所述步骤S34包括：\n[0028] S34b1：根据候选词在用户历史搜索行为数据库查找历史行为信息；\n[0029] S34b2：统计该历史行为信息下不同前缀匹配方式和不同后缀匹配方式下的点击频次；\n[0030] S34b3：对不同前缀匹配方式和不同后缀匹配方式下的点击频次进行自然对数运算获得不同前缀匹配方式和不同后缀匹配方式下的logit值；\n[0031] S34b4：根据二元线性回归参数方程计算公式 中参数\n的值；\n[0032] S34 b5 ：根据公式 计算候选 词的 概率 ，其中\n；\n[0033] S34b6；归一化处理各个候选词的候选词的概率；\n[0034] 其中，所述的历史行为信息包括点击热词、九种候选词匹配类型的点击频次。\n[0035] 进一步，根据本发明的用于搜索的智能提示方法，其特征在于，所述步骤S5包括：\n[0036] S51：客户端根据本地历史搜索数据库计算候选词信息列表中每个候选词的本地相关度；\n[0037] S52：客户端根据候选词的本地相关度、候选词信息计算每个候选词的点击预估值；\n[0038] S53：客户端根据候选词的点击预估值从候选词信息列表选取候选词列表；\n[0039] 其中，所述本地历史搜索数据库为客户端用于保存本地历史搜索信息；所述本地历史搜索信息包括本地历史搜索字符串、本地历史搜索时间、本地历史搜索频次；所述步骤S51包括：\n[0040] S511：用分词器将本地历史搜索数据库中的本地历史搜索字符串和候选词信息列表中的候选词拆分成关键词列表并计算每个关键词的统计频次；\n[0041] S512：根据关键词列表中的关键词的统计频次构建关键词空间向量；\n[0042] S513：根据候选词拆分的关键词在关键词列表中关键词的统计频次构建候选词空间向量；\n[0043] S514：计算关键词空间向量与候选词空间向量的余弦值，获得候选词的本地相关度。\n[0044] 进一步，根据本发明的用于搜索的智能提示方法，其特征在于，所述步骤S511中所述的计算关键词的统计频次包括按时间加权计算的统计频次的步骤。\n[0045] 进一步，根据本发明的用于搜索的智能提示方法，其特征在于，所述步骤S52中：\n[0046] CTR = A×R×C；其中CTR为候选词的点击预估值；A为候选词的概率；R为候选词的本地相关度；C为根据候选词的类型确定的常数。\n[0047] 进一步，根据本发明的用于搜索的智能提示方法，其特征在于，所述步骤S52中：\n[0048] CTR = A×R×C×P；其中CTR为候选词的点击预估值；A为候选词的概率；R为候选词的本地相关度；C为根据候选词的类型确定的常数；P为候选词的搜索频次；其中所述的候选词信息还包括候选词的搜索频次。\n[0049] 根据本发明的一种用于搜索的智能提示装置，其特征在于，包括：\n[0050] 分词装置，用于拆分初始字符串获得前缀词和后缀词；\n[0051] 同义扩展装置，用于根据前缀词和后缀词在同义词库中查找获得前缀同义词和后缀同义词；\n[0052] 后缀树遍历装置，用于遍历热词后缀树查找前缀匹配和或后缀匹配的热词，获得候选词信息列表；所述的前缀匹配为热词的前缀与所述前缀词或前缀同义词相匹配；所述的后缀匹配为热词的后缀与所述后缀词或后缀同义词匹配；\n[0053] 热词库构建装置，用于管理和维护用于保存热词信息的数据库；\n[0054] 后缀树构建装置，用于管理和维护热词后缀树；所述的热词后缀树为服务器根据热词库中的高频搜索热词依据广义后缀树的数据结构而建立；\n[0055] 历史行为分析装置，用于根据用户历史搜索行为数据库的分析计算每个候选词的概率；\n[0056] 用户历史搜索行为数据库装置，用于保存历史行为信息。\n[0057] 进一步，根据本发明的一种用于搜索的智能提示系统，包括客户端和服务器，客户端与服务器通过网络相连，其特征在于：\n[0058] 所述的服务器包括：\n[0059] 分词模块，用于拆分初始字符串获得前缀词和后缀词；\n[0060] 同义扩展模块，用于根据前缀词和后缀词在同义词库中查找获得前缀同义词和后缀同义词；\n[0061] 后缀树遍历模块，用于遍历热词后缀树查找前缀匹配和或后缀匹配的热词，获得候选词信息列表；所述的前缀匹配为热词的前缀与所述前缀词或前缀同义词相匹配；所述的后缀匹配为热词的后缀与所述后缀词或后缀同义词匹配；\n[0062] 热词库构建模块，用于管理和维护用于保存热词信息的数据库；\n[0063] 后缀树构建模块，用于管理和维护热词后缀树；所述的热词后缀树为服务器根据热词库中的高频搜索热词依据广义后缀树的数据结构而建立；\n[0064] 历史行为分析模块，用于根据用户历史搜索行为数据库的分析计算每个候选词的概率；\n[0065] 用户历史搜索行为数据库模块，用于保存历史行为信息；\n[0066] 所述的客户端包括：\n[0067] 本地相关度计算模块，用于根据本地历史搜索数据库计算候选词信息列表中每个候选词的本地相关度；\n[0068] 点击预估值计算模块，用于根据候选词的本地相关度、候选词信息计算每个候选词的点击预估值；\n[0069] 候选词选取模块，用于根据候选词的点击预估值从候选词信息列表选取候选词列表；\n[0070] 本地历史搜索数据库存储模块，用于保存本地历史搜索信息，所述的本地历史搜索信息包括本地历史搜索字符串、本地历史搜索时间、本地历史搜索频次；\n[0071] 所述的本地相关度计算模块包括：\n[0072] 关键词分布统计模块，用于用分词器将本地历史搜索数据库中的本地历史搜索字符串和候选词信息列表中的候选词拆分成关键词列表并计算每个关键词的统计频次；\n[0073] 关键词空间向量构建模块，用于根据关键词列表中的关键词的统计频次构建关键词空间向量；\n[0074] 候选词空间向量构建模块，用于根据候选词拆分的关键词在关键词列表中关键词的统计频次构建候选词空间向量；\n[0075] 向量余弦计算模块，用于计算关键词空间向量与候选词空间向量的余弦值，获得候选词的本地相关度。\n[0076] 本发明的技术效果如下：\n[0077] 1、本发明中，提示词通过前缀词和后缀词匹配获得，并结合了同义词，因此更容易接近语言所表达的含义。\n[0078] 2、本发明中，前缀词和后缀词的匹配通过构建热词广义后缀树实现，并结合热词序号，使得搜索过程快捷，消耗的CPU时间少。\n[0079] 3、本发明中，最终提示词结合了概率计算，计算的概率综合了众多用户搜索的意图，从而使得提示词更接近用户搜索意图。\n[0080] 4、本发明中，最终提示词结合了本地相关度，通过用户搜索历史分析用户搜索意图，从而使得提示词更接近用户搜索意图。\n具体实施方式\n[0081] 下面对本发明的发明内容和权利要求作进一步详细说明。\n[0082] 一、本发明的应用场合与应用环境\n[0083] 本发明应用于搜索引擎的智能提示。搜索时，用户通过网页的文本编辑框输入需要搜索的字符串，然后根据本发明的装置、方法或系统，在网页的文本编辑框下以下拉框的形式显示用户可能搜索的多个提示词，用户选择下拉框中的提示词后，搜索引擎根据提示词进行搜索。当然，出现提示词的下拉框后，用户也可以不选择下拉框继续输入文本，然后搜索引擎根据输入的文本进行搜索。采用智能提示的下拉框的好处是方便用户输入，减少用户文本输入的人工和耗时。提示词的获取主要过程可以归纳成如下步骤：\n[0084] S21：客户端获取初始字符串；\n[0085] S22：客户端发送初始字符串至服务器；\n[0086] S29：服务器接收初始字符串；\n[0087] S3：服务器根据初始字符串搜索热词获得候选词信息列表；\n[0088] S41：服务器将候选词信息列表发送至终端；\n[0089] S49：客户端接收候选词信息列表；\n[0090] S5：客户端根据候选词信息列表获取候选词列表；\n[0091] S91：客户端展示候选词列表；\n[0092] 上述过程中，客户端可以主要以网页形式出现。当然也可以制作成专用的应用程序实现。网页形式的客户端一般安装在用户终端上。用户以网页的方式访问搜索引擎的服务器。当然，本发明中，客户端也可以安装在服务器侧。客户端位于服务器侧的情形还可以理解为某应用程序划分成客户端模块和服务端模块，客户端模块和服务端模块分别为本发明的客户端和服务器。此时，客户端模块和服务端模块之间用于连接两者的“网络”可以理解成更为广泛的通信方式，比如通过本地内存，或管道（Pipe），或套接字（Socket）等等。\n[0093] 上述过程中，步骤S21中“客户端获取初始字符串”可以理解成前述“用户通过网页的文本编辑框输入需要搜索的字符串”。根据前述对客户端的理解，“客户端获取初始字符串”的步骤还可以通过其他形式。一般来说，客户端获取的初始字符串是由人工输入的字符串，而且是用户输入过程中由客户端获取的，通常并非用户最终需要搜索的字符串。\n[0094] 上述过程中，步骤S91中“客户端展示候选词列表”可以理解为前述的“在网页的文本编辑框下以下拉框的形式显示用户可能搜索的多个提示词”，候选词也即为提示词，多个提示词构成了候选词列表。\n[0095] 上述过程可以理解为本发明的现有技术，因为很多搜索引擎也确实按照上述步骤实现智能提示的过程。本发明解决本发明所要解决的问题通过步骤S3和步骤S5的具体实施实现。本说明书后续的说明内容主要针对步骤S3和步骤S5的具体实施以及和步骤S3、S5相关的技术内容。而对于上述过程中的其他步骤，本领域技术人员可以理解，本说明书不再详述。\n[0096] 二、本说明书中的基本概念\n[0097] 本发明所指的关键词是由分词器将字符串拆分后得到的能够表达一定语义的词。\n比如“休闲裤”拆分后的得到两个关键词，“休闲”和“裤”。\n[0098] 本发明所指的前缀词是由分词器将字符串拆分后得到的关键词中的第一个关键词。比如“休闲裤”拆分后的得到两个关键词，“休闲”和“裤”。其中“休闲”为前缀词。\n[0099] 本发明所指的后缀词是由分词器将字符串拆分后得到的关键词中的最后一个关键词。比如“休闲裤”拆分后的得到两个关键词，“休闲”和“裤”。其中“裤”为后缀词。\n[0100] 本领域技术人员理解，如果字符串通过分词器拆分后只能得到一个关键词，则该关键词即是前缀词又是后缀词。\n[0101] 本发明所指的候选词为由一个或多个关键词构成的字符串。\n[0102] 本发明所指的候选词列表可以理解为多个候选词组成的数组。\n[0103] 本发明所指的候选词信息包括候选词和候选词的属性信息或者仅仅是候选词。候选词的属性信息可以包括候选词的搜索频次、候选词的概率和/或候选词本地相关度。\n[0104] 本发明所指的候选词信息列表可以理解为多个候选词信息组成的数组。\n[0105] 本发明所指的分词器为用于将字符串拆分成多个关键词的模块或装置，主要通过词典查找将字符串拆分成多个关键词。本领域技术人员理解，分词器为现有技术。在本发明的具体实施过程中，分词器可以通过市场购买获得，也可以自己构造。\n[0106] 本发明所指的热词为由一个或多个关键词构成的字符串，为服务器用于保存用户搜索历史的字符串。\n[0107] 本发明所指的热词信息包括热词、热词序号、热词搜索频次。其中热词序号用于建立快速查找的索引，热词搜索频次用于统计热词被搜索的次数。\n[0108] 三、实施例1\n[0109] 本实施例中，前述步骤S3通过以下步骤实现：\n[0110] S31：服务器根据分词器拆分初始字符串获得前缀词和后缀词；\n[0111] S32：服务器根据前缀词和后缀词在同义词库中查找获得前缀同义词和后缀同义词；\n[0112] S33：服务器遍历热词后缀树查找前缀匹配和或后缀匹配的热词，获得候选词信息列表。\n[0113] 本实施例中，同义词库为服务器用于保存关键词之间同义关联关系的数据库。同义词库通常由商业词典提供，也可以自己建立。\n[0114] 本实施例中，步骤S31由分词模块或装置实现。分词模块或装置也即前述的分词器。本领域技术人员理解，经步骤S31处理后的前缀词和后缀词可能是相同。在前缀词和后缀词相同的情形下，前缀同义词和后缀同义词也相同，因此步骤S32可以做简化处理，只需要搜索前缀词的同义词或后缀词的同义词即可。\n[0115] 本实施例中，步骤S32由同义扩展模块或装置实现。本领域技术人员理解，一个词的同义词可能有多个，因此步骤S32得到的得前缀同义词和后缀同义词通常为一列表。\n[0116] 本实施例中，步骤S33由后缀树遍历模块或装置实现。这里，前缀匹配为热词的前缀与所述前缀词或前缀同义词相匹配；后缀匹配为热词的后缀与所述后缀词或后缀同义词匹配。“前缀匹配和或后缀匹配”中的“和或”表示的是搜索的热词可能满足前缀匹配或者后缀匹配或者前缀后缀均匹配。后缀树遍历模块或装置通过遍历热词后缀树实现。热词后缀树为服务器根据热词库中的高频搜索热词依据广义后缀树的数据结构而建立。热词后缀树的建立通过后缀树构建模块或装置实现。后缀树构建模块或装置，用于管理和维护热词后缀树。总所周知，后缀树（Suffix tree）是用于用来支持有效的字符串匹配和查询的树形的数据结构。后缀树可以表达一字符串，而广义后缀树可以表达多个字符串。广义后缀树的构建和遍历均为现有技术，本说明书不再累述。需要说明的是，热词后缀树中的热词来自热词库，但热词后缀树中的热词并不包含热词库中所有的热词，只是热词库中高频搜索的热词。\n高频搜索的热词可以通过对热词库中所有的热词根据热词的搜索频次排序获得：首先根据热词的搜索频次对热词库中的热词进行按降序排序，然后获取排序后的热词中前N个热词。\nN在实际应用中通常为事先设定，比如10000或100000等。更为高效的方法还可以在排序前做一次按热词的搜索频次的阈值过滤，只有热词的搜索频次大于某一设定阈值的热词才进行排序。\n[0117] 本实施例中，前述的热词库为服务器用于保存热词信息的数据库，该数据也用于保存用户搜索历史。保存用户搜索历史由热词库构建模块或装置实现。热词库构建模块或装置用于管理和维护用于保存热词信息的数据库。热词信息包括热词、热词序号、热词搜索频次。保存用户搜索历史的过程如下：用户通过客户端向服务器提交被搜索的字符串请求搜索后，服务器接收到被搜索的字符串后在执行搜索的同时，还执行将被搜索的字符串作为热词加入至热词库中的步骤：如果热词库中已经保存有该被搜索的字符串，则将相应的热词搜索频次加1，否则将保存被搜索的字符串至热词库，并将该热词的搜索频次设为1。\n[0118] 需要说明的是，步骤S33获得的候选词信息列表为多个候选词信息组成的数组。本实施例中，候选词信息仅仅是热词，而步骤S5中获得的候选词列表即为候选词信息列表。在其他实施方式下以及后续的实施例候选词信息可以包括更多的内容：比如候选词的热词序号、候选词的属性信息。\n[0119] 四、实施例2\n[0120] 本实施例建立在实施例1的基础上，具体为，在实施例1的步骤S33后增加了一个步骤，即步骤S34：服务器根据用户历史搜索行为数据库的分析计算每个候选词的概率。\n[0121] 本实施例的步骤S34由历史行为分析装置或装置实现，所要解决的问题在于对某一特定的候选词用户历史搜索的统计分析得到用户输入初始字符串的条件下用户意图输入该候选词的概率。本实施例的输入是步骤S33获得的候选词信息列表，输出也为候选词信息列表，不过输出的候选词信息列表中的候选词信息增加了候选词的概率。\n[0122] 候选词的概率的计算通过用户历史搜索行为分析计算获得。用户历史搜索行为数据保存在用户历史搜索行为数据库中，该过程由用户历史搜索行为数据库的装置或模块实现。用户历史搜索行为数据库保存了历史行为信息。实现步骤S34的方法有很多种。本发明说明书提供了两种其中的实施方式：实施方式1和实施方式2。其中实施方式1为一种简单的实施方式。实施方式2为通过逻辑回归算法对候选词的匹配类型统计分析的方法。\n[0123] 实施方式1\n[0124] 设历史行为信息包括原始字符串、点击热词和点击频次。服务器在用户历史搜索行为数据库中查找原始字符串与初始字符串相同且点击热词与候选词相同的历史行为信息。历史行为信息中的点击频次可以作为候选词的概率。由于点击频次是大于0的整数，而一般意义上的概率为0~1之间的值，为此还可以对各个候选词点击频次做归一化处理后作为候选词的概率，点击频次归一化处理可以参考如下方法：设候选词信息列表中包括有K个候选词，各个候选词的点击频次分别为： ，则第i个候选词的概率为：\n。本实施方式下，上述过程可以归纳为：\n[0125] S34a1：服务器在用户历史搜索行为数据库中查找原始字符串与初始字符串相同且点击热词与候选词相同的历史行为信息，获得候选词的点击频次；\n[0126] S34a2：服务器根据对候选词的点击频次做归一化处理获得候选词的概率。\n[0127] 本实施方式下，历史行为信息通过以下方法生成：当客户端执行步骤S91后，用户可以选择步骤S91中展示的候选词列表。用户选择步骤S91中展示的候选词列表后，初始字符串和被选中的候选词同时发送至服务器，并请求检索。服务器收到初始字符串和被选中的候选词后，执行检索和前述将被选中的候选词加入至热词库步骤的同时，还执行将初始字符串和被选中的候选词加入用户历史搜索行为数据库的步骤。这里，初始字符串即为历史行为信息中的原始字符串，被选中的候选词即为点击热词。初始字符串和被选中的候选词加入用户历史搜索行为数据库的通过如下方法实现：如果用户历史搜索行为数据库中已经保存有原始字符串和点击热词的对应关系记录，则将相应的点击频次加1，否则将保存原始字符串和点击热词至热词库，并将相应的点击频次设为1。\n[0128] 实施方式2\n[0129] 设历史行为信息包括点击热词、九种候选词匹配类型的点击频次。九种候选词匹配类型包括五种基本类型：非匹配类型、前缀匹配类型、后缀匹配类型、前缀同义匹配类型、后缀同义匹配类型；以及四种组合类型：前缀后缀匹配类型、前缀后缀同义匹配类型、前缀匹配后缀同义类型以及前缀同义后缀匹配类型。上述九种候选词的匹配类型归结成两个独立变量：x1和x2。x1表示前缀匹配方式，可能的值为前缀不匹配、前缀同义匹配、前缀匹配，分别用1、4、5数值表示。x2表示后缀匹配方式，可能的值为后缀不匹配、后缀同义匹配、后缀匹配，分别用1、4、5数值表示。则候选词选中的概率为：\n[0130] ，其中 ， 为待定参数。\n下述为 待定参数的计算方法。\n[0131] 候选词不选中的概率为：\n[0132]\n[0133] 候选词选中的概率和候选词不选中的概率的比值为：\n[0134] 。\n[0135] logit变换后得到：\n[0136] 。\n[0137] 本实施方式下，根据历史行为信息中的各种候选词匹配类型的点击频次可以得到logit的值以及x1和x2的值。\n[0138] 设一点击热词对应的历史行为信息中九种候选词匹配类型的点击频次保存的值为：\n[0139] {73，98，119，67，89，342，137，123，99}。\n[0140] 则可以得到如下表格的数据：\n[0141]\nx1 x2 点击频次 logit值\n1（前缀不匹配） 1（后缀不匹配） 73 4.29 \n1（前缀不匹配） 4（后缀同义匹配） 89+137+123=349 5.86 \n1（前缀不匹配） 5（后缀匹配） 119+342+99=560 6.33 \n4（前缀同义匹配） 1（后缀不匹配） 67+137+99=303 5.71 \n4（前缀同义匹配） 4（后缀同义匹配） 137 4.92 \n4（前缀同义匹配） 5（后缀匹配） 99 4.60 \n5（前缀匹配） 1（后缀不匹配） 98＋342＋123＝563 6.33 \n5（前缀匹配） 4（后缀同义匹配） 123 4.81 \n5（前缀匹配） 5（后缀匹配） 342 5.83\n[0142] 根据上述表格的数据，采用二元线性回归参数方程即可得到该点击热词的参数值。然后再根据前述的候选词选中的概率计算得到当前候选词的概率。\n进一步得到候选词的概率还可以做归一化处理。本实施方式下，上述过程可以概括为以下步骤：\n[0143] S34b1：根据候选词在用户历史搜索行为数据库查找历史行为信息；\n[0144] S34b2：统计该历史行为信息下不同前缀匹配方式和不同后缀匹配方式下的点击频次；\n[0145] S34b3：对不同前缀匹配方式和不同后缀匹配方式下的点击频次进行自然对数运算获得不同前缀匹配方式和不同后缀匹配方式下的logit值；\n[0146] S34b4：根据二元线性回归参数方程计算公式 中参数\n的值；\n[0147] S34b5：根据公式 计算候选词的概率，其中 ；\n[0148] S34b6；归一化处理各个候选词的候选词的概率。\n[0149] 本实施方式下，用户历史搜索行为数据库可以是独立的数据库；也可以与前述的热词库为合并为同一个，即用前述的热词库保存历史行为信息。在采用热词库保存历史行为信息的方式下，热词库还保存了历史行为信息中的各种候选词匹配类型的点击频次，热词库中的热词即为前述历史行为信息中的点击热词，九种候选词匹配类型的点击频次的总和即为前述实施例1中的热词的搜索频次。本实施方式下，作为步骤S34输入的、步骤S33输出的候选词信息列表中的候选词信息至少包含了两项内容：热词序号和候选词的匹配类型。前述的热词后缀树的叶节点保存了热词序号，当执行步骤S33时，遍历热词后缀树匹配得到的候选词附带上了热词后缀树叶节点保存的热词序号并且根据匹配的方式，遍历热词后缀树匹配得到的候选词信息中还附上了候选词的匹配类型。\n[0150] 本实施方式下，历史行为信息通过保存用户搜索历史的过程实现。本实施方式中的保存用户搜索历史的过程与前述实施例1中的保存用户搜索历史的过程的区别在于：本实施方式下，还需要根据候选词的匹配类型进行搜索频次的分类计数。本实施方式下，用户选择步骤S91中展示的候选词列表后，初始字符串和被选中的候选词同时发送至服务器，并请求检索（该过程参见前述本实施例的实施方式1）。\n[0151] 通过对上述两种实施方式，本领域技术人员理解，不同的步骤S34实现通常需要不同的数学方法，而类似的现有的数学估计方法有很多种，因此实现步骤S34的方法还有很多种。本领域人员理解，步骤S34得到的候选词的概率只不过是估计值，实际也不可能达到完全精确，因此应当允许误差存在，也应允许上述两种实施方式下参数的不同。本领域技术人员理解，上述步骤S34计算候选词的概率过程只是为后续的处理做输入，因此实际应用中还可以将上述得到的候选词的概率与候选词的搜索频次的乘积作为候选词的概率。\n[0152] 五、实施例3\n[0153] 本实施例建立在实施例1或实施例2的基础上，具体为，在实施例1或实施例2的基础上对其中的步骤S5做进一步的改进和优化。本实施例中，步骤S5包括以下步骤：\n[0154] S51：客户端根据本地历史搜索数据库计算候选词信息列表中每个候选词的本地相关度；\n[0155] S52：客户端根据候选词的本地相关度、候选词信息计算每个候选词的点击预估值；\n[0156] S53：客户端根据候选词的点击预估值从候选词信息列表选取候选词列表；\n[0157] 其中，所述的本地历史搜索数据库为客户端用于保存本地历史搜索信息，所述的本地历史搜索信息包括本地历史搜索字符串、本地历史搜索时间、本地历史搜索频次。步骤S51由本地相关度计算装置或模块实现；步骤S52由点击预估值计算装置或模块实现；步骤S53由\n[0158] 候选词选取装置或模块实现。其中，步骤S51包括以下步骤：\n[0159] S511：用分词器将本地历史搜索数据库中的本地历史搜索字符串和候选词信息列表中的候选词拆分成关键词列表并计算每个关键词的统计频次；\n[0160] S512：根据关键词列表中的关键词的统计频次构建关键词空间向量；\n[0161] S513：根据候选词拆分的关键词在关键词列表中关键词的统计频次构建候选词空间向量；\n[0162] S514：计算关键词空间向量与候选词空间向量的余弦值，获得候选词的本地相关度。\n[0163] 其中，步骤S511由关键词分布统计装置或模块实现；步骤S512由关键词空间向量构建装置或模块实现；S513由候选词空间向量构建装置或模块实现；步骤S514由向量余弦计算装置或模块实现。步骤S511又分为两个步骤：步骤S511a：用分词器将本地历史搜索数据库中的本地历史搜索字符串拆分成关键词列表并计算每个关键词的统计频次以及步骤S511b：用分词器将候选词信息列表中的候选词拆分成关键词列表并计算每个关键词的统计频次。步骤S511a和步骤S511b执行后得到同一个关键词列表。为说明上述步骤51计算候选词的本地相关度的过程，现举例说明。\n[0164] 设有本地历史搜索数据库中的内容为长度为n的数组lhi，并具体定义如下：\n[0165] struct LocalHistInfo\n[0166] {\n[0167] String    sSearch;\n[0168] DateTime  tRecent;\n[0169] int      nCount;\n[0170] } lhi[n];\n[0171] 数组lhi的每个成员为本地历史搜索信息。本地历史搜索信息用结构\nLocalHistInfo表示。其中，sSearch为本地历史搜索字符串；tRecent为本地历史搜索时间，记录的是最近一次搜索的时间；nCount为本地历史搜索频次。步骤S511a可以通过以下过程实现：\n[0172] for (int i=0;i m_arData;\n[0186]     …\n[0187]     int VeckterKey::Add(string sKey, int nCount)\n[0188]     {\n[0189]        KeyItem * pItem=NULL;\n[0190]        bool bFind = FindKey(sKey, pItem); // 查找关键词是否已经存在[0191]        if (!bFind) // 如果不存在则新建关键词\n[0192]        {\n[0193]           pItem = new KeyItem;\n[0194]           pItem->sKey = sKey;\n[0195]           pItem->nCount = nCount;  //统计该关键词的搜索频次\n[0196]           m_arData.Add(pItem);\n[0197]         } else // 否则对关键词\n[0198] pItem->nCount += nCount; //统计该关键词的搜索频次\n[0199]         return bFind;\n[0200]     } // end of Add\n[0201] }; // end of VecterKey\n[0202] 其中KeyItem表示关键词的结构，可以表示为：\n[0203] struct KeyItem\n[0204] {\n[0205]   string sKey;\n[0206]   int  nCount;\n[0207] };\n[0208] 上述结果中sKey为关键词，nCount为关键词对应的统计频次。\n[0209] 同理，步骤S511b也运用上述类似步骤S511a，将候选词候选词拆分后加入到前述的vKey中，不过候选词的本地历史搜索频次可以为固定的1或者服务器热词库保存的热词的搜索频次（参见实施例1）。需要说明的是，上述的本地历史搜索数据库中本地历史搜索字符串加入关键词列表vKey时有一按时间加权的计算频次的步骤TimeWeightCount。本领域技术人员理解，该按时间加权的计算频次的步骤也可以省略。按时间加权的计算频次的步骤为本发明优先的实施方式。按时间加权的计算频次即为根据本地历史搜索时间和当前时间的时间间隔对本地历史搜索频次做出调整。简单的方法可以为：当时间间隔超过1个月则加权系数为1；如果时间间隔在半个月与1个月之间则加权系数为2；时间间隔在一星期与半个月之间则加权系数设为3；如果时间间隔少于一星期则加权系数设为5。\n[0210] 上述步骤S511a和S511b执行完成后，得到关键词列表vKey。提取vKey中所有的关键词的统计频次即可得到步骤S512中的关键词空间向量Ks_Vector = ｛v1，v2，v3，…，vm｝。\n其中m为vKey中关键词的个数，表示为m维度的关键词空间向量；向量的每一维度值vi则对应了每个关键词的统计频次。\n[0211] 对于候选词信息列表中的某个候选词用分词器拆分后可以获得多个关键词用HintKeys表示。假如前述的vKey中的关键词在HintKeys中存在，则设向量值为该关键词的统计频次，否则设为该向量值为0也可以得到m维度的候选词空间向量Hs_Vector = ｛w1，w2，w3，…，wm｝。候选词空间向量Hs_Vector中，如果某一维度wi对应的向量值为0，则wi对应的关键词则不在候选词拆分的关键词列表HintKeys中，否则可以表示该关键词存在于候选词拆分的关键词列表HintKeys中。前述获得候选词空间向量Hs_Vector的过程即为前述的步骤S513。\n[0212] 根据前述步骤S512得到的m维度的关键词空间向量Ks_Vector以及步骤S513得到的m维度的候选词空间向量Hs_Vector运用向量余弦公式即可得到余弦值λ：\n[0213]\n[0214] 采用上述公式计算余弦值λ的过程即为前述步骤S514。余弦值λ即可作为候选词的本地相关度。在实际实施中还可以将上述的各个候选词的余弦值进行归一化处理后作为候选词的本地相关度：设各个候选词的余弦值为{λ1，λ2，λ3，…，λK}，其中K表示有K个候选词，则候选词i对应的本地相关度为： 。\n[0215] 步骤S52中计算候选词的点击预估值过程是步骤S51的后续步骤。步骤S52的输入依赖于步骤S51的本地相关度的计算值。步骤S52候选词的点击预估值过程，本说明书给出了两种实施方式：\n[0216] 实施方式1：CTR = A×R×C；其中CTR为候选词的点击预估值；A为候选词的概率；R