SYSTEMS AND METHODS FOR QUERY AUTOCOMPLETION
Embodiments described herein provide a query autocompletion (QAC) framework at subword level. Specifically, the QAC framework employs a subword encoder that encodes or converts the sequence of input alphabet letters into a sequence of output subwords. The generated subword candidate sequences from the subword encoder is then for the n-gram language model to perform beam search on. For example, as user queries for search engines are in general short, e.g., ranging from 10 to 30 characters. The n-gram language model at subword level may be used for modeling such short contexts and outperforms the traditional language model in both completion accuracy and runtime speed. Furthermore, key computations are performed prior to the runtime to prepare segmentation candidates in support of the subword encoder to generate subword candidate sequences, thus eliminating significant computational overhead.
1 . A method of query autocompletion, the method comprising:
receiving a query prefix from a user interface;
forming a sequence of input characters based on the received query prefix;
encoding the sequence at subword level by retrieving one or more segmentation candidates corresponding to the query prefix from a segmentation database;
retrieving, for each segmentation candidates, a respective set of completion candidates and corresponding likelihood scores from a completion database;
selecting a number of completion candidates having highest likelihood scores among all completion candidates corresponding to the one or more segmentation candidates; and
presenting, via the user interface, the number of completion candidates in response to the query prefix.
2 . The method of claim 1 , wherein the one or more segmentation candidates are precomputed by a subword encoder and cached in the segmentation database prior to runtime.
3 . The method of claim 2 , wherein the subword encoder is constructed as a finite state transducer (FST) during training stage prior to runtime.
4 . The method of claim 3 , wherein the FST is constructed by:
constructing a trie structure with a subword vocabulary set extracted from a query log as keys,
adding a transition from each exit state of the trie structure to a start state with an input label representing a failure or fallback transition and an output label associated with the respective exit state; and
performing a breadth-first traversal on the trie structure to add additional failure or fallback transitions at every intermediate state.
5 . The method of claim 3 , wherein the one or more segmentation candidates are precomputed by a breadth-first traversal on the FST from a given state representing a determinate token in a sequence of input characters from the training dataset.
6 . The method of claim 1 , wherein the respective set of completion candidates and corresponding likelihood scores are precomputed by a n-gram language model prior to runtime.
7 . The method of claim 6 , wherein the n-gram language model is constructed as a weighted FST as having a plurality of states, each state representing a history of a subword sequence along a path from a start state to the respective state.
8 . The method of claim 7 , wherein the weighted FST has a plurality of transitions between states, and each transition is associated with a weight representing a likelihood of an output label given the history of the state.
9 . The method of claim 8 , wherein the respective set of completion candidates are precomputed by iterating each state on the weighted FST and generating the plurality of completion candidates for the respective segmentation candidate as having highest likelihoods via beam search.
10 . The method of claim 1 , wherein the number of completion candidates are presented as the query prefix is being entered via the user interface.
11 . A system of query autocompletion, the system comprising:
a communication interface that receives a query prefix from a user interface;
one or more hardware processors that:
form a sequence of input characters based on the received query prefix;
encode the sequence at subword level by retrieving one or more segmentation candidates corresponding to the query prefix from a segmentation database;
retrieve, for each segmentation candidates, a respective set of completion candidates and corresponding likelihood scores from a completion database; and
select a number of completion candidates having highest likelihood scores among all completion candidates corresponding to the one or more segmentation candidates; and
a user interface that presents the number of completion candidates in response to the query prefix.
12 . The system of claim 11 , wherein the one or more segmentation candidates are precomputed by a subword encoder and cached in the segmentation database prior to runtime.
13 . The system of claim 12 , wherein the subword encoder is constructed as a finite state transducer (FST) during training stage prior to runtime.
14 . The system of claim 13 , wherein the FST is constructed by:
constructing a trie structure with a subword vocabulary set extracted from a query log as keys,
adding a transition from each exit state of the trie structure to a start state with an input label representing a failure or fallback transition and an output label associated with the respective exit state; and
performing a breadth-first traversal on the trie structure to add additional failure or fallback transitions at every intermediate state.
15 . The system of claim 13 , wherein the one or more segmentation candidates are precomputed by a breadth-first traversal on the FST from a given state representing a determinate token in a sequence of input characters from the training dataset.
16 . The system of claim 11 , wherein the respective set of completion candidates and corresponding likelihood scores are precomputed by a n-gram language model prior to runtime.
17 . The system of claim 16 , wherein the n-gram language model is constructed as a weighted FST as having a plurality of states, each state representing a history of a subword sequence along a path from a start state to the respective state.
18 . The system of claim 17 , wherein the weighted FST has a plurality of transitions between states, and each transition is associated with a weight representing a likelihood of an output label given the history of the state.
19 . The system of claim 18 , wherein the respective set of completion candidates are precomputed by iterating each state on the weighted FST and generating the plurality of completion candidates for the respective segmentation candidate as having highest likelihoods via beam search.
20 . The system of claim 11 , wherein the number of completion candidates are presented as the query prefix is being entered via the user interface.
21 . A processor-readable non-transitory storage medium storing a plurality of processor-executable instructions for query autocompletion, the instructions being executed by one or more hardware processors to perform operations comprising:
receiving a query prefix from a user interface;
forming a sequence of input characters based on the received query prefix;
encoding the sequence at subword level by retrieving one or more segmentation candidates corresponding to the query prefix from a segmentation database;
retrieving, for each segmentation candidates, a respective set of completion candidates and corresponding likelihood scores from a completion database;
selecting a number of completion candidates having highest likelihood scores among all completion candidates corresponding to the one or more segmentation candidates; and
presenting, via the user interface, the number of completion candidates in response to the query prefix.