2
$\begingroup$

Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases:

index      phrase
-----------------------------------------
0          Stack Overflow
1          Math Overflow
2          Super User
3          Webmasters
4          Electrical Engineering
5          Programming Jokes
6          Programming Puzzles
7          Geographic Information Systems 

The expected behaviour is:

query         result
------------------------------------------------------------------------
s             Stack Overflow, Super User, Geographic Information Systems
web           Webmasters
over          Stack Overflow, Math Overflow
super u       Super User
user s        Super User
e e           Electrical Engineering
p             Programming Jokes, Programming Puzzles
p p           Programming Puzzles

To implement this behaviour I used a trie. Every node in the trie has an array of indices (empty initially).

To insert a phrase to the trie, I first break it to words. For example, Programming Puzzles has index = 6. Therefore, I add 6 to all the following nodes:

p
pr
pro
prog
progr
progra
program
programm
programmi
programmin
programming
pu
puz
puzz
puzzl
puzzle
puzzles

The problem is, when I search for the query prog p, I first get a list of indices for prog which is [5, 6]. Then, I get a list of indices for p which is [5, 6] as well. Finally, I calculate the intersection between the two, and return the result [5, 6], which is obviously wrong (should be [6]).

How would you fix this?

$\endgroup$
2
$\begingroup$

Let's fix some names. Let $q_1, \dots, q_k$ be the query strings and $w_1, \dots, w_n$ the existing phrases. Denote with $w_{i,1}, \dots, w_{i,k_i}$ the words contained in phrase $w_i$, and with $a \sqsubseteq b$ the relation "$a$ is a prefix of $b$".

Currently, you have implemented to obtain this:

$\qquad\displaystyle \{ i \in [1..n] \mid \forall j \in [1..k]\ \exists j' \in [1..k_i].\ q_j \sqsubseteq w_{i,j'}\}$.

Note how the $\exists$-operator does not preclude the same $j'$ for multiple $j$, and that's your problem (as far as I can tell). What you want is

$\qquad\displaystyle \{ i \in [1..n] \mid \exists J = \{j_1, \dots, j_k\} \subseteq [1..k_i]\ \forall j \in [1..k].\ q_j \sqsubseteq w_{i,j_j}\}$.

One way to implement this is to go with the double-indexing I used to describe the problem formally: each node gets the set of labels $(i,j)$ if its corresponding string is a prefix of $w_{i,j}$. Now, $i$ is a match if

  • every $q_l$ leads to a node with label $(i,\_)$ and
  • the second components of these labels are pairwise distinct (if there are multiple $(i,\_)$ for a single $q_l$, one has to check if there is a choice fulfilling the condition).

In your example, instead of just adding 6 to all these nodes you list, you'd add (5,1) and (6,1) to the prefixes of programming, and (6,2) to those of puzzles. Now, prog p gives you (5,1), (6,1) for prog and (5,1), (6,1), (6,2) for p; you can exclude 5 because it has the same second component for both query phrases whereas 6 has a "valid" match with (6,1) and (6,2).

$\endgroup$
  • $\begingroup$ Appreciate how you formalised the question and the proposed solution. All looks good except the last sentence. How would you decide if it's a valid match? I tried to formalise this last bit in this question. $\endgroup$ – Misha Moroshko May 9 '15 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.