CODEWITHSUNDEEP
hashsearchbloom-filter
Reddy
Reddy

Reputation: 1628

Needed an efficient way for search for the following specfic requirement

I have to search a given file name (let say Keyword) in a directory containing files. If there were only few keywords to be searched, I could have used regular search (like creating an array of file names residing in the specified directory and then search each file name with the given keyword). Since I need to search very large number of keywords dynamically, its not efficient to search using regular. I had couple of ideas:

1.using hashing (but not clear how to design it)

2.Using Bloom Filters for searching (please google , if u dont know about it, its working is very interesting!): Problem in using bloom filters is "False positives are possible, but false negatives are not". I might miss some results....

Upvotes: 1

Views: 103

Answers (1)

Ben S
Ben S

Reputation: 69342

Before searching, create a trie of all positive matches.

Creating the trie will take O(n) where n is the number of words.

To to search, try to match the word against the trie. Look-ups are done in O(m) where m is the length of the word to look-up.

Total runtime: O(n + nm) => O(nm) to find all the words.

Upvotes: 1

Related Questions