User:Xyuan2/Final project

Fast C++ Tokenizer for Spaceless Orthographies

Authors: Yana and Frankie

Code: github.com/yanayuan0/apertium-spaceless-tokenizer

The Problem

Languages like Wu Chinese and Mandarin are written without spaces between words:

吃脱好辰光  →  吃脱 好 辰光
中国人民站起来了  →  中国 人民 站 起来 了

This is called word segmentation. In the Apertium pipeline, text must be segmented before morphological analysis via lt-proc. The existing Python tokenizer queries a finite-state transducer for every candidate substring, which is correct but slow (around 0.4 s per 500 lines). This project replaces it with a C++ implementation that is approximately 76x faster and produces identical output.

Previous Work

The original Python tokenizer (tokeniser.py) ships with Apertium packages for spaceless-script languages and uses the HFST Python library to query a compiled .autotok.hfst transducer. Standalone segmenters like Jieba, MeCab, and the Stanford Segmenter exist for Mandarin and Japanese, but they are not integrated with Apertium's FST pipeline. This project stays inside the Apertium ecosystem and generalises to any language that has an Apertium package.

Who Might Benefit

• Apertium packagers: Anyone maintaining a package for a spaceless-script language (Wu Chinese, Mandarin, Japanese, Thai, ...) can drop in this tokenizer with no change to output format, and batch translation workflows that were bottlenecked on the Python tokenizer will see an immediate speedup.
• Language communities: Faster tooling benefits speakers of under-resourced languages like Wu Chinese who depend on Apertium-based translation.

Approach

Algorithm: Left-to-Right Longest Match (LRLM)

Starting from the left, try to match the longest known word. If no match is found, shorten the candidate until a known word is found or fall back to emitting the single character. Advance and repeat. This is the same strategy as the Python tokenizer; the difference is that each lookup is an O(1) hash set query in C++ rather than an FST query through Python.

Word List Generation

The word inventory is extracted from the language package and stored in a plain-text file:

• .hfst transducers (e.g. Wu Chinese): autotok_scraper.py runs hfst-expand to enumerate all surface forms.
• .dix dictionaries (e.g. Mandarin): dix_scraper.py parses the XML and extracts surface forms whose characters are Unicode letters (category Lo, which covers CJK and similar scripts).

Usage

Step 1: Build the tokenizer

make        # produces ./tokeniser

Step 2: Generate a word list for your language

For languages with an .autotok.hfst transducer (e.g. Wu Chinese):

python3 autotok_scraper.py /path/to/wuu.autotok.hfst
# → wuu_autotok_scraped.txt  (370 words)

For languages with a .dix dictionary (e.g. Mandarin, apertium-zho):

python3 dix_scraper.py /path/to/apertium-zho.zho.dix
# → zho_autotok_scraped.txt  (6341 words)

Step 3: Tokenize

echo "吃脱好辰光" | ./tokeniser wuu_autotok_scraped.txt
#  吃脱 好 辰光

echo "中国人民站起来了" | ./tokeniser zho_autotok_scraped.txt
#  中国 人民 站 起来 了

Step 4: Plug into the Apertium pipeline

echo "吃脱好辰光" | ./tokeniser wuu_autotok_scraped.txt | lt-proc -w wuu.automorf.bin

Evaluation

Accuracy

Gold-standard sets of 10 hand-annotated sentences were created for Wu Chinese and Mandarin. The tokenizer is evaluated using precision, recall, and F1 over word boundary spans.

Language	Sentences	Precision	Recall	F1
Wu Chinese (Wuu)	10	1.000	1.000	1.000
Mandarin (Zho)	10	1.000	1.000	1.000

Speed

Measured on 500 lines of Wu Chinese on Apple M-series hardware:

Tokenizer	Time	Relative speed
Python (tokeniser.py + HFST)	0.46 s	1x
C++ (tokeniser + word list)	0.006 s	~76x faster

Known Limitations and Future Work

• Small gold standard: Only 10 sentences per language. A rigorous evaluation would use hundreds of sentences from real corpora.
• Out-of-vocabulary words: Words absent from the Apertium lexicon cause LRLM to fall back to character-by-character output.
• Languages not yet tested: The approach should generalise to Japanese, Thai, and Tibetan, but these have not been evaluated.
• Word list staleness: The word list must be regenerated whenever the language lexicon is updated.

Repository Files

File	Description
tokeniser.cpp	C++ tokenizer source
autotok_scraper.py	Word list from .autotok.hfst
dix_scraper.py	Word list from .dix dictionary
eval/evaluate.py	Precision/recall/F1 script
eval/gold_wuu.txt	Wu Chinese gold standard
eval/gold_zho.txt	Mandarin gold standard
AUTHORS	Author contact information
LICENSE	GPL-3.0 license