Text Classification in Java

Question

Hi, I need some sort of solution in Java for the following requirements:

1. Search in a text for certain terms (each term can be 1-3 words). For example: {"hello world", "hello"}. The match need to be exact.
2. There are about 500 types of terms groups each contains about 30 terms.
3. Each text might contain up to 4000 words.

performance is an important issue.

Thanks, Rod

Answer 1

Use regex expressions. See: http://java.sun.com/docs/books/tutorial/essential/regex/

Answer 2

I have done something similar for a bespoke spam filter.

A technique I found to be both simple and fast is:

1. Split the input file into words first.
2. Call intern() on each word, to simplify the comparisons in step 3.
3. Create a Term class, encapsulating an array of up to three strings. Its equals() method can do pointer comparison on the strings, rather than calling String.equals(). Create a Term instance for each group of 2 or 3 consecutive words in the input.
4. Use a Multimap (from Google Collections) to map each term to the set of files in which it appears.

Answer 3

There seems to be two parts to this. Figuring a decent algorithm, and implementing it in Java. (For the moment let's put aside the idea that surely "out there" someone has already implemented this, and you can probably find some ideas.)

Seems like we want to avoid repeat expensive work. but it's not clear where the costs would be. So I guess you'll need to be prepared to benchmark a few candidate appraoches. Also have in mind what is "good enough".

Start wih the simplest thing you can think of that works. Measure it. You might get the surprising result that it's good enough. Stop right there! For example, this is really dumb:

 read text into String (4k, that's not too big)

 for each term
     use regexp to find matches in text

but it might well give a sub-second response time. Would your users really care if you took a 200ms response down to 100ms? How much would they pay for that?

Another approach. I wonder of this is faster?

 prepare a collection of terms keyed by first word

 tokenize the text

 for each token
    find terms that match
    check for match (using look ahead for multi-word terms)

As for implementing in Java. Separate problem ask specific questions if you need to.