Aho-Corasick text matching on whole words?

Question

I'm using Aho-Corasick text matching and wonder if it could be altered to match terms instead of characters. In other words, I want the the terms to be the basis of matching rather than the characters. As an example:

Search query: "He",

Sentence: "Hello world",

Aho-Corasick will match "he" to the sentence "hello world" ending at index 2, but I would prefer to have no match. So, I mean by "terms" words rather than characters.

Rusel

What do you mean by "terms?" Can you give an example? – Fervid

Answer 1

One way to do this would be to use Aho-Corasick as usual, then do a filtering step where you eliminate all false positives. For example, every time you find a match, you can confirm that the next and previous characters in the input are non-letter characters like spaces or punctuation. That way, you get the speed of the Aho-Corasick lookup, but only consider matches that appear as whole words in the text.

Hope this helps!

Fervid

That's what I thought but while checking the next letter is trivial, checking the previous one in a UTF-8 encoded string is actually fairly complex because you cannot just go one byte back but have to take into account the complete variable-length encoding of that prior character. – Keefe

Answer 2

One possibility would be to include the space character in your search term, possibly after pre-processing your input to convert all sorts of white space (space, line feed, carriage return, tab...) to the same space character.

Another possibility would be to think of the characters of your alphabet, as far as Aho-Corasick is concerned, as being words. Aho-Corasick will work just as quickly (if not more quickly) with an alphabet of size 2^32 where each word seen in the input text is encoded as a single character, as it will with an alphabet of size 2^8 where a character is just a single byte, as usual.

In either case you have to make a decision about what your pre-processing does with punctuation.

Kuomintang

Answer 3

If you use the method onlyWholewords() it should have no results for your example above. For example:

Trie trie = Trie.builder()
             .onlyWholeWords()
             .addKeyword("He")
             .build();
Collection<Emit> emits = trie.parseText("Hello World");

emits in this case will be empty.

It will only reult in whole words only that are "he".

Although beware of characters that are not [a-z A-Z]. for example if you:

"He//Is" 

It would pick up the "He" and ignores the "//"

Two things to add:

1. if you want to assert word boundary, you can use:

   onlyWholeWordsWhiteSpaceSeparated() instead of

   onlyWholeWords()

2. If you want to "white-list" some characters, this read might be helpful:

The word characters used are the default ones modified by the ones provided and boolean flags signal where characters are turned on and off. This is useful when you just want to turn off a specific character in the set of default characters. For example:

The word characters used are the default ones modified by the ones provided and boolean flags signal where characters are turned on and off. This is useful when you just want to turn off a specific character in the set of default characters. For example:

new WholeWordMatchSet(keywords, true, ['_', '='], [false, true])

Will produce a set where letters and digits and - and = are considered word characters, but not _.

Brandabrandais

Answer 4

Very late to the party, but another option is to insert some symbols into the trie that represent the start and end of words. Then, during the matching stage, they must match accordingly. I'm about to try that approach myself.

Apelles