BACKGROUND
natural language processing  is the computer processing of human language  <cit> .
it is a bidirectional chain of transformation from speech to language understanding - from sounds to semantics.
segments of this processing chain are designed to address different nlp problems, including audio to text transformation, text processing and semantic recognition.
this paper focuses on text processing.
tokenization typically plays a role in processing text.
tokenization is broadly defined as the segmentation of text for subsequent processing.
the definition’s breadth reflects the ambiguity and differences of tokenization strategies.
tokenization strategies can vary depending on language  <cit> , software goals  <cit>  and other criteria.
there is no widely accepted tokenization method for english texts, including biomedical texts  <cit> .
in contrast, there are widely accepted solutions to other nlp tasks.
the viterbi algorithm is a widely accepted solution for part-of-speech  tagging  <cit> .
pos tagging assigns tags to tokens, such as assigning the tag noun to the token paper.
similarly, the cky algorithm is a widely accepted solution for syntactic parsing  <cit> .
syntactic parsing constructs a syntactic structure such as a parse tree from a sequence  of tagged tokens.
although there is no widely accepted tokenization method, tokenization is an important component of language processing  <cit> .
as webster and kit  <cit>  argue, tokenization identifies basic units on which further processing depends.
for example, tokenization segments a sentence’s terminating symbol from its last word allowing subsequent processing to identify a text’s sentences .
hassler and fliedl  <cit>  suggest that tokenization is often perceived as a solved problem.
for tomanek, wermter and hahn  <cit> , tokenization can be perceived as “unsophisticated clerical work”.
on the other hand, there is evidence to support that tokenization is not trivial.
a single arabic word can be composed of four independent tokens  <cit> .
chinese words do not have obvious boundary markers  <cit> .
spanish and english can be considered to flow across whitespace boundaries .
biomedical names pose tokenization difficulties because they often contain special characters such as slashes or brackets  <cit> .
proper tokenization in these contexts is a non-trivial problem  <cit> .
within the domain of biomedical tokenization, he and kayaalp  <cit>  applied  <dig> tokenizers to  <dig> medline abstracts.
only  <dig> of the  <dig> tokenizers produced identical results and the differing results varied widely.
given the latter, he and kayaalp advocate awareness of a tokenizer’s details without clearly defining or specifying which tokenizer details are important.
tokenizer details are expected to influence whether a tokenizer is well suited or adaptable to a particular language processing task.
a poor choice of tokenizer is expected to cause  information loss  <cit> .
several tokenizers examined by he and kayaalp  <cit>  used simple rule based tokenization methods .
jiang and zhai’s  <cit>  empirical study of rule based tokenization supports the use of rule based tokenizers on specific texts.
rule based tokenization methods may perform well for specific texts but these methods appear to generalize poorly  <cit> .
other than rule based techniques, tokenization in the biomedical domain has been regarded as a classification task  <cit> .
classification assigns a label to objects.
for example, a classifier could assign a token-separator label to the space character.
classification tokenizers differ in their choice of object and their method for learning and applying tags.
biomedical classification-based tokenization can be divided into two approaches: classifiers that classify textual objects as a token boundaries  and classifiers that reassemble primitive tokens.
in other words, classifier-based tokenizers either split or join textual objects through classification.
split-join based tokenization approaches have applied a variety of machine learning methods with success as exemplified below.
a classifier was used to label selected symbols such as a space or a period as within a token or as a token separator  <cit> .
this split approach performed well on named entity only data  and poorly on named entities in medline abstracts.
this approach neglects un-delimited tokens such as “ <dig> cm”.
mcdonald, crammer and pereira  <cit>  applied multi-label classification techniques to tokenization.
their classifier assigned beginning , inside  and outside  labels to primitive token sequences.
the segments labeled with a b followed by consecutive i labels represented a single large token.
this join approach might also be considered as over-segment and repair because their classifier reassembled incorrectly segmented tokens.
tomanek, wermter and hahn  <cit>  trained two  classifiers to identify sentence and token boundaries using a corpus derived from the pennbioie and genia corpora.
input text was split into sentences and sentences were split into tokens.
the token-splitting classifier used preset token boundary symbols and corpus-based training to identify token boundaries.
wrenn, stetson and johnson  <cit>  used transitional entropy and conditional probability to detect token boundaries .
they compared their tokenization method to human specified sentence boundaries and a rule based tokenizer that segmented sentences by whitespace.
the authors acknowledge that the lack of a gold standard is the most important limitation of their work.
an example of this limitation is that their method is not evaluated on whether punctuation such as a comma is indicative of a token boundary.
motivation
we attempted to select an existing biomedical tokenizer for a biomedical text processing task.
the idiosyncratic nature of each biomedical tokenizer’s output, or documented output, complicated our selection.
he and kayaalp  <cit>  similarly found that output varied between tokenizers .
furthermore, we found that existing biomedical tokenizers generally lacked guidance on how to apply the tokenizer to new text.
as an example of the guidance we sought, consider the question of how improper tokenization of tokens, existing only in the new text, should be resolved.
to address the above difficulties, we identify and complete a novel tokenizer design pattern and suggest a systematic approach to tokenizer creation.
in so doing, we provide a definition of tokenization and describe software components to accompany the proposed definition.
we implement a tokenizer based on our design pattern that combines regular expressions and machine learning.
our machine learning approach differs from the previous split-join classification approaches.
we evaluate our approach against three other tokenizers on the task of tokenizing biomedical text.
RESULTS
algorithm and implementation
in this section, we present a novel tokenizer design pattern for biomedical tokenizers.
according to buschmann, henney and schmidt  <cit> , “a design pattern provides a scheme for refining elements of a software system or the relationships between them.
it describes a commonly-recurring structure of interacting roles that solves a general design problem within a particular context.”.
we present our tokenizer design pattern by defining a tokenizer’s input and output, by defining a tokenizer’s software components and by presenting related pseudocode.
our tokenizer design pattern is named the token lattice design pattern.
input and output
current tokenizers generally compute on raw text  or sentences .
we restrict a tokenizer’s input to raw text.
if the text contains well formed sentences then it may be possible to use existing software that segments text into sentences with few errors .
a tokenizer’s output definition should communicate a tokenizer’s behaviour and foster tokenizer reuse.
he and kayaalp  <cit>  discuss the variability in tokenizer output.
underlying this difference in output is a lack of agreement on what constitutes a token.
furthermore, tokenizers produce tokens based on an intrinsic token definition.
tokenizer output is generally idiosyncratic .
we restrict a tokenizer’s output to the most likely pos-tagged sequence of tokens, given some language model.
this implies that a tokenizer outputs tokens taggable with tags such as noun or adjective.
it also implies that a tokenizer must implement predefined pos tags such as the penn treebank’s  <cit> .
lastly, it implies that a tokenizer should produce a likely sequence of pos-tagged tokens.
for example, a tokenizer should not segment a chemical substance such as “ <dig> -epoxy-3-methyl-1-butyl-diphosphate” into  “ <dig> ,  <dig> epoxy  <dig> methyl  <dig> butyl diphosphate”.
we define the concept of pos-tokens as tokens that adhere to our stated output restrictions.
these restrictions blur the conventional boundary between tokenizers and pos-taggers .
we argue below that pos-tokens are expected to increase tokenization accuracy and tokenizer reuse.
chaining arbitrary tokens together is unlikely to form a valid  sentence.
accordingly, knowing a token’s pos tag indicates which pos tags and tokens are likely to occur in the token’s vicinity  <cit> .
for example, it is likely that a noun follows after the word the , whereas it is less likely that a verb follows the .
pos-tokens inherit language characteristics that are likely to increase tokenization accuracy given that these characteristics have been successfully exploited in the past .
inter-annotator agreement can be measured for pos tagging.
this is a measure of agreement between people performing manual pos tagging of text.
for example, the penn treebank’s inter-annotator agreement for pos tagging is above 90%  <cit> .
since algorithms can mimic human behaviour when assiging pos tags to tokens , tokenizers that output pos-tokens are expected to produce valid pos-token sequences and consequently mimic human performance.
for example, two tokenizers adhering to penn treebank pos tags should segment sentences with over 90% agreement given individually successful implementations.
pos-tokens should foster consistent human-like tokenization behaviour.
such behavior is expected to increase tokenizer reuse.
a tokenizer is a function that given some text and context segments the text into tokens.
in our approach, the segmentation adheres to a language model and each token maps to a pos tag.
the notion of a tokenizer can be formalized as t :=
• Σ is a finite set of symbols called the alphabet.
• s is the set of all finite strings over Σ and s′ := s + {ε}, includes the empty string.
• lm is a language model  that includes a finite set of pos tags and a finite set of tokenization contexts.
• e := e is a finite set of pos tags.
• c := c is a finite set of contexts where a context is a tuple of information specific to a tokenizer instance.
for example, a context could contain the previous sentence’s parse or simply the previous token.
• tt is the set of all tuples over s × e. these tuples represent sequences of tagged tokens, excluding empty tokens.
• Γ : c × s′ → tt
a good tokenizer is a tokenizer that chooses the most likely sequence of tagged tokens for a given context, input and language model.
thus, a good tokenizer satisfies:
• ∀c ε c, s ε s′ Γ = argmax ttεtt p.
• where argmax is  defined as a function that, given an expression resulting in a real-value and a set of elements, returns the subset of elements that maximize the expression’s value.
our design pattern and guidelines are expected to create good tokenizers.
components
having defined a tokenizer’s input and output, we further define a tokenizer by defining its internal structure; its software components.
we separate a tokenizer into three components: a token lattice and lattice constructor, a best lattice-path chooser and token transducers.
token transducers create candidate tokens from text.
these candidate tokens are assembled into a token lattice by the lattice constructor.
the best path  is selected from the token lattice, tokenizing the text.
these components are illustrated in figure  <dig>  the components are further explained below.
text may have multiple segmentations caused by ambiguous token boundaries.
for example, the sentence “the patient’s 10mg tablet.” segments into eight token sequences given that “patient’s”, “10mg” and “tablet.” could also be interpreted as  “patient ’s”, “ <dig> mg” and “tablet .”.
the symbols ’ m and .
ambiguously act as token boundaries in english .
a bounded lattice  <cit>  can represent a text’s segmentations.
in this context, a bounded lattice is a partially ordered set of segmentations with a least and greatest element .
such a lattice is referred to as a token lattice.
conceptualizing a sentence’s segmentations as a bounded lattice has been suggested previously  <cit> , but has not been applied to biomedical tokenizers or biomedical text.
it is unknown whether or not a token lattice is appropriate for biomedical tokenization.
we formalize and complete the token lattice design pattern for the biomedical domain.
when converting text to a token lattice, it may be necessary to transform a text’s raw candidate tokens into candidate tokens that increase the text’s pos-tag  likelihood.
for example, it may be necessary to transform the token “mg” into “milligrams” to increase the pos-tag likelihood of the sentence “the patient’s 10mg tablet.”.
increasing pos-tag likelihood is meant to satisfy our tokenizer definition, that of likely pos tag sequences.
token transducers identify and transform a text into candidate token sequences for the token lattice.
the candidate token sequences are inserted into the token lattice by the lattice constructor.
a token transducer is formally defined as follows:
ttransducer :=
• Σ is a finite set of symbols called the alphabet.
• s is the set of all finite strings over Σ and s′ := s + {ε}, includes the empty string.
• lm is a language model  that includes a finite set of tokenization contexts.
• c := c is a finite set of contexts where a context is a tuple of information specific to a tokenizer instance.
• ts is the set of all tuples over s. these tuples represent token sequences.
• τ : c × s′ → ℕ <dig> × ts.
the transduce function returns the length of text used and a corresponding sequence of tokens.
applying an implementation of the transduce function to the example string “10mg of” might result in: τimpl = ).
the transduce function’s output is restricted such that the quantity of text used by the transducer is bounded by the length of the input, l ε , given  ε ℕ <dig> × ts and some s ε s′.
a value of  indicates that the transducer could not be applied.
the token transducer formalization assumes that the token transducer operates from the input string’s beginning.
an alternate formalization includes an index into the input string specifying the location on which to apply the transducer.
to complete the tokenizer’s components, an algorithm is required that chooses the best path  from the token lattice and one that constructs the token lattice from token transducer output.
the token lattice’s best path is the most likely path through the token lattice given some language model.
an algorithm exists for best path selection .
to construct a token lattice, a lattice constructor applies every transducer to each character position in the input text.
the result of applying a lattice constructor on “the patient’s 10mg tablet.” is seen in figure  <dig>
given:
• Σ is a finite set of symbols called the alphabet.
• s is the set of all finite strings over Σ.
• g :=  is a directed graph consisting of a finite set of vertices and a finite set of labelled edges, e ⊆ v × s × v.
the token lattice g is constructed for some text s ε s as follows:
• let l := {i : i ε ℕ <dig>   <dig> ≤ i ≤ length}.
• s′ is a slice of s; s′ := s given an i ε l.
• vi ε v for i ε l. these vertices represent a position between characters in s.
• for every slice of s and corresponding token transducer output τ = ), a path of edges, , in the token lattice, g, is constructed where the first and last vertices of the path correspond to a position between characters, e <dig> <cit>  = vi and em <cit>  = vi+l, and an edge is associated with a token by label = tj.
pseudocode
of the three described software components, only the lattice constructor’s pseudocode is presented.
this is due to token transducer code being specific to a token transducer’s objective and due to existing documentation of a best-path selection algorithm .
a systematic approach to creating a biomedical tokenizer
given our token lattice design pattern, a biomedical tokenizer can be created by:
• choosing a set of documented pos tags such as the penn treebank’s.
• choosing a best path selection algorithm.
implement the algorithm, if necessary.
• identifying the token transducers.
implement the transducers, if necessary.
identifying token transducers
the proposed tokenizer design pattern does not provide a method for identifying token transducers.
token transducers will vary depending on the tokenizer’s input.
for example, the token transducers required for english will likely differ from the token transducers required for spanish.
in this section, we propose a systematic approach to token transducer identification.
the guidelines are as follows:
• select a set of documented pos tags such as the penn treebank’s.
• collect text segments  from the input texts that are representative of the input texts’ diversity.
this may be via random sampling or another method.
• for each text segment, identify its tokens.
– adhere to pos tag definitions
– insure that each token corresponds to at least one pos tag.
– do not segment text when segmentation results in an unlikely pos-tag sequence such as segmenting “di-trans,poly-cis-undecaprenyl-diphosphate” into  “di trans , poly cis undecaprenyl diphosphate”.
this can be captured as p >t using the introduced notation .
– segment text when text ambiguously maps to multiple pos tags and segmenting establishes a single pos tag per token
• categorize the identified tokens into token classes .
– base classes on pos tag definitions, named entities , abbreviations and acronyms.
– minimize the number of classes and multi-class tokens.
• create a token transducer for each class of token.
example token transducer identification
what follows is an example application of the token transducer guidelines using the penn treebank’s pos tag set, an author’s language model and the following sample descriptions:
<dig>  entire upper dental arch
segmentation: entire upper dental arch
<dig>  royal navy - non-commissioned personnel
segmentation: royal navy - non-commissioned personnel
<dig>  primidone 50mg tablet
segmentation: primidone  <dig> mg tablet
<dig>  primary sjogren’s syndrome with organ/system involvement
segmentation: primary sjogren ’s syndrome with organ and system involvement
<dig>  posterior cervical spinal cord injury, without spinal injury, c1-4
segmentation: posterior cervical spinal cord injury , without spinal injury , c <dig> to 4
<dig>  precorrin-3b c17-methyltransferase
segmentation: precorrin-3b c17-methyltransferase
<dig>  salmonella iii arizonae 47:k: <dig> ,7
segmentation: salmonella iii arizonae 47:k: <dig> ,7
item  <dig> is an example of a simple segmentation.
item  <dig> includes two uses of the symbol -.
the first use is assigned the pos tag : whereas the second use, a hyphen in the token non-commissioned, is more difficult to assess.
the hyphen could have been removed resulting in two tokens.
since hyphen removal might decrease pos tag sequence likelihood, non-commissioned was segmented as one token.
for this limited example, either segmentation could be considered acceptable.
the text 50mg of item  <dig> is segmented because segmenting establishes a single pos tag per token.
the text would otherwise be a partial match to at least two pos category descriptions.
for similar reasons, c1- <dig> of item  <dig> is segmented into multiple tokens.
the penn treebank specifies possessives as a separate pos category.
given this definition, the possessive ’s is split from sjogren’s.
items  <dig>   <dig>   <dig> and  <dig> are segmented to maintain likely pos tag sequences.
that is, 47:k: <dig> , <dig>  precorrin-3b and c17-methyltransferase remain as one token, whereas organ/system and c1- <dig> are modified.
given these segmentations the resulting token transducers are:
• alphabetic
• possessive
• independents
• numeric
• abbreviations
• functional names
• substances
testing
we applied the design pattern and the token transducer identification guidelines in the creation of a tokenizer for biomedical concept descriptions and compared our tokenizer to three other tokenizer methods.
test data
biomedical concept descriptions were extracted from snomed ct  <cit> .
snomed ct  is a clinical terminology that contains approximately  <dig> concepts,  <dig>  million relationships and  <dig>  million additional concept descriptions.
snomed ct is described as a comprehensive clinical terminology, with an objective of “precisely representing clinical information across the scope of health care”  <cit> .
the concept descriptions were extracted from the january  <dig> release’s current concepts .
we randomly selected  <dig> current snomed ct concept descriptions to create the ground truth  tokenizations.
an example concept description is “posterior cervical spinal cord injury, without spinal injury, c1-4”.
an author manually segmented each description by following our definitions and guidelines.
he is a native english speaker.
a second individual also segmented the concept descriptions after reading instructions and practicing on several examples.
the instructions and examples can be found in appendix .
the second individual has a health sciences background but is not a native english speaker.
the second segmentor was provided with open-ended segmenting instructions and five examples.
the segmentor read the instructions and segmented the examples, after which the preferred segmentations were presented.
this was sufficient for the segmentor to conclude that segmentation “separated units of meaning”.
the segmentor was encouraged to develop their own segmentation strategy given that this strategy included the two rules provided in the instructions.
the greatest effect of our segmentation definitions and guidelines was to expand closed-class words into their regular form.
for example, plus and slash separated lists were converted to regular lists .
similarly, dashes representing the word “to” were replaced  and slashes representing the word “per” were replaced .
knowing that these abbreviated forms were generally absent in the training data, their expansion was to satisfy the requirement of likely pos tag sequences.
segmentation agreement is presented in table  <dig>  agreement was measured with cohen’s kappa   <cit>  - a statistic that accounts for chance agreement.
the probability of chance agreement was calculated as  <dig> .
ck is typically calculated in context of categorical agreement .
in our case, agreement was defined as both segmentors producing identical segmentations for a given concept description.
we modeled chance agreement as a coin toss, where one side of the coin is labeled agree and the other disagree.
thus, for each concept description we could flip our coin to determine whether the segmentations would agree by chance.
the expected probability of chance agreement is  <dig> .
inter-segmentor agreement on snomed ct concept description segmentations.
there was weak preliminary agreement  because descriptions ending with a parenthesized word such as “” were considered one segment by the second segmentor.
she judged these parenthesized endings to have a single meaning and thus a single segmentation.
when the second segmentor encountered descriptions ending with several words within parentheses, she opted for segmentation consistency  rather than changing completed segmentations .
an author segmented the parentheses and agreement was recalculated.
this single change of separating parentheses from their adjoining words, for words located at the end of concept descriptions, resulted in a ck of  <dig> .
further minor corrections to both segmentor’s results such as segmenting missed possessives resulted in a ck of  <dig> .
the author’s corrected segmentations were adopted for testing.
these segmentations appear to be reasonable segmentations given a ck of  <dig>  with another segmentor.
tokenizer methods
we constructed a baseline whitespace-only tokenizer and selected tokenizers specifically designed for biomedical text from the list provided by he and kayaalp  <cit> .
specialist  <cit>  and medpost  <cit>  were selected.
specialist is written in java.
specialist considers a contiguous run of alpha-numeric characters bounded by white space as a token, as well as individual punctuation.
specialist over-segments and repairs the segmentation into meaningful tokens at a latter stage.
for example, “ <dig> ” is tokenized as  “ <dig> .
4” and corrected post-tokenization.
specialist was run using the following command: java -classpath nlpproject.jar gov/nih/nlm/nls/utils/tokenize –inputtype=freetext –tokens.
medpost is written in c++ and uses  <dig> interdependent heuristics to tokenize biomedical text.
it segments text for further processing which includes pos tagging.
medpost’s pos tag set is based on the penn treebank’s pos tag set.
medpost was run using the following command: medpost -text.
we implemented the adapted viterbi algorithm  <cit>  to choose a best-path  from the token lattice.
we created two variants of the algorithm’s hidden markov model   <cit> .
these variants were a zero order and first order hmm.
the zero order hmm does not employ transitional probabilities whereas the first order does.
the first order’s transitional probability relies on one previous state, p.
our tokenization methods are written in python  and use nltk   <cit> , a natural language toolkit library.
we trained our hmm’s on a sample  of the penn treebank corpus.
the sample contains newspaper text.
in one case, we augmented the sample penn treebank corpus with % <dig> of the publicly available medpost pos tagged corpus  <cit> .
the medpost corpus contains  <dig> sentences from medline abstracts.
its pos tag set is based on the penn treebank’s.
we ran a script provided in the medpost download to convert the medpost pos tag set to the penn treebank’s.
to identify token transducers, we segmented concept descriptions by whitespace and constructed a set from these segmentations.
prior examination of the concept descriptions had shown that whitespace was rarely found within a token.
we randomly selected  <dig> items from the set of segmentations.
these segmentations were separated into tokens by following our guidelines and using the penn treebank’s pos tags.
several segmentations were tokenized in context of their associated descriptions because the text segment contained insufficient information to perform tokenization .
table  <dig> summarizes the resulting token classes.
token classes derived from snomed ct concept descriptions.
accuracy
the tokenizers were applied to our ground truth data .
a segmentation identical to the ground truth’s was considered successful and any other tokenization was considered in error.
table  <dig> summarizes the results.
medpost and our adapted viterbi tokenizer performed best with a  <dig> % and  <dig> % accuracy respectively.
confidence intervals  were calculated using the normal approximation method of the binomial confidence interval  <cit> .
tokenizer results.
discussion
specialist performed poorly because it takes a different approach to tokenization, that of over-segment and repair.
specialist also removes symbols from the output tokens, such as brackets, resulting in poorer performance than the baseline whitespace-only tokenizer.
medpost’s most consistent error was leaving a quantity and its unit joined rather than segmenting them.
for example, medpost would leave “10mg” as a token whereas our approach was to segment “10mg” into “10” and “mg”.
our most accurate tokenizer’s most consistent error was separating decimal numbers.
for example, our algorithm would separate “ <dig> ” into “ <dig> .
123” .
one explanation could be that our training data contained an insufficient quantity of decimal numbers.
unless the hmm had been trained with the decimal number then the token was unknown to our hmm.
training an hmm using token features as well as the token itself would likely improve our most accurate tokenizer.
the adapted viterbi tokenizer, implemented using our proposed design pattern and our token transducer identification guidelines, performed as well or better than current biomedical text tokenizers.
the results suggest that the design pattern and guidelines are a viable alternative to current biomedical tokenization methods.
pos tag sequences and training data have a significant impact on proper text tokenization.
the 0-order hmm disregards transition probabilities and consequently pos tag sequences, whereas the 1st-order hmm considers one previous state.
considering one previous state improves tokenization by approximately 15%.
a further improvement of approximately 10% is achieved by training the hmm on data that has greater resemblance to the testing data.
in other words, ambiguous tokenizations can be disambiguated through pos tagging.
dividing software into well defined components can increase software extensibility and reuse  <cit> .
our design pattern should increase tokenizer extensibility and reusability.
for example, token transducers can be reused in other token-lattice tokenizers.
as an example of extensibility, consider applying a token-lattice tokenizer to new text.
this should consist of identifying the new text’s token transducers, including these transducers in the existing tokenizer and possibly training the tokenizer with additional data.
this is expected to be less programming work than modifying a large number of segmentation heuristics.
CONCLUSIONS
we presented our tokenizer design pattern named the token lattice design pattern and associated token identification guidelines.
we described the tokenizer’s input, output and components.
the components are a token lattice and lattice constructor, a best lattice-path chooser and token transducers.
our evaluation of our design pattern and guidelines supports our claim that the design pattern and guidelines are a viable approach to tokenization.
the token lattice design pattern is expected to apply to domains other than the biomedical domain.
our evaluation demonstrates that ambiguous tokenizations can be disambiguated through pos tagging.
in doing so, pos tag sequences and training data have a significant impact on proper text tokenization.
our approach of tokenization through pos tagging differs from previous split-join classification approaches.
our tokenizer formalization suggests how various biomedical text processing components such as machine learning of named entities can interact cooperatively .
our formalization also demonstrates that machine learning algorithms are appropriate for choosing the best-lattice path from a  token lattice.
our research results support further investigation of machine learning on token lattices for selecting the best-lattice path.
future work includes applying the tokenizer pattern to other biomedical texts  and testing new best lattice-path chooser algorithms.
improvements to token transducers and the best lattice-path chooser are expected to further improve tokenization.
competing interests
the authors declare that they have no competing interests
authors contributions
nb is a phd student at the university of victoria.
this work has been created as part of his phd research.
jwj is a faculty member at the university and nb’s supervisor.
appendix - secondary segmentor instructions
you are asked to segment a sentence into its tokens .
here’s an example :
a car, faster than lighting, was painted red.
a
car
,
faster
than
lighting
,
was
painted
red
when segmenting a sentence you are permitted to 1) separate and 2) delete pieces of the sentence.
in the example above, spaces were deleted and punctuation was separated from its adjoining word.
tokens may have spaces .
some people may choose to do the following:
new york is a big city.
new york
is
a
big
city
below are segmenting rules that you must follow, these rules apply to very few situations.
for most cases, you will decide how to segment a sentence.
• consider the following as separate tokens : ’ll ’re ’ve n’t ’s ’
• abbreviations of closed-class words must be expanded.
example: the sentence ”jon/roger are running.” would become ”jon and roger are running.” here is a list of closed-class words: a about above across after against all along although among an and another any anybody anyone anything around as at because before behind below beneath beside between beyond both but by despite down during each either enough ever every everybody everyone everything except few for from he her hers herself him himself his how i if in inside into it its itself like many me mine myself near neither no nobody none nor of off on once one onto or ours ourselves out outside over past per several she since so some somebody someone sufficient than that the theirs them themselves these they this those though through throughout till to toward under underneath until up upon us we what whatever when where whether which whichever while who whoever whom whomever with within without yet you yours yourself yourselves
apply what you’ve just learned to these examples:
entire upper dental arch
entire
upper
dental
arch
royal navy - non-commissioned personnel
royal
navy
-
non-commissioned
personnel
posterior cervical spinal cord injury, without spinal injury, c1-4
posterior
cervical
spinal
cord
injury
,
without
spinal
injury
,
c1
to
4
primidone 50mg tablet
primidone
50
mg
tablet
precorrin-3b c17-methyltransferase
precorrin-3b
c17-methyltransferase

 natural language processing is the computer processing of human language. it is a bidirectional chain of transformation from speech to language understanding - from sounds to semantics. segments of this processing chain are designed to address different nlp problems, including audio to text transformation, text processing and semantic recognition. this paper focuses on text processing. tokenization typically plays a role in processing text. tokenization is broadly defined as the segmentation of text for subsequent processing. the definition’s breadth reflects the ambiguity and differences of tokenization strategies. tokenization strategies can vary depending on language, software goals and other criteria. there is no widely accepted tokenization method for english texts, including biomedical texts. in contrast, there are widely accepted solutions to other nlp tasks. the viterbi algorithm is a widely accepted solution for part-of-speech tagging. pos tagging assigns tags to tokens, such as assigning the tag noun to the token paper. similarly, the cky algorithm is a widely accepted solution for syntactic parsing. syntactic parsing constructs a syntactic structure such as a parse tree from a sequence of tagged tokens. although there is no widely accepted tokenization method, tokenization is an important component of language processing. as webster and kit argue, tokenization identifies basic units on which further processing depends. for example, tokenization segments a sentence’s terminating symbol from its last word allowing subsequent processing to identify a text’s sentences. hassler and fliedl suggest that tokenization is often perceived as a solved problem. for tomanek, wermter and hahn, tokenization can be perceived as “unsophisticated clerical work”. on the other hand, there is evidence to support that tokenization is not trivial. a single arabic word can be composed of four independent tokens. chinese words do not have obvious boundary markers. spanish and english can be considered to flow across whitespace boundaries. biomedical names pose tokenization difficulties because they often contain special characters such as slashes or brackets. proper tokenization in these contexts is a non-trivial problem. within the domain of biomedical tokenization, he and kayaalp applied tokenizers to medline abstracts. only of the tokenizers produced identical results and the differing results varied widely. given the latter, he and kayaalp advocate awareness of a tokenizer’s details without clearly defining or specifying which tokenizer details are important. tokenizer details are expected to influence whether a tokenizer is well suited or adaptable to a particular language processing task. a poor choice of tokenizer is expected to cause information loss. several tokenizers examined by he and kayaalp used simple rule based tokenization methods. jiang and zhai’s empirical study of rule based tokenization supports the use of rule based tokenizers on specific texts. rule based tokenization methods may perform well for specific texts but these methods appear to generalize poorly. other than rule based techniques, tokenization in the biomedical domain has been regarded as a classification task. classification assigns a label to objects. for example, a classifier could assign a token-separator label to the space character. classification tokenizers differ in their choice of object and their method for learning and applying tags. biomedical classification-based tokenization can be divided into two approaches: classifiers that classify textual objects as a token boundaries and classifiers that reassemble primitive tokens. in other words, classifier-based tokenizers either split or join textual objects through classification. split-join based tokenization approaches have applied a variety of machine learning methods with success as exemplified below. a classifier was used to label selected symbols such as a space or a period as within a token or as a token separator. this split approach performed well on named entity only data and poorly on named entities in medline abstracts. this approach neglects un-delimited tokens such as “ cm”. mcdonald, crammer and pereira applied multi-label classification techniques to tokenization. their classifier assigned beginning, inside and outside labels to primitive token sequences. the segments labeled with a b followed by consecutive i labels represented a single large token. this join approach might also be considered as over-segment and repair because their classifier reassembled incorrectly segmented tokens. tomanek, wermter and hahn trained two classifiers to identify sentence and token boundaries using a corpus derived from the pennbioie and genia corpora. input text was split into sentences and sentences were split into tokens. the token-splitting classifier used preset token boundary symbols and corpus-based training to identify token boundaries. wrenn, stetson and johnson used transitional entropy and conditional probability to detect token boundaries. they compared their tokenization method to human specified sentence boundaries and a rule based tokenizer that segmented sentences by whitespace. the authors acknowledge that the lack of a gold standard is the most important limitation of their work. an example of this limitation is that their method is not evaluated on whether punctuation such as a comma is indicative of a token boundary. motivation we attempted to select an existing biomedical tokenizer for a biomedical text processing task. the idiosyncratic nature of each biomedical tokenizer’s output, or documented output, complicated our selection. he and kayaalp similarly found that output varied between tokenizers. furthermore, we found that existing biomedical tokenizers generally lacked guidance on how to apply the tokenizer to new text. as an example of the guidance we sought, consider the question of how improper tokenization of tokens, existing only in the new text, should be resolved. to address the above difficulties, we identify and complete a novel tokenizer design pattern and suggest a systematic approach to tokenizer creation. in so doing, we provide a definition of tokenization and describe software components to accompany the proposed definition. we implement a tokenizer based on our design pattern that combines regular expressions and machine learning. our machine learning approach differs from the previous split-join classification approaches. we evaluate our approach against three other tokenizers on the task of tokenizing biomedical text.  algorithm and implementation in this section, we present a novel tokenizer design pattern for biomedical tokenizers. according to buschmann, henney and schmidt, “a design pattern provides a scheme for refining elements of a software system or the relationships between them. it describes a commonly-recurring structure of interacting roles that solves a general design problem within a particular context.”. we present our tokenizer design pattern by defining a tokenizer’s input and output, by defining a tokenizer’s software components and by presenting related pseudocode. our tokenizer design pattern is named the token lattice design pattern. input and output current tokenizers generally compute on raw text or sentences. we restrict a tokenizer’s input to raw text. if the text contains well formed sentences then it may be possible to use existing software that segments text into sentences with few errors. a tokenizer’s output definition should communicate a tokenizer’s behaviour and foster tokenizer reuse. he and kayaalp discuss the variability in tokenizer output. underlying this difference in output is a lack of agreement on what constitutes a token. furthermore, tokenizers produce tokens based on an intrinsic token definition. tokenizer output is generally idiosyncratic. we restrict a tokenizer’s output to the most likely pos-tagged sequence of tokens, given some language model. this implies that a tokenizer outputs tokens taggable with tags such as noun or adjective. it also implies that a tokenizer must implement predefined pos tags such as the penn treebank’s. lastly, it implies that a tokenizer should produce a likely sequence of pos-tagged tokens. for example, a tokenizer should not segment a chemical substance such as “ -epoxy-3-methyl-1-butyl-diphosphate” into “, epoxy methyl butyl diphosphate”. we define the concept of pos-tokens as tokens that adhere to our stated output restrictions. these restrictions blur the conventional boundary between tokenizers and pos-taggers. we argue below that pos-tokens are expected to increase tokenization accuracy and tokenizer reuse. chaining arbitrary tokens together is unlikely to form a valid sentence. accordingly, knowing a token’s pos tag indicates which pos tags and tokens are likely to occur in the token’s vicinity. for example, it is likely that a noun follows after the word the, whereas it is less likely that a verb follows the. pos-tokens inherit language characteristics that are likely to increase tokenization accuracy given that these characteristics have been successfully exploited in the past. inter-annotator agreement can be measured for pos tagging. this is a measure of agreement between people performing manual pos tagging of text. for example, the penn treebank’s inter-annotator agreement for pos tagging is above 90%. since algorithms can mimic human behaviour when assiging pos tags to tokens, tokenizers that output pos-tokens are expected to produce valid pos-token sequences and consequently mimic human performance. for example, two tokenizers adhering to penn treebank pos tags should segment sentences with over 90% agreement given individually successful implementations. pos-tokens should foster consistent human-like tokenization behaviour. such behavior is expected to increase tokenizer reuse. a tokenizer is a function that given some text and context segments the text into tokens. in our approach, the segmentation adheres to a language model and each token maps to a pos tag. the notion of a tokenizer can be formalized as t:= • Σ is a finite set of symbols called the alphabet. • s is the set of all finite strings over Σ and s′:= s + {ε}, includes the empty string. • lm is a language model that includes a finite set of pos tags and a finite set of tokenization contexts. • e:= e is a finite set of pos tags. • c:= c is a finite set of contexts where a context is a tuple of information specific to a tokenizer instance. for example, a context could contain the previous sentence’s parse or simply the previous token. • tt is the set of all tuples over s × e. these tuples represent sequences of tagged tokens, excluding empty tokens. • Γ: c × s′ → tt a good tokenizer is a tokenizer that chooses the most likely sequence of tagged tokens for a given context, input and language model. thus, a good tokenizer satisfies: • ∀c ε c, s ε s′ Γ = argmax ttεtt p. • where argmax is defined as a function that, given an expression resulting in a real-value and a set of elements, returns the subset of elements that maximize the expression’s value. our design pattern and guidelines are expected to create good tokenizers. components having defined a tokenizer’s input and output, we further define a tokenizer by defining its internal structure; its software components. we separate a tokenizer into three components: a token lattice and lattice constructor, a best lattice-path chooser and token transducers. token transducers create candidate tokens from text. these candidate tokens are assembled into a token lattice by the lattice constructor. the best path is selected from the token lattice, tokenizing the text. these components are illustrated in figure the components are further explained below. text may have multiple segmentations caused by ambiguous token boundaries. for example, the sentence “the patient’s 10mg tablet.” segments into eight token sequences given that “patient’s”, “10mg” and “tablet.” could also be interpreted as “patient ’s”, “ mg” and “tablet.”. the symbols ’ m and. ambiguously act as token boundaries in english. a bounded lattice can represent a text’s segmentations. in this context, a bounded lattice is a partially ordered set of segmentations with a least and greatest element. such a lattice is referred to as a token lattice. conceptualizing a sentence’s segmentations as a bounded lattice has been suggested previously, but has not been applied to biomedical tokenizers or biomedical text. it is unknown whether or not a token lattice is appropriate for biomedical tokenization. we formalize and complete the token lattice design pattern for the biomedical domain. when converting text to a token lattice, it may be necessary to transform a text’s raw candidate tokens into candidate tokens that increase the text’s pos-tag likelihood. for example, it may be necessary to transform the token “mg” into “milligrams” to increase the pos-tag likelihood of the sentence “the patient’s 10mg tablet.”. increasing pos-tag likelihood is meant to satisfy our tokenizer definition, that of likely pos tag sequences. token transducers identify and transform a text into candidate token sequences for the token lattice. the candidate token sequences are inserted into the token lattice by the lattice constructor. a token transducer is formally defined as follows: ttransducer:= • Σ is a finite set of symbols called the alphabet. • s is the set of all finite strings over Σ and s′:= s + {ε}, includes the empty string. • lm is a language model that includes a finite set of tokenization contexts. • c:= c is a finite set of contexts where a context is a tuple of information specific to a tokenizer instance. • ts is the set of all tuples over s. these tuples represent token sequences. • τ: c × s′ → ℕ × ts. the transduce function returns the length of text used and a corresponding sequence of tokens. applying an implementation of the transduce function to the example string “10mg of” might result in: τimpl = ). the transduce function’s output is restricted such that the quantity of text used by the transducer is bounded by the length of the input, l ε, given ε ℕ × ts and some s ε s′. a value of indicates that the transducer could not be applied. the token transducer formalization assumes that the token transducer operates from the input string’s beginning. an alternate formalization includes an index into the input string specifying the location on which to apply the transducer. to complete the tokenizer’s components, an algorithm is required that chooses the best path from the token lattice and one that constructs the token lattice from token transducer output. the token lattice’s best path is the most likely path through the token lattice given some language model. an algorithm exists for best path selection. to construct a token lattice, a lattice constructor applies every transducer to each character position in the input text. the result of applying a lattice constructor on “the patient’s 10mg tablet.” is seen in figure given: • Σ is a finite set of symbols called the alphabet. • s is the set of all finite strings over Σ. • g:= is a directed graph consisting of a finite set of vertices and a finite set of labelled edges, e ⊆ v × s × v. the token lattice g is constructed for some text s ε s as follows: • let l:= {i: i ε ℕ ≤ i ≤ length}. • s′ is a slice of s; s′:= s given an i ε l. • vi ε v for i ε l. these vertices represent a position between characters in s. • for every slice of s and corresponding token transducer output τ = ), a path of edges,, in the token lattice, g, is constructed where the first and last vertices of the path correspond to a position between characters, e = vi and em = vi+l, and an edge is associated with a token by label = tj. pseudocode of the three described software components, only the lattice constructor’s pseudocode is presented. this is due to token transducer code being specific to a token transducer’s objective and due to existing documentation of a best-path selection algorithm. a systematic approach to creating a biomedical tokenizer given our token lattice design pattern, a biomedical tokenizer can be created by: • choosing a set of documented pos tags such as the penn treebank’s. • choosing a best path selection algorithm. implement the algorithm, if necessary. • identifying the token transducers. implement the transducers, if necessary. identifying token transducers the proposed tokenizer design pattern does not provide a method for identifying token transducers. token transducers will vary depending on the tokenizer’s input. for example, the token transducers required for english will likely differ from the token transducers required for spanish. in this section, we propose a systematic approach to token transducer identification. the guidelines are as follows: • select a set of documented pos tags such as the penn treebank’s. • collect text segments from the input texts that are representative of the input texts’ diversity. this may be via random sampling or another method. • for each text segment, identify its tokens. – adhere to pos tag definitions – insure that each token corresponds to at least one pos tag. – do not segment text when segmentation results in an unlikely pos-tag sequence such as segmenting “di-trans,poly-cis-undecaprenyl-diphosphate” into “di trans, poly cis undecaprenyl diphosphate”. this can be captured as p >t using the introduced notation. – segment text when text ambiguously maps to multiple pos tags and segmenting establishes a single pos tag per token • categorize the identified tokens into token classes. – base classes on pos tag definitions, named entities, abbreviations and acronyms. – minimize the number of classes and multi-class tokens. • create a token transducer for each class of token. example token transducer identification what follows is an example application of the token transducer guidelines using the penn treebank’s pos tag set, an author’s language model and the following sample descriptions: entire upper dental arch segmentation: entire upper dental arch royal navy - non-commissioned personnel segmentation: royal navy - non-commissioned personnel primidone 50mg tablet segmentation: primidone mg tablet primary sjogren’s syndrome with organ/system involvement segmentation: primary sjogren ’s syndrome with organ and system involvement posterior cervical spinal cord injury, without spinal injury, c1-4 segmentation: posterior cervical spinal cord injury, without spinal injury, c to 4 precorrin-3b c17-methyltransferase segmentation: precorrin-3b c17-methyltransferase salmonella iii arizonae 47:k:,7 segmentation: salmonella iii arizonae 47:k:,7 item is an example of a simple segmentation. item includes two uses of the symbol -. the first use is assigned the pos tag: whereas the second use, a hyphen in the token non-commissioned, is more difficult to assess. the hyphen could have been removed resulting in two tokens. since hyphen removal might decrease pos tag sequence likelihood, non-commissioned was segmented as one token. for this limited example, either segmentation could be considered acceptable. the text 50mg of item is segmented because segmenting establishes a single pos tag per token. the text would otherwise be a partial match to at least two pos category descriptions. for similar reasons, c1- of item is segmented into multiple tokens. the penn treebank specifies possessives as a separate pos category. given this definition, the possessive ’s is split from sjogren’s. items and are segmented to maintain likely pos tag sequences. that is, 47:k:, precorrin-3b and c17-methyltransferase remain as one token, whereas organ/system and c1- are modified. given these segmentations the resulting token transducers are: • alphabetic • possessive • independents • numeric • abbreviations • functional names • substances testing we applied the design pattern and the token transducer identification guidelines in the creation of a tokenizer for biomedical concept descriptions and compared our tokenizer to three other tokenizer methods. test data biomedical concept descriptions were extracted from snomed ct. snomed ct is a clinical terminology that contains approximately concepts, million relationships and million additional concept descriptions. snomed ct is described as a comprehensive clinical terminology, with an objective of “precisely representing clinical information across the scope of health care”. the concept descriptions were extracted from the january release’s current concepts. we randomly selected current snomed ct concept descriptions to create the ground truth tokenizations. an example concept description is “posterior cervical spinal cord injury, without spinal injury, c1-4”. an author manually segmented each description by following our definitions and guidelines. he is a native english speaker. a second individual also segmented the concept descriptions after reading instructions and practicing on several examples. the instructions and examples can be found in appendix. the second individual has a health sciences background but is not a native english speaker. the second segmentor was provided with open-ended segmenting instructions and five examples. the segmentor read the instructions and segmented the examples, after which the preferred segmentations were presented. this was sufficient for the segmentor to conclude that segmentation “separated units of meaning”. the segmentor was encouraged to develop their own segmentation strategy given that this strategy included the two rules provided in the instructions. the greatest effect of our segmentation definitions and guidelines was to expand closed-class words into their regular form. for example, plus and slash separated lists were converted to regular lists. similarly, dashes representing the word “to” were replaced and slashes representing the word “per” were replaced. knowing that these abbreviated forms were generally absent in the training data, their expansion was to satisfy the requirement of likely pos tag sequences. segmentation agreement is presented in table agreement was measured with cohen’s kappa - a statistic that accounts for chance agreement. the probability of chance agreement was calculated as. ck is typically calculated in context of categorical agreement. in our case, agreement was defined as both segmentors producing identical segmentations for a given concept description. we modeled chance agreement as a coin toss, where one side of the coin is labeled agree and the other disagree. thus, for each concept description we could flip our coin to determine whether the segmentations would agree by chance. the expected probability of chance agreement is. inter-segmentor agreement on snomed ct concept description segmentations. there was weak preliminary agreement because descriptions ending with a parenthesized word such as “” were considered one segment by the second segmentor. she judged these parenthesized endings to have a single meaning and thus a single segmentation. when the second segmentor encountered descriptions ending with several words within parentheses, she opted for segmentation consistency rather than changing completed segmentations. an author segmented the parentheses and agreement was recalculated. this single change of separating parentheses from their adjoining words, for words located at the end of concept descriptions, resulted in a ck of. further minor corrections to both segmentor’s results such as segmenting missed possessives resulted in a ck of. the author’s corrected segmentations were adopted for testing. these segmentations appear to be reasonable segmentations given a ck of with another segmentor. tokenizer methods we constructed a baseline whitespace-only tokenizer and selected tokenizers specifically designed for biomedical text from the list provided by he and kayaalp. specialist and medpost were selected. specialist is written in java. specialist considers a contiguous run of alpha-numeric characters bounded by white space as a token, as well as individual punctuation. specialist over-segments and repairs the segmentation into meaningful tokens at a latter stage. for example, “ ” is tokenized as “. 4” and corrected post-tokenization. specialist was run using the following command: java -classpath nlpproject.jar gov/nih/nlm/nls/utils/tokenize –inputtype=freetext –tokens. medpost is written in c++ and uses interdependent heuristics to tokenize biomedical text. it segments text for further processing which includes pos tagging. medpost’s pos tag set is based on the penn treebank’s pos tag set. medpost was run using the following command: medpost -text. we implemented the adapted viterbi algorithm to choose a best-path from the token lattice. we created two variants of the algorithm’s hidden markov model. these variants were a zero order and first order hmm. the zero order hmm does not employ transitional probabilities whereas the first order does. the first order’s transitional probability relies on one previous state, p. our tokenization methods are written in python and use nltk, a natural language toolkit library. we trained our hmm’s on a sample of the penn treebank corpus. the sample contains newspaper text. in one case, we augmented the sample penn treebank corpus with % of the publicly available medpost pos tagged corpus. the medpost corpus contains sentences from medline abstracts. its pos tag set is based on the penn treebank’s. we ran a script provided in the medpost download to convert the medpost pos tag set to the penn treebank’s. to identify token transducers, we segmented concept descriptions by whitespace and constructed a set from these segmentations. prior examination of the concept descriptions had shown that whitespace was rarely found within a token. we randomly selected items from the set of segmentations. these segmentations were separated into tokens by following our guidelines and using the penn treebank’s pos tags. several segmentations were tokenized in context of their associated descriptions because the text segment contained insufficient information to perform tokenization. table summarizes the resulting token classes. token classes derived from snomed ct concept descriptions. accuracy the tokenizers were applied to our ground truth data. a segmentation identical to the ground truth’s was considered successful and any other tokenization was considered in error. table summarizes the results. medpost and our adapted viterbi tokenizer performed best with a % and % accuracy respectively. confidence intervals were calculated using the normal approximation method of the binomial confidence interval. tokenizer results. discussion specialist performed poorly because it takes a different approach to tokenization, that of over-segment and repair. specialist also removes symbols from the output tokens, such as brackets, resulting in poorer performance than the baseline whitespace-only tokenizer. medpost’s most consistent error was leaving a quantity and its unit joined rather than segmenting them. for example, medpost would leave “10mg” as a token whereas our approach was to segment “10mg” into “10” and “mg”. our most accurate tokenizer’s most consistent error was separating decimal numbers. for example, our algorithm would separate “ ” into “. 123”. one explanation could be that our training data contained an insufficient quantity of decimal numbers. unless the hmm had been trained with the decimal number then the token was unknown to our hmm. training an hmm using token features as well as the token itself would likely improve our most accurate tokenizer. the adapted viterbi tokenizer, implemented using our proposed design pattern and our token transducer identification guidelines, performed as well or better than current biomedical text tokenizers. the results suggest that the design pattern and guidelines are a viable alternative to current biomedical tokenization methods. pos tag sequences and training data have a significant impact on proper text tokenization. the 0-order hmm disregards transition probabilities and consequently pos tag sequences, whereas the 1st-order hmm considers one previous state. considering one previous state improves tokenization by approximately 15%. a further improvement of approximately 10% is achieved by training the hmm on data that has greater resemblance to the testing data. in other words, ambiguous tokenizations can be disambiguated through pos tagging. dividing software into well defined components can increase software extensibility and reuse. our design pattern should increase tokenizer extensibility and reusability. for example, token transducers can be reused in other token-lattice tokenizers. as an example of extensibility, consider applying a token-lattice tokenizer to new text. this should consist of identifying the new text’s token transducers, including these transducers in the existing tokenizer and possibly training the tokenizer with additional data. this is expected to be less programming work than modifying a large number of segmentation heuristics.  we presented our tokenizer design pattern named the token lattice design pattern and associated token identification guidelines. we described the tokenizer’s input, output and components. the components are a token lattice and lattice constructor, a best lattice-path chooser and token transducers. our evaluation of our design pattern and guidelines supports our claim that the design pattern and guidelines are a viable approach to tokenization. the token lattice design pattern is expected to apply to domains other than the biomedical domain. our evaluation demonstrates that ambiguous tokenizations can be disambiguated through pos tagging. in doing so, pos tag sequences and training data have a significant impact on proper text tokenization. our approach of tokenization through pos tagging differs from previous split-join classification approaches. our tokenizer formalization suggests how various biomedical text processing components such as machine learning of named entities can interact cooperatively. our formalization also demonstrates that machine learning algorithms are appropriate for choosing the best-lattice path from a token lattice. our research results support further investigation of machine learning on token lattices for selecting the best-lattice path. future work includes applying the tokenizer pattern to other biomedical texts and testing new best lattice-path chooser algorithms. improvements to token transducers and the best lattice-path chooser are expected to further improve tokenization. competing interests the authors declare that they have no competing interests authors contributions nb is a phd student at the university of victoria. this work has been created as part of his phd research. jwj is a faculty member at the university and nb’s supervisor. appendix - secondary segmentor instructions you are asked to segment a sentence into its tokens. here’s an example: a car, faster than lighting, was painted red. a car, faster than lighting, was painted red when segmenting a sentence you are permitted to 1) separate and 2) delete pieces of the sentence. in the example above, spaces were deleted and punctuation was separated from its adjoining word. tokens may have spaces. some people may choose to do the following: new york is a big city. new york is a big city below are segmenting rules that you must follow, these rules apply to very few situations. for most cases, you will decide how to segment a sentence. • consider the following as separate tokens: ’ll ’re ’ve n’t ’s ’ • abbreviations of closed-class words must be expanded. example: the sentence ”jon/roger are running.” would become ”jon and roger are running.” here is a list of closed-class words: a about above across after against all along although among an and another any anybody anyone anything around as at because before behind below beneath beside between beyond both but by despite down during each either enough ever every everybody everyone everything except few for from he her hers herself him himself his how i if in inside into it its itself like many me mine myself near neither no nobody none nor of off on once one onto or ours ourselves out outside over past per several she since so some somebody someone sufficient than that the theirs them themselves these they this those though through throughout till to toward under underneath until up upon us we what whatever when where whether which whichever while who whoever whom whomever with within without yet you yours yourself yourselves apply what you’ve just learned to these examples: entire upper dental arch entire upper dental arch royal navy - non-commissioned personnel royal navy - non-commissioned personnel posterior cervical spinal cord injury, without spinal injury, c1-4 posterior cervical spinal cord injury, without spinal injury, c1 to 4 primidone 50mg tablet primidone 50 mg tablet precorrin-3b c17-methyltransferase precorrin-3b c17-methyltransferase 
