In previous articles on this blog, I have briefly mentioned the issues of Chinese text processing and mining. The biggest difference between Chinese data mining and similar problems in English is that Chinese lacks spaces. To perform linguistic tasks effectively, one must first perform word segmentation. Currently, popular segmentation methods are based on dictionaries. However, a significant problem arises: where do these dictionaries come from? While common words can be manually collected into a dictionary, this cannot keep up with the endless emergence of new words, especially internet slang—which is often the key to linguistic tasks. Therefore, a core task in Chinese language processing is the improvement of new word discovery algorithms.
New word discovery refers to the automatic identification of potential word fragments from a large-scale corpus without any prior materials. A few days ago, I visited Xiaoxia’s company and tried to join one of their development projects, where the main task was processing internet articles. Consequently, I brushed up on my knowledge of new word discovery algorithms, referring to the article "Sociolinguistics in the Internet Age: Text Data Mining Based on SNS" on Matrix67.com, especially the ideas regarding information entropy. Based on his approach, I wrote a simple Python script.
The program’s algorithm is entirely derived from the article on Matrix67.com. Interested readers can visit his blog for a detailed read; I believe you will benefit greatly. Here, I will mainly discuss the implementation logic of the code. The specific program can be found at the end of this article. To process larger texts, I avoided Python’s built-in loops as much as possible and utilized functions from third-party libraries such as Numpy and Pandas. Since a large number of words are involved, indexing is crucial; for example, sorting the words beforehand significantly increases retrieval speed.
Below are the results (partial) of new word discovery performed by this program on the "New Century Revised Edition" of Jin Yong’s novel Demi-Gods and Semi-Devils (txt electronic version, 2.5MB). It took about 20 seconds, and the results seem quite good; the names of the main characters were discovered automatically. Of course, because the code is relatively short and lacks specialized processing, there are still many areas for improvement.
Duan Yu, 3535
What, 2537
Xiao Feng, 1897
Self, 1730
Xu Zhu, 1671
Qiao Feng, 1243
A Zi, 1157
Martial Arts, 1109
A Zhu, 1106
Young Lady, 1047
Smiled and said, 992
We, 832
Master, 805
How, 771
So/Thus, 682
Dali, 665
Beggar’s 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 Budong, 447
Shaolin Temple, 379
Emperor Baoding, 344
Madam Ma, 324
Duan Yanqing, 302
Wu Laoda, 294
Could not help but, 275
Madam Wang, 265
Why, 258
Only heard, 255
Is what, 237
Yun Zhonghe, 236
That young girl, 234
Ba Tianshi, 230
Miss Wang, 227
Suddenly heard, 221
Zhong Wanchou, 218
Shaolin Sect, 216
Ye Erniang, 216
Zhu Danchen, 213
Feng Bo’e, 209
Khitan, 208
Crocodile of the Southern Sea, 485
Young Master Murong, 230
Yelu Hongji, 189
Six Meridian Divine Sword, 168
Stood up, 116
Leading Big Brother, 103
These few words, 100
Nodded, 96
Old Monster of Xingxiu, 92
Immortal Sister, 90
Startled, 87
Greatly startled, 86
Mr. Murong, 86
What else, 86
Complete Code (Version 3.x; can be used in 2.x with minor modifications, mainly regarding the output function):
import numpy as np
import pandas as pd
import re
from numpy import log, min
f = open('data.txt', 'r') # Read the article
s = f.read() # Read as a single string
# Define punctuation marks to be removed (using Unicode escapes)
drop_dict = [u'\uFF0C', u'\n', u'\u3002', u'\u3001', u'\uFF1A', u'(', u')', u'[', u']', u'.', u',', u' ', u'\u3000', u'\u201D', u'\u201C', u'\uFF1F', u'?', u'\uFF01', u'!', u'\u2018', u'\u2019', u'\u2026']
for i in drop_dict: # Remove punctuation
s = s.replace(i, '')
# Custom regex dictionary for convenience
myre = {2:'(..)', 3:'(...)', 4:'(....)', 5:'(.....)', 6:'(......)', 7:'(.......)'}
min_count = 10 # Minimum frequency for a word to be accepted
min_support = 30 # Minimum support; 1 represents random combination
min_s = 3 # Minimum information entropy; higher means more likely to be a word
max_sep = 4 # Maximum length of candidate words
t = [] # Used to store results
t.append(pd.Series(list(s)).value_counts()) # Character-by-character count
tsum = t[0].sum() # Count total number of characters
rt = [] # Used to store results
for m in range(2, max_sep+1):
print('Generating %s-character words...' % m)
t.append([])
for i in range(m): # Generate all possible m-character words
t[m-1] = t[m-1] + re.findall(myre[m], s[i:])
t[m-1] = pd.Series(t[m-1]).value_counts() # Word-by-word count
t[m-1] = t[m-1][t[m-1] > min_count] # Filter by minimum frequency
tt = t[m-1][:]
for k in range(m-1):
# Filter by minimum support
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): # Function to calculate information entropy
return -((sl/sl.sum()).apply(log)*sl/sl.sum()).sum()
for i in range(2, max_sep+1):
print('Performing maximum entropy filtering for %s-character words (%s)...' % (i, len(rt[i-2])))
pp = [] # Store all left and right neighbor results
for j in range(i+2):
pp = pp + re.findall('(.)%s(.)' % myre[i], s[j:])
pp = pd.DataFrame(pp).set_index(1).sort_index() # Sort first; important for speed
index = np.sort(np.intersect1d(rt[i-2], pp.index)) # Compute intersection
# Left and right neighbor entropy filtering
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]
# Pre-processing for output
for i in range(len(rt)):
t[i+1] = t[i+1][rt[i]]
t[i+1].sort(ascending = False)
# Save results and output
pd.DataFrame(pd.concat(t[1:])).to_csv('result.txt', header = False)Reprinting: Please include the original address of this article: https://kexue.fm/archives/3491
For more detailed reprinting matters, please refer to: "Scientific Space FAQ"