Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

Question

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?

Answer 1

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).