Java: Matching Phrases in a String

Question

I have a list of phrases (phrase might consist of one or more words) in a database and an input string. I need to find out which of those phrases appear in the input string.

Is there an efficient way to perform such matching in Java?

Answer 1

A quick hack would be:

1. Build a regexp based on the combined phrases
2. Construct a set listing the phrases that haven't matched so far
3. Repeatedly run find until all phrases have been found or end of input is reached, removing matches from the set of remaining phrases to find

That way, the input is traversed only once, regardless how many phrases you provide. If the regexp compiler generates an efficient matcher for multiple alternatives, this should yield decent performance. However, this depends a lot on your phrases and input string, as well as the quality of the Java regexp engine.

Sample code (tested, but not optimized or profiled for performance):

public static boolean hasAllPhrasesInInput(List<String> phrases, String input) {
    Set<String> phrasesToFind = new HashSet<String>();
    StringBuilder sb = new StringBuilder();
    for (String phrase : phrases) {
        if (sb.length() > 0) {
            sb.append('|');
        }
        sb.append(Pattern.quote(phrase));
        phrasesToFind.add(phrase.toLowerCase());
    }
    Pattern pattern = Pattern.compile(sb.toString(), Pattern.CASE_INSENSITIVE);
    Matcher matcher = pattern.matcher(input);
    while (matcher.find()) {
        phrasesToFind.remove(matcher.group().toLowerCase());
        if (phrasesToFind.isEmpty()) {
            return true;
        }
    }
    return false;
}

Some caveats:

• The code above will match phrases as substrings of words. If only complete words should match, you will need to add word boundaries ("\b") to the generated regexps.
• The code must be modified if some phrases may be substrings of other phrases.
• If you need to match non-ASCII text, you should add the regexp option Pattern.UNICODE_CASE and call toLowerCase(Locale) instead of toLowerCase(), using a suitable Locale.