[go: up one dir, main page]

WO2021077585A1 - 一种查询自动补全的方法和装置 - Google Patents

一种查询自动补全的方法和装置 Download PDF

Info

Publication number
WO2021077585A1
WO2021077585A1 PCT/CN2019/126590 CN2019126590W WO2021077585A1 WO 2021077585 A1 WO2021077585 A1 WO 2021077585A1 CN 2019126590 W CN2019126590 W CN 2019126590W WO 2021077585 A1 WO2021077585 A1 WO 2021077585A1
Authority
WO
WIPO (PCT)
Prior art keywords
dictionary tree
query
user
nested
result
Prior art date
Application number
PCT/CN2019/126590
Other languages
English (en)
French (fr)
Inventor
秦建斌
王尧舒
毛睿
Original Assignee
深圳计算科学研究院
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 深圳计算科学研究院 filed Critical 深圳计算科学研究院
Publication of WO2021077585A1 publication Critical patent/WO2021077585A1/zh

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/95—Retrieval from the web
    • G06F16/953—Querying, e.g. by the use of web search engines
    • G06F16/9532—Query formulation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/903—Querying
    • G06F16/9032—Query formulation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/903—Querying
    • G06F16/90335—Query processing
    • G06F16/90344—Query processing by using string matching techniques

