Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Note 2: I wrote that neither the strings nor the words are constants. This is inaccurate, I'm sorry for not putting it better. Both the strings and the words are supplied from outside for each run of the program. After that they remain constant. Each run of the program should go as follows: 1) read strings 2) read words 3) preprocess strings 4) (?) preprocess words 5) a) find all occurences of each word in each string and b) delete them (or achieve the same thing that a) & b) do without actually doing it separately) –  ThorX89 Nov 26 '12 at 19:01
add comment

3 Answers

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.

share|improve this answer
add comment

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)).

share|improve this answer
    
Is "hush number" the real term or is it "hash number" ? –  user12630 Nov 26 '12 at 19:11
    
sorry. it is 'hash' –  Bush Nov 27 '12 at 4:33
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.