I have a large number of long strings, and I need to search them for a given list of words as fast as reasonably possible. (Neither the strings nor the words are constants) I learned that I can preprocess the strings that I'm going to be searching for my words by building a suffix array and an lcp array, and that I should be able to make the searches faster by doing so. I was wondering, however, if I could preprocess the wordlist in some way as well. It is quite possible that the words will have common parts. I would like to build something like a "word genealogy tree" (or another structure that would achieve the same effect ) where the substring that can be found in a family of words would be at the top and which would then branch down (for both the prefixes and the suffixes of the ancestor) as the descendants would go. I imagine that this would allow me to discard whole branches or trees quickly if an ancestral node failed to match. Could you please direct me to a suitable strategy that would help me achieve my goal (in this or any other reasonably efficient way)? Note: I can't really make use of much existing code (can make use of ideas, though). I'm pretty much limited to the standard c library.
|
|
Searching in a string that changes often, and looking for a set of words, I would use Aho-Corasick, an extension of KMP that builds a tree (based on the set of words) and looks for the words in parallel. |
|||
|
|
|
A convenient way would be to use the KMP algorithm with hash filtering. I understand that your list of string can change anytime so preprocessing may be irrelevant. (although there exist dynamic preprocessing methods). I would suggest to assign each string from your list an hash number (if it is integer it is a number between 0 to 2^32) and when you got a query for some string s, you will calculate h=hash(s) [hash(x) could be a function that summarize the values of the characters in string x]. Now you can search for matches only on the strings in the list that their hash value = hash(s). Clearly the number of required search will reduced. Now for each string in the list such that it's hash = hash(s) make a search using KMP which give you a result in time O(n+m) [n is the text and m is the pattern lengthes] so if there k texts remained after the filtering you will get the result in time O(k(n+m)). |
|||||
|
|
Well the scenario is clear now. My solution is Generalized Suffix tree. You will need to learn a bit about it before implementation. (I didn't find full 'plug-n-play' implementation in the internet but maybe you'll find). Let's say that the length of all the strings in the list together is N and the pattern you are searching is of length M, the solution will require a processing time of O(N) and query time of O(M + #occ). #occ is the number of occurences found by the query. There are many references in the interner so I will not copy all of them. You can see what's GST in http://en.wikipedia.org/wiki/Generalized_suffix_tree And some article of how to build it in linear time in http://www.drdobbs.com/database/a-practical-suffix-tree-implementation/184404184 |
||||
|
|
