factorie/factorie — pull request #189 by Craigacp (2014-06-22 03:56:58+00:00)
Title: Aho-Corasick Trie based Lexicons

This pull request implements the Aho-Corasick string matching algorithm and uses it to replace the current SuffixTree based lexicon implementation. It fixes issue #185, by looking up the whole input at once, preserving the context (which is the issue with the current `PhraseLexicon` implementation) and examining each token once. The `ChainPhraseLexicon` gets around this context problem by tracing through the linked list of tokens for each individual token which wastes a lot of work when used to tag a token sequence (as it looks at each token multiple times). The old implementations still exist, the new implementation is called `TriePhraseLexicon`. TriePhraseLexicon has the same semantics as `ChainPhraseLexicon.contains()` when using `TriePhraseLexicon.tagMentions()` and supplying the token sequence, and the same semantics as `PhraseLexicon.contains()` when using the `TriePhraseLexicon.contains()` methods (i.e. it checks to see if the supplied sequence is an exact match for a lexicon term, irrespective of context outside the supplied sequence).

Startup time to tag 3 test documents using `NoEmbeddingsConllStackedChainNER` (includes lexicon loading, which is the majority of the time):
`ChainPhraseLexicon` - 113070ms
`PhraseLexicon` - 49534ms
`TriePhraseLexicon` - 138995ms

10th run of the StackedChainNER (steady state runtime) on the same three documents:
`ChainPhraseLexicon` - 53776ms
`PhraseLexicon` - 950ms
`TriePhraseLexicon` - 926ms

Runtimes are on a mid 2012 15" rMBP. TriePhraseLexicon is slower to startup than the other two lexicons, but the steady state performance is the same as PhraseLexicon, and both are much faster than ChainPhraseLexicon. I'm going to look into improving the startup time of the TriePhraseLexicon as it's quite high (early profiling suggests its GC pressure as it makes lots of queues on construction, so it might be possible to fix that by converting them to ArrayBuffers). Brief empirical testing shows the NER performance is better than with the `PhraseLexicon` and approximately the same as the `ChainPhraseLexicon`, but I don't have access to the Conll or Ontonotes labelled datasets yet so I can't report numbers on those.

I've updated each NER class to use the new lexicon lookup methods.

`CorefMentions.scala` and `NounPhraseEntityType.scala` may need to be modified as the PhraseLexicon and TriePhraseLexicon both have slightly different semantics to the ChainPhraseLexicon (i.e. PhraseLexicon and TriePhraseLexicon's contains method looks to see if the string is an exact match in the lexicon, ChainPhraseLexicon uses the token and traverses backwards and forwards through the token context to find a match which is equivalent behaviour to TriePhraseLexicon.tagMentions). It's probably best if someone else looks at the coref stuff though, I'm not sure what it's supposed to do. Also the `TokenSpan.fromLexicon` method could probably be added to the TriePhraseLexicon with a variant of the tagMentions method.