Tokenizer Evaluation

This repository contains benchmark scripts for comparing different tokenizers and sentence segmenters of German. For trouble-free testing, all tools are provided in a Dockerfile.

This work was presented at EURALEX 2022. The paper is published for open access. Please cite as:

Diewald, N./Kupietz, M./Lüngen, H. (2022): Tokenizing on scale - Preprocessing large text corpora on the lexical and sentence level. In: Klosa-Kückelhaus, A./Engelberg, S./Möhrs, C./Storjohann, P. (eds.): Dictionaries and Society. Proceedings of the XX EURALEX International Congress. IDS-Verlag, Mannheim, Germany, pp. 208-221.

Creating the container

To build the Docker image, run

$ docker build -f Dockerfile -t korap/tokenbench .

This will create and install an image of approximately 12GB.

Running the evaluation suite

To run the benchmark, call

$ docker run --rm -i \
  -v ${PWD}/benchmarks:/tokenbench/benchmarks \
  -v ${PWD}/corpus:/tokenbench/corpus \
  korap/tokenbench benchmarks/[BENCHMARK-SCRIPT]

The supported benchmark scripts are:

benchmark.pl

Performance measurements of the tools. For the benchmarking, the novel "Effi Briest" by Theodor Fontane in the Project Gutenberg version was used (with a total of 98,207 tokens according to wc -l). See the tools section for some remarks to take into account. Accepts two numerical parameters:

• The duplication count of the example file
• The number of iterations

benchmark_batches.pl

Performance measurements of the tools. See the tools section for some remarks to take into account. Accepts one numerical parameter:

• The number of iterations

Will check batches of 1000, 2000, 4000, 8000 ... 8192000 tokens against all tools.

empirist.pl

To run the empirist evaluation suite, you first need to download the empirist gold standard corpus and tooling, and extract it into the corpus directory.

$ wget https://sites.google.com/site/empirist2015/home/shared-task-data/empirist_gold_cmc.zip
$ unzip empirist_gold_cmc.zip -d corpus

$ wget https://sites.google.com/site/empirist2015/home/shared-task-data/empirist_gold_web.zip
$ unzip empirist_gold_web.zip -d corpus

To investigate the output, start the benchmark with mounted output folders

-v ${PWD}/output_cmc:/tokenbench/empirist_cmc
-v ${PWD}/output_web:/tokenbench/empirist_web

ud_tokens.pl

To run the token evaluation suite against the Universal Dependency corpus, first install the empirist tooling as explained above, and download the corpus.

$ wget https://github.com/UniversalDependencies/UD_German-GSD/raw/master/de_gsd-ud-train.conllu \
  -O corpus/de_gsd-ud-train.conllu

ud_sentences.pl

To run the sentence evaluation suite, first download the corpus as explained above.

Caveat

When running this benchmark using Docker you may need to run all processes privileged to get meaningful results.

docker run --privileged -v

Tools

Our tools for token and sentence boundary detection:

• KorAP-Tokenizer is rule-based and compiles, using the lexical analysis generator framework JFlex, a list of regular expressions into a deterministic finite state automaton that can introduce segment boundaries at terminal nodes. The ruleset is based on Apache Lucene's tokenizer and has been extensively modified. Rule sets are available for English, French and German. KorAP-Tokenizer is used productively for tokenization and (among other tools) for sentence segmentation of DeReKo.
• Datok is rule-based and generates an extended finite deterministic state automaton based on a finite state transducer generated by XFST (Beesley & Karttunen 2003) which is reduced to a few transition rules and can be interpreted by Datok for tokenization and sentence segmentation. The rule set of KorAP-Tokenizer was transferred to XFST for this purpose. The generation is done with Foma (Hulden 2009). Rule sets are only available for German at this time. Datok is currently being evaluated experimentally.

Tools for token and sentence boundary detection:

• SoMaJo (Proisl & Uhrig 2016) is rule-based and applies a list of regular expressions to segment a text. SoMaJo won first place in the competition of the aforementioned EmpiriST 2015 Shared Task for tokenizing German-language Web and CMC corpora and has been regularly improved since then. SoMaJo is available specifically for German.
• Cutter (Graën et al. 2018) is rule-based and recursively applies language-specific and language-independent rules to a text to segment it. Compared to other rule-based tools, Cutter uses a context-free rather than a regular grammar.
• OpenNLP is a framework that offers both tokenizers and sentence segmenters in different models. Both tools are based on a maximum entropy approach. In addition, OpenNLP offers SimpleTokenizer, a tool based on simple character class decisions.
• JTok is based on cascading regular expressions that segment tokens until they can be assigned to a token class, which (cf. SoMaJo) can also be returned. Rules exist for English, German and Italian.
• Waste (Jurish/Würzner 2013) is based on a hidden Markov model in which a pre-segmented stream of (pseudo)tokens are re-evaluated at the boundaries found and classified as to whether they are word-initial or sentence-initial.
• Stanford Tokenizer is rule-based, and relies on JFlex (cf. KorAP tokenizer) to compile a deterministic finite state automaton based on a list of regular expressions that can introduce segment boundaries at terminal nodes.
• SpaCy is a framework in which the tokenization stage is rule-based and runs in several phases in which the tokens are split into increasingly finer segments. Rule sets are provided for numerous languages. Different models are offered for sentence segmentation: Sentencizer is rule-based, Dependency Parser performs a syntactic analysis, Statistical segments based on a simple statistical model.
• Syntok is rule-based and applies successive separation rules, primarily in the form of regular expressions, to an input string for segmentation. There is both a tokenizer and a sentence segmenter based on it. Rules exist for Spanish, English, and German.
• BlingFire is rule-based and compiles a deterministic finite state automaton based on regular expressions, which segments at terminal nodes. The tested model is implemented cross-language with a focus on English.

