NLP中文信息处理---正向最大匹配法分词_正向最大匹配算法分词顺序

弄了好几天正向最大匹配法分词，终于弄完了吧。Python写的。Python确实是一门好语言，写起来很简单、顺手。

一、关于正向最大匹配法分词

中文分词(Chinese Word Segmentation)指的是将一个汉字序列切分成一个一个单独的词。中文分词是文本挖掘的基础，对于输入的一段中文，成功的进行中文分词，可以达到电脑自动识别语句含义的效果。

正向最大匹配法：

例子: 将句子 ’ 今天来了许多新同事 ’ 分词。  设最大词长为5

今天来了许
今天来了
今天来
今天  ====》 得到一个词 – 今天
来了许多新
来了许多
来了许
来了
来   ====》 得到一个词 – 来
了许多新同
了许多新
了许多
了许
了   ====》 得到一个词 – 了
许多新同事
许多新同
许多新
许多 ====》得到一个词 – 许多
新同事
新同
新   ====》得到一个词 – 新
同事 ====》得到一个词 – 同事

最后正向最大匹配的结果是：/今天/来/了/许多/新/同事/

二、正向最大匹配分词算法

三、语料库的处理与算法的输入

语料库的处理流程：

输入：人民日报语料库199801.txt

输出：dict.txt词表文件

分词算法：

输入：将dict.txt处理后得到的list集，以及最大词长；待分词的句子

输出：分词后的句子

四、Python实现

1. 语料库的初步处理 ( MaxBuildDict.py )

# -*- coding: cp936 -*-
#最大匹配法进行分词----创建词表文件.
#author 徐能
#date 2013/3/23
import string
import re
 
#输入:语料库199801.txt文件; 输出:换行分割后的词表文件dict.txt(已经去重复, 去日期)
def create_dict(filename):
	print("读取文件......")
	src_data = open(filename,'r').read()
	sp_data = src_data.split()#分割
 
	print("原始词数为:",len(sp_data))
	set_data = set(sp_data)	#去重复
	data = list(set_data) #set转换成list, 否则不能索引
	print("去除重复后总词数为:",len(data))
 
	print("正在建立词表文件......")
	tmp = []
	for i in range(0,len(data)):
		if re.compile(r'\d+\-\S+').match(data[i]):  #去除类似这样的词'19980101-01-001-002/m'
			continue
		else:
			p_ok_data = re.compile(r'\/\w+').sub('\n',data[i]) #将类似的词'埃特纳/ns'替换为'埃特纳'
			if re.compile(r'(\[\S+)|(\]\S+)').match(p_ok_data):    #找到以'['或']'开头的词
				ok_data = re.compile(r'(\]\w+\[)|(\])|(\[)').sub('',p_ok_data) #去除']nt[澳门',']澳门','[澳门'三类词的头部无用部分(先匹配长的部分)
				tmp.append(ok_data)
				continue
 
			tmp.append(p_ok_data)
 
 
	print("最终得到的词表文件中总词数为:",len(tmp))
	open('dict_tmp.txt','w').writelines(tmp)
	print("初步词表文件建立完成! (dict_tmp.txt)")
 
 
#运行
if __name__ == '__main__':
    create_dict('199801.txt')

2. 进一步对词表的优化 ( MaxBuildDictModify.py )

# -*- coding: cp936 -*-
#修正词表文件.
#author 徐能
#date 2013/3/24
import string
import re
 
#输入:dict_tmp.txt文件; 输出:dict.txt(已经去重复, 去特殊符号)
def create_dict(filename):
	print("读取文件......")
	src_data = open(filename,'r').read()
	data = src_data.split()#分割
 
	print("正在建立词表文件......")
	tmp = []
	for i in range(0,len(data)):
	   ok_data = re.compile(r'\]..').sub('',data[i]) #将类似的词']..埃特纳'前面的东西去掉
	   tmp.append(ok_data+'\n')
 
	print("去重复前的词数为:",len(tmp))
	set_data = set(tmp)	#去重复
	lalst_data = list(set_data) #set转换成list, 否则不能索引
	print("去除重复后总词数为:",len(lalst_data))
 
	open('dict.txt','w').writelines(lalst_data)
	print("最终词表文件建立完成! (dict.txt)")
 
 
#运行
if __name__ == '__main__':
    create_dict('dict_tmp.txt')
##    create_dict('testdict1.txt')
##    create_dict('testdict2.txt')

3. 分词算法实现 ( MaxWordSegmentation.py )

# -*- coding: cp936 -*-
#最大匹配法进行分词, 测试文件为MaxWordSegmentationTest.py
#author 徐能
#date 2013/3/25
import string
import re
 
#读入词表文件到内存list
#输入:词典文件名, 输出:词典中所有词的list表,其中最大词长
def load_dict(filename):
	f = open(filename,'r').read()
	maxLen = 1
	strList=f.split("\n")
 
	#寻找最大词长
	for i in strList:
		if len(i)>maxLen:
			maxLen=len(i)
 
	return strList,maxLen;
 
#分词方法.
#输入:词表中所有词的列表与其中的最大词长, 输出:分词后的列表
def segmentation(strList,maxLen,sentence):
	wordList=[]	 #用于输出的词列表
 
	while(len(sentence)>0):
		word=sentence[0:maxLen] #每次取最大词长的词
 
		meet=False;   #标记位, 判断是否找到该词
 
		while((not meet) and (len(word)>0)):
			#如果词在词表中
			if(word in strList):
				wordList.append(word)   #添加到输出列表
				sentence=sentence[len(word):len(sentence)]#后移
				meet=True;
			#词不在词表中时
			else:
				#当词长为1时, 添加到输出表, 并后移总词位
				if(len(word)==1):
					wordList.append(word)
					sentence=sentence[len(word):len(sentence)]
					meet=True;
				else:
				#当词长不为1时, 词长减1(最后一位)
					word=word[0:len(word)-1]
	return wordList
 
#主函数
def main():
	strList,maxLen=load_dict('dict.txt')
	print("词表中最大词长度为:",maxLen)
    #输入句子
	sentence = input('请输入中文句子：')
	print('输入的句子为:',sentence)
#	sentence='迈向充满希望的新世纪'
	print('输入的句子为:',sentence)
	length=len(sentence)
	print('输入的句子长度:',length)
	print("****************开始解析**********************")
	wordl=segmentation(strList,maxLen,sentence)
	#打印分词结果
	for eachChar in wordl:
		print(eachChar,end = "/ ")
	print("")#换行
	print("****************解析完毕!*********************")
 
#运行
if __name__ == '__main__':
	main()

五、运行结果

六、总结

关于效率：

正向最大匹配法分词占用很大计算量，结果本人测试，100多个字的一段话一般2秒分完。1000个字的一段话，需要20几秒才能分完。以最大词长为20来计算的话，待分的句子为20个字，假设全部分成2字词，词表中有5万个词，则计算量约为22*5*50000=550万。如此可见，当待分词句子很长，最大词长很大时，计算量是惊人的。

关于分词准确度：

正向最大匹配法的缺陷在与精确度不能达到理想的状态。同时也不能解决词的歧义问题。（统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。）

（文章如有错误，敬请指正）

运行源码以及全部文档下载地址: http://download.csdn.net/detail/xn4545945/5182311

原创文章，转载请注明出处：http://blog.csdn.net/xn4545945