Information Entropy Methods for New Word Discovery: Theory and Implementation

新词发现的信息熵方法与实现 苏剑林 · 2015-10-26 · Machine Learning Python maximum entropy vocabulary new word discovery

In earlier posts on this blog, I've briefly touched on Chinese text processing and mining. The biggest difference between Chinese data mining and its English counterpart is that Chinese has no spaces between words. To do a good job on language tasks, you first need to segment the text into words. Currently popular word segmentation methods are dictionary-based, but this raises an important question right away: where does the dictionary come from? People can manually collect common words into a dictionary, but this cannot keep up with the endless stream of new words being coined — especially internet neologisms — which are often exactly the words that matter most for language tasks. Hence, one of the core tasks in Chinese language processing is improving new-word discovery algorithms.

New word discovery refers to automatically discovering language fragments that could plausibly be words, directly from a large-scale corpus, without relying on any prior material. A couple of days ago I visited Xiaoxia's company to pay my respects, and got involved in one of their development projects, whose main task was processing web articles. In the process, I brushed up on new word discovery algorithms, drawing on Matrix67.com's article "Internet-Era Sociolinguistics: Text Data Mining Based on SNS", especially the ideas around information entropy in it. Following his approach, I wrote a simple script in Python. more

The algorithm in this program comes entirely from the Matrix67.com article; readers interested in the details should head over to his blog for a careful read — I'm sure it's well worth it. Here I'll just briefly discuss the implementation approach for the code. The full program is at the end of the post. To handle larger texts, I tried to avoid Python's built-in loops as much as possible, relying instead on functions from third-party libraries such as NumPy and Pandas. Since a large number of words are involved, good indexing matters a lot — for instance, sorting the words in advance greatly speeds up lookups.

Below are (partial) results of running the new word discovery program on the century's new edition of Jin Yong's novel Demi-Gods and Semi-Devils (a 2.5MB text file). It took about 20 seconds, and the results look pretty good — the names of all the major characters were automatically discovered. Of course, since the code is fairly short and doesn't include much special handling, there's still plenty of room for improvement.

Duan Yu, 3535
what, 2537
Xiao Feng, 1897
oneself, 1730
Xu Zhu, 1671
Qiao Feng, 1243
A Zi, 1157
martial arts, 1109
A Zhu, 1106
young lady, 1047
said with a smile, 992
we, 832
master (shifu), 805
how, 771
like this, 682
Dali, 665
Beggars' Sect, 645
suddenly, 640
Wang Yuyan, 920
Murong Fu, 900
Duan Zhengchun, 780
Mu Wanqing, 751
Jiumozhi, 600
You Tanzhi, 515
Ding Chunqiu, 463
have what, 460
Bao Butong, 447
Shaolin Temple, 379
Regent Emperor (Baoding), 344
Madam Ma, 324
Duan Yanqing, 302
Old Wu, 294
couldn't help, 275
Madam Wang, 265
why, 258
only heard, 255
what is it, 237
Yun Zhonghe, 236
that young woman, 234
Ba Tianshi, 230
Miss Wang, 227
suddenly heard, 221
Zhong Wanchou, 218
Shaolin sect, 216
Ye Erniang, 216
Zhu Danchen, 213
Feng Boe, 209
Khitan person, 208
South Sea Crocodile God, 485
Young Master Murong, 230
Yelü Hongji, 189
Six Meridian Divine Sword, 168
stood up, 116
Big Brother (leader), 103
these few words, 100
nodded, 96
Old Devil of the Stars, 92
divine sister, 90
was startled, 87
greatly startled, 86
Mr. Murong, 86

Full code (Python 3.x; can be adapted for 2.x with minor changes, mainly in the output function):

import numpy as np
import pandas as pd
import re
from numpy import log,min

f = open('data.txt', 'r') #读取文章
s = f.read() #读取为一个字符串

#定义要去掉的标点字
drop_dict = [u'，', u'\n', u'。', u'、', u'：', u'(', u')', u'[', u']', u'.', u',', u' ', u'\u3000', u'”', u'“', u'？', u'?', u'！', u'‘', u'’', u'…']
for i in drop_dict: #去掉标点字
    s = s.replace(i, '')

#为了方便调用，自定义了一个正则表达式的词典
myre = {2:'(..)', 3:'(...)', 4:'(....)', 5:'(.....)', 6:'(......)', 7:'(.......)'}

min_count = 10 #录取词语最小出现次数
min_support = 30 #录取词语最低支持度，1代表着随机组合
min_s = 3 #录取词语最低信息熵，越大说明越有可能独立成词
max_sep = 4 #候选词语的最大字数
t=[] #保存结果用。

t.append(pd.Series(list(s)).value_counts()) #逐字统计
tsum = t[0].sum() #统计总字数
rt = [] #保存结果用

for m in range(2, max_sep+1):
    print(u'正在生成%s字词...'%m)
    t.append([])
    for i in range(m): #生成所有可能的m字词
        t[m-1] = t[m-1] + re.findall(myre[m], s[i:])
    
    t[m-1] = pd.Series(t[m-1]).value_counts() #逐词统计
    t[m-1] = t[m-1][t[m-1] > min_count] #最小次数筛选
    tt = t[m-1][:]
    for k in range(m-1):
        qq = np.array(list(map(lambda ms: tsum*t[m-1][ms]/t[m-2-k][ms[:m-1-k]]/t[k][ms[m-1-k:]], tt.index))) > min_support #最小支持度筛选。
        tt = tt[qq]
    rt.append(tt.index)

def cal_S(sl): #信息熵计算函数
    return -((sl/sl.sum()).apply(log)*sl/sl.sum()).sum()

for i in range(2, max_sep+1):
    print(u'正在进行%s字词的最大熵筛选(%s)...'%(i, len(rt[i-2])))
    pp = [] #保存所有的左右邻结果
    for j in range(i+2):
        pp = pp + re.findall('(.)%s(.)'%myre[i], s[j:])
    pp = pd.DataFrame(pp).set_index(1).sort_index() #先排序，这个很重要，可以加快检索速度
    index = np.sort(np.intersect1d(rt[i-2], pp.index)) #作交集
    #下面两句分别是左邻和右邻信息熵筛选
    index = index[np.array(list(map(lambda s: cal_S(pd.Series(pp[0][s]).value_counts()), index))) > min_s]
    rt[i-2] = index[np.array(list(map(lambda s: cal_S(pd.Series(pp[2][s]).value_counts()), index))) > min_s]

#下面都是输出前处理
for i in range(len(rt)):
    t[i+1] = t[i+1][rt[i]]
    t[i+1].sort(ascending = False)

#保存结果并输出
pd.DataFrame(pd.concat(t[1:])).to_csv('result.txt', header = False)