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.
精彩评论