MDL最小描述长度在分词研究中的应用

本文主要是介绍MDL最小描述长度在分词研究中的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CODE(Data| L) + CODE( L)

其中L是词典，Data是语料，ODE函数表示描述数据需要的最小位数

两个部分中，CODE( L)就是描述词典所需的信息，也就是记录模型需要信息：CODE(L) = b*sum(length(w))，其中b表示描述字母集所需要的位数，如2个字母，需要的位数就是1bit，4个就是2bits，依次类推。w表示词典中词的长度 

CODE(Data|L)为分词后的语料，记录这样的语料需要的信息：

CODE(Data|L) = -sum[ C(w) * ( log(C(w))-  log(N) )  ]

其中C(w)为语料中词w的出现的次数，N为语料的包含总的词数。如语料为：Data =  w3 w1  w5  w2 w2  w3 则语料共有6个词，其中w3的数量为2，w1为1...， 这个里面的log应该是以2为底的

举一个简单的例子，两行已经分好词的语料：

a b

ab a ba

字典部分：

共有两个字符，则b=1，即为用一个bit就可以表示a，b两个字母了

共有4个词，a,b,ab,ba

其长度和为1+1+2+2 = 6

则CODE(L)部分的值为1*6 = 6

分词后的语料部分：

语料长度为5个词，则N=5

其中：

a出现2次，则对应的值为2*( log(2)-log(5) ) = -2.64

b,ab,ba均出现1次，对应的值均为1*( log(1)-log(5) ) =-2.32

则CODE(Data|L) ，也就是语料部分的值为 ：

-1*(-2.64 -2.32-2.32-2.32 ) = 9.61

则该词语料的总的描述长度 mdl=6+9.61 = 15.61

这个数组其实是描述这个分词方法和对应语料需要的总的信息量。对其取2为底的对数，则值为log2(15.61)=3.9，也就是编码这个分词后的数据，需要的最小2进制位数是4位。

相应的，我们可以计算一下，不经分词，就是只用字母来表示这个语料，需要的信息量约为8.8966，显然，这样的分词方式是得不偿失的，当然，如果词出现很多，分词后记录语料的信息量会是少的。

对应的python代码如下，其中输入文件为分词好的语料，词直接用空格隔开，一行一个句子

[python]  view plain copy

1. #!/usr/bin/env python  
2. #coding=utf-8  
3. import sys   
4. import math  
5. reload(sys)  
6. sys.setdefaultencoding('utf-8')  
7.   
8. #MDL，(minimum description length),最小描述长度  
9. #输入，分好词的文件，格式为 词 空格 词 空格...  
10. word_dict = {}  
11.   
12. #加载语料，统计词和词频，用于后续的处理  
13. def load_corpus(word_seq_file_name):  
14.     data_file = open(word_seq_file_name, "r")  
15.     for line in data_file:  
16.         line = line.strip()  
17.         word_list = line.split(" ")  
18.         for word in word_list:  
19.             word_dict.setdefault(word,float(0))  
20.             word_dict[word] += 1  
21.     return 0  
22.   
23. #获得字母的描述长度值  
24. #目前只处理单字节的字母  
25. def get_letter_info():  
26.     letter_dict = {}  
27.     #统计letter  
28.     for word in word_dict:  
29.         for letter in word:  
30.             letter_dict.setdefault(letter, 0)  
31.             letter_dict[letter] += 1  
32.       
33.     #计算字母的描述长度  
34.     letter_num = float(len(letter_dict))  
35.     letter_info = math.log(letter_num, 2)  
36.   
37.     return letter_info  
38.   
39. #获得词典的词的总长度  
40. def get_dict_info():  
41.     word_length_sum = 0  
42.     for word in word_dict:  
43.         word_length_sum += len(word)  
44.   
45.     return word_length_sum  
46.   
47. #获得单词序列的描述长度  
48. def get_word_seq_info():  
49.     word_info_sum = 0  
50.     freq_sum = sum(word_dict.itervalues()) #所有词的词频  
51.     for word in word_dict:  
52.         word_freq = word_dict[word]  
53.         word_info = word_freq * ( math.log(word_freq, 2) - math.log(freq_sum, 2) )  
54.         word_info_sum += word_info  
55.       
56.     word_seq_info = -1*word_info_sum  
57.     return word_seq_info  
58.   
59. #获得最终的mdl  
60. def get_mdl():  
61.     letter_info = get_letter_info()  
62.     dict_info = get_dict_info()  
63.     word_seq_info = get_word_seq_info()  
64.     mdl = letter_info*dict_info + word_seq_info  
65.     return mdl  
66.   
67. if __name__=="__main__":  
68.     if len(sys.argv)!=2:  
69.         print "please input word corpus filename"  
70.         sys.exit()  
71.     load_corpus(sys.argv[1])  
72.     print get_mdl()  

数据文件例子：

[html]  view plain copy

1. a b  
2. ab a ba  

处理这个文件，获得的值得应该是

15.61

这篇关于MDL最小描述长度在分词研究中的应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！