Rewriting the Previous New Word Discovery Algorithm: Faster and Better New Word Discovery

Background

When I wrote "[Chinese Word Segmentation Series] 8. A Better New Word Discovery Algorithm", I provided a basic implementation and verified its effectiveness. However, that version was written in pure Python and was intended only for quick validation, resulting in rather casual code with significant efficiency issues. Recently, I revisited this and decided not to let the algorithm go to waste. I have rewritten it, utilizing various tools and techniques to improve its speed.

As a side note, "new word discovery" is a common name, but a more accurate term would be "unsupervised lexicon construction." In principle, it can construct an entire lexicon from scratch, not just "new" words. Of course, you can compare the results with a standard dictionary and remove common words to isolate the new ones.

Details

The main changes are as follows:

1. Used the kenlm language modeling tool’s count_ngrams program to count n-grams. Since KenLM is written in C++, its speed is guaranteed, and it is optimized to be very memory-friendly.

2. During the second pass over the lexicon to obtain candidate words, a Trie tree structure was used to accelerate the search for whether a string contains specific n-grams. Trie trees (or their variants) are standard in almost all dictionary-based segmentation tools because they significantly speed up the process of searching for dictionary words within a string.

Usage

The open-source repository for this project is located at:

https://github.com/bojone/word-discovery

Note that this script is intended for use on Linux systems. If you wish to use it on Windows, modifications will likely be required; I am not certain what specific changes are needed, so please resolve those independently. Note that while the algorithm is theoretically applicable to any language, this implementation is primarily designed for languages where the "character" is the basic unit.

Before using this library, I recommend readers take a moment to read "[Chinese Word Segmentation Series] 8. A Better New Word Discovery Algorithm" to gain a basic understanding of the algorithmic steps and the following usage instructions.

The core script in the GitHub repository is word_discovery.py, which contains the full implementation and usage examples. Let’s briefly walk through the example.

First, write a corpus generator that yields the corpus line by line:

import re
import glob

# Corpus generator and preliminary preprocessing
# The specific meaning of this generator example is not important; 
# just know it yields text line by line.
def text_generator():
    txts = glob.glob('/root/thuctc/THUCNews/*/*.txt')
    for txt in txts:
        d = open(txt).read()
        d = d.decode('utf-8').replace(u'\u3000', ' ').strip()
        yield re.sub(u'[^\u4e00-\u9fa50-9a-zA-Z ]+', '\n', d)

You don’t need to understand exactly what this generator is doing; just know that it yields the raw corpus line by line. If you don’t know how to write a generator, please learn that first. Please do not use the comments section to discuss questions like "what should the corpus format be" or "how do I change this for my corpus." Thank you.

As a side note, since this is unsupervised training, larger corpora are generally better—anywhere from several hundred MB to several GB. However, if you only have a few MB (e.g., a single novel), you can still test it and see basic results (though you may need to adjust the parameters below).

Once the generator is ready, configure the parameters and execute the steps:

min_count = 32
order = 4
corpus_file = 'thucnews.corpus' # Filename for saved corpus
vocab_file = 'thucnews.chars' # Filename for saved character set
ngram_file = 'thucnews.ngrams' # Filename for saved n-grams
output_file = 'thucnews.vocab' # Filename for final exported lexicon

write_corpus(text_generator(), corpus_file) # Save corpus as text
count_ngrams(corpus_file, order, vocab_file, ngram_file) # Count n-grams with KenLM
ngrams = KenlmNgrams(vocab_file, ngram_file, order, min_count) # Load n-grams
ngrams = filter_ngrams(ngrams.ngrams, ngrams.total, [0, 2, 4, 6]) # Filter n-grams

