?
Simple and Efficient String Algorithms for Query Suggestion Metrics Computation
In order to make query suggestion mechanisms more efficient, it is important to have metrics that will estimate query suggestions quality well. Recently, Kharitonov et al.~\cite{SuggestEvalKharitonov} proposed a family of metrics that showed much better alignment with user satisfaction than previously known metrics. However, they did not address the problem of computing the proposed metrics. In this paper we show that the problem can be reduced to one of the two string problems which we call Top-$k$ and Sorted-Top-$k$. Given an integer $k$ and two sets of pairwise distinct strings (queries) with weights, $Q$ and $Q_{test}$, the Top-$k$ problem is to find, for each query $q \in Q_{test}$, its shortest prefix~$q[1..i]$ such that $q$ belongs to the list of $k$ heaviest queries in $Q$ starting with~$q[1..i]$. The Sorted-Top-$k$ problem is to retrieve, for each $q \in Q_{test}$ and $1 \le i \le |q|$, a position of~$q$ in the sorted list of the $k$ heaviest queries in $Q$ starting with $q[1..i]$. We show several linear-time solutions to these problems and compare them experimentally.