Preface: This summer, I spent a significant amount of time on Chinese word segmentation and language models. I encountered numerous obstacles but also achieved some scattered gains. I plan to write a series to share my experiences and insights. Although it is a "series," it is merely a collection of notes rather than a systematic tutorial. I hope for the readers’ understanding.
Chinese Word Segmentation
Regarding the introduction and importance of Chinese word segmentation (CWS), I will not say much. There is a very clear introduction to segmentation and its algorithms on Matrix67’s blog that is worth reading. In text mining, although many articles have explored methods without segmentation—such as the post "Text Sentiment Classification (III): Segmentation OR No Segmentation" on this blog—segmentation is generally treated as the first step in text mining. Therefore, an effective segmentation algorithm is crucial. Of course, as the first step, CWS has been explored for a long time. Much of the current work is summary in nature or involves minor improvements rather than revolutionary changes.
Currently, there are two main approaches to CWS: Dictionary Lookup and Character Tagging. First, dictionary-based
methods include: mechanical Maximum Matching, Minimum Word Count,
Maximum Probability Combination based on Directed Acyclic Graphs (DAG),
and Maximum Probability Combination based on Language Models, etc.
Dictionary methods are simple and efficient (benefiting from the idea of
dynamic programming). In particular, the Maximum Probability method
combined with a language model can effectively resolve ambiguity.
However, it cannot solve one of the major difficulties in CWS:
Out-of-Vocabulary (OOV) words (the two major difficulties are ambiguity
and OOV words). To address this, the Character Tagging approach was
proposed. Character tagging represents the correct segmentation of a
sentence through several labels (for example, the 4-tag set:
single for a single-character word; begin for
the start of a multi-character word; middle for the middle
of words with three or more characters; and end for the end
of a multi-character word). This is a sequence-to-sequence process
(input sentence to tag sequence) that handles OOV words well but is
slower. Furthermore, in scenarios with a complete dictionary, the
performance of character tagging might not be as good as dictionary
methods. In short, both have pros and cons. In practice, they are often
combined. For instance, Jieba uses Maximum Probability based on
a DAG, while using a Hidden Markov Model (HMM) with character tagging to
identify sequences of single characters.
AC Automaton
This article first implements a dictionary-based segmentation method. The process of dictionary lookup is: 1. Given a set of words, find if the given sentence contains these words; 2. If it does, how to resolve ambiguity. Step 1 is known in computer science as "multi-pattern matching." This step looks simple, but implementing it efficiently is not easy. A complete dictionary has at least hundreds of thousands of words. If you iterate through them one by one, the computational cost is unbearable. In fact, humans don’t do it that way. When we look up a dictionary, we first look at the first letter, then only search in the section with the same first letter, then compare the next letter, and so on. This requires two conditions: 1. A dictionary with a special sort order; 2. Efficient search techniques. For the first condition, we have the Trie (prefix tree); for the second, we have classic algorithms like the AC Automaton (Aho and Corasick).
I won’t comment much more on these two conditions—not because I don’t
want to, but because my understanding ends here. To me, an AC automaton
is an efficient multi-pattern matching algorithm using a Trie data
structure. I don’t need to implement it myself because Python already
has a library for it: pyahocorasick.
Therefore, we only need to care about how to use it. The official
tutorial provides a detailed introduction to the basic usage of
pyahocorasick. (Unfortunately, although
pyahocorasick supports both Python 2 and Python 3, in
Python 2 it only supports bytes strings and not
unicode strings, while in Python 3 it defaults to
unicode. This causes some confusion when writing code,
though it is not fundamental. This article uses Python 2.7.)
To build a segmentation system based on an AC automaton, you first need a text dictionary. Suppose the dictionary has two columns: the word and its frequency, separated by a space. You can build an AC automaton with the following code:
import ahocorasick
def load_dic(dicfile):
from math import log
dic = ahocorasick.Automaton()
total = 0.0
with open(dicfile) as f:
words = []
for line in f:
line = line.split(' ')
words.append((line[0], int(line[1])))
total += int(line[1])
for i, j in words:
# Use log probability to prevent overflow
dic.add_word(i, (i, log(j/total)))
dic.make_automaton()
return dic
dic = load_dic('me.dic')A very user-friendly feature of pyahocorasick is that it
allows adding words in "key-annotation" pairs (note the line
dic.add_word(i, (i, log(j/total)))). This allows us to
store information we want, such as frequency or part-of-speech, in the
annotation, which will be returned during the search. With the AC
automaton above, we can easily build a "full-mode" segmentation, which
scans for all words present in the dictionary (which is essentially the
primary job of an AC automaton).
def all_cut(sentence):
words = []
for i, j in dic.iter(sentence):
words.append(j[0])
return wordsFor a long sentence, this might return many words, so use it with caution.
Maximum Matching
The so-called "full-mode" segmentation mentioned above is not really segmentation; it is just a simple search. Next, we implement a classic segmentation algorithm: Maximum Matching.
Maximum Matching refers to matching words from the dictionary from left to right, choosing the longest possible match at each step. This is a relatively crude method. As mentioned in Matrix67’s article, it is easy to construct counter-examples. If the dictionary contains "not", "cannot", "be", and "possible", but not "impossible", then "impossible" would be segmented as "cannot/be". Nevertheless, when accuracy requirements are not extremely high, this algorithm is acceptable because it is very fast. Below is an implementation of Maximum Matching based on the AC automaton:
def max_match_cut(sentence):
sentence = sentence.decode('utf-8')
words = ['']
for i in sentence:
i = i.encode('utf-8')
if dic.match(words[-1] + i):
words[-1] += i
else:
words.append(i)
return wordsThe code is short and clear, mainly using the match
function of pyahocorasick. On my machine, the efficiency of
this algorithm is about 4MB/s. According to the author of HanLP, doing
something similar in Java can reach 20MB/s! Using Python has two
limitations: one is the speed of Python itself, and the other is the
limitation of pyahocorasick. The implementation above is
not the most efficient because pyahocorasick does not
support Unicode, so Chinese characters have varying byte lengths,
requiring constant encoding conversions to determine character
boundaries.
The method described above is specifically "Forward Maximum Matching." Similarly, there is "Backward Maximum Matching," which scans the sentence from right to left. Its results are generally slightly better than forward matching. To implement this with an AC automaton, the only way is to store all words in the dictionary in reverse order, reverse the input sentence, and then perform forward matching.
Maximum Probability Combination
The method based on Maximum Probability Combination is currently an excellent approach that balances speed and accuracy. It states that for a sentence, if the segmentation into words w_1, w_2, \dots, w_n is the optimal scheme, it should maximize the following probability: P(w_1, w_2, \dots, w_n) Directly estimating this probability is difficult, so approximation schemes are used, such as: P(w_1, w_2, \dots, w_n) \approx P(w_1)P(w_2|w_1)P(w_3|w_2)\dots P(w_n|w_{n-1}) Here P(w_k|w_{k-1}) is called a language model, which already considers some semantics. However, ordinary segmentation tools find it hard to estimate P(w_k|w_{k-1}) and usually adopt a simpler approximation: P(w_1, w_2, \dots, w_n) \approx P(w_1)P(w_2)P(w_3)\dots P(w_n) From a graph theory perspective, this is the maximum probability path in a Directed Acyclic Graph (DAG).
Below, we introduce how to use the AC automaton combined with dynamic programming to implement the latter scheme.
def max_proba_cut(sentence):
paths = {0:([], 0)}
end = 0
for i,j in dic.iter(sentence):
start,end = 1+i-len(j[0]), i+1
if start not in paths:
last = max([i for i in paths if i < start])
paths[start] = (paths[last][0]+[sentence[last:start]], paths[last][1]-10)
proba = paths[start][1]+j[1]
if end not in paths or proba > paths[end][1]:
paths[end] = (paths[start][0]+[j[0]], proba)
if end < len(sentence):
return paths[end][0] + [sentence[end:]]
else:
return paths[end][0]The code is still very brief and clear. Here, it is assumed that the frequency of unmatched parts is e^{-10}, which can be modified. It should be noted that because the logic used is different, the dynamic programming scheme here is different from the general DAG dynamic programming, but the logic is very natural. Note that if you directly use this function to segment sentences with tens of thousands of characters, it will be slow and consume a lot of memory because I keep all temporary schemes during the dynamic programming process in a dictionary. Fortunately, there are many natural sentence-breaking markers in Chinese text, such as punctuation marks and newline characters. We can use these markers to divide the sentence into many parts and then segment them step by step, as follows:
to_break = ahocorasick.Automaton()
# Using English equivalents for common Chinese punctuation
for i in [',', '.', '!', ',', '?', ' ', '\n']:
to_break.add_word(i, i)
to_break.make_automaton()
def map_cut(sentence):
start = 0
words = []
for i in to_break.iter(sentence):
words.extend(max_proba_cut(sentence[start:i[0]+1]))
start = i[0]+1
words.extend(max_proba_cut(sentence[start:]))
return wordsOn the server, I extracted 100,000 articles (over 100 million
characters) and compared the speed with Jieba segmentation. I found that
using the same dictionary and turning off Jieba’s new word discovery,
the speed of this map_cut implemented with an AC automaton
is about 2 to 3 times faster than Jieba, reaching approximately
1MB/s.
Finally, it is worth mentioning that the implementation idea of
max_proba_cut can be used for other dynamic
programming-based segmentation methods, such as Minimum Word Count
segmentation:
def min_words_cut(sentence):
paths = {0:([], 0)}
end = 0
for i,j in dic.iter(sentence):
start,end = 1+i-len(j[0]), i+1
if start not in paths:
last = max([i for i in paths if i < start])
paths[start] = (paths[last][0]+[sentence[last:start]], paths[last][1]+1)
num = paths[start][1]+1
if end not in paths or num < paths[end][1]:
paths[end] = (paths[start][0]+[j[0]], num)
if end < len(sentence):
return paths[end][0] + [sentence[end:]]
else:
return paths[end][0]Here, a penalty rule is adopted: a penalty point is given for each word, and an additional point for OOV words. The scheme with the lowest penalty wins.
Summary
In fact, as long as dictionary lookup operations are involved, AC automata will have a place. Applying AC automata to word segmentation is a very natural application. We look forward to the emergence of more data structures and algorithms with better support for Chinese, so that we can design even more efficient algorithms.
Reprinting please include the original address: https://kexue.fm/archives/3908
For more details on reprinting, please refer to: Scientific Space FAQ