we identify and complete a novel tokenizer design pattern and suggest a systematic approach to tokenizer creation. tokenization is an important component of language processing yet there is no widely accepted tokenization method for english texts, including biomedical texts. in doing so, pos tag sequences and training data have a significant impact on proper text tokenization. the idiosyncratic nature of each biomedical tokenizer’s output complicates adoption and reuse. our machine learning approach differs from the previous split-join classification approaches. furthermore, biomedical tokenizers generally lack guidance on how to apply an existing tokenizer to a new domain. other than rule based techniques, tokenization in the biomedical domain has been regarded as a classification task. we implement a tokenizer based on our design pattern that combines regular expressions and machine learning. our evaluation of our design pattern and guidelines supports our claim that the design pattern and guidelines are a viable approach to tokenizer construction. medpost and our adapted viterbi tokenizer performed best with a % and % accuracy respectively. we evaluate our approach against three other tokenizers on the task of tokenizing biomedical text. biomedical classifier-based tokenizers either split or join textual objects through classification to form tokens. 12- december machine learning for biomedical literature analysis and text retrieval in the international conference for machine learning and applications washington, dc, usa our evaluation also demonstrates that ambiguous tokenizations can be disambiguated through pos tagging.
 tokenization is an important component of language processing yet there is no widely accepted tokenization method for english texts, including biomedical texts. other than rule based techniques, tokenization in the biomedical domain has been regarded as a classification task. biomedical classifier-based tokenizers either split or join textual objects through classification to form tokens. the idiosyncratic nature of each biomedical tokenizer’s output complicates adoption and reuse. furthermore, biomedical tokenizers generally lack guidance on how to apply an existing tokenizer to a new domain. we identify and complete a novel tokenizer design pattern and suggest a systematic approach to tokenizer creation. we implement a tokenizer based on our design pattern that combines regular expressions and machine learning. our machine learning approach differs from the previous split-join classification approaches. we evaluate our approach against three other tokenizers on the task of tokenizing biomedical text.  medpost and our adapted viterbi tokenizer performed best with a % and % accuracy respectively.  our evaluation of our design pattern and guidelines supports our claim that the design pattern and guidelines are a viable approach to tokenizer construction. our evaluation also demonstrates that ambiguous tokenizations can be disambiguated through pos tagging. in doing so, pos tag sequences and training data have a significant impact on proper text tokenization. 12- december machine learning for biomedical literature analysis and text retrieval in the international conference for machine learning and applications washington, dc, usa 