How can I parse free text (Twitter tweets) against a large database of values?

Question

Hi there

Suppose I have a database containing 500,000 records, each representing, say, an animal. What would be the best approach for parsing 140 character tweets to identify matching records by animal name? For instance, in this string...

"I went down to the woods to day and couldn't believe my eyes: I saw a giant polar bear having a picnic with a red squirrel."

... I would like to flag up the phrases "giant polar bear" and "red squirrel", as they appear in my database.

This strikes me as a problem that has probably been solved many times, but from where I'm sitting it looks prohibitively intensive - iterating over every db record checking for a match in the string is surely a crazy way to do it.

Can anyone with a comp sci degree put me out of my misery? I'm working in C# if that makes any difference. Cheers!

Answer 1

Assuming the database is fairly static, use a bloom filter. It is a degenerate form of hash table that only stores bits indicating the presence of a value, without storing the value itself. It is probabilistic, since hashes may collide, so each hit would require a full lookup. But a 1 MB bloom filter with 500,000 entries can have as low as a 0.03% rate of false positives.

Some math: To get this low rate requires up to 23 hash codes, each with 23 bits of entropy, for a total of 529 bits. Bob Jenkins's 64-bit hash function generates 192 bits of entropy in a single pass (if you use the unreported variables in hash(), which Bob cites as probably being OK as a "mediocre" hash), thus requiring at most three passes. Because of the way bloom filters work, you don't need all the entropy on every query, since most lookups will report a miss well before getting to the 23rd hash code.

EDIT: You will obviously have to parse words from the text. Finding every instance of /\b\w+\b/ will probably do for a first version.

To match phrases, you will have to test every n-word subsequence (aka n-gram) where n is every number from 2 to the largest phrase in your dictionary. You can make it much cheaper by adding any word that appears in a phrase to a separate bloom filter, and only testing n-grams for which every word passes this second filter.

Answer 2

Why reinvent the wheel. Use a free text indexing tool to handle the heavy lifting. Lucene.Net comes to mind.

Answer 3

What's wrong with Regex? =) That will do for small text searches.

string input = @"I went down to the woods to day and couldn't believe my eyes: I saw a bear having a picnic with a squirrel. I am a human though!";
Regex animalFilter = new Regex(@"\b(bear|squirrel|tiger|human)\b");
foreach (Match s in animalFilter.Matches(input))
{
    textBox1.Text += s.Value + Environment.NewLine;
}

It gives output:

bear
squirrel
human

Some more:

string input = @"I went down to the woods to day and couldn't believe my eyes: I saw a bear having a picnic with a squirrel. I am a human though!";
Regex animalFilter = new Regex(@"\b(bear|squirrel|tiger|human)\b");

Dictionary<string, int> animals = new Dictionary<string, int>();

foreach (Match s in animalFilter.Matches(input))
{
    int ctr = 1;
    if (animals.ContainsKey(s.Value))
    {
        ctr = animals[s.Value] + 1;
    }
    animals[s.Value] = ctr;
}
foreach (KeyValuePair<string,int> k in animals)
{
    textBox1.Text += k.Key + " ocurred " + k.Value + " times" + Environment.NewLine;
}

Results:

bear ocurred 1 times
squirrel ocurred 1 times
human ocurred 1 times

Answer 4

Have you tried to build a trie for your dictionary? If you split the tweet into pieces and match each piece to the trie, you get linear complexity.