Tokenization Repair in the Presence of Spelling Errors (2021)

Abstract: We consider the following tokenization repair problem: Given a natural language text with any combination of missing or spurious spaces, correct these. Spelling errors can be present, but it’s not part of the problem to correct them. For example, given: “Tispa per isabout token izaionrep air”, compute “Tis paper is about tokenizaion repair”. We identify three key ingredients of high-quality tokenization repair, all missing from previous work: deep language models with a bidirectional component, training the models on text with spelling errors, and making use of the space information already present. Our methods also improve existing spell checkers by fixing not only more tokenization errors but also more spelling errors: once it is clear which characters form a word, it is much easier for them to figure out the correct word. We provide six benchmarks that cover three use cases (OCR errors, text extraction from PDF, human errors) and the cases of partially correct space information and all spaces missing. We evaluate our methods against the best existing methods and a non-trivial baseline. We provide full reproducibility under https://ad.informatik.uni-freiburg.de/publications .

## introduction tokenizing a given text into words is the first step in many natural language processing applications, including: search engines, translation services, spell checkers and all kinds of learning tasks performed on text. this tokenization is typically performed by the following simple method or a variant of it: define a set of word characters and take each maximal sequence of word characters as one token. for example, for this algoritm runs in linear time (1) a simple such tokenization yields the six words this, algoritm, runs, in, linear, time. note the spelling error in the second word. spelling correction is not part of tokenization. we come back to this important aspect in section 1.2. missing and spurious spaces are common errors in digital text documents. we refer to the union of both types of errors as tokenization errors. here is a variant of the sentence above with one missing space and one spurious space: this algor itm runsin linear time in this paper, we consider the following tokenization repair problem: given a sequence of characters representing a natural language text, with an arbitrary amount of missing and spurious spaces and possibly also with spelling errors, compute the variant of the text with correct spacing. for example, given (2) above, compute (1). tokenization repair can be considered as a generalization of the word segmentation problem, where the text is given without any space information. indeed, we also evaluate our methods on this special case in section 5. ## related work a beam search with neural and character n-gram language models is used for word segmentation in @xcite . in section 5, we evaluate our own implementation of this approach on our benchmark and we also compare against their results on their benchmark. we improve on their approach in several respects: integrating a bidirectional model (which is not trivial), considering the given spaces in the input (they remove all spaces), and explicitly addressing typos by incorporating error models in training (they test their approach on tweets, but do not explicitly handle typos). tokenization repair on the acl anthology corpus is done in @xcite with a neural machine translation model translating from the sequence without spaces to the sequence with spaces. they also remove all spaces from the input text, thus discarding valuable information. in section 5.3, we compare our results against theirs. a beam search with a word bigram language model, instead of a character-based language model, is used in @xcite to correct missing spaces in croatian texts that were digitized by ocr. in @xcite , n-gram statistics are used to determine when to split an out-ofvocabulary token into two words. by using neural language models, we extend the scope of this context beyond the boundaries of n-gram models. recent work on chinese and arabic word segmentation uses bidirectional neural network models to predict word boundaries, e.g. based on bi-lstms @xcite or a pre-trained bert model @xcite . these models are not directly applicable for our task of tokenization repair for the english language, since our inputs contain spurious and missing spaces and the english bert model @xcite is pre-trained on text with correct tokenization. there is a large body of research on ocr postcorrection @xcite @xcite @xcite @xcite @xcite , which usually does not address tokenization errors explicitly. only few publications provide code so that we can evaluate their tokenization repair capabilities. ## approach our approach is a beam search based on deep character-based models, unidirectional and bidirectional. ## conclusion we identified three key ingredients of high-quality tokenization repair, all missing from previous work: bidirectional models, training on text with spelling errors, and making use of the space information already present. our methods also improve existing spell checkers, by helping them to identify which characters form a word. there is still room for improvement, especially in a scenario where many spelling (or ocr) errors and tokenization errors come together. however, we show that the remaining errors are hard, with many ambiguous situations. we paid attention to practical running times and all our methods have linear complexity. a carefully trained transformer model @xcite , however, has the potential to achieve comparable results with much faster running times @xcite . it remains an open problem whether tokenization repair and spelling correction can be solved "together" both efficiently and with high quality. our own methods can be extended to also correct spelling errors, but only with very large beam sizes and impractically large running times. existing models that correct both types of errors (and sometimes even grammar errors) simultaneously fare poorly in comparison to the results we presented.