[Chinese Word Segmentation Series] 2. New Word Discovery Based on Segmentation

Algorithm

Reviewing the process of new word discovery in matrix67’s algorithm, we should realize that new word discovery is about judging whether a given fragment truly forms a word based on the corpus. A "word" is something relatively independent and indivisible. Why not do the opposite? Why don’t we look for which fragments cannot form a word? According to the previous logic, we say a fragment might be a word if its cohesion is above a certain level (and then we consider its boundary entropy). Doesn’t this imply that if the cohesion of a fragment is below a certain level, it cannot be a word? Then we can simply break it at that point in the original corpus.

We can simplify this appropriately. If a and b are two adjacent characters in the corpus, we can count the number of times the pair (a,b) appears, denoted as \#(a,b), and estimate its frequency P(a,b). Then we count the occurrences of a and b separately, \#a and \#b, and estimate their frequencies P(a) and P(b). If \frac{P(a,b)}{P(a)P(b)} < \alpha \quad (\alpha \text{ is a given threshold greater than 1}) then we should break these two characters in the original corpus. This operation is essentially performing a preliminary segmentation of the original corpus based on this indicator! After completing this preliminary segmentation, we can count the word frequencies and filter them accordingly.

Comparing this to the three indicators in matrix67’s article, we are now only using two: frequency and cohesion. We have removed the most computationally expensive boundary entropy. Furthermore, when calculating cohesion, we only need to calculate it for two-character fragments, saving the calculation for longer fragments. However, because we are working based on segmentation, we have much less computation but can theoretically obtain words of any length!

Implementation

It looks perfect—less computation, more power. How is the actual effect? How much does it differ from the results of the algorithm in matrix67’s article? This can only be determined by trying it out. I experimented with 300,000 WeChat public account articles (about 1GB) and found the results satisfactory, taking about 10 minutes. Below is the implementation code. It is very short, pure Python, requires no third-party libraries, and is memory-friendly. The texts variable can be a list or an iterator (returning one article at a time). Combined with the tqdm library, it is easy to display progress. Finally, during statistics, a \gamma smoothing method is used to mitigate the appearance of unreasonable words. Previously, I would use Pandas for these calculations without thinking, but recently I tried some native Python libraries and found them quite useful too.

import pymongo

db = pymongo.MongoClient().baike.items
def texts():
    for a in db.find(no_cursor_timeout=True).limit(1000000):
        yield a['content']

from collections import defaultdict # defaultdict is a wrapper for dict to set default values
from tqdm import tqdm # tqdm is an easy-to-use library for progress bars
from math import log
import re

class Find_Words:
    def __init__(self, min_count=10, min_pmi=0):
        self.min_count = min_count
        self.min_pmi = min_pmi
        self.chars, self.pairs = defaultdict(int), defaultdict(int) 
        # If key doesn't exist, use int() to initialize to 0
        self.total = 0.
        
    def text_filter(self, texts): 
        # Pre-split sentences to avoid meaningless non-alphanumeric strings
        for a in tqdm(texts):
            for t in re.split(u'[^\u4e00-\u9fa50-9a-zA-Z]+', a): 
                # Matches any non-Chinese, non-English, non-numeric character
                if t:
                    yield t
                    
    def count(self, texts): 
        # Counting function: calculates single character and bigram frequencies
        for text in self.text_filter(texts):
            self.chars[text[0]] += 1
            for i in range(len(text)-1):
                self.chars[text[i+1]] += 1
                self.pairs[text[i:i+2]] += 1
                self.total += 1
        # Filter by minimum frequency
        self.chars = {i:j for i,j in self.chars.items() if j >= self.min_count}
        self.pairs = {i:j for i,j in self.pairs.items() if j >= self.min_count}
        self.strong_segments = set()
        for i,j in self.pairs.items(): 
            # Identify "closely related" adjacent characters based on PMI
            _ = log(self.total*j/(self.chars[i[0]]*self.chars[i[1]]))
            if _ >= self.min_pmi:
                self.strong_segments.add(i)
                
    def find_words(self, texts): 
        # Find words based on the previous results
        self.words = defaultdict(int)
        for text in self.text_filter(texts):
            s = text[0]
            for i in range(len(text)-1):
                if text[i:i+2] in self.strong_segments: 
                    # If closely related, do not break
                    s += text[i+1]
                else:
                    # Otherwise break, count the segment as a word
                    self.words[s] += 1
                    s = text[i+1]
            self.words[s] += 1 # The last "word"
        # Final filtering by frequency
        self.words = {i:j for i,j in self.words.items() if j >= self.min_count}

fw = Find_Words(16, 1)
fw.count(texts())
fw.find_words(texts())

import pandas as pd
words = pd.Series(fw.words).sort_values(ascending=False)

Reference code for streaming SQL data in Python:

from sqlalchemy import *

def sql_data_generator():
    db = create_engine('mysql+pymysql://user:password@123.456.789.123/yourdatabase?charset=utf8')
    result = db.execution_options(stream_results=True).execute(text('select content from articles'))
    for t in result:
        yield t[0]

Analysis

Of course, this algorithm is not without its drawbacks; some issues are worth discussing. Generally, to obtain finer-grained words (and avoid extracting too many invalid long words), we can choose a larger \alpha, such as \alpha=10. However, this brings a problem: the cohesion between adjacent characters in a word is not necessarily very high. A typical example is "Republic" (Gong-He-Guo). "He" (and) and "Guo" (country) are both very frequent characters, so the cohesion of the pair "He-Guo" is not high (about 3 in WeChat text). If \alpha is too large, it will lead to the incorrect splitting of this word (in fact, "Gong-He" and "Guo" have high cohesion). There are many such examples, such as "Xin-Ru" in the name "Lin Xin-Ru" (Ruby Lin), where the cohesion is not high (unless the corpus is specifically from the entertainment industry). If we set \alpha=1, we need a larger corpus to make the vocabulary complete. This is something that needs careful consideration when using this algorithm.

WeChat Dictionary

Finally, I am sharing a word list extracted from 300,000 recent WeChat public account articles (about 1GB, over 300 million characters), with a minimum cohesion of 1 and a minimum frequency of 100. From the list, you can see that words clearly related to WeChat have been extracted. Furthermore, since these are recent articles, recent hot topics—such as the Olympics and Wang Baoqiang—related words have also been extracted.

WeChat Dictionary: dict.txt

References

"Non-mainstream Natural Language Processing — Forgetting Algorithm Series (2): Large-scale Corpus Vocabulary Generation": http://www.52nlp.cn/forgetnlp2

Please include the original address when reposting: https://kexue.fm/archives/3913

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