Definitions

  • the invention relates to the field of search technology, in particular to a method for automatic query completion and a device for automatic query completion.
  • the query auto-completion technology is an important part of guiding the user to input the query correctly and reducing the characters that need to be input.
  • search engines such as Google, Baidu, etc.
  • users often want to enter a small amount of information and return the results they want. For example, the user enters the query MJ and expects the search engine to return results about Michael Jordan.
  • the query auto-completion will give a suitable suggestion that the query input character is used as the prefix.
  • automatic query completion is often used in various error-prone applications that require a lot of human input, such as command lines, desktop search, and mobile devices. Because of its importance, automatic query completion technology has been widely valued and applied in information extraction and database search.
  • the main purpose of this application is to provide a method for automatic query completion and a device for automatic query completion. It aims to solve the existing automatic query completion method.
  • the user needs to manually separate the search input keywords, and these The method uses the query character as the prefix of the keyword to perform the technical problem of matching operation.
  • this application proposes a method for automatic query completion, which includes:
  • This application also provides a device for automatic query completion, including:
  • the receiving module is used to receive the query prefix from the client
  • the matching module is used to match the character result of the query prefix based on the nested dictionary tree structure
  • the interval list merging module is used to add the character result to the interval list according to the nested dictionary tree node
  • the interval result sorting module is used to sort the interval list according to the analysis of the user's target character string to obtain a result set.
  • the present application also provides an electronic device, including a processor, a memory, and a computer program stored on the memory and capable of running on the processor.
  • the computer program When the computer program is executed by the processor, the method is implemented as described above. Any one of the steps of the method for automatic completion of a query.
  • the present application also provides a computer-readable storage medium on which a computer program is stored, and when the computer program is executed by a processor, the method for automatic query completion as described in any of the above methods is implemented A step of.
  • the embodiment of the present invention includes the following advantages: the embedded dictionary tree can more accurately locate the string range of the matching prefix, supports the automatic query completion technology of keyword reduction, greatly reduces the query length that the user needs to enter, and improves the user Experience the comfort.
  • Figure 1 is a schematic diagram of a nested dictionary tree structure in a specific embodiment of the present invention.
  • Figure 2 is a fast query dictionary tree algorithm in a specific embodiment of the present invention.
  • FIG. 3 is a flowchart of steps of an embodiment of an automatic query completion method of the present invention.
  • Figure 5 is a structural block diagram of an embodiment of an automatic query completion device of the present invention.
  • Fig. 6 is a structural block diagram of another embodiment of an automatic query completion device of the present invention.
  • One of the core concepts of the embodiments of the present invention is to provide a method and device for automatic query completion.
  • One of the methods for automatic query completion includes: receiving a query prefix from a user terminal; and matching based on a nested dictionary tree structure Query the character result of the prefix; add the character result to the interval list according to the nested dictionary tree node; sort the interval list according to the analysis of the user's target string, and get the result set.
  • the embedded dictionary tree can more accurately locate the string range that matches the prefix, and supports automatic query completion technology for keyword reduction, which greatly reduces the length of the query that users need to enter, and improves the comfort of the user experience.
  • ⁇ is a limited set of characters; a string s is an ordered array of characters extracted from ⁇ .
  • represents the length of the string s, and s[i] represents the i-th character in s.
  • s[i..j] represents the substring from the i-th character to the j-th character in s.
  • Use st to represent the string concatenated in the order of s and t.
  • a set of string arrays [s 1 ,s 2 ,..s n ] (n>1), if s s 1 s 2 ..s n concatenation, put [s 1 ,s 2 ,..s n ] A cut called s.
  • S is a string data set
  • each string s ⁇ S can be cut into a set of keywords, assuming that ⁇ contains a set of English letters.
  • the dividing symbol can be spaces, punctuation, uppercase letters, etc. For example, "AddNextValue" is divided into three parts: “Add”, "Next” and "Value”.
  • a string s can be divided into a set of keywords [s1,...,sn].
  • gene is a prefix abbreviation match of the string "GetNextValue", because ge and ne are prefixes of Get and Next. Use PAM to stand for prefix abbreviation matching.
  • a query string q Given a string data set S, a query string q, and a prefix abbreviation query auto-completion (QACPA) is to find all string sets si ⁇ S that satisfies The output result is calculated incrementally based on the user's current input characters.
  • QCPA prefix abbreviation query auto-completion
  • An automatic query completion method disclosed in the present application allows users to enter a link with a reduced keyword prefix as a query, thereby improving experience.
  • an index structure and query method are designed to complete its function.
  • a sorting algorithm combined it in the above query, to ensure the quality of the result output sorting, that is, the top results are most likely to be what users expect.
  • Use the Top-K method to return a small amount, that is, K, and high-quality results.
  • the index data structure in this embodiment is a nested dictionary tree structure, including multiple internal dictionary trees nested in one external dictionary tree.
  • Figure 1 for a schematic diagram of the nested dictionary tree structure.
  • the nodes and edges in the external dictionary tree are called external nodes and edges, and the nodes and edges in the internal dictionary tree are called internal nodes and edges.
  • the root node of the nested dictionary tree is the root node of the outer dictionary tree.
  • the target node of the link is always a subset of the outer edge. Based on this phenomenon, for an external edge, one bit, which is a bit vector, is used for storage. The i-th bit indicates that the destination of the node's link is the same as the destination outside the i-th. This can avoid repeatedly saving edges with the same function.
  • nested dictionary trees combine keywords that share the same initial letter. In the following algorithm description, such a data structure can effectively reduce the number of active nodes. At the same time, the activation node can also be found quickly.
  • an activation node n is a node with at least one path (via an edge or link) from the root node to n that can exactly match the query string input by the user.
  • the algorithm starts from the external root node, and for each character input by the user, it starts from the existing activation node to find a new activation node. Given this input character, it can match the first character or non-first character.
  • Nested dictionary trees can well support such matching. For a non-first character, find a new activation node by walking the inner edge. For an initial letter, a new activation node can be found by walking the outer edge.
  • a shortcut link can be used to jump from an internal node to an external node to generate a new activation node.
  • the data under each node is not all the desired result.
  • In is a sorted interval sequence
  • xi and yj represent two intervals.
  • Property 1 given a path from the root node to n, n1,...,nk.
  • the result of query q is only in among.
  • a fast query dictionary tree algorithm in this embodiment the complexity of this algorithm is: O(log
  • the query in the nested dictionary tree algorithm may not match all the strings under the active node.
  • each node in the dictionary tree is added to a sorted interval list to display a string that matches the description prefix and a path in the dictionary tree.
  • In order to calculate the interval in the list given a string, traverse the nodes in the dictionary tree, and add the ID of the string to the interval list of the corresponding node.
  • a basic method is to use the sweepline algorithm to process interval list merging. Its time complexity is O(
  • S400 Sort the interval list according to the analysis of the user's target character string to obtain a result set.
  • the output result is sorted according to the target character string of the estimated user.
  • S100 before the step of receiving the query prefix from the client, includes:
  • the steps of establishing a nested dictionary tree structure include:
  • the dictionary tree includes an internal dictionary tree and an external dictionary tree.
  • the steps of dividing keywords and building the dictionary tree include:
  • the first letter of the keyword is added to the external dictionary tree, and the other letters of the corresponding keyword are added to the internal dictionary tree.
  • the step of linking dictionary trees together to form a nested dictionary tree structure includes:
  • the step of sorting the interval list according to the analysis of the user's target character string to obtain the result set includes:
  • a given data string s is cut into [s 1 ,...,s n ], assuming that the first m keywords have been abbreviated into the query, and the remaining (nm) keywords are still It has not been entered. Therefore q can be cut into [q 1 ,...,q m ], and satisfies q i ⁇ s i , 1 ⁇ i ⁇ m ⁇ n. Add (nm) an empty string, which is represented by q m+1 ,...,q n . Then q and s will have the same number of cuts.
  • P(q 1 ...q n ) P(q), which is true for all strings matched by PA The same value.
  • P(s) is characterized by the popularity of s. In order to calculate P(q 1 ...q n
  • s 1 ...s n ) P(q 1
  • s i ) describes the probability that the string s i is prefixed when the user enters the query string q i. For characters that are not input, assume P(q i
  • s i ) 1, and m ⁇ i ⁇ n. The reason for this setting is that these keywords will be input as the user next time. In order to prevent the score of s from being too low due to sequence operations, especially when n is much greater than m, set these probability values to 1.
  • l is the number of Gaussian distributions
  • w i is the weight of each Gaussian distribution
  • ⁇ i , ⁇ i ) is the probability density function with ⁇ i as the mean and ⁇ i as the variance matrix and p.
  • the parameter l can be fine-tuned during training.
  • other parameters can be learned in a clustering method and using the EM algorithm: a series of data strings are given by the user, and then all the prefixes of the data are collected and converted into data pairs of keywords and prefixes as the training data feature.
  • S400 after the step of sorting the interval list according to the analysis of the user target character string, and obtaining the result set, further includes:
  • the Top-K algorithm is used to return the target result set according to user requirements.
  • the user when the user enters a query, the user is not interested in all the results, and is usually only interested in the top K results. Under this assumption, the results that are unlikely to enter the top K can be filtered in advance. Estimate the upper limit of the score under a certain activation node. If this upper limit is already lower than the lower limit of the current previous K results, this activation node can be filtered out in advance.
  • the interval list algorithm a merged interval list is obtained as a verification set in each valid node. If you want to get the result of TopK, traverse the interval list in each valid node, calculate the corresponding score value for each string in the interval, and then sort according to the calculated score, and extract the result of Top-K.
  • the biggest cost in the execution of the current method is to use a Gaussian mixture model to calculate the probability P(q i
  • the maximum possible score in the combined interval list is limited. According to the characteristics of the combined list, it has the following characteristics: For each interval [u,v] ⁇ J n , there is always an interval [u',v'] ⁇ I n that satisfies the condition u' ⁇ u and v' ⁇ v. Therefore, the maximum possible score value of the string in the list J n is the upper bound of the list I n. In order to calculate the score for each interval, consider the root node of a dictionary tree as n. Use d to represent the depth of the dictionary tree.
  • This embodiment discloses an online Top-K result extraction algorithm.
  • a priority queue R is initialized to store the results of Top-K.
  • the intervals in the list J n are sorted in descending order of the maximum score.
  • the score of each string is sequentially calculated, and then updated to the priority queue. If an interval is reached and his maximum score is not greater than the k-th result, the processing of n can be safely ended.
  • p (q i
  • s i ) For two adjacent strings s i and s i+1 in an interval [u,v] ⁇ I n , check the number of keywords they share as prefixes offline, and record this value in si+1 , Expressed by s i+1 ⁇ spr.
  • the Gaussian mixture model calculation of the first s i+1 ⁇ spr keyword can be skipped because it has already been calculated pass.
  • the strings in S are sorted in the earlier order.
  • This application allows the user to determine the number of results. If the user expects to get all the results and filter them one by one, they can skip the above step of S500 using Top-K algorithm to return the target result set according to user needs. If the user only wants a limited number of high-quality results, then the above return to the user most wanted K results required.
  • the method for query automatic completion disclosed in the present application is based on a model of prefix abbreviation matching of query completion technology, and the prefix matching model of query automatic completion technology is a new algorithm in automatic completion technology.
  • this application fully takes into account various scenarios, especially the user will not display the separator of the keyword.
  • This application can save 20% of the number of characters input by the user.
  • Embedded dictionary tree is a new data structure that supports automatic completion technology. Compared with the traditional dictionary tree index structure, the embedded dictionary tree of the present application can more accurately locate the string range of the matching prefix. In order to return more meaningful results, a sorting algorithm is designed.
  • This sorting algorithm uses the probability of the query string relative to the segmentation of the data string to calculate, and uses the Bayesian formula and the Gaussian mixture model structure to calculate its probability value.
  • the sorting algorithm can return the result that the user wants more.
  • two Top-K optimization algorithms are designed, namely, designing the upper bound of the score of each interval list and skipping the calculation times of the Gaussian mixture model with higher complexity.
  • the Top-K optimization algorithm is more efficient and accurate than existing algorithms.
  • This application is not limited to the application of prompts for database query input, search box optimization of search engines, code prompts in integrated development environments, query prompt systems in the field of biochemical medicine, fast input interfaces of input methods, and restricted terminal input interfaces And other technical fields.
  • FIG. 5-6 there is shown a structural block diagram of an embodiment of a device for automatic query completion of the present invention, which may specifically include the following modules:
  • the receiving module 100 is used to receive the query prefix from the user end;
  • the matching module 200 is used to match the character result of the query prefix based on the nested dictionary tree structure
  • the interval list merging module 300 is used to add character results to the interval list according to the nested dictionary tree nodes
  • the interval result sorting module 400 is used to sort the interval list according to the analysis of the user's target character string to obtain a result set.
  • it also includes:
  • the result screening module 500 is used to adopt the Top-K algorithm to return the target result set according to user requirements.
  • it also includes:
  • the structure building module is used to build a nested dictionary tree structure.
  • the structure establishment module includes:
  • the link unit is used to link the dictionary trees together to form a nested dictionary tree structure.
  • the splitting unit includes:
  • the link unit includes:
  • the link subunit is used to link the external dictionary tree and the internal dictionary tree to form a nested dictionary tree.
  • the interval result sorting module includes:
  • the segmentation probability calculation unit is used to calculate the segmentation matching probability of the target string using Bayes' theorem and the Gaussian mixture model;
  • the sorting unit is used to sort the interval list in a descending order of the split matching probability.
  • the description is relatively simple, and for related parts, please refer to the part of the description of the method embodiment.
  • the embodiment of the present invention discloses an electronic device, including a processor, a memory, and a computer program stored in the memory and capable of running on the processor.
  • the computer program is executed by the processor to realize the steps of the above-mentioned query auto-completion method. .
  • the embodiment of the present invention discloses a computer-readable storage medium, and a computer program is stored on the computer-readable storage medium.
  • the computer program is executed by a processor, the steps of the above-mentioned query automatic completion method are realized.
  • the embodiments of the embodiments of the present invention may be provided as methods, devices, or computer program products. Therefore, the embodiments of the present invention may adopt the form of a complete hardware embodiment, a complete software embodiment, or an embodiment combining software and hardware. Moreover, the embodiments of the present invention may adopt the form of a computer program product implemented on one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) containing computer-usable program codes.
  • computer-usable storage media including but not limited to disk storage, CD-ROM, optical storage, etc.
  • These computer program instructions can also be stored in a computer-readable memory that can guide a computer or other programmable data processing terminal equipment to work in a specific manner, so that the instructions stored in the computer-readable memory produce an article of manufacture including the instruction device.
  • the instruction device implements the functions specified in one process or multiple processes in the flowchart and/or one block or multiple blocks in the block diagram.
  • These computer program instructions can also be loaded on a computer or other programmable data processing terminal equipment, so that a series of operation steps are executed on the computer or other programmable terminal equipment to produce computer-implemented processing, so that the computer or other programmable terminal equipment
  • the instructions executed above provide steps for implementing functions specified in a flow or multiple flows in the flowchart and/or a block or multiple blocks in the block diagram.

Landscapes

  • Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Computational Linguistics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

一种查询自动补全的方法和装置，其中一种查询自动补全的方法，包括：接收来自用户端的查询前缀；基于嵌套字典树结构匹配所述查询前缀的字符结果；将所述字符结果按照嵌套字典树节点加入到区间列表；根据用户目标字符串的分析对所述区间列表进行排序，得到结果集合。嵌入式字典树能更精确地定位到匹配前缀的字符串区间，支持关键词缩减的查询自动补全技术，极大减少了用户需要输入的查询长度，提高了用户体验的舒适度。

Description

一种查询自动补全的方法和装置
本申请要求于2019年10月23日提交中国专利局、申请号为2019110140612，发明名称为“一种查询自动补全的方法和装置”的中国专利申请的优先权，其全部内容通过引用结合在本申请中。
技术领域
本发明涉及搜索技术领域，特别是涉及一种查询自动补全的方法和一种查询自动补全的装置。
背景技术
查询自动补全技术是指导用户正确输入查询并且减少需要输入的字符的一个重要组成部分。在搜索引擎中(如Google，百度等)，用户往往想要输入少量的信息，而返回他们想要的结果。比如用户输入MJ这个查询而期望搜索引擎返回关于Michael Jordan的结果。当用户在搜索框中输入查询的时候，查询自动补全会给出合适的，把查询输入字符作为前缀的建议。
为了更好地提高人机交互的体验度，查询自动补全经常被用在各种需要大量人力输入且易错的应用中，比如命令行，桌面搜索和移动设备等。由于它的重要性，查询自动补全技术已经被广泛地重视，并应用在信息抽取，数据库搜索中。
对于现有的查询自动补全方法，用户需要手动地分开查询输入的关键词，并且这些方法把查询字符作为关键词的前缀进行匹配操作。当用户不倾向于或者不方便于在查询中手动分开关键词的时候，这些方法就不会有效了。
技术问题
本申请的主要目的为提供一种查询自动补全的方法和一种查询自动补全的装置，旨在解决现有的查询自动补全方法，用户需要手动地分开查询输入的关键词，并且这些方法把查询字符作为关键词的前缀进行匹配操作的技术问题。
技术解决方案
为了实现上述申请目的，本申请提出一种查询自动补全的方法，包括：
接收来自用户端的查询前缀；
基于嵌套字典树结构匹配所述查询前缀的字符结果；
将所述字符结果按照嵌套字典树节点加入到区间列表；
根据用户目标字符串的分析对所述区间列表进行排序，得到结果集合。
本申请还提供了一种查询自动补全的装置，包括：
接收模块，用于接收来自用户端的查询前缀；
匹配模块，用于基于嵌套字典树结构匹配所述查询前缀的字符结果；
区间列表合并模块，用于将所述字符结果按照嵌套字典树节点加入到区间列表；
区间结果排序模块，用于根据用户目标字符串的分析对所述区间列表进行排序，得到结果集合。
本申请还提供一种电子设备，包括处理器、存储器及存储在所述存储器上并能够在所述处理器上运行的计算机程序，所述计算机程序被所述处理器执行时实现如上述方法中任一项所述的查询自动补全的方法的步骤。
本申请还提供一种计算机可读存储介质，所述计算机可读存储介质上存储计算机程序，所述计算机程序被处理器执行时实现如上述方法中任一项所述的查询自动补全的方法的步骤。
有益效果
本发明实施例包括以下优点：嵌入式字典树能更精确地定位到匹配前缀的字符串区间，支持关键词缩减的查询自动补全技术，极大减少了用户需要输入的查询长度，提高了用户体验的舒适度。
附图说明
图1是本发明一具体实施例中嵌套字典树结构示意图；
图2是本发明一具体实施例中一个快速查询字典树算法；
图3是本发明的一种查询自动补全方法实施例的步骤流程图；
图4是本发明的一种查询自动补全方法另一实施例的步骤流程图；
图5是本发明的一种查询自动补全装置实施例的结构框图；
图6是本发明的一种查询自动补全装置另一实施例的结构框图。
本发明的最佳实施方式
为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。
本发明实施例的核心构思之一在于，提供了一种查询自动补全的方法和装置，其中一种查询自动补全的方法，包括：接收来自用户端的查询前缀；基于嵌套字典树结构匹配查询前缀的字符结果；将字符结果按照嵌套字典树节点加入到区间列表；根据用户目标字符串的分析对区间列表进行排序，得到结果集合。嵌入式字典树能更精确地定位到匹配前缀的字符串区间，支持关键词缩减的查询自动补全技术，极大减少了用户需要输入的查询长度，提高了用户体验的舒适度。
参照图1-4，示出了本发明的一种查询自动补全的方法实施例的步骤流程图，具体可以包括如下步骤：
S100，接收来自用户端的查询前缀；
在本实施例中，Σ是一个有限的字符集合；一条字符串s是一个从Σ中抽取的有序的字符数组。|s|表示字符串s的长度，s[i]表示s中的第i个字符。s[i..j]表示s中从第i个字符到第j个字符的子串。给定2个字符串s和t，s是t的前缀表达为s≤t，当且仅当s[1..i]＝t[1..i],1≤i≤|s|。用st表示用s和t顺序拼接的字符串。一组字符串数组[s 1,s 2,..s n](n>1),如果s＝s 1s 2..s n的拼接，把[s 1,s 2,..s n]称作s的一个切割。用s<表示任意一个s的前缀子字符串。给定S是一个字符串数据集，每一个字符串s∈S可以被切割成一个关键字集合，假设Σ包含的是英文字母集合。分割符号可以是空格，标点，大写字母等。比如"AddNextValue"被分割成"Add"、"Next"和"Value"这三个部分。考虑一个字符串s可以分割成一组关键字[s1,...,sn]。给定一个查询字符串q，说q是s的前缀缩写匹配，表达为
Figure PCTCN2019126590-appb-000001
当且仅当q＝s1<s2<..si<，1≤i≤n；q是s的前i个关键字的前缀缩写的拼接。比如gene是字符串”GetNextValue”的一个前缀缩写匹配，因为ge和ne是Get和Next的前缀。用PAM来代表前缀缩写匹配。给定一个字符串数据集合S，一个查询字符串q，一个前缀缩写查询自动补全(QACPA)是找到所有字符串集合si∈S，满足
Figure PCTCN2019126590-appb-000002
输出的结果是根据用户当前的输入字符来增量计算得到的。
本申请公开的一种查询自动补全的方法，允许用户输入可缩减的关键词前缀的链接作为查询，提升体验度。根据关键词前缀链接这一场景，设计了一个的索引结构和查询方法来完成其功能。并提出了一个排序算法，把它结合在上 述查询中，保证结果输出的质量排序，即为排在前列的结果以最大的可能是用户所期望的。以Top-K方法来返回少量，即为K，且高质量的结果。
在本实施例中，通过建立嵌套字典树索引结构，查询算法，区间列表合并方法，区间结果排序方法和区间Top-K算法，在线下，当原始数据给定之后，针对不同的需求对数据进行预处理，比如去除噪音、脏数据等，并且建立索引结构。在线上用户查询的时候，从查询算法开始执行，直到输出结果呈现给用户。
本实施例中的索引数据结构为嵌套字典树结构，包含多个内部字典树嵌套在一个外部字典树中。参照图1显示的嵌套字典树结构示意图。为了构建嵌套字典树，给定每一个字符串输入S，选取字符串每一个关键字的首字母加入到外部字典树。然后对于每一个首字母所在的外节点，将相应的关键字的其他字母加入到内部字典树中。把在外部字典树的节点和边叫外部节点和边，把内部字典树的节点和边叫做内部节点和边。嵌套字典树的根节点是外部字典树的根节点。还在树的节点之间增加了从内部节点到外部节点的链接。对于一个内部节点n，用初始节点代表包含n的内部字段数的根节点。对于任何一个非初始字符所在的数据字符串，如果它后面有一个紧连的关键词，对这个内部节点所对应的初始节点，增加一个快捷链接到外部节点。这个快捷链接的标签就是下一个关键词的首字母。
为了减少快捷链接的空间，大部分的链接不需要被实际保存下来。链接的目标节点总是外部边的一个子集。基于这个现象，对于一个外部边，使用一个位，即为bit向量来保存。第i个bit的表示节点的链接的目的地是跟第i条外边的目的地是一样的。这样可以避免重复的保存相同功能的边。跟传统的字典树相比，嵌套字典树将共享同一个首字母的关键字合并起来。在后面的算法描述中，这样的数据结构可以有效的降低激活节点的数量。同时，激活结点也可以快速被找到。
S200，基于嵌套字典树结构匹配查询前缀的字符结果；
在本实施例中，在嵌套字典树结构中，一个激活结点n是一个节点存在至少一条路径(通过边或者链接)从根节点到n能够精确匹配用户输入的查询字符串。算法从外部根节点出发，对于每一个用户输入的字符，从已有的激活结点出发找到新的激活结点。给定这个输入的字符，可以匹配首字符或者非首 字符。嵌套字典树能够很好的支持这样的匹配。对于一个非首字符，通过走内部边找到一个新的激活结点。对于一个首字母，可以通过走外部边找到一个新的激活结点。另外也可以通过一条快捷链接从内部节点跳到外部节点产生新的激活结点。
在本实施例中，每一个节点下的数据并不全是所要的结果。通过列表合并的方法来去除不是结果的字符串。给定In为一个排好序的区间序列，定义
Figure PCTCN2019126590-appb-000003
操作为合并两个interval的序列。
Figure PCTCN2019126590-appb-000004
Figure PCTCN2019126590-appb-000005
这里xi和yj表示两个区间。性质1，给定一个一条从根节点到n的路径，n1,...,nk。查询q的结果是仅存在于
Figure PCTCN2019126590-appb-000006
当中。基于性质1，本实施例中的一个快速查询字典树算法，这个算法的复杂度是：O(log|In'|).具体算法参见图2。
S300，将字符结果按照嵌套字典树节点加入到区间列表；
在本实施例中，嵌套式字典树算法中的查询可能不会匹配积极节点下面的所有字符串。为了不报告非结果的数据，把字典树中每个节点加入一个排好序的区间列表来显示描述前缀和字典树中一条路径有匹配的字符串。为了计算列表中的区间，给定一个字符串，遍历字典树中的节点，并且把该字符串的ID加入到对应节点的区间列表中。一个基础方法是用sweepline算法来处理区间列表合并，他的时间复杂度是O(|I n|+|I n'|),其中|*|表示列表中区间的个数。由于合并操作，|I n|一般在实际情况中是很小并且远远小于|I n'|。如果把|I n|看做一个常数，时间复杂度变成O(|I n'|)。当在嵌套字典树中遍历深层节点的时候，存储裂变中的区间会变得很分散，并且|I n'|在变大，这里就会引入大量的合并的代价。针对上述问题，本实施例中的一个列表合并的算法。对于列表中的一个区间[u,v]，使用二分查找的方式把u作为键值在I n'中查找第一个和[u,v]有交集的区间。
S400，根据用户目标字符串的分析对区间列表进行排序，得到结果集合。
在本实施例中，基于对用户需求的分析，对输出的结果根据估计用户的目标字符串来对结果排序。
在本实施例中，S100，接收来自用户端的查询前缀的步骤之前，包括：
建立嵌套字典树结构。
在本实施例中，建立嵌套字典树结构的步骤，包括：
将关键词划分并建立字典树；
将字典树链接在一起形成嵌套字典树结构。
在本实施例中，字典树包括内部字典树和外部字典树，将关键词划分并建立字典树的步骤，包括：
将关键词的首字母加到外部字典树，将相应的关键词的其他字母加到内部字典树。
在本实施例中，将字典树链接在一起形成嵌套字典树结构的步骤，包括：
将外部字典树与内部字典树链接在一起形成嵌套字典树。
在本实施例中，S400，根据用户目标字符串的分析对区间列表进行排序，得到结果集合的步骤，包括：
利用贝叶斯定理和混合高斯模型计算出目标字符串的分割匹配概率；
按照分割匹配概率降序的方式对区间列表进行排序。
在本实施例中，给定一个数据字符串s切割成[s 1,...,s n]，假设前m个关键字已经被缩写到查询中，剩下的(n-m)个关键字还没有被输入。因此
Figure PCTCN2019126590-appb-000007
q可以被切割成[q 1,...,q m]，并满足q i≤s i，1≤i≤m≤n。增加(n-m)个空字符串，用q m+1,...,q n来表示。这样q和s就会拥有同样的数量的切割。排序s的分数定义为字符串s是查询字符串关于分割[q 1,...,q n]和[s 1,...,s n]匹配的概率，用score(s,q)＝P(s 1...s n|q 1...q n)来表示。如果有多种切割的方式，选取一种切割方式能得到最大的分数。对于所有的q的PAM结果，用score(s,q)函数进行排序，得到一个降序的结果集合。
为了计算score(s,q)，应用贝叶斯定理：
score(s,q)＝P(s 1...s n|q 1...q n)
＝P(q 1...q n|s 1...s n)*P(s 1...s n)/P(q 1...q n)
∝P(q 1...q n|s 1...s n)*P(s 1...s n)
＝P(q 1...q n|s 1...s n)*P(s)
上面公式中分母P(q 1...q n)可以被安全地忽略，因为P(q 1...q n)＝P(q)，这个对于所有的PA匹配的字符串来说都是一样的数值。P(s)是通过s的流行度来刻画的。为了计算P(q 1...q n|s 1...s n)，假设P(q i|s i)，1≤i≤n彼此独立。因此，有：P(q 1...q n|s 1...s n)＝P(q 1|s 1)·...·P(q n|s n)，得到以下公式：
score(s,q)∝P(q 1|s 1)·...·P(q n|s n)·P(s)
每一个P(q i|s i)描述的用户输入查询字符串q i的情况下是字符串s i前缀的概率。对于没有输入的字符假设P(q i|s i)＝1，m<i≤n。这样设置的原因是这些关键词是在接下会被作为用户输入。为了让s的分数不会因为序列操作导致的数值很低，尤其是当n远远大于m的时候，把这些概率数值设置成1。
为了更好地计算P(q i|s i)，发现用户习惯性缩减一些特殊的字符序列，比如忽略辅音部分，并且这种省略存在一定的模式。因此使用向量来描述当前的特征：(1)q i的长度，(2)q i中有多少个元音，(3)q i中有多少个辅音，(4)q i是否以辅音结束，(5)i的值，也就是字符s i在字符串中的位置。由上所述，用5维度的向量来表示当前的特征。这里s i并没有完全地编码在该向量中。这里的原因如下：让p i表示用户把si缩减成q i的模式向量。因为知道一个关键词是如何进行缩减的，即为P(q i,s i)＝P(p i)·P(s i)。因为P(q i,s i)＝P(q i|s i)·P(s i),P(p i)。因此P(p i)的结果就是P(q i|s i)。
给定一个模式向量，使用混合高斯模型(GMM)来计算P(p i)的值。此高斯混合模型使用未知的参数，计算p的密度函数，即为概率如下：
Figure PCTCN2019126590-appb-000008
其中l是高斯分布的个数，w i是每个高斯分布的权重，N(p|μ i,∑ i)是以μ i为均值以及∑ i为方差矩阵且为p的概率密度函数。其中参数l是可以在训练中精调的。同时，其他参数可以以一个聚类方式和用EM算法来学习：一系列数据字符串被用户给定，之后收集其数据的所有前缀并且把他们转换成关键词和前缀的数据对作为训练数据的特征。
在本实施例中，S400，根据用户目标字符串的分析对区间列表进行排序，得到结果集合的步骤之后，还包括：
S500，根据用户需求采用Top-K算法返回目标结果集合。
在本实施例中，在用户输入查询的过程中，用户并不会对所有的结果感兴 趣，通常仅对最前面的K个结果感兴趣。在这种假设下，可以提前对不可能进入前K个的结果进行提前过滤。估计某一个激活结点下的分数的上限，如果这个上限已经低于当前前K个结果的下限，就可以把这个激活结点提前过滤掉。在区间列表算法中，一个合并之后的区间列表在每个有效节点中被获得作为验证集。如果要想得到结果的TopK，遍历每个有效节点中的区间列表，对区间内的每个字符串计算相应的分数值，之后根据计算的分数排序，抽取Top-K的结果。当前方法执行中最大的代价是使用高斯混合模型去计算概率P(q i|s i)。因为区间内的字符串数量在实际情况中会很大，尤其是对于长度较短的查询字符串，这里很有必要去设计一个高效的Top-K算法来降低高斯混合模型的计算次数。
在一具体实施例中，限定合并区间列表中最大可能的分数。根据合并列表的特点，有如下特性：对于每个区间[u,v]∈J n，总是存在一个区间[u',v']∈I n，满足条件u'≤u，且v'≥v。因此，在列表J n中字符串的最大可能分数值是列表I n的上界。为了计算每个区间的分数，考虑一个字典树的根节点为n。用d表示字典树的深度，这里可以推出所有列表I n中的字符串都有至少d个关键词，并且当n变成一个激活节点的时候，查询q有精确的d个非空分割。因此对于每个区间[u,v]∈I n，可以用线下的方式处理字符串s u...s v，并且使用最大数值来限定线上查询的边界。给定一个字符串s i，对于每d个关键词
Figure PCTCN2019126590-appb-000009
枚举字符串s i所有可能的前缀
Figure PCTCN2019126590-appb-000010
之后计算概率
Figure PCTCN2019126590-appb-000011
这里注意当j＝d的时候，由于在节点n上产生匹配，所以只存在一个可能的前缀。最大概率
Figure PCTCN2019126590-appb-000012
的乘积被字符串s i的流行度所计算，这里取出最大值并把它存储在字典树中的区间[u,v]中。
本实施例公开的一种在线的Top-K结果抽取算法。在最开始的时候，初始化一个优先队列R用于存储Top-K的结果。对于每个激活结点n，对于列表J n中的区间按照最大分数的降序进行排序。其次，对于J n中的每个区间[u,v]，顺序地计算每个字符串的分数，之后更新到优先队列中。如果达到了一个区间，他的最大分数不大于第k个结果的时候，对于n的处理可以安全地结束。
在另一具体实施例中，跳过一些高斯混合模型的计算，在相同区间内的字符串以很大的概率分享一些关键词，即为有相同的概率p＝(q i|s i)。对于在一个区间[u,v]∈I n的两个相邻字符串s i和s i+1，线下检查他们共享作为前缀的关键词的数量，并且把这个数值记录在si+1中，用s i+1·spr来表示。对于在线查询处理，如果s i和s i+1同时出现在J n的同一个区间中，能够对于第一个s i+1·spr关键字的高斯混合模型计算进行跳过，因为已经被计算过了。为了更好地利用关键词共享，把S中的字符串按照早点顺序进行排序。
本申请允许用户决定结果数量。如果用户期望得到全部结果，并一一筛选，则可以跳过上述S500根据用户需求采用Top-K算法返回目标结果集合步骤，如果用户只想要有限个高质量的结果，则上述返回用户最想要的K个结果。
本申请公开的一种查询自动补全的方法，基于查询补全技术的前缀缩写匹配的模型，查询自动补全技术的前缀匹配模型是自动补全技术中的新算法。相比于现有的技术，本申请充分考虑到各种情景，尤其是对于用户不会显示地表明关键词的分隔符。本申请能够节约20％用户输入的字符数。嵌入式字典树是提出支持自动补全技术的新数据结构。相比于传统的字典树索引结构，本申请的嵌入式字典树能更精确地定位到匹配前缀的字符串区间。为了返回更有意义的结果，设计了一个排序算法，此排序算法利用查询字符串对于数据字符串相对于分割的概率来计算，并且利用贝叶斯公式和高斯混合模型结构来计算其概率数值。该排序算法能够把用户更想要的结果返回。考虑到用户感兴趣的结果，设计两种Top-K的优化算法，即为设计每个区间列表的分数上界和跳过复杂度较高的高斯混合模型的计算次数。该Top-K优化算法相比于现有的算法具有更高效性和准确度。
本申请不限于应用在数据库查询输入的提示、搜索引擎的搜索框优化、集成开发环境中的代码提示、生物化学医学领域内的查询提示系统、输入法的快速输入接口、受限的终端输入接口等技术领域。
需要说明的是，对于方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本发明实施例并不受所描述的动作顺序的限制，因为依据本发明实施例，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优 选实施例，所涉及的动作并不一定是本发明实施例所必须的。
参照图5-6，示出了本发明的一种查询自动补全的装置实施例的结构框图，具体可以包括如下模块：
接收模块100，用于接收来自用户端的查询前缀；
匹配模块200，用于基于嵌套字典树结构匹配查询前缀的字符结果；
区间列表合并模块300，用于将字符结果按照嵌套字典树节点加入到区间列表；
区间结果排序模块400，用于根据用户目标字符串的分析对区间列表进行排序，得到结果集合。
在本实施例中，还包括：
结果筛选模块500，用于根据用户需求采用Top-K算法返回目标结果集合。
在本实施例中，还包括：
结构建立模块，用于建立嵌套字典树结构。
在本实施例中，结构建立模块包括：
拆分单元，用于将关键词划分并建立字典树；
链接单元，用于将字典树链接在一起形成嵌套字典树结构。
在本实施例中，拆分单元包括：
拆分子单元，用于将关键词的首字母加到外部字典树，将相应的关键词的其他字母加到内部字典树。
在本实施例中，链接单元包括：
链接子单元，用于将外部字典树与内部字典树链接在一起形成嵌套字典树。
在本实施例中，区间结果排序模块包括：
分割概率计算单元，用于利用贝叶斯定理和混合高斯模型计算出目标字符串的分割匹配概率；
排序单元，用于按照分割匹配概率降序的方式对区间列表进行排序。
对于装置实施例而言，由于其与方法实施例基本相似，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。
本发明实施例公开了一种电子设备，包括处理器、存储器及存储在存储器上并能够在处理器上运行的计算机程序，计算机程序被处理器执行时实现上述 的查询自动补全的方法的步骤。
本发明实施例公开了一种计算机可读存储介质，计算机可读存储介质上存储计算机程序，计算机程序被处理器执行时实现上述的查询自动补全的方法的步骤。
本说明书中的各个实施例均采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似的部分互相参见即可。
本领域内的技术人员应明白，本发明实施例的实施例可提供为方法、装置、或计算机程序产品。因此，本发明实施例可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明实施例可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。
本发明实施例是参照根据本发明实施例的方法、终端设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理终端设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理终端设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理终端设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
这些计算机程序指令也可装载到计算机或其他可编程数据处理终端设备上，使得在计算机或其他可编程终端设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程终端设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
尽管已描述了本发明实施例的优选实施例，但本领域内的技术人员一旦得 知了基本创造性概念，则可对这些实施例做出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明实施例范围的所有变更和修改。
最后，还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者终端设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者终端设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者终端设备中还存在另外的相同要素。
以上对本发明所提供的一种查询自动补全的方法和相应的一种查询自动补全的装置，进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。

Claims (10)

  1. 一种查询自动补全的方法，其特征在于，包括：
    接收来自用户端的查询前缀；
    基于嵌套字典树结构匹配所述查询前缀的字符结果；
    将所述字符结果按照嵌套字典树节点加入到区间列表；
    根据用户目标字符串的分析对所述区间列表进行排序，得到结果集合。
  2. 根据权利要求1所述的方法，其特征在于，所述根据用户目标字符串的分析对所述区间列表进行排序，得到结果集合的步骤之后，还包括：
    根据用户需求采用Top-K算法返回目标结果集合。
  3. 根据权利要求1所述的方法，其特征在于，所述接收来自用户端的查询前缀的步骤之前，包括：
    建立所述嵌套字典树结构。
  4. 根据权利要求3所述的方法，其特征在于，所述建立所述嵌套字典树结构的步骤，包括：
    将关键词划分并建立字典树；
    将所述字典树链接在一起形成嵌套字典树结构。
  5. 根据权利要求4所述的方法，其特征在于，所述字典树包括内部字典树和外部字典树，所述将关键词划分并建立字典树的步骤，包括：
    将所述关键词的首字母加到外部字典树，将相应的所述关键词的其他字母加到内部字典树。
  6. 根据权利要求5所述的方法，其特征在于，所述将所述字典树链接在一起形成嵌套字典树结构的步骤，包括：
    将所述外部字典树与所述内部字典树链接在一起形成嵌套字典树。
  7. 根据权利要求1所述的方法，其特征在于，所述根据用户目标字符串的分析对所述区间列表进行排序，得到结果集合的步骤，包括：
    利用贝叶斯定理和混合高斯模型计算出目标字符串的分割匹配概率；
    按照所述分割匹配概率降序的方式对所述区间列表进行排序。
  8. 一种查询自动补全的装置，其特征在于，包括：
    接收模块，用于接收来自用户端的查询前缀；
    匹配模块，用于基于嵌套字典树结构匹配所述查询前缀的字符结果；
    区间列表合并模块，用于将所述字符结果按照嵌套字典树节点加入到区间列表；
    区间结果排序模块，用于根据用户目标字符串的分析对所述区间列表进行排序，得到结果集合。
  9. 电子设备，其特征在于，包括处理器、存储器及存储在所述存储器上并能够在所述处理器上运行的计算机程序，所述计算机程序被所述处理器执行时实现如权利要求1至7中任一项所述的查询自动补全的方法的步骤。
  10. 计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储计算机程序，所述计算机程序被处理器执行时实现如权利要求1至7中任一项所述的查询自动补全的方法的步骤。
PCT/CN2019/126590 2019-10-23 2019-12-19 一种查询自动补全的方法和装置 WO2021077585A1 (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN201911014061.2 2019-10-23
CN201911014061.2A CN110750704B (zh) 2019-10-23 2019-10-23 一种查询自动补全的方法和装置

Publications (1)

Publication Number Publication Date
WO2021077585A1 true WO2021077585A1 (zh) 2021-04-29

Family

ID=69279673

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2019/126590 WO2021077585A1 (zh) 2019-10-23 2019-12-19 一种查询自动补全的方法和装置

Country Status (2)

Country Link
CN (1) CN110750704B (zh)
WO (1) WO2021077585A1 (zh)

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN113312549A (zh) * 2021-05-25 2021-08-27 北京天空卫士网络安全技术有限公司 一种域名处理方法和装置
CN113360666A (zh) * 2021-05-31 2021-09-07 珠海大横琴科技发展有限公司 数据字典管理方法及装置、电子设备、存储介质
CN114519115A (zh) * 2022-01-20 2022-05-20 青岛图灵科技有限公司 一种基于多块分叉字典树索引结构的图像检索方法
WO2022261345A1 (en) * 2021-06-10 2022-12-15 Visa International Service Association System, method, and computer program product for feature analysis using an embedding tree
CN115878924A (zh) * 2021-09-27 2023-03-31 小沃科技有限公司 一种基于双字典树数据处理方法、装置、介质及电子设备
CN117640259A (zh) * 2024-01-25 2024-03-01 武汉思普崚技术有限公司 一种脚本分步检测方法、装置、电子设备及介质
US12032608B1 (en) 2023-02-06 2024-07-09 Walmart Apollo, Llc Systems and methods for generating query suggestions
US12079279B2 (en) 2023-02-06 2024-09-03 Walmart Apollo, Llc Systems and methods for generating query suggestions

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112256821B (zh) * 2020-09-23 2024-05-17 北京捷通华声科技股份有限公司 中文地址补全的方法、装置、设备及存储介质
CN114090722B (zh) * 2022-01-19 2022-04-22 支付宝(杭州)信息技术有限公司 查询内容自动补全的方法及装置

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102063508A (zh) * 2011-01-10 2011-05-18 浙江大学 基于广义后缀树的中文搜索引擎模糊自动补全方法
CN102084363A (zh) * 2008-07-03 2011-06-01 加利福尼亚大学董事会 一种用于在结构化数据上高效地支持交互式模糊搜索的方法
US20150347503A1 (en) * 2014-05-30 2015-12-03 Apple Inc. Multi-domain query completion
CN108241695A (zh) * 2016-12-26 2018-07-03 北京国双科技有限公司 信息处理方法及装置
CN108427756A (zh) * 2018-03-16 2018-08-21 中国人民解放军国防科技大学 基于同类用户模型的个性化查询词补全推荐方法和装置

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104052669B (zh) * 2013-03-12 2018-12-07 凯为公司 用于处理交替配置的最长前缀匹配表的装置
CN105447080B (zh) * 2015-11-05 2018-10-26 华建宇通科技(北京)有限责任公司 一种社区问答搜索中的查询补全方法
CN107169045A (zh) * 2017-04-19 2017-09-15 中国人民解放军国防科学技术大学 一种基于时域特征的查询词自动补全方法与装置
CN109325635B (zh) * 2018-10-25 2022-02-15 电子科技大学中山学院 一种基于自动补全的位置预测方法

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102084363A (zh) * 2008-07-03 2011-06-01 加利福尼亚大学董事会 一种用于在结构化数据上高效地支持交互式模糊搜索的方法
CN102063508A (zh) * 2011-01-10 2011-05-18 浙江大学 基于广义后缀树的中文搜索引擎模糊自动补全方法
US20150347503A1 (en) * 2014-05-30 2015-12-03 Apple Inc. Multi-domain query completion
CN108241695A (zh) * 2016-12-26 2018-07-03 北京国双科技有限公司 信息处理方法及装置
CN108427756A (zh) * 2018-03-16 2018-08-21 中国人民解放军国防科技大学 基于同类用户模型的个性化查询词补全推荐方法和装置

Cited By (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN113312549A (zh) * 2021-05-25 2021-08-27 北京天空卫士网络安全技术有限公司 一种域名处理方法和装置
CN113312549B (zh) * 2021-05-25 2024-01-26 北京天空卫士网络安全技术有限公司 一种域名处理方法和装置
CN113360666A (zh) * 2021-05-31 2021-09-07 珠海大横琴科技发展有限公司 数据字典管理方法及装置、电子设备、存储介质
WO2022261345A1 (en) * 2021-06-10 2022-12-15 Visa International Service Association System, method, and computer program product for feature analysis using an embedding tree
US12253991B2 (en) 2021-06-10 2025-03-18 Visa International Service Association System, method, and computer program product for feature analysis using an embedding tree
CN115878924A (zh) * 2021-09-27 2023-03-31 小沃科技有限公司 一种基于双字典树数据处理方法、装置、介质及电子设备
CN115878924B (zh) * 2021-09-27 2024-03-12 小沃科技有限公司 一种基于双字典树数据处理方法、装置、介质及电子设备
CN114519115A (zh) * 2022-01-20 2022-05-20 青岛图灵科技有限公司 一种基于多块分叉字典树索引结构的图像检索方法
US12032608B1 (en) 2023-02-06 2024-07-09 Walmart Apollo, Llc Systems and methods for generating query suggestions
US12079279B2 (en) 2023-02-06 2024-09-03 Walmart Apollo, Llc Systems and methods for generating query suggestions
CN117640259A (zh) * 2024-01-25 2024-03-01 武汉思普崚技术有限公司 一种脚本分步检测方法、装置、电子设备及介质
CN117640259B (zh) * 2024-01-25 2024-06-04 武汉思普崚技术有限公司 一种脚本分步检测方法、装置、电子设备及介质

Also Published As

Publication number Publication date
CN110750704A (zh) 2020-02-04
CN110750704B (zh) 2022-03-11

Similar Documents

Publication Publication Date Title
WO2021077585A1 (zh) 一种查询自动补全的方法和装置
CN109101479B (zh) 一种用于中文语句的聚类方法及装置
CN109947904B (zh) 一种基于Spark环境的偏好空间Skyline查询处理方法
CN105045875B (zh) 个性化信息检索方法及装置
CN1916905A (zh) 基于倒排表进行检索提示的方法
WO2008098507A1 (fr) Méthode de saisie permettant de combiner des mots de façon intelligente, système associé à la méthode de saisie et méthode de renouvellement
CN111177591A (zh) 面向可视化需求的基于知识图谱的Web数据优化方法
CN108520033B (zh) 基于超空间模拟语言的增强伪相关反馈模型信息检索方法
CN112115232A (zh) 一种数据纠错方法、装置及服务器
CN112632261A (zh) 智能问答方法、装置、设备及存储介质
CN106484797A (zh) 基于稀疏学习的突发事件摘要抽取方法
CN108875065B (zh) 一种基于内容的印尼新闻网页推荐方法
CN111325030A (zh) 文本标签构建方法、装置、计算机设备和存储介质
CN105912662A (zh) 基于Coreseek的垂直搜索引擎研究与优化的方法
CN105404677B (zh) 一种基于树形结构的检索方法
CN117390169A (zh) 表格数据问答方法、装置、设备及存储介质
CN111930953B (zh) 一种文本属性特征的识别、分类及结构分析方法及装置
CN108491407B (zh) 一种面向代码检索的查询扩展方法
CN111723179B (zh) 基于概念图谱的反馈模型信息检索方法、系统及介质
CN110019637B (zh) 一种标准文献检索的排序算法
CN110209765B (zh) 一种按语义搜索关键词的方法和装置
CN109670102B (zh) 基于词表模型的用户检索意图判断方法
CN105426490B (zh) 一种基于树形结构的索引方法
CN109918661B (zh) 同义词获取方法及装置
Li et al. Complex query recognition based on dynamic learning mechanism

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 19949799

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 19949799

Country of ref document: EP

Kind code of ref document: A1