Tools for token boundary detection only:

• TreeTagger (Schmid 1994) is a part-of-speech tagger that carries a separate rule-based tokenization tool that also uses a set of regular expressions to segment a text. TreeTagger does not itself introduce markers for sentence boundaries. license terms.
• Elephant (Evang et al. 2013) is a machine-trained system for segmentation based on Conditional Random Fields and Recurrent Neural Networks. We evaluate here a wrapper implementation (Moreau/Vogel, 2018) that considers only token segmentation and not sentence segmentation, although Elephant provides both.

Tools for sentence boundary detection only:

• Deep-EOS (Schweter/Ahmed 2019) is based on different implementations of neural networks with long short-term memory (LSTM), bidirectional LSTM, and convolutional neural networks. It is not based on pre-tokenization and operates directly on character streams.
• NNSplit is a machine-trained approach based on a byte-level LSTM neural network.

Results

Overview of all compared tools and models with their performance measures.

In terms of speed, the native output of the tools was measured, while in terms of accuracy, further reshaping was necessary to make it comparable to the gold standard. See the tools section for further caveats.

The measures correspond to the average value of 100 runs of benchmark.pl. Since the length of a text can have an impact on performance, a tenfold concatenation of the text was also tested. The test system was an Intel Xeon CPU E5-2630 v2 @ 2.60GHz with 12 cores and 64 GB of RAM

Tool	V.	Model	UD-GSD (Tokens) F1	Empirist-CMC F1	Empirist-Web F1	UD-GSD (Sentences) F1	1 x Effi (T/ms)	10 x Effi (T/ms)
KorAP-Tokenizer	2.2.2		99.45	99.06	99.27	96.87	72.90	199.28
Datok	0.1.5	datok	99.45	98.79	99.21	97.60	614.72	2304.13
"	"	matok	"	"	"	"	1041.63	2798.78
BlingFire	0.1.8	wbd.bin	99.25	55.85	95.80	-	431.92	1697.73
"	"	sbd.bin	-	-	-	95.90	417.10	1908.87
Cutter	2.5		99.47	96.24	99.38	97.31	0.38	*-
JTok	2.1.19		99.56	58.44	98.09	97.92	31.19	117.22
OpenNLP	1.9.4	Simple	95.70	55.26	91.69	-	290.71	1330.23
"	"	Tokenizer (de-ud-gsd)	99.67	65.22	97.58	-	74.65	145.08
"	"	SentenceDetector (de-ud-gsd)	-	-	-	98.51	247.84	853.01
SoMaJo	2.2.0	p=1	99.46	99.21	99.87	97.05	8.15	8.41
"	"	p=8	"	"	"	"	27.32	39.91
SpaCy	3.2.3	Tokenizer	99.49	69.94	98.29	-	19.73	44.40
"	"	Sentencizer	-	-	-	96.80	16.94	40.58
"	"	Statistical	-	-	-	97.16	4.90	10.01
"	"	Dependency	-	-	-	96.93	2.24	0.48
Stanford	4.4.0	tokenize	99.93	97.71	98.46	-	75.47	156.24
"	"	tokenize,split,mwt	"	"	"	98.22	46.95	91.56
Syntok	1.4.3	Tokenizer	99.41	70.76	97.50	-	103.90	108.40
"	"	Segmenter	-	-	-	97.50	59.66	61.07
Waste	2.0.20-1		99.55	65.90	98.49	97.46	141.07	144.95
Elephant	0.2.3		99.62	66.96	97.88	-	8.57	8.68
TreeTagger	3.2.4		99.52	95.58	99.27	-	69.92	72.98
Deep-EOS	0.1	bi-lstm-de	-	-	-	97.47	**0.25	**0.24
"	"	cnn-de	-	-	-	97.49	**0.27	**0.25
"	"	lstm-de	-	-	-	97.47	**0.29	**0.27
NNSplit	0.5.8		-	-	-	95.55	**0.90	**0.90

* Did not finish on the test machine.

** No GPU acceleration tested.

Result chart

Literature

• Beesley, K. R./Karttunen, L. (2003): Finite State Morphology. CSLI Publications.
• Evang, K./Basile, V./Chrupała, G./Bos, J. (2013): Elephant: Sequence Labeling for Word and Sentence Segmentation. Proceedings of the EMNLP 2013: Conference on Empirical Methods in Natural Language Processing, Seattle, US.
• Graën, J./Bertamini, M./Volk, M. (2018): Cutter – a universal multilingual tokenizer. In: Cieliebak, M./Tuggener, D./Benites, F. (eds.): Swiss text analytics conference, Nr. 2226, pp. 75–81. CEUR-WS.
• Hulden, M. (2009): Foma: A finite-state toolkit and library. Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, pp. 29–32.
• Jurish, B./Würzner, K.-M. (2013): Word and Sentence Tokenization with Hidden Markov Models. JLCL, 28 (2), pp. 61–83.
• Moreau, E./Vogel, C. (2018): Multilingual Word Segmentation: Training Many Language-Specific Tokenizers Smoothly Thanks to the Universal Dependencies Corpus. Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018). Miyazaki, Japan.
• Proisl, T./Uhrig, P. (2016): SoMaJo: State-of-the-art tokenization for German web and social media texts. Proceedings of the 10th Web as Corpus Workshop, pp. 57–62.
• Schmid, H. (1994): Probabilistic Part-of-Speech Tagging Using Decision Trees. Proceedings of International Conference on New Methods in Language Processing.
• Schweter, S./Ahmed, S. (2019): Deep-EOS: General-Purpose Neural Networks for Sentence Boundary Detection. Proceedings of the 15th Conference on Natural Language Processing (KONVENS). KONVENS, Erlangen, Germany.