Note that KenLM requires a space-separated, plain text corpus as input. The write_corpus function handles this for us, and count_ngrams calls KenLM’s count_ngrams program. Therefore, you need to compile KenLM yourself and place the count_ngrams executable in the same directory as word_discovery.py. In a Linux environment, compiling KenLM is quite simple; I have discussed KenLM here previously. After count_ngrams finishes, the results are saved in a binary file, which KenlmNgrams then reads. If your input corpus is large, this step will require significant memory. Finally, filter_ngrams filters the n-grams. The list [0, 2, 4, 6] represents the mutual information thresholds; the first 0 is a placeholder, while 2, 4, 6 are the thresholds for 2-grams, 3-grams, and 4-grams respectively. Generally, a monotonically increasing sequence works best.

At this point, the "preparation" is complete, and we can begin building the lexicon. First, construct a Trie tree of the n-grams, then use this Trie tree for basic "pre-segmentation":

ngtrie = SimpleTrie() # Build the n-gram Trie tree

for w in Progress(ngrams, 100000, desc=u'build ngram trie'):
    _ = ngtrie.add_word(w)

candidates = {} # Extract candidate words
for t in Progress(text_generator(), 1000, desc='discovering words'):
    for w in ngtrie.tokenize(t): # Pre-segmentation
        candidates[w] = candidates.get(w, 0) + 1

This pre-segmentation process was introduced in "A Better New Word Discovery Algorithm". In short, it functions similarly to maximum matching, where n-gram segments are concatenated into the longest possible candidate words.

Finally, filter the candidate words and save the lexicon:

# Frequency filtering
candidates = {i: j for i, j in candidates.items() if j >= min_count}
# Mutual information filtering (backtracking)
candidates = filter_vocab(candidates, ngrams, order)

# Output result file
with open(output_file, 'w') as f:
    for i, j in sorted(candidates.items(), key=lambda s: -s[1]):
        s = '%s %s\n' % (i.encode('utf-8'), j)
        f.write(s)

Evaluation

Readers have previously mentioned that my algorithms lacked standard evaluations. This time, I have performed a simple evaluation using the script evaluate.py.

Specifically, using THUCNews as the base corpus, I constructed a lexicon using the script above (total time approximately 40 minutes). I kept only the top 50,000 words and loaded this lexicon into the Jieba segmenter (disabling its built-in dictionary and new word discovery feature). This created a segmentation tool based on unsupervised lexicon construction, and then used this segmentation tool to segment the test set provided by bakeoff 2005, and evaluated it using its test script. The final score on the PKU test set was:

\begin{array}{c|c|c} \hline \text{RECALL} & \text{PRECISION} & \text{F1}\\ \hline 0.777 & 0.711 & 0.742\\ \hline \end{array}

In other words, it achieved an 0.742 F1 score. What level is this? An ICLR 2019 paper titled "Unsupervised Word Discovery with Segmental Neural Language Models" mentioned that its result on the same test set was F1=0.731. From this perspective, the result of this algorithm is no worse than the state-of-the-art results from top conferences. Readers can download the THUCNews corpus to fully reproduce the above results.

Additionally, more data can lead to better results. This is a lexicon I extracted from 5 million WeChat official account articles (about 20GB after saving as text): wx.vocab.zip, for readers to use if needed. Keeping the top 50,000 words of this lexicon and performing the same evaluation, the F1 significantly exceeded the results of the top conference paper:

\begin{array}{c|c|c} \hline \text{RECALL} & \text{PRECISION} & \text{F1}\\ \hline 0.799 & 0.734 & 0.765\\ \hline \end{array}

(Note: This is to provide an intuitive sense of the effect; the comparison might be unfair because I am not sure which corpora were used in the training set of that paper. However, I feel that within the same amount of time, the algorithm in this article would outperform the paper’s algorithm, as my intuition is that the paper’s algorithm would be very slow to train. The authors have not open-sourced it either, so there are many uncertainties. If there are any errors, please correct me.)

Summary

This article re-implements the new word discovery (lexicon construction) algorithm I proposed earlier, mainly focusing on speed optimization and simple performance evaluation. However, the specific effects still need to be tuned by readers during use.

Wishing everyone a pleasant experience! Enjoy it!

Reprinting: Please include the original address of this article: https://kexue.fm/archives/6920

For more detailed reprinting matters, please refer to: "Scientific Space FAQ"