Algorithm for multiple word matching in text

Question

I have a large set of words (about 10,000) and I need to find if any of those words appear in a given block of text.

Is there a faster algorithm than doing a simple text search for each of the words in the block of text?

Answer 1

input the 10,000 words into a hashtable then check each of the words in the block of text if its hash has an entry.

Faster though I don't know, just another method (would depend on how many words you are searching for).

simple perl examp:

my $word_block = "the guy went afk after being popped by a brownrabbit";
my %hash = ();
my @words = split /\s/, $word_block;
while(<DATA>) { chomp; $hash{$_} = 1; }
foreach $word (@words)
{
    print "found word: $word\n" if exists $hash{$word};
}

__DATA__
afk
lol
brownrabbit
popped
garbage
trash
sitdown

Answer 2

The answer heavily depends on the actual requirements.

1. How large is the word list?
2. How large is the text block?
3. How many text blocks must be processed?
4. How often must each text block be processed?
5. Do the text blocks or the word list change? If, how frequent?

Assuming relativly small text blocks compared to the word list and processing each text block only once, I suggest to put the words from the word list into a hash table. Then you can perform a hash lookup for each word in the text block and find out if the word list contains the word.

If you have to process the text blocks multiple times, I suggest to invert the text blocks. Inverting a text block means creating a list for each word that containing all the text blocks containing the specific word.

In still other situations it might be helpful to generate a bit vector for each text block with one bit per word indicating if the word is contained in the text block.

Answer 3

Try out the Aho-Corasick algorithm: http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

Answer 4

Build up a trie of your words, and then use that to find which words are in the text.

Answer 5

The Boyer-Moore string algorithm should work. depending on the size/# or words in the block of text, you might want to use it as the key to search the word list (are there more words in the list then in the block). Also - you probably want to remove any dups from both lists.