Answers inline, below:
David Buttler <[EMAIL PROTECTED]> wrote on 05/08/2008 06:59:31 PM:
>
> I wrote a tool similar to this, but with a bit less functionality,
so I
> think this type of tool is very useful and I would be interested in
> contributing. The key features that I would look for are:
> 1) it is fast
I don't have any hard numbers to share at the moment, but performance
is very good, even with very large dictionaries.
> 2) it can handle very large dictionaries without slowing down. For
> example, you might want to load UMLS into a dictionary (Assuming
you had
> sufficient memory)
It can. Or so I say :)
> You mentioned that you support 10K entries -- is the runtime
dependent
> on the number of entries in the dictionary or on the number of token
> matches? Is the internal data structure some type of state machine?
>
My comment about 10K entries was just an example. You're limited only
by your available memory. Someone I know has used the annotator with
millions of entries with no problems.
The internal data structure is simply a map keyed by a head word,
pointing to an potential matches starting with that head word (ordered
by length, to facilitate longest-match). When order-independent lookup
is enabled (yes, this is a dangerous thing, but can be useful in some
domains), each token of each entry is used as a key, which does blow
up memory usage a bit.
> It wasn't clear to me if you supported boolean operators but perhaps
> this is the type of functionality that you would put in a post
filter?
> e.g. you match 'colon' and 'rectum' separately and only produce
results
> when both matches are made, but not when 'colonoscopy' is present.
>
That would probably be done with some post-processing. Matching is
strictly done as string matches, with the only exception being case-
insensitivity, stemming and token skipping (either via stop word list
or based on particular feature values, as I described [or tried to]).
One other possibility might be to run the annotator twice, once
marking all tokens in the presence of 'colonoscopy' with some marker,
then skipping all tokens with said marker in the second pass. That's
not too efficient, but might be suitable in certain circumstances.
> So, if you could skip tokens, would it be possible for an entire
> document to match assuming the dictionary contained 'A B' and the
first
> token in the document is 'A' and the last token is 'B'? Or do you
limit
> the match to a window of some type? If it is a window, is the window
> defined by the data (e.g. paragraph markers) or by the dictionary
(e.g.
> N tokens?)
As I said in my original post: "Input tokens are processed one span at
a time, where both the token and span (usually a sentence) annotation
type are configurable." So, you could specify DocumentAnnotation as
the span, but I have usually used a sentence. In any case, the span to
use is an annotation, and the type of annotation is specified in the
descriptor file used for running the annotator.
>
> Another feature that seems useful is token-based regular expressions
> (e.g. matching 'run*' or '199?'). This feature really killed
> performance when I added it to my tool; perhaps you have a better
way of
> approaching that requirement.
Nope. This is not supported at this point. Some have suggested adding
this, but it was not something deemed necessary in any of my projects,
and would likely be difficult to implement efficiently, as you had
found. It would certainly be a nice thing to add in the next release,
if done well...
>
> In any case, it seems very interesting.
> Dave
>
> Michael A Tanenblatt wrote:
> > My group would like to offer the following UIMA component,
ConceptMapper,
> > as an open source offering into the UIMA sandbox, assuming there is
> > interest from the community:
> >
> > ConceptMapper is a token-based dictionary lookup UIMA component.
It was
> > designed specifically to allow any external tokenizer that is a
UIMA
> > component to be used to tokenize its dictionary. Using the same
tokenizer
> > on both the dictionary and for subsequent text processing prevents
> > situations where a particular dictionary entry is not found,
though it
> > exists, because it was tokenized differently than the text being
processed.
> >
> > ConceptMapper is highly configurable, in terms of:
> > * the way dictionary entries are mapped to resultant annotations
> > * the way input documents are processed
> > * the availability of multiple lookup strategies
> > * its various output options.
> >
> > Additionally, a set of post-processing filters are supplied, as
well as an
> > interface to easily create new filters. This allows for
overgenerating
> > results during the lookup phase, if so desired, then reducing the
result
> > set according to particular rules.
> >
> > More details:
> >
> > The structure of the dictionary itself is quite flexible. Entries
can have
> > any number of variants (synonyms), and arbitrary features can be
associated
> > with dictionary entries. Individual variants inherit features
from parent
> > token (i.e., the canonical from), but can override them or add
additional
> > features. In the following sample dictionary entry, there are 5
variants of
> > the canonical form, and as described earlier, each inherits the
SemClass
> > and POS attributes from the canonical form, with the exception of
the
> > variant "mesenteric fibromatosis (c48.1)", which overrides the
value of the
> > SemClass attribute (this is somewhat of a contrived example, just
to make
> > that point):
> >
> > <token canonical="abdominal fibromatosis" SemClass="Diagnosis"
POS="NN">
> > <variant base="abdominal fibromatosis" />
> > <variant base="abdominal desmoid" />
> > <variant base="mesenteric fibromatosis (c48.1)"
> > SemClass="Diagnosis-Site" />
> > <variant base="mesenteric fibromatosis" />
> > <variant base="retroperitoneal fibromatosis" />
> > </token>
> >
> > Input tokens are processed one span at a time, where both the
token and
> > span (usually a sentence) annotation type are configurable.
Additionally,
> > the particular feature of the token annotation to use for lookups
can be
> > specified, otherwise its covered text is used. Other input
configuration
> > settings are whether to use case sensitive matching, an optional
class name
> > of a stemmer to apply to the tokens, and a list of stop words to
to ignore
> > during lookup. One additional input control mechanism is the
ability to
> > skip tokens during lookups based on particular feature values. In
this way,
> > it is easy to skip, for example, all tokens with particular part
of speech
> > tags, or with some previously computed semantic class.
> >
> > Output is in the form of new annotations, and the type of resulting
> > annotations can be specified in a descriptor file. The mapping from
> > dictionary entry attributes to the result annotation features can
also be
> > specified. Additionally, a string containing the matched text, a
list of
> > matched tokens, and the span enclosing the match can be specified
to be set
> > in the result annotations. It is also possible to indicate
dictionary
> > attributes to write back into each of the matched tokens.
> >
> > Dictionary lookup is controlled by three parameters in the
descriptor, one
> > of which allows for order-independent lookup (i.e., A B == B A),
another
> > togles between finding only the longest match vs. finding all
possible
> > matches. The final parameter specifies the search strategy, of
which there
> > are three. The default search strategy only considers contiguous
tokens
> > (not including tokens frm the stop word list or otherwise skipped
tokens),
> > and then begins the subsequent search after the longest match.
The second
> > strategy allows for ignoring non-matching tokens, allowing for
disjoint
> > matches, so that a dictionary entry of
> >
> > A C
> >
> > would match against the text
> >
> > A B C
> >
> > As with the default search strategy, the subsequent search begins
after the
> > longest match. The final search strategy is identical to the
previous,
> > except that subsequent searches begin one token ahead, instead of
after the
> > previous match. This enables overlapped matching.
> >
> >
> > --
> > Michael Tanenblatt
> > IBM T.J. Watson Research Center
> > 19 Skyline Drive
> > P.O. Box 704
> > Hawthorne, NY 10532
> > USA
> > Tel: +1 (914) 784 7030 t/l 863 7030
> > Fax: +1 (914) 784 6054
> > [EMAIL PROTECTED]
> >
> >
> >
>
