fast comparison

Are the substrings always whole words as in the example?
If not you may want to look into suffix trees.

yes, they are always whole words.

~guyaton

I'd break down the string into smaller pieces, separated by " " ... i.e words.


pseudo:

while (not at end of the string)
{
word = GatherLettersUntilSpaceIsFound();

CheckForMatch(word);
}


hmm... maybe that wasn't very helpful... :/

anyway, peace!

Quote:

Original post by guyaton yes, they are always whole words.

Great, that makes things a lot easier.
Then you could simply store all the words in a data structure with fast search times (such as a hash table or even std::map) and compare the input word-for-word.

The most efficient way to do this in the general case would probably be to treat the list of keywords as a regular grammar, and build a FSA which flagged keywords as it found them. For more information on how to do this, read up on how regular expressions are compiled and processed.

for clarification for myself, make a hash of the "comparing string" as i used in my example? havn't used a hash table in C++ but i know it is a member of the stl. how would i do it using c++ stl?

thanks again
~guyaton

Depending on how long your strings are, you may be interested in the Boyer-Moore String matching algorithm.
[google]

Why can't you just load up your reference strings in an array, and just cycle through any phrase something like this:

unsigned int i;std::string my_phrase = "some sample string for testing purposes";std::vector<std::string>my_words;my_words.push_back("for");my_words.push_back("noun");my_words.push_back("something");my_words.push_back("is");my_words.push_back("test");my_words.push_back("blah");for ( i = 0; i < my_words.size(); ++i){  if (my_phrase.find(my_words) != std::string::npos)  {      // Do something if found.  }}

--random_thinker

Edit: No, that won't work, it will show "test" is there...hang on...

[Edited by - random_thinker on August 29, 2005 3:20:09 PM]

random_thinker: i was just trying to find something fairly efficiant. If I have 30 keyworks and say 40,000 works (even if i loaded it all line by line) it could take a while to search thru each word. This is why I am trying to find something efficiant.

~guyaton

edit: i came up with this real quick...still questioning how fast it is:



edit #2: been reading on the Boyer-Moore Algorythm and it sounds pretty fast and cool. might check that out.

[Edited by - guyaton on August 29, 2005 4:45:13 PM]

Oh, I see. You could also try using an ifstream that would only pick up 'whole words', something like the following (you might need to strip punctuation from current_string):



--random_thinker

if anyone else is interested found a really good tut of what the Boyer-Moore algorithm is compliments of www.google.com

http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html

~guyaton

guyaton,

I would have thought that if you could limit your string search to the 30 words rather than the 40,000 by streaming the 40,000 one at a time then the C++ string search algorithm should be fast enough, no?

--random_thinker

You can do things like find_first_of() which might speed things up...

Quote:

Original post by Anonymous Poster You don't need/want boyer-moore here because you're searching for specific words.. And std::map is not a hash map, it's a tree which also keeps the elements in order (a feature you don't need here). There's no standard hash map in STL (yet) although many STL implementations place some sort of hash_map into the std-namespace. hash map has less indirection than tree structures, so it's easy on cache. It should be a very fast solution.. Whether you should place the comparing strings in the hash map or the words in the other string, depends on which ones change less often (you want to build the hash only rarely)

In all honesty that's generally quite good advice, and I must admit, I didn't read every previous post before suggesting the Boyer-Moore algorithm (particularly the ones about it always being single words). I also didn't post a link because there's bound to be HEAPS of stuff on the net about it.

I'm a big fan of hash-tables myself too, however the Boyer-Moore, or other related algorithms are very likely to be around as quick as hashing the words when you consider the time taken for hashing every word.
The Boyer-Moore algorithm has a reasonably good payback for a relatively smallish setup cost, not to mention a relatively smallish memory overhead compared to hashing.

It's all about tradeoffs between memory usage / speed / flexability / simplicity etc. I'm merely saying that it's still an option, depending on how important the things I just mentioned are.[smile]

unless there is a faster way to compare multiple strings with one string.

What I am trying to do is extract variables out of a .java file and retreive the line number that they are on. At first I thought maybe the fastest way, would be to test if the item was a function, function call or a loop and everything that ISN'T would be a variable (excluding {,} and any other odd possibilities). Is there an easier way instead of testing for "void", "class" etc?

~guyaton

Why not use grep then? I think that it uses the Boyer-Moore algorithm. BTW, I've played around with this code:



on a tex file (well, really a .lyx file) that is 59453 words in length, and it runs quite fast. The biggest problem that I see is making sure that all your 'found' strings are only whole words, that you pick up capitalized and non-capitalized, that you pick up those that end with '.' or ',' but not other strings, etc. I think that this type of filtering may slow your program more than anything else.

Anyway, here's the output:

Time : 0.08 s.
Found : 853
Total : 59453

Is that not fast enough? I have to say that I do agree with Sneftel on this one, because you want whole words in the context of puncuation, an FSA is really the most efficient way to go, and not that hard to do.

--random_thinker

Edit: And if you want the line number where found words are, you can filter using std::getline() to accomplish this.

I've had to do something very similar, for moderately large amounts of data (chunks of 20-30KB at a time, with usually between 5 and 20 search words, although sometimes as many as 100+). The solution I ended up with was fairly simple:

- Construct a simple hash algorithm that hashes a string into a 32-bit unsigned integer. This is fairly trivial and you can find them all over the place with a quick Google search; checking GameDev's articles section should net you an article on hashing as well. You might consider tweaking the hash function a bit so it performs well on the types of input you're dealing with.

- Go through each search word and find its hash. Store the hash and the full keyword (as a std::string) in a structure, and then hold this in a std::vector.

- Once the vector is completely built, sort it by the hash values.

- Take the input data and parse it into words. For each word, compute the hash, and store the hash and the matching word in a second vector. You can do this in a single pass over the input string fairly easily.

- Determine the smaller of the two vectors - we'll call it S, and the other vector L. Iterate over each element in S. With the hash from the element, do a binary search for a matching hash in L. If both vectors are sorted by hash, you can speed up the binary search a bit by excluding the top portion of L from further surches each time you find a matching hash in S. If a word is found in both S and L, store it in a result list. In the result list, also store the word that was found in the input data (which might be S and might be L, depending on how the data works out).

- Check through the result list for collisions (words that have the exact same hash but are different strings). These should be quite rare, especially if you calibrate your hash function a bit beforehand, but it is smart to be prepared for handling them.

- If S tends to be very short compared to L, you can skip doing two vectors and just look for the hash of each word in the search list as you parse the input data. This will reduce memory consumption, and, for small numbers of search words, can speed things up a bit as well. In this case it will also benefit you greatly to check for collisions during the parse rather than as a final step.


That should get you a very fast solution. If your memory space tends to be large, it might create some CPU cache problems. In this case, opt for just storing 8 bytes per string record in a flat C-style array (32 bits for hash plus a 32 bit pointer to the actual word string). If collisions do not matter or are so rare they can be ignored, you can trim this down further to a plain 32 bits for the hash itself, although I don't recommend it.

If you're comfortable with managing your own data, you can make this still more efficient by building a data structure that resembles a chained hash table, and using it for the lookup rather than doing collision checking as a post-process step. However this tends to introduce large penalties for collisions because they incur an extra layer of indirection and therefore cache coherency problems. Unless you need to handle vast amounts of data in realtime, it's probably best to stick with a post-process collision check or an in-process check depending on which you find simpler to implement.

Quote:

Original post by guyaton unless there is a faster way to compare multiple strings with one string. What I am trying to do is extract variables out of a .java file and retreive the line number that they are on. At first I thought maybe the fastest way, would be to test if the item was a function, function call or a loop and everything that ISN'T would be a variable (excluding {,} and any other odd possibilities). Is there an easier way instead of testing for "void", "class" etc? ~guyaton

In that case it sounds more like you'll need a more complex parser than something that merely tokenizes things into words. Otherwise, text within string literals would look like variables.
Or are you really more focused on speed than correctness?

If you care about speed, listen to the poster that talked about building the FSA. Try reading up on regular expressions and converting them to NFAs and DFAs. I didn't spend too much time looking, but this link might help:

http://lambda.uta.edu/cse5317/notes/node9.html