开发者

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 contai开发者_StackOverflowning 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....


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