CODEWITHSUNDEEP
algorithmsearchfull-text-searchtrie
kju
kju

Reputation: 146

TRIE search with logical operator

I want to build a simple searcher using TRIE (http://en.wikipedia.org/wiki/Trie) But I met a problem with Logical operators (AND, OR, NOT) to my trie. Are there any way to add an operator to Trie?

I want to search some cases below:

Input data with 3 sentences:

1. Tom is husband of Marry.
2. Tom is a teacher.
3. Tom is old friend of Marry.

Query like:

(Tom AND Marry NOT friend). 
=> result is 1st sentence.

And 2 way to build trie:

a. Build trie from Query and read input data search on it.

b. Build trie from input data with each sentence. search each word of query on trie.

Thank you.

Upvotes: 0

Views: 175

Answers (1)

M Oehm
M Oehm

Reputation: 29126

You need a data structure to relate a keywords to sets of sentences. This could be a hashmap or a trie. In your example:

Tom => [1, 2, 3]
Mary => [1, 3]
husband => [1]
teacher => [2]
friend => [3]

This data structure does not include the logical operators. You apply them separately, for example:

"Tom" => lookup("Tom")
"Tom AND Mary" => intersection(lookup("Tom"), lookup("Mary"))
"Tom OR Mary" => union(lookup("Tom"), lookup("Mary"))
"Tom NOT Mary" => difference(lookup("Tom"), lookup("Mary"))

In this pseudocode, only lookup operates on the trie or whatever data structure you'll use to store the words. The other functions operate on sets, i.e. the values of the stored items.

There are two questions you need to answer for your design: How do I relate words to sets of sentences? And how do I represent sets of sentences? A Trie is only an answer to the first question.

There's also the question of how to parse the query to get the logical function you need, of course. (You haven't specified a language, but before implementing a trie I'd try to use standard data structures that are available to you.)

Upvotes: 2

Related Questions